#

#
Choreography

#
Dennis Shasha

#
Omniheurist Course

#
Computer Science

##
*
Description
*

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 -- 8

Last Configuration
oo -- 0
oo -- 1
oxxo -- 2
oxxo -- 3
oxxo -- 4
oxxo -- 5
oxxo -- 6
oxxo -- 7
oo -- 8
oo -- 9

Here 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

# Your Task

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.
# Architecture Team

Your job is to verify that the transitions from one step
to the next are legal and to render each player's output
in a nice way.