Entering gracefully, her white cape ondulating slowly behind her as she walked, the choreographer entered my office. "You've heard of ghost writers," she said. "I need a ghost choreographer." I motioned her to sit. Here I paraphrase her tale.
The company consists of 12 men (represented by xs) and 20 women (represented by os). At a key point in their dance, they go from a configuration where the men surround the women to one where the women surround the men. In the transition, each dancer takes three steps. Each step can be either to the left, to the right, forward, or backward or the dancer can dance in place. There are two important conditions: two dancers cannot swap positions during a step, nor can two dancers occupy the same space at the end of a step. Above all, we want to avoid collisions.
I will give you starting and ending configurations and want you to design the moves of the dancers at each step so that they can reach the final position without violating the conditions and in the shortest time possible.
xx -- 1 xxxx -- 2 oooooo -- 3 oooo -- 4 oooo -- 5 oooooo -- 6 xxxx -- 7 xx -- 8Last Configuration
oo -- 0 oo -- 1 oxxo -- 2 oxxo -- 3 oxxo -- 4 oxxo -- 5 oxxo -- 6 oxxo -- 7 oo -- 8 oo -- 9Here is the solution to the above:
xx -- 1 xxxx -- 2 oooooo -- 3 oooo -- 4 oooo -- 5 oooooo -- 6 xxxx -- 7 xx -- 8 x x -- 1 oxooxo -- 2 oxooxo -- 3 o o -- 4 o o -- 5 oxooxo -- 6 oxooxo -- 7 x x -- 8 oo -- 1 oxooxo -- 2 ox xo -- 3 ox xo -- 4 ox xo -- 5 ox xo -- 6 oxooxo -- 7 oo -- 8 oo -- 0 oo -- 1 oxxo -- 2 oxxo -- 3 oxxo -- 4 oxxo -- 5 oxxo -- 6 oxxo -- 7 oo -- 8 oo -- 9
I will present an initial configuration and a final configuration. Your job is to find a fast way to go from the beginning to the end while satisfying the constraints. Please show the intermediate steps as I have done above.
Input data format:
..xx. .xxxx oooooo .oooo .oooo oooooo .xxxx ..xx.No border at all. Output format will be similar. There will be no more than 26 xs and 26os, so you should translate xs to lower case alphabetics and os to upper case and then show your transitions.