Last byte

# Polychromatic Choreography

View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook

A certain modern dance choreographer has her dancers wear k different-colored leotards. For example, when k is 2, half the dancers wear red and the other half wear blue. In general, there are k colors with n dancers wearing each color. The basic algorithmic problem she has to solve is how to instruct her dancers to move from some given configuration to a configuration in which the dancers form disjoint vertical or horizontal line segments, with each line segment consisting of one dancer from each of the k colors in any ordera "perfect lineup." A movement of one dancer consists of a horizontal or vertical step.

Warm-Up. Consider the following configuration of six dancers on a grid, where three wear blue leotards and three wear red leotards. Can you achieve a perfect lineup in just two moves?

Solution to Warm-Up.

and, moving vertically

Challenge. Starting with two red and two blue dancers, now add two green dancers. We want to create two disjoint segments, each with a red, blue, and green dancer in any order, constituting the perfect lineup in this case. Note the blues and reds are two spaces apart. Where should the two greens start in order to create a perfect lineup in two steps? Show those two steps.

Solution.

Here are the two steps

Upstart 1. Given an initial configurations of k colors, each with an equal number n of dancers of each color on a grid, design an algorithm that uses as few steps as possible to achieve a perfect lineup.

Upstart 2. Given k colors and n dancers of each color and a board of size B x B, find a maximally hard configuration of the dancers; a configuration c is maximally hard if c requires m parallel steps to achieve a perfect lineup and no other configuration requires more than m steps to achieve a perfect lineup.

Figure. Consider k groups of dancers, where the dancers in each group wear leotards of the same color. The choreographer's goal is to get them to move on the grid in parallel, producing a set of disjoint line segments, each including a dancer of each color.

Upstart 3. Given a maximally hard configuration with cost m, is there any way to add a k+1st color of n dancers to reduce the number of steps required to achieve a perfect lineup?

Upstart 4. How would these upstarts change if diagonal (and counter-diagonal) segments were allowed?

### Author

Dennis Shasha (dennisshasha@yahoo.com) is a professor of computer science in the Computer Science Department of the Courant Institute at New York University, New York, as well as the chronicler of his good friend the omniheurist Dr. Ecco.