Recursion: The Towers of Hanoi problem

[DigitalKitty]

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

[blokhead]

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.

[merlyn]

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}

[tachyon]

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

[pg]

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

  }
}

[dragonchild]

This has been discussed before. You might want to look at:
• Re: Worst thing you ever made with Perl
• Hanoi
• (Golf) Towers of Hanoi
• Towers of Hanoi

[Anonymous Monk]

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@{$_[$-]}
}

[pg]

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.

[apotheon]

Did I miss the part where you told us what the criteria are for "finishing" the puzzle?

[Theo]

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.

[apotheon]

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.

[Ytrew]

You forgot the line at the end! It should read:

undef $world; # DESTROY method invokes clap_of_thunder()

:-)

--
Ytrew Q. Uiop

[MistaMuShu]

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

[insaniac]

[terra incognita]

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

[pmonk4ever]

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

[abitkin]

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.

[Jasper]

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

[abitkin]

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.

[SpanishInquisition]

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

[osunderdog]

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

 <M>-x hanoi <ret>

[gellyfish]

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\

[kutsu]

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

[Anonymous Monk]

Can't open file /usr/share/vim/macros/hanoi/hanoi.vim

Guess not for every vim.

PICO RULZ!

[Anonymous Monk]

Really simple implementation. You might be interested in this visualization of Towers of Hanoi: https://thewalnut.io/visualizer/visualize/1322/342/ It is based on a non-recursive algorithm, although the implementation is in Python, instead of Perl. I'm not experienced enough to port it yet...