COMPUTING SCIENCE
Trains of Thought
Computing with locomotives and box cars takes a one-track mind
Brian Hayes
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.
» Post Comment