Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

cannot follow hanoi subroutine

by convenientstore (Pilgrim)
on Nov 05, 2007 at 03:34 UTC ( [id://648942]=perlquestion: print w/replies, xml ) Need Help??

convenientstore has asked for the wisdom of the Perl Monks concerning the following question:

Hello Monks,
I think I need some help understanding Hanoi tower program. I was just going over Hanoi in subroutine tutorial section and I can't exactly follow the program.
How does below step get --> 3 ??

I think I understand the algorithm but I don't think I understand the technique this program is using

----Move disk #3 from A to C.----

#!/usr/bin/perl -w use strict; sub hanoi { my ($n, $start, $end, $extra) = @_; if ($n == 1) { print "HELLLLLOOOOOOOOOOOOO Move disk #1 from $start to $end.\n +"; } else { hanoi($n-1, $start, $extra, $end); print "Move disk #$n from $start to $end.\n"; hanoi($n-1, $extra, $end, $start); } } hanoi(3, 'A', 'C', 'B'); ./perl.hanoi1 HELLLLLOOOOOOOOOOOOO Move disk #1 from A to C. Move disk #2 from A to B. HELLLLLOOOOOOOOOOOOO Move disk #1 from C to B. Move disk #3 from A to C. HELLLLLOOOOOOOOOOOOO Move disk #1 from B to A. Move disk #2 from B to C. HELLLLLOOOOOOOOOOOOO Move disk #1 from A to C. DB<2> main::hanoi(perl.hanoi1:7): if ($n == 1) { + DB<2> +x $n 0 1 + DB<3> +s main::hanoi(perl.hanoi1:8): print "HELLLLLOOOOOOOOOOOOO Mov +e disk #1 from $start to $end.\n"; + DB<3> +s HELLLLLOOOOOOOOOOOOO Move disk #1 from A to C. main::hanoi(perl.hanoi1:11): print "Move disk #$n from $sta +rt to $end.\n"; + DB<3> +s Move disk #2 from A to B. main::hanoi(perl.hanoi1:12): hanoi($n-1, $extra, $end, $sta +rt); + DB<3> +x $n 0 2 + DB<4> +s main::hanoi(perl.hanoi1:6): my ($n, $start, $end, $extra) = @_; + DB<4> +x $n 0 undef + DB<5> +s main::hanoi(perl.hanoi1:7): if ($n == 1) { + DB<5> +x $n 0 1 + DB<6> +s main::hanoi(perl.hanoi1:8): print "HELLLLLOOOOOOOOOOOOO Mov +e disk #1 from $start to $end.\n"; + DB<6> +s HELLLLLOOOOOOOOOOOOO Move disk #1 from C to B. main::hanoi(perl.hanoi1:11): print "Move disk #$n from $sta +rt to $end.\n"; + DB<6> +x $n 0 3

Replies are listed 'Best First'.
Re: cannot follow hanoi subroutine
by GrandFather (Saint) on Nov 05, 2007 at 04:08 UTC

    The technique is to use recursion. Maybe it is clearer if we get the code to actually move the "rings" and show the state of the piles after each move? Consider:

    #!/usr/bin/perl -w use strict; use warnings; my %piles = (A => [reverse 1..3], B => [], C => []); dumpPiles (); hanoi (scalar @{$piles{A}}, keys %piles); sub hanoi { my ($n, $start, $end, $extra) = @_; if ($n == 1) { report ($start, $end); } else { hanoi($n-1, $start, $extra, $end); report ($start, $end); hanoi($n-1, $extra, $end, $start); } } sub report { my ($start, $end) = @_; my $disk = pop @{$piles{$start}}; print "Moved disk $disk from $start to $end.\n"; push @{$piles{$end}}, $disk; dumpPiles (); } sub dumpPiles { for my $pile (sort keys %piles) { print "$pile: @{$piles{$pile}}\n"; } }

    Prints:

    A: 3 2 1 B: C: Moved disk 1 from A to C. A: 3 2 B: C: 1 Moved disk 2 from A to B. A: 3 B: 2 C: 1 Moved disk 1 from C to B. A: 3 B: 2 1 C: Moved disk 3 from A to C. A: B: 2 1 C: 3 Moved disk 1 from B to A. A: 1 B: 2 C: 3 Moved disk 2 from B to C. A: 1 B: C: 3 2 Moved disk 1 from A to C. A: B: C: 3 2 1

    Perl is environmentally friendly - it saves trees
      First of all, that's a great code to explain visually and I thank you.
      But my question is actually in syntax of the perl. Or perhaps I should say I can't read this program properly
      I was debugging the program since I coudln't follow how they are coming up with results

      ./perl.hanoi1 HELLLLLOOOOOOOOOOOOO Move disk #1 from A to C. Move disk #2 from A to B.
      ##### I think I can follow up to here and understand why $n is 2
      HELLLLLOOOOOOOOOOOOO Move disk #1 from C to B. Move disk #3 from A to C.
      ##### This is where it lost me.. don't see how $n became 3 ?
      HELLLLLOOOOOOOOOOOOO Move disk #1 from B to A. Move disk #2 from B to C. HELLLLLOOOOOOOOOOOOO Move disk #1 from A to C.

        I suspect you are having trouble coming to grips with recursion. Recursion happens when a sub calls itself (either directly or indirectly). It is a powerful and elegant way of solving problems and works by "remembering" some state information on the subroutine call stack.

        You will notice that the hanoi sub calls itself in two places - that's where the recursion happens. Notice that each time hanoi calls itself it does so with the first parameter set to one less that the value on entry thus the recursion eventually stops with $n ==1.

        The following version that in essence dumps the call stack on each entry to hanoi and reports each exit from the sub may make it a little clearer (the entry numbers are the lines that hanoi was called from):

        #!/usr/bin/perl -w use strict; use warnings; my %piles = (A => [reverse 1..3], B => [], C => []); dumpPiles (); hanoi (scalar @{$piles{A}}, keys %piles); sub hanoi { my ($n, $start, $end, $extra) = @_; dumpStack (); if ($n == 1) { report ($start, $end); } else { hanoi($n-1, $start, $extra, $end); report ($start, $end); hanoi($n-1, $extra, $end, $start); } print "Exiting<\n"; } sub report { my ($start, $end) = @_; my $disk = pop @{$piles{$start}}; print "Moved disk $disk from $start to $end.\n"; push @{$piles{$end}}, $disk; dumpPiles (); } sub dumpPiles { for my $pile (sort keys %piles) { print "$pile: @{$piles{$pile}}\n"; } print "\n"; } sub dumpStack { my $index = 1; # Don't care where dumpStack was called so start at + 1 my @stack; while ((my @params) = caller $index++) { unshift @stack, $params[2]; } print "Entered> @stack\n"; }

        Prints:

        A: 3 2 1 B: C: Entered> 8 Entered> 8 18 Entered> 8 18 18 Moved disk 1 from A to C. A: 3 2 B: C: 1 Exiting< Moved disk 2 from A to B. A: 3 B: 2 C: 1 Entered> 8 18 20 Moved disk 1 from C to B. A: 3 B: 2 1 C: Exiting< Exiting< Moved disk 3 from A to C. A: B: 2 1 C: 3 Entered> 8 20 Entered> 8 20 18 Moved disk 1 from B to A. A: 1 B: 2 C: 3 Exiting< Moved disk 2 from B to C. A: 1 B: C: 3 2 Entered> 8 20 20 Moved disk 1 from A to C. A: B: C: 3 2 1 Exiting< Exiting< Exiting<

        Perl is environmentally friendly - it saves trees
        First all, apologies for ruining some nice code. I have added a print statement and 4 comment points (A .. D).
        #!/usr/bin/perl -w use strict; use warnings; my %piles = (A => [reverse 1..3], B => [], C => []); dumpPiles (); hanoi (scalar @{$piles{A}}, keys %piles); #A sub hanoi { my ($n, $start, $end, $extra, $recursion) = @_; print "Hanoi: Disk $n\n"; if ($n == 1) { #B report ($start, $end, $recursion); } else { hanoi($n-1, $start, $extra, $end); #C report ($start, $end, $recursion); hanoi($n-1, $extra, $end, $start); #D } } sub report { my ($start, $end) = @_; my $disk = pop @{$piles{$start}}; print "Moved disk $disk from $start to $end.\n"; push @{$piles{$end}}, $disk; dumpPiles (); } sub dumpPiles { for my $pile (sort keys %piles) { print "$pile: @{$piles{$pile}}\n"; } }

        The first hanoi call happens at point A, where the first argument (which disk to move) is equal the number of discs on pile A; namely '3'. We then move into the hanoi iterative method where the logical statement at B is false and we move to point C.

        At point C we call hanoi again (note we have not called report yet, but the first argument has been decremented to '2'. This means we arrive at point B for the second time and the logical statement is still false.

        We arrive at point C again, calling hanoi on disk number 1. Now the statement at B is true and the iterations begin to unravel.

        Perhaps, together with the additional print statement in the code, this will help to explain things?

        -=( Graq )=-

        Its because you're not really following :)
        #!/usr/bin/perl -w use strict; sub hanoi { warn "invoked @_"; my ($n, $start, $end, $extra) = @_; if ($n == 1) { warn "Move disk #1 from $start to $end."; } else { hanoi($n-1, $start, $extra, $end); warn "Move disk #$n from $start to $end."; hanoi($n-1, $extra, $end, $start); } } hanoi(3, 'A', 'C', 'B'); __END__ invoked 3 A C B at hanoisub.pl line 5. invoked 2 A B C at hanoisub.pl line 5. invoked 1 A C B at hanoisub.pl line 5. Move disk #1 from A to C. at hanoisub.pl line 8. Move disk #2 from A to B. at hanoisub.pl line 11. invoked 1 C B A at hanoisub.pl line 5. Move disk #1 from C to B. at hanoisub.pl line 8. Move disk #3 from A to C. at hanoisub.pl line 11. invoked 2 B C A at hanoisub.pl line 5. invoked 1 B A C at hanoisub.pl line 5. Move disk #1 from B to A. at hanoisub.pl line 8. Move disk #2 from B to C. at hanoisub.pl line 11. invoked 1 A C B at hanoisub.pl line 5. Move disk #1 from A to C. at hanoisub.pl line 8.
        get it now?
Re: cannot follow hanoi subroutine
by bart (Canon) on Nov 05, 2007 at 13:52 UTC
    It's a clear example, to me at least, on how showing the lengthy debugger output of the debugger does not help you understand a program.

    It just appears to show virtually the same action over and over again. Doesn't it?

    It's much better to try to explain an algorithm in a few simple lines. Now the idea is to move the largest disk from the start position to the end position. For that, you have to first move the smaller stack of disks on top of it (1 disk less), as a Tower of Hanoi, to the help (extra) position; and afterwards, in the same way, move it back on top of the larger disk, now in the end position. So to move a 4 disk Tower of Hanoi from A to B, you have to move a 3 disk ToH from A to C, move the bottom disk from A to B, and move the 3 disk ToH from C to B, on top of the big disk.

    (I happen to have explained how to solve a (physical) Tower Of Hanoi puzzle to my 7 year old son, only last week. Now that's a coincidence. The way I did it is start with 1 disk, next with 2, then 3; and every time he solved it, add one more disk to the puzzle.)

Re: cannot follow hanoi subroutine
by Dominus (Parson) on Nov 05, 2007 at 18:27 UTC
    That code seems to come from chapter 1 of the book Higher-Order Perl. In the book, it's accompanied by a detailed explanation, and a simpler example.

    I hope it wouldn't be out of line to suggest that you might understand the code better if you had the book.

      IMHO not out of line at all. Chapter 1 alone is worth the price of the book.
Re: cannot follow hanoi subroutine
by tilly (Archbishop) on Nov 05, 2007 at 23:24 UTC
    I've always found it useful to use indentation to indicate program calling depth. While it is very simple, that makes it easy to keep straight how many call frames are open at any point, and what they are. (All the statements from a particular call to the function should line up nicely.)
    #!/usr/bin/perl -w use strict; my $recursion = 0; sub hanoi { my ($n, $start, $end, $extra) = @_; $recursion++; my $indent = " " x $recursion; print $indent, "Entering hanoi($n, $start, $end, $extra)\n"; if ($n == 1) { print $indent, "Move disk #1 from $start to $end.\n"; } else { hanoi($n-1, $start, $extra, $end); print $indent, "Move disk #$n from $start to $end.\n"; hanoi($n-1, $extra, $end, $start); } print $indent, "Leaving hanoi($n, $start, $end, $extra)\n"; $recursion--; } hanoi(3, 'A', 'C', 'B'); __END__ Entering hanoi(3, A, C, B) Entering hanoi(2, A, B, C) Entering hanoi(1, A, C, B) Move disk #1 from A to C. Leaving hanoi(1, A, C, B) Move disk #2 from A to B. Entering hanoi(1, C, B, A) Move disk #1 from C to B. Leaving hanoi(1, C, B, A) Leaving hanoi(2, A, B, C) Move disk #3 from A to C. Entering hanoi(2, B, C, A) Entering hanoi(1, B, A, C) Move disk #1 from B to A. Leaving hanoi(1, B, A, C) Move disk #2 from B to C. Entering hanoi(1, A, C, B) Move disk #1 from A to C. Leaving hanoi(1, A, C, B) Leaving hanoi(2, B, C, A) Leaving hanoi(3, A, C, B)
    As the saying goes, to understand recursion you must first understand recursion. But hopefully this simple output will help you get that "ah hah!" moment where it starts to make sense.
      Huge thank you to everyone as I finally got it..

      It took re-reading everyone's post and trying combination of different things.. but I finally got it. Thank you so much!!!!
      Long time ago, I took a pascal course and there was a tracing program where I can actually step through the program and I personally think perl's debugging mechanism is little bit behind.(but then what do i know)

      I ran the debug on this program but I was not able to follow through.. now that i am running with extra print and indentation, I can clearly see

      btw, Mark, when is book "Perl Program Repair Shop and Red Flags" coming out? I am reading the "higher learning" (but bit too advance for me at this stage) and I feel that beginners like me can benefit big time by reading the completed book of reapir shop
      1 #!/usr/bin/perl -w 2 use strict; 3 4 my $recursion = 0; 5 my $count; 6 7 sub hanoi { 8 warn "invoked @_"; 9 my ($n, $start, $end, $extra) = @_; 10 $recursion++; 11 my $indent = " " x $recursion; 12 13 print$indent, "Entering hanoi($n, $start, $end, $extra)\n"; 14 15 if ($n == 1) { 16 warn $indent, "----------Move disk #1 from $start to $e +nd.------------\n"; 17 $count++; 18 } else { 19 print"enter first hanoi\n"; 20 print"\$n is $n\n"; 21 hanoi($n-1, $start, $extra, $end); 22 print"AFTER first hanoi\n"; 23 print "\$n is $n\n"; 24 warn $indent, "----------$count Move disk #$n from $st +art to $end.\n"; 25 print " enter second hanoi\n"; 26 hanoi($n-1, $extra, $end, $start); 27 print " AFTER second hanoi\n"; 28 print " \$n is $n\n"; 29 } 30 print $indent, " __LEAVING hanoi($n, $start, $end, + $extra)\n"; 31 print " \$n is $n\n"; 32 $recursion--; 33 } 34 35 hanoi(3, 'A', 'C', 'B'); invoked 3 A C B at ././perl.hanoi_f line 8. Entering hanoi(3, A, C, B) enter first hanoi $n is 3 invoked 2 A B C at ././perl.hanoi_f line 8. Entering hanoi(2, A, B, C) enter first hanoi $n is 2 invoked 1 A C B at ././perl.hanoi_f line 8. Entering hanoi(1, A, C, B) ----------Move disk #1 from A to C.------------ __LEAVING hanoi(1, A, C, B) $n is 1 AFTER first hanoi $n is 2 ----------1 Move disk #2 from A to B. enter second hanoi invoked 1 C B A at ././perl.hanoi_f line 8. Entering hanoi(1, C, B, A) ----------Move disk #1 from C to B.------------ __LEAVING hanoi(1, C, B, A) $n is 1 AFTER second hanoi $n is 2 __LEAVING hanoi(2, A, B, C) $n is 2 AFTER first hanoi $n is 3 ----------2 Move disk #3 from A to C. enter second hanoi invoked 2 B C A at ././perl.hanoi_f line 8. Entering hanoi(2, B, C, A) enter first hanoi $n is 2 invoked 1 B A C at ././perl.hanoi_f line 8. Entering hanoi(1, B, A, C) ----------Move disk #1 from B to A.------------ __LEAVING hanoi(1, B, A, C) $n is 1 AFTER first hanoi $n is 2 ----------3 Move disk #2 from B to C. enter second hanoi invoked 1 A C B at ././perl.hanoi_f line 8. Entering hanoi(1, A, C, B) ----------Move disk #1 from A to C.------------ __LEAVING hanoi(1, A, C, B) $n is 1 AFTER second hanoi $n is 2 __LEAVING hanoi(2, B, C, A) $n is 2 AFTER second hanoi $n is 3 __LEAVING hanoi(3, A, C, B) $n is 3
        When you said "... there was a tracing program where I can actually step through the program and I personally think perl's debugging mechanism is little bit behind. ...."
        I wondered if you were aware that Perl has a trace command that you can turn on the trace flag, and then just continue the code and watch it work --- that might be easier to follow than "stepping" through the program.
        DB<1> t Trace = on DB<1> c
        Long time ago, I took a pascal course and there was a tracing program where I can actually step through the program and I personally think perl's debugging mechanism is little bit behind.
        While it's not state-of-the-art, Perl's debugger is useful either by itself or when used from another tool.

        The full version of Komodo IDE comes with Perl debugger integration, allowing you to visually set/clear breakpoints and to step through the code as with other IDEs.

        The Data Display Debugger also integrates with the Perl debugger in a way familiar to users of GDB, allowing you to trace the execution of your programs and to visualise the contents of your data-structures over time.

        Aside from "backward in time" debuggers which are starting to appear recently, the state-of-the-art is probably Visual Studio 2005's .NET debugger. Specifically the edit-and-continue and exception tracing facilities are fantastic. Hopefully Perl will one day attract such tools.

        -David

        btw, Mark, when is book "Perl Program Repair Shop and Red Flags" coming out?
        That is a good question. Thanks for asking.

        It was supposed to be out already, but about a year ago, the publisher fired my editor and did not appoint another one. I am not sure what is going on, and I have been busy enough with other stuff that I have not pursued it.

        So I don't know.

        Sorry.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://648942]
Approved by blokhead
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others sharing their wisdom with the Monastery: (4)
As of 2024-03-19 03:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found