{
Solution of task MAGIC
-------- -- ---- -----
The following algorithm written in pseudocode generates all configurations
that can be obtained by applying a sequence of basic transformations to
the initial configuration.
Make the set Generated empty;
Make the set Disp empty;
Include the configuration Ini in Disp;
While Disp is not empty Do Begin
take an element P out of Disp;
for all basic transformation C Do Begin
let Q be the configuration obtained by applying C to P;
If Q is not in the set Generated Then Begin
include Q in the set Generated;
include Q in the set Disp;
End
End
End;
We can stop searching if the configuration Q is the target.
Let us first investigate the implementation of the operations on the set
Generated.
The number of all configurations is 8!=40320. It is too large to store the
configurations in an array. We can overcome this problem by using an
bijective function Rank that maps a configuration into a number in the range
0..8!-1. We can obtain such function by defining Rank(Q) as the number of
configurations that precedes Q according to the lexicographic ordering of the
permutations of the numbers 1..8.
Let us observe that each basic transformation C has a unique inverse in the
sense that for any configuration Q if C transforms Q to P then its inverse
transforms P to Q and conversely, if the inverse of C transforms P to Q then
C transforms Q to P. The inverses of the basic transformations are:
A: A itself,
B: single left circular shifting,
C: single anti-clockwise rotation of the middle four squares.
If the configuration Q is obtained in the algorithm by applying the basic
transformation C to P then there is a sequence of basic transformations that
transforms the initial configuration to Q whose last element is C. If we know
Q and C then we can compute P by applying the inverse of C to Q.
Consider the array Last: Array[0..8!-1] Of Char. We use the array Last for
two purposes. Last[Rank(Q)]=' ' iff the configuration Q has not been
generated. If Q is obtained during the generation by applying C to a
configuration P then Last[Rank(Q)] is set to C. Following the link provided
by the inverse transformation we can compose the whole sequence of basic
transformations for the target configuration T.
S:=''; (* string S is set to empty *)
While T <> Ini Do Begin
X:=Last[Rank(T)];
S:=X+S; (* append X to the left end of S *)
Apply_1(T,X,P); (* Apply the inverse of X to T *)
T:=P; (* link to backward *)
End (* While *);
We implement the dispenser Disp as a queue, i.e. by first-in first-out policy;
items come out in the order of their insertion.
A simple experiment will show that the maximal length of the sequences
produced by the algorithm is 22.
The queue implementation of the dispenser provides optimal solution in the
sense that for each configuration T the algorithm produces the shortest
sequence of basic transformations.
We prove by induction on the length of the optimal solution.
Let us denote by l(T) the length of the sequence generated by the algorithm
for configuration T.
Suppose that during the execution of the algorithm the queue contains the
configurations T1,...,Tk where T1 is the head. Then the
following two conditions hold:
1) l(T1)<=...<=l(Tk)
2) l(Tk)<=l(T1)+1
The proof is by induction on the number of queue operations.
Initially the statement holds because only the initial configuration
is in the queue and l(Ini)=0. If the head T1 is dequeued, then the new head is
T2. But then we have l(Tk)<=l(T1)+1<=l(T2)+1, and the remaining inequalities
are unaffected. Consider the case when T1 is dequeued and the new
configuration Q which is obtained by applying C to T1 is enqueued.
Then l(Q)=l(T1)+1, therefore the inequalities
l(Tk)<=l(T1)+1=l(Q) and l(Q)=l(T1)+1<=l(T2)+1
hold by 1) and 2).
It follows from the previous statement that if the configurations inserted
into the queue over the course of the algorithm in the order T1,...,Tn
then l(T1)<=...<=l(Tn).
Let T(k) denote the set of all configurations Q that the minimal length of the
sequence of basic transformations that transform Ini to Q is k. The proof of
the optimality of the algorithm follows by induction on k.
The elements of T(1) are those configurations that can be obtained by applying
the basic transformations to Ini. The statement obviously holds for k=1.
Assume that the statement holds for all lSize;
End { Equal };
Procedure Generate(Const T: Config);
{ Generates a sequence of basic transformations that transforms the }
{ initial configuration to T. Last[Rank(T)] will be the last element of }
{ the sequence. }
{ Global input-output variable: Last }
Const
Qs=7000; { Queue size }
Var
Queue:Array[0..Qs-1] Of Config;
NotFound:Boolean;
Head,Tail:Word; { head and tail of the queue }
R,S: Config;
X: Char;
Procedure InitGener;
Var i:Word;
Begin
For i:=0 To M Do Last[i]:=' '; { initialize }
Last[0]:='.'; { 0=Rank(Ini), sentinel }
End;
Procedure InitQueue;
{ initialize the queue }
Begin
Head:=0; Tail:=1;
Queue[0]:=Ini; { put Ini into the queue }
End { InitQueue} ;
Procedure Enqueue(Const Q:Config);
Begin
Queue[Tail]:=Q;
Inc(Tail); If Tail=Qs Then Tail:=0;
End { Enqueue };
Procedure Dequeue(Var Q:Config);
Begin
Q:=Queue[Head];
Inc(Head); If Head=Qs Then Head:=0;
End { Dequeue };
Function NotMember(Const Q:Config; X:Char):Boolean;
{ Checks membership of Q in the set of generated configurations. }
{ If it is not generated then marks it as generated by setting the value }
{ of Last[Rank(Q)] to X. }
{ Global input-output variable: Last }
Var RankQ:Word;
Begin
RankQ:=Rank(Q);
If Last[RankQ]=' ' Then Begin
NotMember:=True;
Last[RankQ]:=X;
End Else
NotMember:=False;
End { NotMember };
Begin { Generate }
InitGener;
InitQueue;
NotFound:=True;
While NotFound Do Begin
Dequeue(R);
For X:='A' To 'C' Do Begin { apply all basic }
Apply(R, X, S); { transformations to R }
If NotMember(S,X) Then Begin { S is a new configuration }
If Equal(T,S) Then Begin { T=R*C decomposition found }
NotFound:= False;
Break; { exit the loop }
End;
Enqueue(S);
End { If new tr. };
End { For j };
End { While };
End { Generate };
Procedure Compose(Const T: Config; Var S:String);
{ Composes the sequence of basic transformations from the array Last }
{ following the link provided by the inverse transformation. }
{ Global input variable: Last }
Var
RankQ:Word; X:Char;
P,Q : Config;
Begin
Q:=T;
RankQ:=Rank(Q);
S:='';
While RankQ <> 0 Do Begin { while Q<>Ini }
X:=Last[RankQ];
S:=X+S; { append X to the left end of S }
Apply_1(Q,X,P); { Apply the inverse of X to Q }
Q:=P; { link to backward }
RankQ:=Rank(Q);
End { While };
End { Compose };
Procedure WriteOut;
{ Global input variable: Answer }
Var OutFile:Text;
L,i:Word;
Begin
Assign(OutFile,'output.txt'); Rewrite(OutFile);
L:=Length(Answer);
WriteLn(OutFile,L);
For i:=1 To L Do WriteLn(OutFile,Answer[i]);
Close(OutFile);
End { WriteOut };
Begin { Program }
ReadInput;
ComputeFact;
Generate(T);
Compose(T, Answer);
WriteOut;
End.
{ Scientific Committee IOI'96 }