Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998); Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992); Database Tuning: A Principled Approach (Prentice Hall, 1992); (coauthored with Jason Wang and Bruce Shapiro) Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications Oxford University Press, 1999); and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer-Verlag, 1998). He can be contacted at [email protected].
He said his name was David Carolina, not bothering to state his profession. There was something about the purposefulness of the walk and precision of his speech that suggested a military connection, all of this despite his unruly blond curls.
"A particularly brutal and fickle general named Slit runs the Libdan army in the war against the rebels," he explained. "He is quite fearful of being shot by his enemies, so he travels with one unit of soldiers and then sends his orders out by motorcycle messenger to his top commanders. On these roads, the motorcycles take about an hour to arrive. The commanders relay messages to their subordinates in the same way.
"From what we can gather, Slit's army works according to strict hierarchical principles. Each subordinate will have his unit do whatever his superior last commanded on pain of death and will relay those orders to his own subordinates immediately. There are two commands: attack or retreat. Our goal is to discover the hierarchy by the patterns of fighting decisions that our satellites see among the fighting units.
"Two days ago there was a 16-hour battle involving 12 Libdan army units. Taking 1 to be attack and 0 to be retreat, here is what the units did in the first hour:
101110011001.
That is, unit 1 attacked; unit 2 retreated; units 3, 4, and 5 attacked, and so on. Here are all the configurations in all the battles listed in order by hour.
101110011001
011101111111
100110101111
110111011110
011001010000
001000100001
100110101111
111111011110
011001110001
100110101111
110111011110
010001010000
001000000000
000000100001
100110001110
011001010000
"Remember that it takes an hour for a command to travel from a commander to a subordinate. You can assume, therefore, that the subordinate will do what the commander did the hour before. You can also assume that each commander has at least two subordinates."
"Hold on. Could we try a little example?" 13-year-old Liane asked, putting down her electric guitar. "Suppose there were just three units (one associated with the general and two having lower ranking officers) and we observed the following fighting configurations:
010
101
000
"Then we would strongly suspect that the general commanded the middle unit (unit 2) directly, because the other units always copy what the middle unit does, with an hour's delay. Is that correct?"
"Precisely," said Carolina. "You clearly can do more than twing twang on that thing. Can you discover the hierarchy and which unit the general was with?"
Liane narrowed her eyes at Carolina, but, taken by the problem, soon found herself staring at the sheet of papers with fighting configurations. She even returned her guitar to its stand.
Reader: Give it a try. Liane and Ecco worked on the problem and arrived at a hierarchy consisting of a four-level unbalanced tree.
Carolina reviewed their analysis. "This makes a lot of sense. I'll take it back to my colleagues, but let me continue my story. It turns out that the day did not go well for General Slit. So, he decided to bring in his mistress, Silky. She became a commander, though we don't know where in the hierarchy (we also suspect he changed the hierarchy — a few heads got stuck, if you get my drift). It seems that Silky has a mind of her own, however, and started making her own decisions in the 16-hour battle that occurred three days later. Can you figure out the units Slit and Silky commanded directly, as well as the new hierarchy?
001010010111
110011011001
111111101111
111100101111
000000010000
000010010000
110011011001
111111111111
111111101111
111101111111
001111100110
111101101111
001100110110
000011010000
111111111111
111111101111
Reader: Liane and Ecco were able to find an answer consistent with the data in which Silky disobeyed three times, but were not sure how many others were possible, particularly ones where Silky might have disobeyed less often. Would you like to give it a try?
Last Month's Solution
Starting where (0,0) is the upper left corner, here are the coordinates of the guard towers.
38 36
20 22
30 49
41 30
52 24
2911 square meters are seen by at least one guard.
1242 by at least two guards.
777 by at least three guards.
115 by at least four guards.
Here is the map of the area with numbers representing how many guards can see each point. The towers are indicated by asterices.
0000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000100000000000000000000000000000000000000000000000000000
0000000000000000011111111111000000000000000000000000000000000000000000000000
0000000000000011111111111111111000000000000000000000000000000000000000000000
0000000000000111111111111111111100000000000000000000000000000000000000000000
0000000000011111111111111111111111000000000000000000000000000000000000000000
0000000000111111111111111111111111100000000000000000000000000000000000000000
0000000001111111111111111111111111110000000000000000000000000000000000000000
0000000011111111111111111111111111111000000000000000000000000000000000000000
0000000011111111111111111111111111111000000000000000000000000000000000000000
0000000111111111111111111111111111111100000000000000000000000000000000000000
0000001111111111111111111111111111111110000000000100000000000000000000000000
0000001111111111111111111111111111111110000011111111111000000000000000000000
0000001111111111111111111111111111111110011111111111111111000000000000000000
0000011111111111111111111111111111111111111111111111111111100000000000000000
0000011111111111111111111111111111111122111111111111111111111000000000000000
0000011111111111111111111111111111111222111111111111111111111100000000000000
0000011111111111111111111111111111112222111111111111111111111110000000000000
0000011111111111111111111111111111122222111111111111111111111111000000000000
0000111111111111111111*11111111111123222211111111111111111111111000000000000
0000011111111111111111111111111222333333221111111111111111111111100000000000
0000011111111111111111111111222223333333222221111111111111111111110000000000
0000011111111111111111111112223223333333222222111111111111111111110000000000
0000011111111111111111111333333334443333222222221111111111111111110000000000
0000011111111111111111223333333344444443222222222111111111111111111000000000
0000001111111111111112233333333344444443222222222211111111111111111000000000
0000001111111111111222333333333344444443332222222221111111111111111000000000
0000001111111111112222333333333344444443333222222221111111111111111000000000
0000000111111111122223333333333344444433333322222222111111111111111000000000
0000000011111111222233333333333444444333333332222*22211111111111111100000000
0000000011111111222233333333333344444333333332222222211111111111111000000000
0000000001111112222233333333333344443333333333222222211111111111111000000000
0000000000111122222333333333333344433333333333322222221111111111111000000000
0000000000011122222333334333333344333333333333322222221111111111111000000000
0000000000000122222444444444443333333333333333322222221111111111111000000000
0000000000000122333444444444444333333333333333332222221111111111110000000000
0000000000000112233444444444333334333333333333332222221111111111110000000000
000000000000022222333343333333333444*333333333332222222111111111110000000000
0000000000001222222333333333333333444333333333332222221111111111100000000000
0000000000011222222333333333333333344433333333332222221111111111000000000000
000000000011222222233333333333*333344443333333333222221111111111000000000000
0000000000111222222333333333333333334443333333332222221111111110000000000000
0000000001111222222333333333333333333444333333332222221111111100000000000000
0000000011111222222233333333333333333344433333332222211111111000000000000000
0000000011111222222233333333333333333333433333332222211111100000000000000000
0000000011111222222233333333333333333333333333332222211111000000000000000000
0000000111111122222223333333333333333333332233322222111000000000000000000000
0000000111111122222222333333333333333333332222211210000000000000000000000000
0000000111111122222222333333333333333333332222211110000000000000000000000000
0000000111111112222222233333333333333333332222111100000000000000000000000000
0000000111111111222222223333333333333333332221111000000000000000000000000000
000000111111111122222222*333333333333333333221110000000000000000000000000000
0000000111111111122222222223333333333333332211000000000000000000000000000000
0000000111111111112222222222333333333333332110000000000000000000000000000000
0000000111111111111222222222222333333333330000000000000000000000000000000000
0000000111111111111112222222222222223222110000000000000000000000000000000000
0000000111111111111111222222222222222221110000000000000000000000000000000000
0000000011111111111111111222222222221111100000000000000000000000000000000000
0000000011111111111111111111112111111111100000000000000000000000000000000000
0000000011111111111111111111111111111111100000000000000000000000000000000000
0000000001111111111111111111111111111111000000000000000000000000000000000000
0000000000111111111111111111111111111110000000000000000000000000000000000000
0000000000111111111111111111111111111110000000000000000000000000000000000000
0000000000011111111111111111111111111100000000000000000000000000000000000000
0000000000001111111111111111111111111000000000000000000000000000000000000000
0000000000000111111111111111111111110000000000000000000000000000000000000000
0000000000000001111111111111111111000000000000000000000000000000000000000000
0000000000000000111111111111111110000000000000000000000000000000000000000000
0000000000000000000111111111110000000000000000000000000000000000000000000000
0000000000000000000000001000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000
Reader Notes
The best solutions to the Panamax problem (DDJ, June 2001) came from Dennis Yelle, Steve Hammer, Nick Knight, and James Walby. They noted that routing the ship in the opposite direction would lower the cost, but McLean wants to know the worst case. The first problem was posed by Ecco as follows: The ship is going to 8 ports (numbered 0...7) and has two piles of up to four each. Every port deposits one container that goes to the farthest possible port. What is the smallest overhead (extra moves) per cycle (a visit to all 8 ports in order) that you can manage?
Dennis Yelle had a solution that averaged 16 overhead moves per cycle, though the initial pattern repeats itself only after 5 cycles. Steve Hammer proposed another solution having an average of 13 1/3 overhead moves per cycle and whose initial configuration was repeated every three cycles. The overhead varies per cycle from 10 to 15 and again 15.
Start with a "full" (7 containers) well-ordered ship. OH means overhead and the parentheses denote the order of containers.
At 0: ( 1,2,3,4 ) ( 5,6,7 )
At 1, remove 1, put on 0, yielding:
( 2,3,4 ) ( 0,5,6,7 )
At 2, remove 2, put on 1, yielding:
( 1,3,4 ) ( 0,5,6,7 )
At 3, remove 1 (OH), remove 0 (OH), remove 3,
move 4 (OH) giving:
( )( 4,5,6,7 )
put on 2, put on 1 (OH), put on 0 (OH) yielding:
( 0,1,2 ) ( 4,5,6,7 )
At 4, remove 4, put on 3, yielding:
( 3,0,1,2 ) ( 5,6,7 )
At 5, remove 5, put on 4, yielding:
( 3,0,1,2 ) ( 4,6,7 )
At 6, remove 4 (OH), remove 3 (OH), remove 6,
move 7 (OH) giving:
( 7,0,1,2 ) ( )
put on 5, put on 4 (OH), put on 3 (OH) yielding:
( 7,0,1,2 ) ( 3,4,5)
At 7, remove 7, put on 6, yielding:
( 0,1,2 ) ( 6,3,4,5)
At 0, remove 0, put on 7, yielding:
( 7,1,2 ) ( 6,3,4,5)
At 1, remove 7 (OH), remove 6 (OH), remove 1,
move 2 (OH) giving:
( ) ( 2,3,4,5 )
put on 0, put on 7 (OH), put on 6 (OH) yielding:
( 6,7,0 ) ( 2,3,4,5 )
At 2, remove 2, put on 1, yielding:
( 1,6,7,0 ) ( 3,4,5 )
At 3, remove 3, put on 2, yielding:
( 1,6,7,0 ) ( 2,4,5 )
At 4, remove 2 (OH), remove 1 (OH), remove 4,
move 5 (OH) giving:
( 5,6,7,0 ) ( )
put on 3, put on 2 (OH), put on 1 (OH) yielding:
( 5,6,7,0 ) ( 1,2,3 )
At 5, remove 5, put on 4, yielding:
( 6,7,0 ) ( 4,1,2,3 )
At 6, remove 6, put on 5, yielding:
( 5,7,0 ) ( 4,1,2,3 )
At 7, remove 5 (OH), remove 4 (OH), remove 7,
move 0 (OH) giving:
( ) ( 0,1,2,3 )
put on 6, put on 5 (OH), put on 4 (OH) yielding:
( 4,5,6 ) ( 0,1,2,3 )
At 0, remove 0, put on 7, yielding:
( 7,4,5,6 ) ( 1,2,3 )
At 1, remove 1, put on 0, yielding:
( 7,4,5,6 ) ( 0,2,3 )
At 2, remove 0 (OH), remove 7 (OH), remove 2,
move 3 (OH) giving:
( 3,4,5,6 ) ( )
put on 1, put on 0 (OH), put on 7 (OH) yielding:
( 3,4,5,6 ) ( 7,0,1 )
At 3, remove 3, put on 2, yielding:
( 4,5,6 ) ( 2,7,0,1 )
At 4, remove 4, put on 3, yielding:
( 3,5,6 ) ( 2,7,0,1 )
At 5, remove 3 (OH), remove 2 (OH), remove 5,
move 6 (OH) giving:
( ) ( 6,7,0,1 )
put on 4, put on 3 (OH), put on 2 (OH) yielding:
( 2,3,4 ) ( 6,7,0,1 )
At 6, remove 6, put on 5, yielding:
( 5,2,3,4 ) ( 7,0,1 )
At 7, remove 7, put on 6, yielding:
( 5,2,3,4 ) ( 6,0,1 )
At 0, remove 6 (OH), remove 5 (OH), remove 0,
move 1 (OH) giving:
( 1,2,3,4 ) ( )
put on 7, put on 6 (OH), put on 5 (OH) yielding:
( 1,2,3,4 ) ( 5,6,7 )
Steve Hammer and James Walby both had 24-move overhead solutions to the second problem: You have the 8 busy ports I mentioned before and 4 piles each of height 12. Each port sends 6 containers to the farthest port in the cycle. What is the smallest overhead per cycle that you can manage?
See Table 1 for Walby's solution, where each 6-container group is denoted by a single letter (the letter of its port of destination) and stacks are listed from bottom to top (so EA means A over E).
The question remains open as to whether sending containers to the farthest port yields the highest overhead.
DDJ
