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.