• Not logged in
• Login
• Signup
• Activity Log
• Challenges
• Forums
• Help

See who is active in this challenge →

Tower of Hanoi

(Challenge added 513 days ago.)

To recurse, or not to recurse, that is the question.

Discuss This Challenge →

The Problem

The Tower of Hanoi puzzle was invented by Edouard Lucas in 1883. It consists of three pegs, and a number of disks of varying sizes which can slide onto the pegs.

Traditionally, the puzzle starts with the disks stacked in order of size on one peg, which the smallest disk at the top. The objective is to move the entire stack to another peg, obeying these simple rules:

• Only one disk can be moved at a time.
• You can only move the top-most disk off one of the pegs, and place it on top of disks which may already be present another peg.
• You cannot place a disk on top of a smaller disk.

For more information about the puzzle, including images of the puzzle and various methods of solving it computationally, see the Tower of Hanoi Wikipedia page. Note that because of some of our tests, your solution will have to be capable of starting with the disks being in any valid arrangement.

More Information

• The puzzle will always have three pegs, which can be imagined to be placed side-by-side and labeled from left-to-right as A, B and C.
• There will be at least 3 disks, and at most 9. The disks are labeled according to their relative sizes, 9 being larger then 8, and will be numbered continuously from 1.
• The starting arrangement of disks will be provided to you on stdin in the form of three lines separated by newlines. The first line describes the disks which start on peg A, the second line the disks which start on peg B, and the third, the disks which start on peg C.
• Each line will contain a single sequence of numbers with no separation which identify the disks on that peg. The first number in the sequence should be considered to be at the bottom of that peg, and subsequent numbers being above that disk. For example, the sequence

  631

  means that disk 6 is at the bottom of the peg, with disk 3 above, and disk 1 at the top.
• Your code should output the moves necessary to move all of the disks onto peg C, ordered in increasing size from top-to-bottom, on stdout. Each individual move should be on its own line, and each move should be separated by a single newline.
• The format of each move should be of the form

  disk to peg

  For example, a move of

  1 to C

  means "move disk 1 (from whichever peg it is currently on) to peg C"
• Each move you output will be checked to ensure it is valid. Any invalid moves will result in an error message being generated. Moving a disk onto the peg it is currently on is valid, but ultimately useless.
• You can use as many or as few moves as you need to solve the puzzle. The number of moves you make doesn't influence the final score you'll receive, the challenge is about writing the shortest possible code which can solve the puzzle. Remember however that your code must successfully run within a maximum of 4 seconds per test.
• Each of your submissions will be run 10 times. Your submission will have to pass all 10 tests for it to be deemed successful.

Examples

Out of the 10 tests your code will be subjected to, the first five will always provide the same input. You can see the input and the expected output for these runs below :

• Run 1 - 321.
• Run 2 - 54321.
• Run 3 - 7654321.
• Run 4 - 52, 31, 4.
• Run 5 - 6, 75, 321.

For the other five runs, your submission will be provided with random input. To see a random input and some sample output with solves the puzzle, click here. To see other random input, reload that page.

Thanks

Thanks to Flagitious who suggested this challenge a whole 53 days ago in the forums, and also provided some sample code (Which I then largely ignored!) Thanks also to Mick for his comments on that thread. Sorry for not deciding to go with your Python friendly input idea - Although it would have been nice for Ruby also, It would have made the PHP implementation even less likely to win!