Figure 3: Initial configuration
In this task we consider the version where each square has a different colour. Colours are denoted by the first 8 positive integers (see Figure 3). A sheet configuration is given by the sequence of colours obtained by reading the colours of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 3 is given by the sequence (1,2,3,4,5,6,7,8). This configuration is the initial configuration.
Three basic transformations, identified by the letters 'A', 'B' and 'C', can be applied to a sheet:
All configurations are available using the three basic transformations.
Figure 4: Basic transformations
You are to write a program that computes a sequence of basic transformations that transforms the initial configuration of Figure 3 to a specific target configuration (Subtask A). Two extra points will be given for the solution if the length of the transformation sequence does not exceed 300 (Subtask B).
The file INPUT.TXT contains 8 positive integers in the first line, the description of the target configuration.
On the first line of file OUTPUT.TXT your program must write the length L of the transformation sequence. On the following L lines it must write the sequence of identifiers of basic transformations, one letter in the first position of each line.
MTOOL.EXE is a program in the task directory that lets you play with the magic squares. By executing "mtool input.txt output.txt" you can experiment with the target configuration and the sequence of transformations.
INPUT.TXT OUTPUT.TXT 2 6 8 4 5 7 3 1 7 B C A B C C B
Figure 5: Example Input and Output