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].
With her wispy hair and dreamy eyes, she looked every bit the poet she was in her spare time. In her day job, however, she was a shipping magnate and Katy McLean had big ambitions.
"In 1946, my granddaddy Malcolm McLean sent a metal container from New York City to a southern U.S. port," she began. "Now he always thought big, but how could he know that this little innovation would turn the shipping world upside down and bring fabulous profits to his little company that became Sea-Land?
"Here I am trying to extend the adventure with a fleet of fast, specially designed panamax ships. Post-panamax ships are too large to pass through some of the smaller locks in the Panama Canal. They carry a lot but the trip around the tip of South America is quite a detour. Current rules limit ships to carrying around 13 piles of containers, each around 9 deep. We want a ship long enough to hold only 4 piles, but 12 deep, so it will fit comfortably in the canal, even allowing 2-way traffic and still fall within the canal's 200-foot height limit. This will speed up our journey. Our technology allows us to hold our 10-foot high containers even when sailing over rough ocean. Building the ship is no problem, but what is hard is loading and unloading her efficiently. To keep our ships busy, we will send our ships to 8 of the busiest ports in the world: South Louisiana, New York, Le Havre, Rotterdam, Singapore, Shanghai, Hong Kong, Los Angeles, and then back to South Louisiana. Docking fees are high though, so we want to reduce them to a minimum by minimizing the number of containers that need to be moved on and off a ship each time.
"To give you some idea of what is going on, say we have 4 ports visited in the order (A, B, C, D, A...) and 2 piles. One container is added at each port and goes to the farthest possible port. So, at A a container is added going to D. At B, a container is added going to A, and so on. Containers are removed at their destination. Let's see how this might go:
At A: (D), ()
At B: (D), (A)
At C: (D), (B,A) — means B on top of A
At D, remove D, put on C, yielding:
(C), (B,A)
At A move B (overhead), yielding:
(B,C), (A)
then remove A, then put on D, giving
(B,C), (D)
At B:
remove B, put on A.
(C), (A,D)
At C:
remove C, put on B.
(B), (A,D)
At D: move A (overhead), yielding:
(A,B), (D)
then remove D, then put on C, giving
(A,B), C
At A: remove A
(B), (C)
move B, yielding
(), (B, C)
add in D
(D), (B,C).
"So, there is an overhead of 2 moves per cycle. Each move costs us time and time means money, Dr. Ecco."
"How much time does a move cost?" Liane asked.
"That depends on the port," McLean responded, unfazed that a 13-year-old was asking her questions, "maybe only a few minutes. It doesn't matter. Dock time is expensive, so we want to minimize it."
"Can you put a crane on the ship and move containers while the ship is in the ocean?" Liane continued.
"Good question," McLean responded. "We thought of that idea but decided against adding the cranes because we don't believe we can guarantee stability with piles 12 high."
"Okay, so each move costs a certain amount of time," Ecco concluded. "Can the dock area near the ship be used, say, to rearrange an entire pile?"
"On our ships, yes," McLean answered. "So a 12-container pile can be completely reorganized in 24 moves. In fact, we suspect that this might be useful, at least for partial rearrangements."
"Okay, Liane, let's try a new problem," Ecco said. "The ship is going to 8 ports (numbered 0...7) and has 2 piles of up to 4 each. Every port deposits 1 container that goes to the farthest possible port. What is the smallest overhead (extra moves) per cycle that you can manage?"
Reader: Liane was able to manage with an overhead of 22. Can you do better?
McLean liked the solution Liane came up with.
"Now for the real problem," she said. "You have the 8 busy ports I mentioned before and 4 piles each of height 12. Each port sends 6 containers to 1 or several other ports. What is the smallest overhead per cycle that you can manage for sure? Is the most expensive case always when the containers are sent to the most far-away ports (in the cycle, not geographically)?"
Reader: Would you like to try your hand at these questions? Ecco and Liane were working on them when I left.
Last Month's Solution
For Liane's solution to the 3-car Beats problem, see Figure 1 that shows the beats for 3 police cars taking 17 or fewer minutes each.
Reader Notes
Several readers came up with better solutions than Liane for the Ambulance puzzle (DDJ, March 2001). The best came from Onno Waalewijn, Steve Kietzman, Jimmy Hu, Pearl Pauling, Rodney Meyer, and Michael Elkins.
With the initial configuration of ambulances and the requirement that every ambulance had to return to its home site, Dennis Yelle and Andrew Palfreyman were the first to be able to save 18 victims using the following allocation of ambulances (the line De Gaulle 1: 16 10, 13 12 means that the first ambulance from De Gaulle first picks up victims 16 and 10, returns to De Gaulle, then goes out and rescues 13 and 12):
Austerlitz 1: 0 (34 of 35)
Austerlitz 2: 2 (28 of 32)
Austerlitz 3: 4 (26 of 31)
Austerlitz 4: 5 (20 of 28)
Pasteur 1: 8 6 (31,32 of 42,33)
Pasteur 2: 18 7 (29,30 of 31,32)
Pasteur 3: 1 (36 of 42)
De Gaulle 1: 16 10, 13 12 (15,16 of 32,31: 32,33 of 34,34)
Finish 16, 10 by time 16.
Then take 18 to get the others.
De Gaulle 2: 26 19, 3 (25,26 of 27,31: 35 of 39)
De Gaulle 3: 29 27 (31,32 of 31,32)
Andrew and Onno came up with the best solution so far for the second case in which ambulances can be based wherever they are most useful (saving 22):
Pasteur 1: 2 0, 6 (19,20 of 32,35: 29 of 33)
Pasteur 2: 5 4, 7 (19,20 of 28,31: 27 of 32)
De Gaulle 1: 16 3, 13 12 (15,16 of 32,39: 32 of 34,34)
De Gaulle 2: 8 1 (39,40 of 42,42)
De Gaulle 3: 18 15 (29,30 of 31,33)
De Gaulle 4: 23 10 (27,28 of 29,31)
De Gaulle 5: 26 19 (25,26 of 27,31)
De Gaulle 6: 29 27 (31,32 of 31,32)
De Gaulle 7: 9 (40 of 42)
De Gaulle 8: 14 (32 of 34)
Jimmy Hu was the first to notice that 6 out of the 30 were out of range for any hospital, so it is hard to improve much on this 22-rescue solution.
Dennis Yelle came up with the best solution when each ambulance had to start at its home site but could drop off victims at any hospital, provided it could find available bays (saving 21). Here I'm using his notation in which 1 is Austerlitz, 2 is Pasteur, and 3 is De Gaulle. So, the second line means the ambulance starts at Austerlitz, rescues victims 2 and 0 and ends at De Gaulle, and then rescues victim 3.
h1 1 h2
h1 2 0 h3 3 h3
h1 5 4 h2 7 h2
h1 6 10 h3
h2 9 h2
h2 17 h3
h2 18 15 h3
h3 19 12 h3 13 h3
h3 26 16 h3 8 h3
h3 29 27 h3
Rodney Meyer suggested a way to add two ambulances and base 6 at Pasteur and 7 at De Gaulle to lead to the rescue of 23 victims.
DDJ
