TY - JOUR
T1 - Reversing trains
T2 - A turn of the century sorting problem
AU - Amato, Nancy
AU - Blum, Manuel
AU - Irani, Sandra
AU - Rubinfeld, Ronitt
N1 - Funding Information:
*This work was supported in part by Bell Communications Research and in part by the National Science Foundation under Grant DCR85-13926. +Current address: Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801.
PY - 1989/9
Y1 - 1989/9
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=38249006967&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38249006967&partnerID=8YFLogxK
U2 - 10.1016/0196-6774(89)90037-0
DO - 10.1016/0196-6774(89)90037-0
M3 - Article
AN - SCOPUS:38249006967
SN - 0196-6774
VL - 10
SP - 413
EP - 428
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 3
ER -