last byte
P
H
O
T
O
B
Y
G
U
R
Y
A
N
O
V
A
N
D
R
E
Y
DOI: 10.1145/3157090 Dennis Shasha
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.
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-diago-nal) segments were allowed?
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
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.
Copyright held by the author.
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,
A CERTAIN MODERN dance choreographer has her dancers wear k
differ-ent-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
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 Puzzles
Polychromatic Choreography
