Cruise Control
Dr. Dobb's Journal November, 2004
By Dennis E. Shasha
Dennis is a professor of computer science at New York University. His latest books include Dr. Ecco's Cyberpuzzles: 36 Puzzles for Hackers and Other Mathematical Detectives (W.W. Norton, 2002) and Database Tuning: Principles, Experiments, and Troubleshooting Techniques (Morgan Kaufman, 2002). He can be contacted at [email protected].
Solution to last month's Dr. Ecco
Sheriff Brandt seemed to carry desert dust in his sunbeaten face. He wasn't chewing tobacco, though his mouth moved as if he were. He came quickly to the point:
"A fugitive—a white-collar criminal of great reknown—will drive his Porsche on a flat, straight, lonely six-kilometer desert road sometime tonight.
He prefers to travel on the road because it is faster and he can use cruise control (he's been up for nearly two days). On the other hand, the only hope we police have of trapping him is on that road, because once he crosses the border at the end of the road, he will be hidden by his friends. Also our sensors won't find him in the desert.
"On the road, we have sensors at every kilometer, though the fugitive neither knows this nor can see them. The bad news is that they are not very capable. When queried, each sensor reports either: The car has already passed, or the car has not yet passed. It won't give a precise time.
"For a sensor to report, it must be queried from police headquarters (otherwise, it remains silent). Because the batteries on the sensors run low at night, each sensor can report at most once, though many can be queried simultaneously.
"Also, at each kilometer sensor it's possible to send a signal that raises netting from the road floor. If it's done no more than 10 seconds before the time the car is about to cross that section of the road, then we will trap the rich boy. If done too early, the fugitive will see it, drive into the desert, and we may never get him.
"One of my assistants at the start of the road will report to us the second the fugitive's vehicle passes. We don't think he'll be able to record the fugitive's speed, however. We know the fugitive's sport's car cannot travel faster than 360 kilometers per hour nor will the fugitive drive slower than 30 kilometers per hour.
"To summarize, because of cruise control the fugitive always travels at a constant speed between 30 and 360 kilometers per hour. The fugitive drives along the road at this constant speed unless he sees netting deployed for more than 10 seconds ahead of him. (He can see very far and, once the netting is deployed, we can't get rid of it.) In that case, he would go into the desert and escape.
"We want to capture him as early on the road as possible, so we would like to know his speed."
Warm-Up: If the fugitive travels at either 30, 40, 50, 60, 70, 80, or 90 kilometers per hour, then how many kilometers will it take to know his exact speed?
Solution to Warm-Up: 61 seconds after he arrives at kilometer 0, ask whether the car has passed at kilometer 1. If so, then it is going at 60, 70, 80, or 90; otherwise, it is going slower. Suppose it is going faster: If it is going 80 or 90 kph (or 80/60 or 90/60 kilometers per minute), it passes kilometer 2 at time 120/80 minutes (90 seconds). So, at 91 seconds, see whether the car has passed the sensor at two kilometers. We can use binary search in this way to ensure that by the 3-kilometer sensor, the police can know the speed precisely.
"That was pretty easy," Tyler complained.
The sheriff nodded and said, "Here are some tougher challenges, young man:
- Suppose the fugitive travels at any of the speeds 30, 40, 50 ,..., 360 kilometers per hour but nothing in between. Then how many kilometers would be necessary to find the exact speed?
- By when can you guarantee to net him?
- If his speed varied between 230 and 560 instead, could you do better?"
Liane and Tyler answered the questions but the sheriff still looked upset. He spoke: "We have so far enjoyed the rather artificial condition that the speeds could be only multiples of 10. Suppose all you knew was that his speed ranged from 30 to 360 kilometers/hour but any intermediate speed is possible. Can you still catch the fugitive by the end of the road without exceeding the 10 second warning time? If not, how much longer would the road have to be?
"For the last question (where any speed between 30 kph to 360 kph is possible), it might help to have sensors that could report over 10 seconds. So the sensor would then report: has not yet passed, has passed in the last 10 seconds, has passed more than 10 seconds ago. Could you net the fugitive in this case in six kilometers?"
I never heard the answer.
Reader Solutions to the "Zamboni" Puzzle
Mark Miller was able to clean the ice in 37 moves for one Zamboni and in only 18 moves when using two Zambonis. Michael Birken improved the solution for one Zamboni by using a mixture of A* search and the Floyd-Warshall Algorithm to 35 moves (http://cs.nyu.edu/cs/faculty/shasha/papers/zamboni1.png). Adam Speight showed some 4 Zamboni solutions where each Zamboni crossed only 9 edges.
DDJ
