Laser Shuttles

Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998) 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].

Emma Skylight explained, "NASA is preparing missions for 100 years from now." The appropriately named scientist described herself as an optical propulsion physicist. She came to Ecco's apartment with an armful of detailed construction and laser designs.

"Among the propulsion mechanisms we have designed for space colonies are laser shuttles," she continued. "A laser shuttle propels a vehicle at high speed for short distances (a few tens of kilometers). In a large Martian plane, this will permit vehicles to be ejected from one space station and 'caught' by braking lasers on the other side. By the very nature of this transport mechanism, the route that is taken must be linear. Further, for safety's sake, we don't want routes to intersect. Collisions would almost surely be fatal."

"Let me see if I understand," Liane said. "Between two stations, there can be only one route. Between three stations there can be the three routes of a triangle. Among four stations in a square there can be the four links of a square, plus one diagonal. The other diagonal is disallowed because it would cross the first."

"Right," said Skylight. "At the same time, we want there to be as many connections as possible among the stations so that no station will be isolated. Let me tell you about the stations. Each one will have a ground area of 200×200 meters and a height of 100 meters. The laser shuttles will fly to and from the roof. The stations will be placed at points in a large grid. The grid points are separated by 10 kilometers in the x- and y-coordinates.

"We have 20 points. They are not laid out very symmetrically I admit, but they follow the contours of the most temperate Martian valley, as in Figure 1. What we seek from you is a way to lay out the routes, so there are as many as possible and no station has fewer than three routes connecting it to other stations. Further, no journey should require more than four shuttle trips."

Reader: Would you like to give it a try? Ecco and Liane were able to lay out 44 flight paths (edges in the graph) while meeting the constraints, including the absence of crossing edges. If you have as good or a better solution, please send me a web page address for viewing a GIF or JPEG of your solution -- I'm not good at attachments. Doing better means maintaining the positions of the stations and meeting the other conditions of the problem while either: increasing the number of routes without increasing the maximum length of a trip; or decreasing the maximum length of a trip without decreasing the number of routes.

Last Month's Solution

Figure 2(a) illustrates the winning strategy Liane worked out for "Straight Flats and Steeps." Each player has 12 possible moves. We will count moves taken or moves eliminated. In the first move, flat moves across in the middle. In the first two moves, flats may get Figure 2(b). In doing so, flats eliminate six steep moves. In the next two turns, flats can eliminate at least two more steep moves by moving into either the first or last column. Steep player, in the meantime, has moved four times. So, steep has no more to do.

Alternatively, the steep player may respond to the first move as in Figure 2(c), in which case flat player can play as in Figure 2(d). As a result, flat has eliminated seven steep moves and has reserved two flat moves for the future; see Figure 2(e). In the next move, flat can eliminate one more steep move and guarantee one more flat move for the future. So, there will be eight eliminated steeps, three taken steeps, and three guaranteed flats. Therefore, flats can guarantee a victory. Please remember that "Straight Flats and Steeps" leaves open the much more complex "Articulated Flats and Steeps," especially for larger sizes. I will report on web sites having clever algorithms in a future column.

Reader Notes

There were two parts to the "Rosetta" puzzle (DDJ, May 1999) -- figuring out the graph isomorphism of the encrypted graph with the template graph, after resolving the errors; and cracking the single substitution code. Several readers solved the first problem and a remarkably large number solved both.

Those who solved both include: Eugene Eric Kim, Earl Paddon, Pearl Pauling, Alan E. Dragoo, Andrey Jivsov, Grulg Bvvlp (encrypted), Bob Angstadt, Sam Stump, Gabin Kattukaran, Robert H. Morrison, Landon Rabern, Andy W. Desplenter, Jonathan Chen, Mayne Oestlyngen, and Jacco Kulman.

Those who solved the first part include: Richard W. Lipp, Wesley T. Perkins, Gabin Kattukaran, Christian Tanguy, and Burghart Hoffrichter.

And finally, Scott Warren, chief scientist of Rosetta Inc., wrote and said: "Rosetta is a registered trademark of Rosetta, Inc." Napoleon, watch out.

DDJ