Reversing trains: A turn of the century sorting problem | Academic Article individual record
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
author list (cited authors)
Amato, N., Blum, M., Irani, S., & Rubinfeld, R.
publication date
1989
published in
altmetric score

2.0

citation count

10