COMPUTING SCIENCE
Trains of Thought
Computing with locomotives and box cars takes a one-track mind
Brian Hayes
All the Livelong Day
From the mathematical literature on railroad sorting, one might get
the impression that putting the train in order is the end of all
difficulties. The cars can then be dropped off at their
destinations, one by one, without further thought. Train crews tell
a different story. A memoir by Ralph E. Fisher, who worked on the
Boston and Maine Railroad until the 1950s, refers to the process of
making deliveries as a chess game. "Figuring out all these
moves required no small skill if they were to be done in the
shortest time and the least amount of motion."
Inspired by Fisher's stories, I offer the little puzzle
(right). The task is simply to deliver cars 1, 2 and 3 to
destinations A, B and C. The cars are
already in delivery order. The procedure shown requires six
reversals, three couplings and six uncouplings, for a total of 15
steps. Is there a better solution? Would some other initial
permutation of the cars be more efficient? Is there a worse permutation?
The chess game of making freight-car deliveries is one aspect of
railroading that has gotten easier in recent years. Many of the spur
lines used for such local runs have been closed. Much rail freight
is now shipped in containers or piggy-back trailers that are lifted
off the train at a central terminal and delivered by truck. Such
"intermodal" transport doubtless has several advantages.
One of them is escape from the tyranny of the one-track mind.
© Brian Hayes
» Post Comment