Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Recursion: The Towers of Hanoi problem

by DigitalKitty (Parson)
on Oct 19, 2004 at 00:37 UTC ( #400359=perltutorial: print w/ replies, xml ) Need Help??

Hi all.

Many computer science professors eventually discuss the concept of recursion. To help illustrate the power and elegance (yes, there are drawbacks as well) it provides, a classic problem known as the 'Towers of Hanoi' is often used. For those unfamiliar with this classic, please allow me explain the history and rules...

The History:


The puzzle is called "Towers of Hanoi" because an early popular presentation wove a fanciful legend around it. According to this myth (uttered long before the Vietnam War), there is a Buddhist monastery at Hanoi which contains a large room with three time-worn posts in it surrounded by 21 golden discs. Monks, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle, once every day since the monastery was founded over a thousand years ago. They are said to believe that when the last move of the puzzle is completed, the world will end in a clap of thunder. Fortunately, they are nowhere even close to being done.

The Rules:


  • There are n disks (1, 2, 3,..., n) and three towers (pegs). The towers are labeled 'A', 'B', and 'C'.
  • All the disks are initially placed on the first peg (the 'A' peg).
  • No disk may be placed on top of a smaller disk.
  • You may only move one disk at a time and this disk must be the top disk on a peg.


The Code:


use warnings; use strict; # Towers of Hanoi # Perl version (5.8.0) # Ported from Java my $numdisks = 0; print "Number of disks? "; chomp( $numdisks = <STDIN> ); print "The moves are:\n\n"; movedisks( $numdisks, 'A', 'B', 'C' ); sub movedisks { my( $num, $from, $to, $aux ) = @_; if( $num == 1 ) { print "Move disk $num from $from to $to\n"; } else { movedisks( $num-1, $from, $aux, $to ); print "Move disk $num from $from to $to\n"; movedisks( $num-1, $aux, $to, $from ); } }


Any suggestions on how to 'fine tune' this program are more than welcome.

Hope this proves interesting.

Thanks,
~Katie

20041023 Edit by Steve_p: Changed title from 'Visiting the Towers of Hanoi.'

Comment on Recursion: The Towers of Hanoi problem
Download Code
Re: Recursion: the Towers of Hanoi problem
by blokhead (Monsignor) on Oct 19, 2004 at 01:39 UTC
    Another related fun 'n' interesting problem is to start with the disks placed randomly onto the three pegs and then try to sort them all onto one peg. In this version, you are allowed to place any disk onto any other disk (no size restrictions). In fact, a question on a recent algorithms Ph.D qualifying exam here at UIUC was to show that disks can be sorted in O(n log n) moves, and to also show that in fact, &Omega(n log n) moves are required in general. I won't give away how to sort the disks in O(n log n) time, but here's a hint: adapt quicksort.

    If we aren't allowed to put larger disks on top of smaller disks (as in the classic example above), you need an exponential number of moves. If T(n) is the number of moves needed to sort n disks, your recursion gives the recurrence T(n) = 2T(n-1). You can verify that T(n) = 2^n.

    Towers of Hanoi problems are good examples in that they are easy to visualize, and their relationship to sorting with stacks is obvious.

    blokhead

      Towers of Hanoi problems are good examples in that they are easy to visualize, and their relationship to sorting with stacks is obvious.
      However, if you are selecting problems for a syllabus, please be aware that "easy to visualize" can actually give an unfair disadvantage to some of your students. I've commented on my own affliction with regard to using GUIs and learning to program.

      I completely understand the algorithm for Towers of Hanoi, and why it works, and have translated it into a few languages. But I understood it only by playing with physical disks or marks (and erasing) on a piece of paper. I could never have constructed it by "visualization", since my brain doesn't work that way.

      So, beware when you pretend you know what skills are "universal" about thinking... you may have wrong thinking about that. {grin}

      -- Randal L. Schwartz, Perl hacker
      Be sure to read my standard disclaimer if this is a reply.

Re: Recursion: the Towers of Hanoi problem
by pg (Canon) on Oct 19, 2004 at 01:40 UTC

    This is a real beauty. In this case, without recursion, you have to use something like stack to rememeber all the steps you went through, and for an average person, it wold take you quite some time to make the stack right, when to push, when to pop...

    With recursion, the REAL code is only about 4 or 5 lines long.

    This could even be viewed as sort of AI program, but the solution is definite.

Re: Recursion: the Towers of Hanoi problem
by apotheon (Deacon) on Oct 19, 2004 at 02:14 UTC
    Did I miss the part where you told us what the criteria are for "finishing" the puzzle?

    - apotheon
    CopyWrite Chad Perrin
      When all of the disks are on a different peg than they started on, size ordered smallest to largest, top to bottom. An extra "twist" is to require them to end up on a specific peg.

      -Theo-
      (so many nodes and so little time ... )

        Ah! Thank you.

        I'd seen this puzzle before (perhaps even in a CompSci course, and/or in a book about programming), but frankly didn't recall its conditions. I needed a memory refresher.

        - apotheon
        CopyWrite Chad Perrin
Re: Recursion: the Towers of Hanoi problem
by dragonchild (Archbishop) on Oct 19, 2004 at 03:03 UTC
    This has been discussed before. You might want to look at:

    Being right, does not endow the right to be rude; politeness costs nothing.
    Being unknowing, is not the same as being stupid.
    Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
    Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

Re: Recursion: the Towers of Hanoi problem
by tachyon (Chancellor) on Oct 19, 2004 at 03:34 UTC

    As always there are non recursive solutions. This one is 14 lines long if you exclude the animation code.

    #!/usr/bin/perl -w print "Number of disks? "; chomp( my $numdisks = <STDIN> ); print "Sleep? "; chomp( my $sleep = <STDIN> ); $numdisks ||= 8; $sleep ||= 0.1; my $board = [ [], [], [], [] ]; push @{$board->[1]}, $_ for reverse 1 .. $numdisks; my %tower = map{ my $str =' 'x($numdisks-$_).'o'x$_; $str = $str.($_?'+':'|').reverse($str); $_, " $str " } 0..$numdisks; hanoi( $numdisks ); sub hanoi { my $n = shift; my $n1 = $n+1; my @D = (1)x$n1; my @s = 1..$n1+1; my $dir = 1 & $n; for(;;) { my $i = $s[0]; do{ show($n,0,0,1); last } if $i>$n; my $to =($D[$i]+($i&1?$dir:1-$dir))%3+1; show( $i, $D[$i], $to ); $D[$i] = $to; $s[0] = 1; $s[$i-1] = $s[$i]; $s[$i] = $i+1; } } sub show { my ( $num, $from, $to, $show_final ) = @_; $^O =~ m/Win32/ ? system("cls") : system("clear"); for my $i( reverse 0..$numdisks ) { print "\n", map{$tower{ $board->[$_]->[$i] || 0} }1..3; } return if $show_final; push @{$board->[$to]}, pop @{$board->[$from]}; print "\n\nMove disk $num from $from to $to\n"; select undef, undef, undef, $sleep; }

    cheers

    tachyon

      To be fair, you didn't win today ;-)

      Yesterday, you gave a non-recursive version of the number guessing game. You won, as in that case, there was absolutely no need for recursion, other than for fun.

      But in the case of Towers of Hanoi, the recursive version is way more beautiful than the non-recursive version. I am not talking about the fact that your code is longer than the recursive version, although that is one of those little things...

      Th real winning point is that: in the recursive version, you don't think or coding, but simply tell the computer that: to make this move, you have to make those two moves first. That's it, that's all what you need to tell the computer. The rest is not your business any more:

      sub movedisks { #to make this move
      my( $num, $from, $to, $aux ) = @_; if( $num == 1 ) { ; } else {
      #you have to make those two moves first movedisks( $num-1, $from, $aux, $to ); movedisks( $num-1, $aux, $to, $from );
      } }
Re: Recursion: the Towers of Hanoi problem
by Anonymous Monk on Oct 19, 2004 at 12:53 UTC
    Too bad people introduce the Towers of Hanoi, and then stop when they have introduced recursion. Because there's much more to discover. For instance that disks move in simple cycles, with half the disks moving in one direction, the other half in another. And that given the move number, one can calculate which disk needs to be moved based on the binary respresentation of the move number. Here's an interative solution based on those facts:
    $*=shift; for($_=1;$_<=$*;$_++){$_[$_]=[split$,,(($*%2)xor($_%2))?ABC:ACB]} for($_=1;$_<2**$*;$_++){ $-=1+length((sprintf("%b",$_)=~/(0*)$/)[0]); printf"Move disk %d from pole %s to pole %s\n",$-,@{$_[$-]}[0,1]; push@{$_[$-]},shift@{$_[$-]} }
Re: Recursion: the Towers of Hanoi problem
by Ytrew (Pilgrim) on Oct 19, 2004 at 22:51 UTC
    You forgot the line at the end! It should read:
    undef $world; # DESTROY method invokes clap_of_thunder()
    :-)

    --
    Ytrew Q. Uiop

Re: Recursion: the Towers of Hanoi problem
by MistaMuShu (Beadle) on Oct 19, 2004 at 23:30 UTC
    Forgive me, but I'm not seeing how the last statements in the else loop get executed:

    print "Move disk $num from $from to $to\n"; movedisks( $num-1, $aux, $to, $from );

    I jotted down the steps with 3 discs on a piece of paper and this is how I saw it:

    $numdisks = 3 movedisks( 3-1, A, C, B) movedisks( 2-1, A, B, C) print "Move disk 1 from A to B" for the base case

    Shouldn't the last two statements be right outside the else block?

    Neato problem, I didn't get it at first, but now I'm tempted to start my own 3-peg disc rotating habit. It all sounds very zen ;-)

      well that's easy, the last 2 statements get executed when the algorithm is "rolling back" the loop. I mean: the last time the first movedisks statement is executed in the loop, it will start executing the last 2 statements from back to front (read: go over the loop from back to front)... that's what recursion is all about ;-)

      --
      to ask a question is a moment of shame
      to remain ignorant is a lifelong shame
OT: Towers of Hanoi: emacs
by osunderdog (Deacon) on Oct 20, 2004 at 15:54 UTC

    For those of you that run emacs, you can see the Towers of Hanoi by typing:

    <M>-x hanoi <ret>

    "Look, Shiny Things!" is not a better business strategy than compatibility and reuse.


    OSUnderdog

      And for those that might use vim you can type:

      :so /usr/share/vim/macros/hanoi/hanoi.vim <ret> g
      But to be honest it is a bit fast to be interesting ;-)

      /J\

        Can't open file /usr/share/vim/macros/hanoi/hanoi.vim
        Guess not for every vim.

        PICO RULZ!

        if you have vim version 61 they changed the default share directory: /usr/share/vim/vim61/macros/hanoi/hanoi.vim, regardless locate hanoi (or window find hanoi) should reveal it's location. So that's:

        :so /usr/share/vim/vim61/macros/hanoi/hanoi.vim g

        "Cogito cogito ergo cogito sum - I think that I think, therefore I think that I am." Ambrose Bierce

Re: Recursion: the Towers of Hanoi problem
by abitkin (Monk) on Oct 20, 2004 at 16:52 UTC
    My own code, for a class I had
    #!/usr/bin/perl -w use strict; han('A','B','C',$ARGV[0]); sub han{ return if $_[3] <= 0; han($_[0],$_[2],$_[1],$_[3]-1); print "Move disc $_[3] from $_[0] to $_[2]\n"; han($_[1],$_[0],$_[2],$_[3]-1); }
    Number of discs is supplied as $ARGV[0] so, yeah. You could continue to play with this to see how much more it will compress. (I really didn't like the TA's for this class and eventually started using map and grep in all the programs.)

    Edit:
    made it shorter.


    ==
    Kwyjibo. A big, dumb, balding North American ape. With no chin.
      Ironically that's the way I feel about work...

      It's not about obfuscation, it's about coding 9 planes of existance higher than them because you can, and they don't want to learn...

      sub han { if (my $l = pop) { han(@_[0,2,1],$l-1); print "Move disc $l from $_[0] to $_[2]\n"; han(@_[1,0,2],$l-1); } }

      little shorter
        Try this on:
        sub a{my$l=pop;a(@_[0,2,1],--$l)."Move disc $l from $_[0] to $_[2] ".a(@_[1,0,2],$l)if$l>0;}print a 'A'..'C',shift;
        Now trying for the least number of chars. 116 in this solution.
        New rules, no #! needed.

        ==
        Kwyjibo. A big, dumb, balding North American ape. With no chin.
Re: Recursion: the Towers of Hanoi problem
by terra incognita (Pilgrim) on Oct 20, 2004 at 20:11 UTC
    Here is a modified version that will display a simple ASCII representation for those people like myself that think better in pictures.
    I am sure that this can be improved significantly.
    Comments on where I can improve this code and what practices I should stay away from are appreciated.
    This should work on both Windows and Solaris though the format may be a little off on Solaris.
    #!/usr/local/bin/perl use strict; # Towers of Hanoi # Perl version (5.8.0) # Ported from Java my $numdisks = 0; my $count =0; print "Number of disks? "; chomp( $numdisks = <STDIN> ); clear (); my $i; my @polea; my @poleb; my @polec; my $loop = 0; my $string ; while ($numdisks > $loop++) { $string = $string ."x"; push (@polea, $string); push (@poleb, ""); push (@polec, ""); } print "A\tB\tC\n"; for (my $len = 0 ;$len <= ($numdisks -1); $len++) { print "$polea[$len]\t$poleb[$len]\t$polec[$len]\n"; } sleep 2; clear (); movedisks( $numdisks, 'A', 'B', 'C' ); # SUB LAND sub clear { if ($^O eq "MSWin32") { system 'cls'; }else{ system 'clear'; } } sub movedisks { my( $num, $from, $to, $aux ) = @_; if( $num == 1 ) { paintdisks ($num, $to, $from); }else{ movedisks( $num-1, $from, $aux, $to ); paintdisks ($num, $to, $from); movedisks( $num-1, $aux, $to, $from ); } } sub paintdisks { my( $num, $dest, $source) = @_; my $foo; if ($source eq "A") { $foo = $polea[0]; shift @polea; }elsif ($source eq "B") { $foo = $poleb[0]; shift @poleb; }else{ $foo = $polec[0]; shift @polec; } if ($dest eq "A") { unshift @polea, $foo; }elsif ($dest eq "B") { unshift @poleb, $foo; }else{ unshift @polec, $foo; } print "A\tB\tC\n"; for (my $len = 0 ;$len <= ($numdisks -1); $len++) { print "$polea[$len]\t$poleb[$len]\t$polec[$len]\n"; } sleep 2; clear (); }
      All,

      This runs on ActiveState Perl 5.10.0 as it is written, which is really a nice implementation for visualization of the problem space... :)

      I tinkered with it a little, added a variable to count the number of moves. 10 disks were my limit, that solves fairly quickly. Never did get to the 21 disc version, I didn't want to wait that long. :)

      However, one of the links published by dragonchild led me to this site:

      http://www.superkids.com/aweb/tools/logic/towers

      where I found a short history of the tale, seems there are 64! discs, so the final solution works out to ~585 billion years or so, moving one disc a second...too much time for me to spend...but it was a very interesting exercise... ;>)

      ki6jux

      "No trees were harmed in the creation of this node. However, a rather large number of electrons were somewhat inconvenienced."

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perltutorial [id://400359]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (7)
As of 2014-08-30 08:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (291 votes), past polls