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].
Yves Maison introduced himself as a disaster planner. He didn't say which city he was planning a disaster (response) for, but it couldn't have been one of the old ones of his native France, because the city was laid out in a grid.
"You see, docteur Ecco," he began, "we have a new kind of ambulance that can carry two beds. We have 10 such ambulances, four at the Austerlitz Hospital, three at the Pasteur Hospital, and three at the De Gaulle Hospital.
"We serve our population very well in normal circumstances. But we have not a plan for disasters. That is my job."
With that introduction, Yves lit a cigarette and sat down. We were all amazed to see a medical person smoking, but even Liane let it pass.
"Dr. Maison," Ecco said putting a plastic cup near his guest in lieu of an ash tray, "please tell us more about your city."
"We are laid out as a 100 by 100 grid," Maison replied. "Each grid point is an intersection, so the city is divided into blocks like your Manhattan. Our hospitals are at positions (45,45) for Austerlitz; (50,50) for Pasteur; and (55,55) for De Gaulle.
"If there is a disaster, we want to save as many people as possible, but perhaps not all. We in France remember the La Grande Guerre [World War I to the rest of Europe] where doctors would triage patients into 'require immediate surgery,' 'can travel back to hospital,' and 'will die no matter what.' We view this as reality in any disaster.
"It takes one minute for an ambulance to travel one block. To rescue a person, it takes the time to get to the victim, plus three minutes to get him into the ambulance, plus the time to get him to the hospital, plus one minute to get him out at the hospital and deliver him to the emergency room. Each ambulance fits two victims. European ambulances can perform some emergency care, but these disasters are anticipated to require hospital care. Each victim has a certain amount of time, called his "survival time," beyond which it is no longer worthwhile to get him to the hospital. We want to figure out whom to rescue and by whom.
"We have a sample problem for you and would like to hear how many people you could rescue in time to enable them to survive. In our sample problem, we characterize the 30 victims by their positions and their survival time. So, for example victim 0 (the first one) is at position (50,55) and has a survival time of 35 minutes. (So, if we can't deliver victim 0 to a hospital in 35 minutes, we don't attempt a rescue.)
0: 50 55 35
1: 48 64 42
2: 49 53 32
3: 53 56 39
4: 53 48 31
5: 51 47 28
6: 52 51 33
7: 52 50 32
8: 52 60 42
9: 47 65 42
10: 57 54 31
11: 69 50 39
12: 57 57 34
13: 56 58 34
14: 64 50 34
15: 62 51 33
16: 56 56 32
17: 63 61 44
18: 60 51 31
19: 58 53 31
20: 57 72 39
21: 66 60 36
22: 77 56 43
23: 57 62 29
24: 65 65 40
25: 58 69 37
26: 61 56 27
27: 65 57 32
28: 63 70 43
29: 65 56 31
"Our question to you is how many people can you rescue, assuming that each ambulance starting at some hospital H, will pick up one or possibly two victims (if there is time for both), and return to hospital H? We are interested in both an answer and a method."
Ecco and Liane started discussing the method. I kept hearing words like "pruning" and "greedy," but didn't catch the details. Liane wrote a little program in her favorite language K and concluded that, with her heuristics, she could rescue only 14 out of the 30 victims.
Reader: Would you like to try, given the initial distribution of ambulances, which is 4 at (45,45), 3 at (50,50), and 3 at (55,55)?
She explained her reasoning to Maison, then added, "If you allow me to change the initial placement of ambulances, I can save 19 victims."
Reader: How well can you do if you can choose the initial distribution of ambulances, but still under the rule that an ambulance leaves a hospital and then returns to the same hospital?
Maison shook his head. "Unhappily, we have only a fixed number of ambulance bays at each hospital. That number matches the number of ambulances we have bought (four bays at Austerlitz, three at Pasteur, and three at De Gaulle). One thing you can do, however, is to stipulate that an ambulance can leave one hospital and deliver its patients to another one. Our emergency rooms can handle many patients. If more ambulances arrive at a hospital than there are bays, some may have to wait. It takes two minutes to empty an ambulance with two victims and one minute with one victim."
I had to leave, so I never heard what Ecco thought about that one.
Reader: What could you do if ambulances from one hospital could deliver victims to another one, possibly increasing waiting time at the hospital bays? How many could you save then?
Last Month's Solution
Here were the five routes Ecco and Liane came up with.
M I
I D
C J
J K
H G
Reader Notes
In regard to the "Causality" problem (DDJ, December 2000), the clever readers of DDJ have shown their ability to figure out biological circuits. The following readers solved the puzzle (or major parts of it): Warren Dougherty, Paolo Friedli, Bob Morrison, David E. Siegel, Dennis Yelle, Jesper Lauridsen, Andrew Palfreyman, Manor Askenazi, Jimmy Hu, Matt Lasley, Robert Jamison, and Rodney P. Meyer.
Some used Prolog (a good choice for this problem). Others used brute force. And some used paper and pencil. Rodney Meyer was the first to show the 18 solutions to the first puzzle and the 140 solutions to the cyclic second puzzle.
Corrections
Thee figures reflecting Ecco's solutions to the "Causality" puzzle, published in the January 2001 issue, were inconsistent with the text, as several attentive readers pointed out. The text solutions were correct, but the illustrations were not. Figures 1 and 2, presented here, are the corrected figures.
Also, in the "Tundra" puzzle, published in the February 2001 issue, each leg of the pipeline is a one-way pipe from one letter position to another. When describing the the pipes already laid, the correct description should be:
A F
A H
B M
D L
F E
F G
G A
G J
G L
H C
H I
J B
J D
J M
K C
K D
K H
K J
K M
L C
L I
DDJ
