Reversing trains: A turn of the century sorting problem

Nancy Amato, Manuel Blum, Sandra Irani, Ronitt Rubinfeld

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)413-428
Number of pages16
JournalJournal of Algorithms
Volume10
Issue number3
DOIs
StatePublished - Sep 1989
Externally publishedYes

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Reversing trains: A turn of the century sorting problem'. Together they form a unique fingerprint.

  • Cite this