Reversing trains: A turn of the century sorting problem Academic Article

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(n 2 log 2 n) algorithm for accomplishing this task. 1989.

authors

• Amato, Nancy

published proceedings

• Journal of Algorithms

altmetric score

• 2

author list (cited authors)

• Amato, N., Blum, M., Irani, S., & Rubinfeld, R.

citation count

• 10

complete list of authors

• Amato, Nancy||Blum, Manuel||Irani, Sandra||Rubinfeld, Ronitt

publication date

• September 1989

publisher

• Elsevier  Publisher

published in

• Journal of Algorithms in Cognition, Informatics and Logic  Journal

Digital Object Identifier (DOI)

• 10.1016/0196-6774(89)90037-0

start page

• 413

end page

• 428

volume

• 10

issue

• 3

URL

• http://dx.doi.org/10.1016/0196-6774(89)90037-0