MY AMERICAN SCIENTIST
SEARCH

HOME > PAST ISSUE > March-April 2007 > Article Detail

COMPUTING SCIENCE

# Trains of Thought

Computing with locomotives and box cars takes a one-track mind

Track Topology

Playing with a puzzle like this one will quickly acquaint you with a salient fact about railroads: They are one-dimensional. Rail cars cannot jump over or go around one another. Indeed, if a rail line has no switch points—if it is an unbranched length or loop of track—then the order of the cars is absolutely invariant. So is their orientation, or polarity; each car always faces in the same direction along the track. As a matter of fact, even in the presence of sidings like the one in Dewdney's puzzle, no rearrangement of the cars can ever alter their orientation; you can shuffle their sequence but you cannot change the direction they are facing. Certain other configurations of tracks and switches, however, do allow the orientation to be reversed.

Railroad switches (also known as turnouts, or points) have roughly the same geometry as highway on-ramps and off-ramps:

The action of the switch is asymmetrical. A train departing A and moving from right to left can be steered either to B or to C, but trains traveling from left to right have no choices. The switch does not allow a turn from B to C or from C to B (except by going through the switch toward A and then backing up). For trains headed right to left, a switch in this configuration is called a facing-point switch; for those going left to right it is a trailing-point switch.

Switches combine with straight and curved sections of track to form the basic structural motifs of railroad layouts. The simplest such element (other than an unbranched length of track) is a lead, or stub: a dead-end branch connected to the main track by a switch at one end. Depending on a train's direction of travel, leads are entered either head-on through a facing-point switch or by backing up through a trailing-point switch.

A siding, as mentioned above, is a parallel track with connections to the main line at both ends; the two switches face in opposite directions, which means that a train can run through the siding and return to the main track still going the same way. A turnaround loop has a jug-handle shape, with two switches that face in the same direction; turnarounds are rare except at the terminus of a rail line. Finally there is the wye, a configuration of three switches joining three tracks, and allowing a train on any track to reach either of the other tracks. Turnarounds and wyes differ from other track elements in that they change a car's orientation: The car can go in facing east and come out facing west.

Some versions of the passing puzzle have the trains confronting each other at a wye instead of a siding. The third track attached to the wye is a short spur, with room for just one car. Despite this change in topology, essentially the same procedure can be used to get the trains past each other. Again the intact westbound train shuttles back and forth, parking the eastbound cars one at a time on the spur, then doing a runaround before pulling them out and shoving them along to the east. But there's a difference: The cars come out of the spur with reversed orientation. Turning them to face in the right direction takes another pass through the wye.

Can the trains pass if all they have to work with is a one-car, dead-end lead? Around 1900 Sam Loyd published a solution for trains of length 4 and 5. It takes 33 reversals of direction.

Another famous railroad puzzle asks if a train can make a U-turn at a wye with a one-car-length spur. A suitable unit of measure for the work done in turning the train around is the effort expended in moving a single car through its own length. For a train of n cars, Dewdney gave an algorithm requiring an amount of work proportional to n 3; in essence, n cars move through n car-lengths n times. In 1988 Nancy Amato, Manuel Blum, Sandra Irani and Ronitt Ruvinfeld (all then at the University of California, Berkeley) found an improvement, reducing the effort required to n 2log2 n.