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), 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].
It was unusual for Dr. Ecco to answer questions posed by four-year-old children, but that was what he was being asked to do. The mouthpiece, as it happened, was the Sultan of Brunei. This gentleman, possibly the richest in the world, draws his wealth from a lake of oil that sits under his country's jungle. His palaces dot the land, some larger than Versailles. His subjects pay no taxes, get free medical care, and free television sets. Wealth has other privileges.
For example, the Sultan reportedly bought London's Dorcester Hotel because he arrived unannounced one night and was told there were no rooms available. Purchasing the hotel has vastly improved his chances of getting a room on demand.
During a recent visit to the United States, he asked Dr. Ecco to come to his suite at the Plaza Hotel to solve a design problem. Ecco, in turn, asked Liane and me to come along.
In spite of his wealth, the Sultan conveyed an air of disarming informality. He did not remark on our casual clothes or the fact that we were three instead of one, seeming to be well aware of our working style. Wanting at once to dispel any feeling of unequal status, he stood up and shook our hands when we entered. Tea was served to all.
We sat around an elegant antique desk in equally comfortable chairs. His secretary of protocol had requested only one favor from Ecco when he called to invite him: "Please let the Sultan ask all the questions. Commoners are not to ask questions of royalty, even honored commoners like yourself."
With that admonition in mind, we waited for the Sultan to begin the conversation. The Sultan approached the problem indirectly.
"As this young lady will certainly appreciate," said the Sultan pointing to Liane, "children can come to a nearly fanatical early fascination with objects. So it is with my four-year-old son Hasan. He has a fine collection of electric trains, which he plays with for hours on end -- a concentration befitting a much older child. He memorizes train maps and has his governess quiz him on them. He looks at my fleet of Rolls Royces with disdain, preferring the Da-Da-Da-Dun of rolling stock.
"Two weeks ago, he put the question to me this way: 'Father, why are there so many more cars than trains?' I thought about this awhile and then responded, 'Because cars go wherever you ask them to, whenever you ask them to. Trains have fixed routes on fixed schedules.' Hasan fell silent. A day later, though, he came back to me: 'Father, in our beloved Brunei, if we built tracks where we now have roads, then trains would be able to go to most places where cars go. That eliminates the problem of fixed routes. As for the problem of fixed schedules, we could make the trains come at our demand.'"
"He's very smart for a four-year-old," Liane said appreciatively.
The Sultan nodded and smiled. He then raised his index finger and more tea was served.
"Little Hasan is also single-minded," the Sultan continued. "He has mapped out the routes among the seven principal population centers of Brunei. The names are difficult for westerners to pronounce, so I have designated them with letters for you. The letter B represents our downtown and the letter E represents a principal recreational area."
The three of us studied the Sultan's map (see Figure 1).
"My engineers suggest a light rail system where each train has three cars and can carry 50 people in the comfort they are accustomed to. They have designed the system so it takes 15 minutes to traverse a leg from one station to its neighbor. Each train station will have room for two trains, but there will be only one track between stations. The engineers say that there is no justification for more tracks. Several trains can go on the same track provided they are going in the same direction.
"Little Hasan, on the other hand, wants every passenger to get to his or her destination without changing trains and by one of the shortest paths possible. Further, he wants to be sure that even at times of peak demand, passengers can get to their destinations quickly.
"Here is the demand at rush hour:
150 want to go from A to F
100 want to go from B to E
50 from C to G
150 from C to D
150 from D to C
100 from E to B
50 from E to D
50 from F to C
50 from F to A
50 from G to A
"Can you, Dr. Ecco, ensure that everyone arrives at his or her destination as fast as possible, given that," the Sultan put on his reading glasses and summarized, "there is initially a train at each destination, each leg takes 15 minutes, there is only one track between stations, trains can take only 50 people at a time, no passenger needs to switch trains, and no passenger spends more time once on a train than the minimum time necessary?"
Reader: Please have a try.
Liane and Ecco began working immediately. After several minutes, they presented a schedule and train routing to the Sultan in which the latest passenger arrived at his or her destination after 105 minutes.
The Sultan nodded. "That is very good, but I think Hasan will not be pleased," he said. "It's just too much time. Is there any engineering change that would lead to a faster solution?"
"If you convert five of your trains to carry 150 people instead of 50, allow station B to hold four trains instead of two, buy one more 50 person train, and allow me to change the starting position of one of the existing trains, then we can get everyone to his or her destination in 45 minutes," Liane volunteered.
"Please tell me how," the Sultan said.
Reader: Can you match Liane's achievement or find a more efficient way? More efficient means either reducing the station size of B or the train size of at least some of the trains.
After she presented her solution, the Sultan beamed. He snapped his fingers and a servant arrived with a glistening diamond necklace. "For a future occasion," he said to Liane as he presented it to her.
Last Month's Solution
1. If every subset is possible, the total number of nonempty subsets of n elements is 2n-1. Each of these must have a unique sum. If n=12, then 2n-1=4095.
2. Labeling for 12 items but sets of size 3 or less:
1 2 4 8 15 28 52 96 165 278 460 663.
The biggest sum is 278+460+663=1401.
3. Labeling for 12 items but sets of size 4 or less:
1 2 4 8 16 31 60 116 224 432 805 1494.
The biggest sum is 224+432+805+ 1494=2955.
Reader Solutions to Subway
Several readers told me they thought the Subway puzzle (DDJ, December 1998) was too easy. Naturally, I apologized. When writing this column, I realized that at least some respondents had simplified the problem by assuming that there is a train ready to depart at every station at every moment. (That simplification makes the problem beyond easy!) Another simplification was to ignore the time to switch trains.
Still, hats off to those readers who beat Dr. Ecco in their answers to the first two problems. The first such correct answer I received was from Alan E. Dragoo, who proposed a method for dropping 13 stinky postcards off in 140 minutes after getting some extra sleep (and, ominously, acting closer to rush hour):
A nasty person can drop postcards at 13 stations in 140 minutes by boarding the special train at station (2,4) at 7:40, arriving at (0,0) at 8:30. He/she then boards the eastbound train at 8:40 and disembarks at (0,3) at 9:10. Finally, she/he boards the southbound train at 9:20 and arrives at (4,3) at 10:00. I know of no solution that works (without the above simplifications) when the poster begins at 6am.
Alan also sent in one of many good 19 station/240 minute solutions:
Starting at (0,0) at 6:00, he/she takes the special train to (2,4) at 6:50; takes the 7:00 westbound train to (2,1) at 7:30; switches to the northbound train at 7:40, arriving at (0,1) at 8:00; 8:10 east to (0,3) at 8:30; 8:40 south to (4,3) at 9:20; and 9:30 west to (4,0) at 10:00.
Others who found a way to deliver postcards to 19 stations in 240 minutes include Tom Dinger, Tamas L. Visegrady, B. Hoffrichter, Charles Taylor, and Joe Straitiff.
DDJ
Copyright © 1999, Dr. Dobb's Journal
