Communications of the ACM
Polychromatic Choreography
Credit: Getty Images
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 order—a "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?
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2018 ACM, Inc.