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].
A century earlier, he would also have been British. Only then, he would have been defending Britain's imperial privileges. Now, he was on a humanitarian mission -- at least that's how matters appear.
General Nigel Collins stood straight in his spotless uniform and explained the problem he was having in the Balkan district under his command.
"I don't know who laid the mines or why," he began. "Whichever side it was must have known that they were endangering their own people as much as anyone else. It's a very nasty business, very nasty indeed. It's the worst when you see the kids who..."
He paused, shaking his head slightly. Regaining his professional air, he went on: "In any case, removing a certain kind of mine has proven to be a bit more difficult than we had anticipated. The problem mines are called "stick mines." They are laid down in long straight lines, can sense movement anywhere along their length, and can blow up anything nearby. We have to clear them and we don't know how, unless we know exactly where they are. They are difficult to detect because they go off only if they are stepped on and only with some small probability based on an internal clock. This means that they may lie dormant for years and then blow up when a group of youngsters are in the middle of a cricket match. And that's not altogether unlikely, because the infested area is an enormous children's park, measuring 3-kilometers long and 1-kilometer wide and there are 12 stick mines. We know certain distances between their endpoints, but we know neither their lengths nor (in most cases) their orientation. We do know that no two sticks touch. Because the park is more or less a rectangle, we describe the distances we know about using the directions up, down, left, right.
"We've labeled the segments as follows for purposes of discussion: AQ, PB, OC, KM, JN, RF, WX, LE, UD, IS, VT, and GH.
"We know the following (all distances are in eighths of kilometers):
A is 4 to the left of B
B is 9 to the left of R
C is 2 to the left of X
X is 3 to the left of F
F is 1 to the left of E
E is 3 to the left of D
P is 3 to the left of O
O is 6 to the left of M
M is 1 to the left of N
N is 4 to the left of L
L is 2 to the left of U
U is 5 to the left of S
S is 2 to the left of T
K is 9 to the left of J
J is 5 to the left of I
I is 6 to the left of V
V is 3 to the left of G
W is 9 to the left of H
GH (G on top) is vertical and of length 1
UD (U on top) is vertical and of length 3
RF (R on top) is vertical and of length 1
Q is 2 above P
K is 2 above Q
O is 2 above B
M is 3 above X
J is 4 above M
I is 1 above W
W is 3 above L
A is to the left and downward of P
C is to the right and downward of A.
"We also know that T, H, G, V, I, J, K, A, C, X, F, E, and D are on the edges of the park, though not necessarily in the corners. No stick mine extends beyond the border of the park.
"We have learned all of this through our spies and through, well, the 'persuasion' of our allied security forces. Unfortunately, this does not quite solve the problem for us. In fact, we haven't yet been able to construct a map of the stick mines. And that, Dr. Ecco, is why I'm here. Could you construct a map that is consistent with this evidence or tell me that the evidence is inconsistent? If it's inconsistent, we'll ask our friends to try a bit more...persuasion. I've seen one wounded child too many."
"This might take a while," Liane volunteered. "General, could you give us a day?"
"If you insist," the general replied. "There are children in the neighborhood and it is all we can do to restrain them from playing in the park. The equipment is too tempting."
Reader: Is the data consistent or not? Draw a map that is consistent with as much data as you consider consistent. Is any of the data redundant?
Ecco and Liane worked out a map, but they didn't tell me whether there were any inconsistencies before I left for a conference the next day. During the conference, the following question kept gnawing at me: Was there only one possible map, several possibilities, or an infinite number? If there were many, how should they be characterized?
Reader: If you have any insight into this question, please let me know. A characterization may say, for example, that there are an infinite number of maps but they are offset only by translation.
Last Month's Solution
Ecco and Liane suggest the following ordering of the scenes in last month's problem.
Casta Patt
Casta
Hacket Murphy Casta Patt
Patt
Hacket
Scolaro Patt Brown
Patt Hacket Brown Murphy
Hacket Thompson McDougal Murphy Brown
Scolaro McDougal Hacket Thompson
Thompson Murphy McDougal Patt
Casta Mercer
Casta McDougal Mercer Scolaro Thompson
Casta McDougal Scolaro Patt
Mercer Anderson Patt McDougal Spring
Scolaro McDougal Casta Mercer
Mercer Murphy
Thompson McDougal Anderson Scolaro Spring
McDougal Scolaro Mercer Brown
Anderson Scolaro
This gives a final price of $3,517,350.00.
Reader Notes
The extremely clever reader solutions to the "Calabaza" problems (DDJ, November 1999) that I'll discuss in a moment contrasted brilliantly with the bug in the solution I presented last month.
First, my bug: The third question asked about the situation in which one hole drained in n minutes, and two holes in m minutes where m is the integer below half of n. The question asked whether any n would be troublesome in that situation where troublesome means that there would be no way to mark minutes. As pointed out first by Pearl Pauling and then later by the other readers mentioned below, no solution is possible if n and m are both even. That is not the case for n=20, for example, but it is true for n=22 and n=18. Please don't tell Dr. Ecco.
Otherwise, several readers found solutions that were similar to Dr. Ecco's: Greg Smith, Pearl Pauling, Robert H. Morrison, Yves Piguet, Steve Kietzman, Jonathan Parker, Richard W. Lipp, Rodney Meyer, Patrick R. Schonfeld, Rollin Crittendon, Chad Harrington, Alan E. Dragoo, David Stevenson, Marty Pinaud, and Burghard Hoffrichter.
And then there were the unconventional solutions that involved changing the number of open holes in midstream, if you'll excuse the pun. Philip Straite (and later Kevin A. Shepherd) proposed the first one (imagining that the holes are filled with corks): "Consider 5 calabazas, A through E. Here is the basis for generating a calabaza-emptying event every minute between 15 and 19 minutes inclusive. Once you have these, it is a simple matter to refill and pull both corks from the calabazas and repeat each on a 5 minute interval.
"Calabaza A. T0 (time 0) pull both corks (i.e., pull both corks at time 0). T5 empties (i.e., calabaza A empties at time 5). T5 refill and pull both corks, repeat every 5 minutes.
"Calabaza B. T0 pull one cork. T11 empties. T11 refill and pull both corks, repeat every 5 minutes.
"Calabaza C. T0 pull one cork. T5 replace cork. T11 pull one cork. T17 empties. T17 refill and pull both corks, repeat every 5 minutes.
"Calabaza D. T11 pull both corks. T15 replace both corks. T17 pull both corks. T18 empties. T18 refill and pull both corks, repeat every 5 minutes.
"Calabaza E. T10 pull both corks. T11 replace both corks. T15 pull both corks. T19 empties. T19 refill and pull both corks, repeat every 5 minutes."
Jimmy Hu, Scott J. Taylor, and Jeff Hafner proposed the following even quicker and more economical solution (I'm quoting here from Jimmy): "Fill 2 gourds. Open one hole in gourd A and two holes in gourd B. At 5 minutes, gourd B will drain, so refill it. At 10 minutes, gourd B will drain again so quickly plug the holes and put it under gourd A so that gourd A (which has 1 minute left of water) will be draining into gourd B. So now you can time every minute by letting the gourds drain into each other and switching them every minute. That is to say, at 11 minutes, when gourd A drains, plug its holes and put it under gourd B and then open 1 hole in gourd B."
As Alan Dragoo points out, this solution requires that the two gourds have the same water flow per second with one hole open and the same water flow per second with two holes open. (That is stronger than saying that they will drain at the same rate, do you see why?)
Ralph Fellow and Magne Oestlyngen showed how to match the time of this solution but without this stronger assumption. Their solution required 5 calabazas, however. Magne went on to give a 9 minute solution using 5 calabazas and assuming that each one flows at the same rate (as in Jimmy Hu's assumption).
DDJ
