9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Do we need to solve arbitrarily big towers, or is there some limit we can assume, like 10, 100, 1k, 1M discs? \$\endgroup\$ – user unknown May 11 '12 at 23:23
  • \$\begingroup\$ @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. \$\endgroup\$ – Carter Pape May 12 '12 at 1:43
  • \$\begingroup\$ 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. \$\endgroup\$ – user unknown May 12 '12 at 1:48

16 Answers 16

1
\$\begingroup\$

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.
\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Save 5 chars by removing the braces. $x=--$_&-$_,say(($_-$x)%3,($_+$x)%3)for 2..1<<<> \$\endgroup\$ – marinus May 13 '12 at 22:54
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ No doubt the same logic in sed is even shorter, but my sed abilities aren't up to it. \$\endgroup\$ – Peter Taylor May 11 '12 at 18:32
  • 1
    \$\begingroup\$ You can do it in 25 chars: ])~{.{3^3%}%2,@{2\-}%++}* \$\endgroup\$ – Ilmari Karonen May 13 '12 at 14:37
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ [stock "just use say" recommendation] \$\endgroup\$ – J B May 11 '12 at 7:10
  • \$\begingroup\$ Okay -- but wouldn't I have to include the cost of enabling 5.10 features against my char count? \$\endgroup\$ – breadbox May 11 '12 at 7:54
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – J B May 11 '12 at 9:03
  • \$\begingroup\$ Thanks for the link; I was looking for that sort of thing earlier. \$\endgroup\$ – breadbox May 11 '12 at 14:05
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Nice use of xor. \$\endgroup\$ – Peter Taylor May 11 '12 at 18:33
2
\$\begingroup\$

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);}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Griffin Oct 11 '12 at 16:27
  • 1
    \$\begingroup\$ 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--. \$\endgroup\$ – ugoren Oct 11 '12 at 17:42
  • \$\begingroup\$ 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? \$\endgroup\$ – Griffin Oct 11 '12 at 18:21
  • \$\begingroup\$ @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. \$\endgroup\$ – ugoren Oct 12 '12 at 5:22
2
\$\begingroup\$

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, 2n-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 2n-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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

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

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ the coincidental nature of submitting your answer over 5 years after the original question was posed within the same hour that I returned to review the answers to this question I submitted over 5 years ago… wow. +1 \$\endgroup\$ – Carter Pape Nov 29 '17 at 6:54
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

K (ngn/k), 23 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.