COMPUTING SCIENCE
Trains of Thought
Computing with locomotives and box cars takes a one-track mind
Brian Hayes
What a Way to Run a Railroad
Railroads were the epitome of high tech in the later years of the
19th century. Even more than dot-com businesses of recent times,
they were a magnet for capital investment and intellectual talent.
They dominated the economy; nine of the eleven companies in the
earliest precursor of the Dow-Jones stock average were railroads.
Technological innovations bloomed: Pneumatic brakes in 1869,
automatic signals a decade later. Like the Internet today, railroads
transformed aspects of daily life and culture, knitting together
distant regions and even changing the way people kept time.
Trains have also become a part of our mental furniture. They appear
in paintings, poems, novels, songs, legends and figures of speech;
children are still strangely enchanted by them. In the sciences,
too, trains have made an impression. Einstein worked out some of his
ideas on special relativity by thinking about hypothetical events
inside railway carriages. Trains are also common props in the
problems found at the end of the chapter in mathematics and physics textbooks.
Somewhat more challenging than a typical textbook problem are
various railway-switching puzzles that began appearing in the 1880s.
W. W. Rouse Ball presented a few of them in his Mathematical
Recreations and Essays, first published in 1892. A good
example of the genre was discussed at length by A. K. Dewdney in
1987. Eastbound and westbound trains are chuffing toward each other
on a single track; they stop just in time to avert disaster, at a
place where a short siding parallels the main track. The siding,
which connects to the main line through switches at both ends, can
hold only one car or locomotive. The question is: Can the trains get
past each other, so that both of them can continue in their original
direction, pulling the same cars in the same order? (You might want
to try finding a solution on your own before reading on or peeking
at the diagram under the subheading "On the Right Track," below.)
If each train consisted of a single engine, unaccompanied by any
cars, the problem would be easy: Just have one engine (say the
eastbound one) duck into the siding while the other engine proceeds
along the main track; afterward, the eastbound engine can exit the
siding and continue on its way without obstruction. In fact, this
scheme works no matter what the length of the westbound train.
What if both trains have several cars? The trains can still
pass, but the crews will have a busy day, coupling and uncoupling
cars and throwing switches. The basic idea is to break the eastbound
train into single cars and pass them through the siding one at a
time. (The westbound train remains intact throughout the procedure.)
The eastbound engine can slip by in the way described previously;
for the rest of the process, the westbound train does all the work.
First it moves forward and grabs the leading eastbound car; then the
train backs up into the siding and uncouples the car, leaving it
there. Now the train performs a maneuver called a runaround, backing
out of the eastern end of the siding, driving forward along the main
track until it is clear of the western switch, then reversing again
into the siding in order to push the eastbound car out and hitch it
to the waiting eastbound locomotive. The runaround procedure is
repeated for each of the remaining eastbound cars; for each one the
crew has to perform three hitching and three unhitching operations,
and the westbound train reverses direction twice.
» Post Comment