Programming Problem #20
"In the Foxhole"

The Gapoofian army likes to train its soldiers in foxholes. Soldiers are trained in squads that contain at least 3 and at most 24 soldiers in multiples of three. The soldiers in a squad are identified by A, B, C, etc., with A being the sergeant. A foxhole for a squad of size n consists of a main passage of length n plus a side passage of length n/3 in the middle that runs alongside the main passage. The soldiers are initially placed in the foxhole in alphabetical order along the main passage. For example, the starting configuration for a squad of six soldiers is shown below, where '*' indicates an empty space. 
  **
ABCDEF
Soldiers in a foxhole can only move north, south, east or west to an adjacent empty space; 'diagonal' moves are not allowed. During the training exercises the sergeant A occassionally needs to talk to another soldier, and the soldiers must make the necessary moves to get the soldier in the square next to the sergeant. The sergeant never moves. Sometimes the order is impossible to carry out; for example, there is no way for F to move next to A.

The input consists of one or more lines, each of which contains a letter representing a soldier followed by the size of the squad. If the letter is 'A' and the size is 0 this signals the end of the input. Otherwise, calculate a sequence of moves that will get the indicated soldier next to the sergeant (if possible) and display them in the format shown in the examples. Note that if the order can be carried out, the moves are numbered consecutively with the initial configuration considered to be move 0. The move numbers and configurations must all line up neatly as shown.

Input must be read from the file "prob20.in", and output must be written to the file "prob20.out". All output to the screen will be ignored.

Example Input

<BOF>
I 9
C 6
A 0
<EOF>

Example Output

Can't move I to A with 9 soldiers.
Moving C to A in a squad of 6 soldiers...
      **
 0) ABCDEF
      C*
 1) AB*DEF
      CD
 2) AB**EF
      CD
 3) A*B*EF
      CD
 4) A**BEF
      *D
 5) A*CBEF
      *D
 6) AC*BEF
A version of this problem originally appeared in the 1989 Pacific regionals.

Dr. Eric Shade