# Tower of hanoi solver

For reference as to what the tower of Hanoi is, either Google it or look on the Wikipedia page.

Your code should be able to do 2 things, and they are the following:

• Accept user input that specifies the number of discs at the starting point of the Hanoi tower
• Create output in a fashion of your choosing (so long as it is somehow logical) to show the solution to the tower puzzle.

An example of logical output would be the following (using a 4 disc start):

`L1L2C1L1R-2R-1L1L2C1C-1R-2C1L1L2C1`

`L` represents the left peg, `C` represents the center peg and `R` represents the right peg and the numbers are how far to move the disk on that peg and in what direction. Positive numbers represent the number of pegs moving towards the rightmost peg (because the disks start on the leftmost peg).

The rules to tower of Hanoi are simple:

• Only one disk may be moved at a time.
• Each move consists of taking the upper disk from one of the pegs and sliding it onto another peg, on top of the other disks that may already be present on that peg.
• No disk may be placed on top of a smaller disk.

The disks start on the leftmost peg, largest on the bottom, smallest on the top, naturally.

-
 Do we need to solve arbitrarily big towers, or is there some limit we can assume, like 10, 100, 1k, 1M discs? – user unknown May 11 '12 at 23:23 @userunknown if I were you, I wouldn't worry too much about extraordinarily large numbers, but I'll say that the highest number of disks that your program can handle should only be limited by the computer's memory capacity or its call stack limit (kind of the same thing I guess, since memory is a pretty general term). Don't let arbitrarily high numbers scare you when submitting your code, though; if your solution is creative but can only handle so many disks, I for one would still give you credit. – Carter Pape May 12 '12 at 1:43 Well, my idea was a pretty inefficient solving algorithm, and if the limit is, was the program can handle, it would be fine. But I had a look at the solutions so far, and realized, that I would play in a completely different league. – user unknown May 12 '12 at 1:48

## GolfScript (31 25 24 chars)

``````])~{{~3%}%.{)3%}%2,@++}*
``````

With thanks to Ilmari Karonen for pointing out that my original `tr`s/permutations could be shortened by 6 chars. By decomposing them as a product of two permutations I managed to save one more.

Note that factoring out the `3%` increases length by one character:

``````])~{{~}%.{)}%2,@++}*{3%}%
``````

Some people have really complicated output formats. This outputs the peg moved from (numbered 0, 1, 2) and the peg moved to. The spec doesn't say to which peg to move, so it moves to peg 1.

E.g.

``````\$ golfscript hanoi.gs <<<"3"
01021201202101
``````
-
No doubt the same logic in sed is even shorter, but my sed abilities aren't up to it. – Peter Taylor May 11 '12 at 18:32
You can do it in 25 chars: `])~{.{3^3%}%2,@{2\-}%++}*` – Ilmari Karonen May 13 '12 at 14:37

## Perl - 54 chars

``````for(2..1<<<>){\$_--;\$x=\$_&-\$_;say((\$_-\$x)%3,(\$_+\$x)%3)}
``````

Run with `perl -M5.010` and enter the number of discs on stdin.

Output format:

One line per move, first digit is from peg, second digit is to peg (starting from 0)

Example:

``````02 -- move from peg 0 to peg 2
01
21
02
10
12
02
``````
-
 Save 5 chars by removing the braces. `\$x=--\$_&-\$_,say((\$_-\$x)%3,(\$_+\$x)%3)for 2..1<<<>` – marinus May 13 '12 at 22:54

## Python, 76 chars

``````def S(n,a,b):
if n:S(n-1,a,6-a-b);print n,a,b;S(n-1,6-a-b,b)
S(input(),1,3)
``````

For instance, for N=3 it returns:

``````1 1 3  (move disk 1 from peg 1 to peg 3)
2 1 2  (move disk 2 from peg 1 to peg 2)
1 3 2  (move disk 1 from peg 3 to peg 2)
3 1 3  ...
1 2 1
2 2 3
1 1 3
``````
-

## Perl, 75 79 chars

Totally stealing Keith Randall's output format:

``````sub h{my(\$n,\$p,\$q)=@_;h(\$n,\$p^\$q^h(\$n,\$p,\$p^\$q),\$q*say"@_")if\$n--}h pop,1,3
``````

Invoke with `-M5.010` for the `say`.

(I think this can be improved if you can find a way to make use of the function's return value instead of just suppressing it.)

-
[stock "just use `say`" recommendation] – J B May 11 '12 at 7:10
Okay -- but wouldn't I have to include the cost of enabling 5.10 features against my char count? – breadbox May 11 '12 at 7:54
You wouldâ€”but it's free. Just make a note of how to invoke your program so that people not fluent in perl invocation specifics can give it a shot anyway. – J B May 11 '12 at 9:03
Thanks for the link; I was looking for that sort of thing earlier. – breadbox May 11 '12 at 14:05

## Bash (64 chars)

``````t(){ tr 2\$1 \$12 <<<\$s;};for((i=\$1;i--;))do s=`t 1`01`t 0`;done;t
``````

Posting this one despite being more than twice the length of the GolfScript one because I like the reuse of `t` to serve as `echo \$s`.

-

# Scala,9288 87 chars

``````def?(n:Int,a:Int,b:Int){if(n>0){?(n-1,a,a^b)
``````

Output format

Say number of disk=3 then,

``````(1,1,3)(2,1,2)(1,3,2)(3,1,3)(1,2,1)(2,2,3)(1,1,3) (disk number,from peg, to peg)
\---------------------------/
Move 1              ... Move n
``````
-
 Nice use of xor. – Peter Taylor May 11 '12 at 18:33

## Awk, 72 chars

``````function t(n,a,b){if(n){t(n-1,a,a^b);print n,a,b;t(n-1,a^b,b)}}t(\$0,1,3)
``````

Output format is same as Keith Randall's one.

``````awk -f tower.awk <<< "3"
1 1 1
2 1 1
1 1 1
3 1 3
1 1 1
2 1 3
1 1 3
``````
-

### Bash script, 100 96 chars

``````t(){ [[ \$1<1 ]] && return
t \$((\$1-1)) \$2 \$((\$2^\$3))
echo \$@
t \$((\$1-1)) \$((\$2^\$3)) \$3
}
t \$1 1 3
``````

Output format is same as Keith Randall's one.

``````1 1 3
2 1 2
1 3 2
3 1 3
1 2 1
2 2 3
1 1 3
``````

Edit: Saved 4 chars by peter's comment.

-
You can add the spaces and save a few chars by echoing `\$@` – Peter Taylor May 11 '12 at 23:04
@PeterTaylor: Good point. let me update it. – Prince John Wesley May 12 '12 at 2:17

## C, 9892 87 chars

Implements the most trivial algorithm.
Output is in the form `ab ab ab` where each pair means "move the top disc from peg a to peg b".
EDIT: Moves are now encoded in hex - 0x12 means move from peg 1 to peg 2. Saved some characeters.
EDIT: Reads the number from stdin, rather than parameter. Shorter.
Example:
`% echo 3 | ./hanoi`
`13 12 32 13 21 23 13`

``````n;
h(d){n--&&h(d^d%16*16,printf("%02x ",d,h(d^d/16))),n++;}
main(){scanf("%d",&n);h(19);}
``````
-
Can someone explain the syntax of the body of function h() - particularly the apparent two arguments in its recursive call (d^d%16*16 and printf(...)), and the last operation apparently hanging off the end. Based on my knowledge, that function has two syntax errors, but I already know it builds (after including stdio) and executes correctly. – Griffin Oct 11 '12 at 16:27
It's possible to pass more parameters than the function wants. Their values go nowhere. `h(x,printf(...))` is simply a way to call `printf` before `h` is called. The last `n++` is made after the inner `h` returns. It's used to undo the initial `n--`. – ugoren Oct 11 '12 at 17:42
Thanks, that makes sense (the purpose of n++ was evident). Why isn't there a semicolon preceeding n++ instead of a comma, or does it make a difference? – Griffin Oct 11 '12 at 18:21
@Griffin, Actually `;` would be the same here. `,` is often useful (e.g. `if(x)a,b;` replaces `if(x){a;b;}`), but has no advantage here. – ugoren Oct 12 '12 at 5:22