Authors: Nancy Amato, Manuel Blum, Sandra Irani, Ronitt Rubinfeld

Venue: Journal of Algorithms
DOI: 10.1016/0196-6774(89)90037-0
Link to Publication

Abstract:
In this paper we study a reversing train puzzle proposed by Sam Loyd near the turn of the century. We concern ourselves with a version of this puzzle described most recently by A. K. Dewdney in Scientific American. There is a train, locomotive and n cars, that must be entirely reversed using only a short spur line attached to the main track. The efficiency of a solution is determined by summing, for all cars, the total distance moved by each car, where distance is measured in car lengths. We present an O(n2 log2 n) algorithm for accomplishing this task. 

@article{Amato-rtatot-1989, 
 author = {Nancy Amato and Manuel Blum and Sandra Irani and Ronitt Rubinfeld}, 
 journal = {Journal of Algorithms}, 
 month = {September}, 
 note = {DOI: 10.1016/0196-6774(89)90037-0}, 
 number = {3}, 
 pages = {413--428}, 
 title = {Reversing Trains: A Turn of the Century Sorting Problem}, 
 volume = {10}, 
 year = {1989} 
}