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].
The warden was a gray-haired man with smile wrinkles. The friendly pastor look and manner failed to match my image of the guardian of violent criminals. His companion, by contrast, had a hard face locked in permanent scowl. He introduced himself only as "From the FBI," but volunteered neither name nor badge.
In any case, the warden began the conversation: "Cliff River is our state-of-the-art federal prison for high-security prisoners. Our guards are robots to eliminate any chance of corruption. People back up the guards with video monitors. There is a river on the south side that is impassable to boats and would drown the strongest swimmer. There is a cliff on the north side with a wall in front of it. The east and west sides have two rows of rolled barbed wire. Yet prisoner Doe apparently slipped out of his cell, traversed at least 19 others, and jumped off the cliff on the north side to safety with a parachute."
"Worthy of James Bond," 12-year-old Liane volunteered, one leg over the arm chair.
"Right, young lady, except this is a bad guy," the warden said. "He's blown up six buildings and killed scores of people. During the trial, we suppressed publicity for fear of making people panic."
"Whenever I see lots of human guards, each one assumes the other has taken care of me and I can usually walk through unmolested. The motto seems to be: 'The more apparent security, the less real security,'" Ecco observed.
"Practically no security whatsoever," the FBI man growled.
"We think it should have been very secure," the warden said, trying not to sound defensive. "Let me tell you more about the prison. It is organized as a one story matrix: 20 north-south rows and 35 east-west columns. Each prisoner is in a cell block by himself. The cell blocks themselves are concrete rectangular blocks so the prisoner cannot see outside into the hallway. He has a bed, a toilet, and a bare light bulb. Books are permitted only on good behavior."
"The constitution allows this?" Ecco asked, his cheeks reddening. The FBI man looked at Ecco with narrowed eyes.
The warden seemed to ignore the comment and went on: "The five robot guards are in constant patrol to check that no cell block door has been opened. They start at midnight, one at the west side of rows 4, 12, and 20, and one at the east side of rows 8 and 16. The prisoner was at cell (10,1) to start with. So, he was on the south side and had to get to the north side without being seen by the robots.
"Now for the timing. The robots proceed across (the west ones go east, the east ones go west), then when they cross completely, they go down one row, then they cross back, and so on for four rows, at which point, they return to their starting point. So, the southern-most robot starts at (1,4) (see the tick mark), crosses to (35,4), then goes to (35,3), then crosses to (1,3), then (1,2), and crosses to (35,2), then to (35,1), and crosses to (1,1) and then returns to (1,4). Since it checks each door, altogether it is checking 4×35 or 140 doors. It takes 10 seconds per door and 40 seconds to travel between rows, so it completes the whole task in 24 minutes. Figure 1 shows what happens after 1 minute. (Each robot has visited six doors.)"
"But wait," said Liane, "It looks as if the robots have passed only five rooms."
"Nice observation, young lady," the warden said.
"The cells are the narrow line segments pointing north-south. The north-south corridors are very wide, whereas the east-west ones are very narrow. So, you should count each verticle line segment as a cell.
"While the robot moves east or west, it can sense anything that moves down the hallway and will shoot it (that's why we can't have more than one robot in a hallway at the same time). It cannot see backwards or sideways, however. The prisoner moves faster: five seconds per block going north or south and two seconds per block going east or west.
"At first, we figured that the prisoner must have escaped by going directly north, because he broke through the wall at position (10,20). But in that case, he would have had to wait until the west-moving robot at row 4 reached position 10 (100 seconds), then the east-moving robot at row 8 reached position 10 (250 seconds), and then he'd be able to dash for the top without waiting further, reaching it at 310 seconds. But in fact, we have evidence to show that he reached the top in under four minutes. How is this possible?"
Liane and Ecco conferred. They talked in hushed voices and then Liane giggled, passing her hand through the hair on the back of her uncle's head. "That's what he must have done," she said. Soon after, she produced a solution.
Reader: Would you like to try to find the shortest time, after midnight, the prisoner could have reached the north side? Liane was able to get the prisoner out before 12:03:35.
The FBI man snatched the solution, grunted, and stormed out of the room. The warden smiled, "He has a reason to be unhappy. His job is antiterrorism. This Doe will be caught I'm sure, but I need your help to make sure this never happens again. I still want all cell blocks checked every 24 minutes, but can I reorganize the routes and/or timing of the robots in such a way that escape becomes impossible? Note that two robots will shoot each other if they see each other except when they are going north or south."
I never heard the answer to that one.
Reader: Is there any way to reorganize the robots so they visit every prison door every 24 minutes while completely eliminating the chance of escape and avoiding shooting one another?
Last Month's Solution
Here is Ecco's ordered list. This wordsnake has a score of 357.
invent
tense
seem
emerge
merger
geriatric
tricky
yes
essential
ally
yet
eternal
alas
lasting
stinger
gerund
underdevelop
eloped
pediatric
trice
icer
certain
incredible
blemish
mishapen
penultimate
terrible
blend
lending
ingrate
rates
tessilate
later
terrestrial
trials
sudden
denude
dense
sea
Figure 2 is the wordsnake in long form. Here is the list that yields an 18 letter sequence in long form:
antiestablishment
establishment
establishments
Reader Notes
Several readers objected to my use of the prefix "centi" to mean hundreds as opposed to hundredths in "CentiMillionaires" (DDJ, May 2000). The correct prefix is "hecto." Readers who discovered this bug include: Rich Mickelsen, Michael McCormick, Jan Vanderbrugge, Lloyd Rice, Chad Harrington, Peter Hornby, and Dale R. Sinclair. I appreciate the correction and note its consistency with words like hectare and centimeter, though I wonder what they think of words like centipede, century, or centennial?
As for alternatives to Liane's solution, Oleg Kiselyov suggests a "weird cross-over between RSA and Diffie-Hellman key exchange" that requires only 58 messages and can be done over a broadcast medium without loss of security. It works by having C1 send information to C2, C2 to C3 up to C20, then C20 sends information to C1 and C1 starts anew. At the end, C20 broadcasts the answer. For details, look at http://pobox .com/~oleg/ftp/secure-count.html.
Jason Strickland suggested a cryptography-free protocol: "In the annual meeting letter that goes out to the Centimillionaires direct them to disable caller ID and call a certain phone # and say how many centimillions they have. The phone could be a 3rd party (to alleviate voice recognition concerns). Or, they could simply enter their wealth by pressing the value in centimillions on the Telephone pad (1-100) (followed by # or whatever). Which could be decoded by modem, etc." My worry was the disabling assumption, but this too was very clever and required just 20 phone calls.
DDJ
