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

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

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 4

Husk, 5 bytes

↑≠⁰İr

Try it online!
Each n in the output represents moving disk n to the next available peg (wrapping cyclically).

Explanation

   İr   The ruler sequence [0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, ...]
↑       Take while...
 ≠⁰     ... not equal to the input.

Answer 5

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 6

SML, 63

fun f(0,_,_)=[]|f(n,s,t)=f(n-1,s,6-s-t)@[n,s,t]@f(n-1,6-s-t,t);

call function f(n,s,t) with:

• n number of disks
• s starting point
• t goal point

Answer 7

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 8

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 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);}

Answer 10

Jelly, 5 bytes

2*Ṗọ2

Try it online!

0 move the smallest disk one space to the right (wrapping back to the start if necessary)
1 move the second-smallest disk to the only other legal column
2 move the third-smallest disk to the only other legal column
etc.

Algorithm

We can see the solution of the Towers of Hanoi problem recursively; to move a stack of size n from A to B, move a stack of size n-1 from A to C, then the disk of size n from A to B, then move a stack of size n-1 from B to C. This produces a pattern of the following form (in the output format used by this program):

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2 …

We can observe that this sequence is A007814 on the OEIS. Another possible definition of the sequence is "the kth (1-based) element of the sequence is the number of zeroes at the end of the number k when it's written in binary". And that's what the program here is calculating.

Explanation

First, we calculate the number of moves in the solution, 2ⁿ-1. It turns out to be shortest to actually calculate one extra move and discard it later, so this is 2*, i.e. 2 to the power of something. (The only input we've taken so far is the command line argument, so that gets used by default.)

Next, we use Jelly's builtin for calculating the number of zeroes at the end of a number in base b; that's ọb. As we're calculating in binary, it's ọ2. All we need to do is to apply this builtin to the numbers from 1 to 2ⁿ-1 inclusive.

There are two simple ways to iterate over a range of numbers in Jelly, € and R, and my earlier attempts at this problem used one of these. However, in this case, it's possible to go slightly shorter: Ṗ, when given a number as input, will let you do an iteration that stops one element short (in general, Ṗ is a builtin used to process all but one element of something). That's exactly what we want in this case (because 2* generates one too many elments), so using it to link 2* and ọ2 into 2*Ṗọ2 gives us a 5-byte solution to the problem.

Answer 11

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 12

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 13

J, 23 bytes

binary numbers solution

2&(+/@:~:/\)@#:@i.@^~&2

This solution uses the binary counting method described in this video.

Which is to say, I generate the binary digits from 1 up to 2^n, then take infixes of length 2 and compare each bit to the corresponding bit of the previous number, and check if they're unequal. The number of unequal bits is the output for that move.

Output, eg, for 3 disks, where smallest disk is labeled 1:

1 2 1 3 1 2 1

1 means "move the smallest disk one peg right, looping back to the first peg if needed"

n, for all other n, means "move disk n to a legal peg" (there will always be exactly one)

Try it online!

recursive solution

((],[,])$:@<:)`]@.(1=])

Same output as the above solution, but the logic here makes the recursive nature of the problem clearer.

Visualizing it as a tree also emphasizes this point:

              4
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      3               3      
     / \             / \    
    /   \           /   \
   /     \         /     \ 
  2       2       2       2  
 / \     / \     / \     / \
1   1   1   1   1   1   1   1

Try it online!

Answer 14

R, 73 bytes

Putting R on the map. Inspired by [Keith Randall's answer][1] with simplified input, print only end and start peg to save 2 bytes. Also 0-indexed pegs.

f=function(n,s=0,e=2){if(n){f(n-1,s,3-s-e)
print(c(s,e))
f(n-1,3-s-e,e)}}

Try it online!

Answer 15

APL (Dyalog Classic), 19 bytes

3|(-⍪0 1⍪2∘-)⍣⎕,⍨⍪⍬

Try it online!

output is a 2-column matrix of ints in {0,1,2} - from peg, to peg

Answer 16

K (ngn/k), 23 bytes

{3!x{-x,(,0 2),1+x}/()}

Try it online!

Answer 17

JavaScript (ES6), 45b

h=(n,f,a,t)=>n?h(--n,f,t,a)+f+t+h(n,a,f,t):''

e.g. calling h(4, 'A', 'B', 'C') (move 4 discs from peg A to peg C using auxiliary peg B)

returns 'ABACBCABCACBABACBCBACABCABACBC' (move a disc from peg A to peg B, move a disc from peg A to peg C, move a disc from peg B to peg C, etc.)