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].
Apparently successful in spiriting her loot out of the Sudan (as you may remember from the Dig puzzle in an earlier issue), the famous archaeologist Natasha W. was back in action, this time in Greece.
"The famous temple at Menea was a center for games and prayer to Athena," the fit, tanned 30-year-old said by way of introduction. "You, Ecco and Liane, the best puzzle minds in the world, should by rights help to reconstruct it, since Athena was the Goddess of Wisdom. Let me tell you about the building.
"From ancient texts, we know that the temple was built as a rectangle and the front pillars were exactly aligned with the back ones, as you can see from my drawing (Figure 1). Put geometrically, the front and back were parallel lines, and a perpendicular line segment from every front pillar would hit a back pillar and vice versa. For reasons we do not understand, the spacing between successive pillars (on both the front or the back) was very irregular. So, starting on the left, the spacing between the first and second pillars might be very different from the spacing between the third and fourth pillars. I illustrate that in my drawing, too. In fact, the ancient texts say the temple had 7 pillars and speak of lengths ranging from 4 to over 11 cubits for the beams. The lengths may have varied because of the terrain or because of the local superstition that Zeus would be angry at a too perfect temple to Athena — she was supposed to be his favorite, but then, Zeus was fickle in his anger.
"Zeus's jealousy aside, the temple was viewed as a marvel in its time. History has not been kind to it, however. The beams crumbled in an earthquake and were much moved around by treasure seekers, though no front beam was moved to the back or vice versa, we believe. Vandals and church building projects cannibalized the pillars.
"Our goal is to reconstruct the spacing of the pillars from the fragments of the beams. We have some hopes that this can be done for the following reasons: First, in the original temple, each beam was a solid piece of stone from the center of one pillar to the center of the next one (except the end beams). Second, each beam broke into just a few fragments — there are only 20 in front and 17 in back altogether. Third, the weather in Menea is particularly dry so the beam fragments have hardly been eroded. Finally, the beams were cut from plentiful local stone, so nobody helped themselves to them."
"Can you fit the fragments together based on the shape of their faces?" Liane asked.
"We have tried, but the textures are too similar in all of them," Natasha replied. "Also, the fragments are almost exactly rectangular. All we can do is give you lengths."
"Okay, so let's try an example," Liane suggested. "Suppose there were 3 pillars (so 2 beams originally). Suppose the front fragments (numbered 1 through 4) had lengths 1:2.1, 2:3.1, 3:2.1, and 4:1.8. Suppose the back beam fragments had lengths 1:3.9, 2:0.3, 3:1.4, 4:2.2, and 5:1.3. Then we might form 2 groups in front: 1 and 3 (giving a length of 4.2), and 2 and 4 (giving a length of 4.9). The back would then be grouped as 1 and 2 (again a length of 4.2), and 3, 4, and 5 (again a length of 4.9)."
"Exactly," Natasha exclaimed. "You are even smarter as a 13-year-old than you were two years ago. Now for the real problem. Here are the front fragments (labeled for your convenience) with their lengths:
1:2.4
2:1.0
3:2.5
4:0.4
5:3.0
6:3.7
7:0.4
8:1.2
9:4.2
10:2.4
11:4.4
12:3.6
13:4.6
14:1.2
15:3.7
16:4.0
17:1.1
18:0.7
19:3.3
20:0.1
Here are the 17 back fragments in similar format:
1:1.4
2:4.6
3:2.8
4:2.4
5:3.1
6:2.1
7:3.9
8:6.8
9:1.0
10:1.3
11:4.3
12:1.4
13:3.3
14:2.6
15:2.2
16:2.0
17:2.7
Reader: Can you find groupings of the beams in front and back, to account for 7 pillars (including corners) in the front and in the back where the longest beam span is over 11 cubits, and the minimum is 4 cubits? Remember that the front and back have the same pillar separations.
Last Month's Solution
The first "Panamax" problem was to figure out how to move containers on a ship carrying 2 piles of 4 containers each. The ship's route cycles through 8 ports and at each port a container is loaded that goes to the farthest possible port. You want a solution that minimizes the overhead measured as extra moves.
At 0: (7), ()
At 1: (0, 7), ()
At 2: (1, 0, 7), ()
At 3: (2, 1, 0, 7), ()
At 4: (2, 1, 0, 7), (3)
At 5: (2, 1, 0, 7), (4, 3)
At 6: (2, 1, 0, 7), (5, 4, 3)
At 7: remove and sort: (2, 1, 0, 7)
and return it, yielding
(0, 1, 2), (5, 4, 3)
and removing 7.
Then add in 6 to give
(0, 1, 2), (6, 5, 4, 3)
Overhead: 7.
At 0: remove 0.
This leaves
(1, 2), (6, 5, 4, 3)
Then add in 7, yielding
(7, 1, 2), (6, 5, 4, 3)
At 1: remove (7, 1, 2).
Then reload in order
(2, 7, 0).
(6, 5, 4, 3)
Overhead: 4
At 2: remove 2.
Then put in 1.
(1, 7, 0), (6, 5, 4, 3)
At 3: reorder
(6, 5, 4, 3)
to give
(4, 5, 6)
(2, 1, 7, 0)
Overhead: 7
At 4: remove 4 yielding
(5, 6)
then move 5 to dock, put on 3, and then 5:
(5, 3, 6)
(2, 1, 7, 0)
At 5: remove 5
(3, 6)
then remove (3, 6) and put on 4, yielding
(6, 3, 4)
(2, 1, 7, 0)
Overhead: 4
At 6: remove 6 and put on 5
(5, 3, 4)
(2, 1, 7, 0)
At 7: resort
(2, 1, 7, 0)
to
(0, 1, 2)
and add in 6:
(6, 5, 3, 4)
Overhead: 7
Each cycle has an overhead of 7+7+8=22.
Reader Notes
Many readers submitted perfect solutions to the "Foxy" problem (DDJ, April 2001) meeting the bounds that Liane had set (by keeping A to a winning average of 7 with 9 players on each side and 6 1/3 when 25 players were on each side). These smart readers included: Dennis Okon, Rodney Meyer, Karl Putland, Pauling, Pearl, Earl Paddon, Eric Wiseblatt, Jimmy Hu, Marc Bellusci, John A. Trono, Steve Kietzman, Robert H. Morrison, Robert Huff, Andrew Palfreyman, Matt Jones, Roman Rytov, Tomas G. Rokicki, Jesper Lauridsen, Art Grant, and Dennis Yelle.
Dennis Okon was the first to show that Liane's solution was the best possible. Tomas G. Rokicki showed that the average A win cannot be smaller than 6+ 8/(i-1) where i is the number of players each side. So it can never reach 6. Jesper Lauridsen suggested random lineups and showed that team B still has more than a 1/4 chance of winning and that this chance increases as the number of players per team increases.
DDJ
