Tower of hanoi solver

Question

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.

Answer 1

GolfScript (31 25 24 chars)

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

With thanks to Ilmari Karonen for pointing out that my original trs/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

Answer 2

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

Answer 3

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

Answer 4

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.)

Answer 5

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.

Answer 6

Scala,92 88 87 chars

def?(n:Int,a:Int,b:Int){if(n>0){?(n-1,a,a^b)
print(n,a,b);?(n-1,a^b,b)}};?(readInt,1,3)

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

Answer 7

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

Answer 8

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.

Answer 9

C, 98 92 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);}