Sign In

Communications of the ACM

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
Polychromatic Choreography, illustrative photo

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?

ins01.gif

Solution to Warm-Up.

ins02.gif

and, moving vertically

ins03.gif

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.

ins04.gif

Solution.

ins05.gif

Here are the two steps

ins06.gif

ins07.gif

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.

uf1.jpg
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?

Back to Top

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.

Back to Top

Footnotes

All are invited to submit their solutions to upstartpuzzles@cacm.acm.org; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html


Copyright held by author.
Request permission to (re)publish from the owner/author

The Digital Library is published by the Association for Computing Machinery. Copyright © 2018 ACM, Inc.


 

No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents:
  • Article
  • Author
  • Footnotes