Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

How to debug a long while loop

by nbezzala (Scribe)
on May 17, 2007 at 11:29 UTC ( #615969=perlquestion: print w/ replies, xml ) Need Help??
nbezzala has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks,

I am trying to write a program to solve a puzzle I came across.

There is one horse on a chessboard, and it can move according to the rules of chess. It needs to cover all the 64 squares of the board in 63 moves. So, it can not go back to a square which it has already been in.

I am attaching what I have so far, and it works for the first 42 moves, but it fails for the 43rd move.

Can someone please tell me what is the best way to debug such a program?

Also, is this the kind of solution you would have thought of or is there a better solution?
Should I rather have created objects and used them?

Thanks,
Nitish

#! /usr/bin/perl use strict; use warnings; use Data::Dumper; my $puzzle_board = create_board(); solve ($puzzle_board); print_board ($puzzle_board); sub solve { my $board = shift @_; my $move = 1; my ($x, $y) = (0, 1); # Change this number to solve more or less of the puzzle while ( $move < 44 ) { my ($newx, $newy) = calculate_move($board, $x, $y); print "$move: $x,$y->$newx,$newy\t"; if ( verify_move($board, $newx, $newy) == 1 ) { forward($board, $x, $y, $newx, $newy); } elsif ( $board->[$x][$y]{trial} < 7 ) { $board->[$x][$y]{trial}++; next; } else { back($board, $x, $y, $newx, $newy); $x = $board->[$newx][$newy]{oldx}; $y = $board->[$newx][$newy]{oldy}; $move--; next; } ($x, $y) = ($newx, $newy); $move++; } } sub forward { my ($board, $x, $y, $newx, $newy) = @_; $board->[$newx][$newy]->{visited} = $board->[$x][$y]->{visited} + + 1; $board->[$newx][$newy]->{oldx} = $x; $board->[$newx][$newy]->{oldy} = $y; } sub back { my ($board, $x, $y, $newx, $newy) = @_; $board->[$newx][$newy]{trial} = 0; $board->[$newx][$newy]{visited} = 0; } # Assumes that it is passed valid x and y values in the board. sub calculate_move { my ($board, $x, $y) = @_; my ($newx, $newy) = 0; if ($board->[$x][$y]{trial} == 0) { $newx = $x + 1; $newy = $y + 2; } if ($board->[$x][$y]{trial} == 1) { $newx = $x - 1; $newy = $y + 2; } if ($board->[$x][$y]{trial} == 2) { $newx = $x + 1; $newy = $y - 2; } if ($board->[$x][$y]{trial} == 3) { $newx = $x - 1; $newy = $y - 2; } if ($board->[$x][$y]{trial} == 4) { $newx = $x + 2; $newy = $y + 1; } if ($board->[$x][$y]{trial} == 5) { $newx = $x - 2; $newy = $y + 1; } if ($board->[$x][$y]{trial} == 6) { $newx = $x + 2; $newy = $y - 1; } if ($board->[$x][$y]{trial} == 7) { $newx = $x - 2; $newy = $y - 1; } return ($newx, $newy); } sub verify_move { my ($board, $x, $y) = @_; if ($x > 7 || $x < 0 || $y > 7 || $y < 0) { return 0; } if ($board->[$x][$y]{visited} > 0) { return 0; } return 1; } sub create_board { my @board; my ($i, $j); for ( $i = 0; $i < 8; $i++ ) { for ( $j = 0; $j < 8; $j++ ) { $board[$i][$j] = { x => $i, y => $j, visited => 0, trial => 0, oldx => 0, oldy => 0 } } } $board[0][1] = { x => 0, y => 1, visited => 1, trial => 0 }; return \@board; } sub print_board { my $board_ref = shift @_; my ($i, $j); print Dumper $board_ref; print "\nThe Chess Board\n"; for ($i = 7; $i >= 0; $i--) { for ($j = 0; $j < 8; $j++) { printf ("%02d ", $board_ref->[$i][$j]{visited} ); } print "\n\n"; } }

Comment on How to debug a long while loop
Download Code
Re: How to debug a long while loop
by BrowserUk (Pope) on May 17, 2007 at 12:01 UTC

    On my system, your (unmodified) code happily completes up to step 61--which is intriguing. It fails attempting to complete step 62. When it fails, it produces a bunch of "Uninitialised value errors":

    c:\test>615969 62 57: Use of uninitialized value in array element at c:\test\615969.pl l +ine 66. Use of uninitialized value in array element at c:\test\615969.pl line +66. Use of uninitialized value in array element at c:\test\615969.pl line +70. Use of uninitialized value in array element at c:\test\615969.pl line +70. Use of uninitialized value in array element at c:\test\615969.pl line +74. Use of uninitialized value in array element at c:\test\615969.pl line +74. Use of uninitialized value in array element at c:\test\615969.pl line +78. Use of uninitialized value in array element at c:\test\615969.pl line +78. Use of uninitialized value in array element at c:\test\615969.pl line +82. Use of uninitialized value in array element at c:\test\615969.pl line +82. Use of uninitialized value in array element at c:\test\615969.pl line +86. Use of uninitialized value in array element at c:\test\615969.pl line +86. Use of uninitialized value in array element at c:\test\615969.pl line +90. Use of uninitialized value in array element at c:\test\615969.pl line +90. Use of uninitialized value in array element at c:\test\615969.pl line +94. Use of uninitialized value in array element at c:\test\615969.pl line +94. Use of uninitialized value in subtraction (-) at c:\test\615969.pl lin +e 95. Use of uninitialized value in subtraction (-) at c:\test\615969.pl lin +e 96. Use of uninitialized value in concatenation (.) or string at c:\test\6 +15969.pl line 23. Use of uninitialized value in concatenation (.) or string at c:\test\6 +15969.pl line 23. Use of uninitialized value in array element at c:\test\615969.pl line +25. Use of uninitialized value in array element at c:\test\615969.pl line +25. 60: 0,0->2,1

    Note: For the above run I made two changes.

    1. I made the step counter a command line argument:
      my $steps = shift( @ARGV ) || 64; my $puzzle_board = create_board(); solve ($puzzle_board); print_board ($puzzle_board); ... # Change this number to solve more or less of the puzzle while ( $move < $steps ) {
    2. I changed the trace statement so that it overwrites on the same line:
      my ($newx, $newy) = calculate_move($board, $x, $y); printf "\r$move: $x,$y->$newx,$newy\t";

    The errors seem to indicate that something goes wrong during backtracking? Sorry I don't have any better explanation than that so far.

    The really mysterious things is why would it get further on my machine than yours? It consumes very little memory so that isn't the problem. Maybe Perl version differences?

    I'm using

    c:\test>perl -v This is perl, v5.8.6 built for MSWin32-x86-multi-thread (with 3 registered patches, see perl -V for more detail) Copyright 1987-2004, Larry Wall Binary build 811 provided by ActiveState Corp. http://www.ActiveState. +com ActiveState is a division of Sophos. Built Dec 13 2004 09:52:01

    Maybe if you get a few other reports they might correlate to a clue as to what is happening to make the boundary of error move.

    HTH


    Update:

    Added the following trace into your back() sub:

    sub back { print "\n*** BACK ***\n"; ...

    (I also disabled the Dumper output for conciseness) and when I run 61 steps I get the following output:

    The interesting thing is that the first time it backtracks is at step 43, the very place where it is failing for you. I'd suggest you take a close look at the logic there and see if you can spot anything amiss.


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re: How to debug a long while loop
by roboticus (Canon) on May 17, 2007 at 13:09 UTC
    nbezalla:

    I don't want to solve a homework problem for you, especially as you've made such a great start at it. Here's a hint that may help you out:

    Unless you're specifically avoiding it, recursion would be your best bet here. You're doing a lot of work in your code that recursion would "automatically" take care of for you. You're making a complex data structure (board) to track a handful of state variables that you would get "free" using recursion.

    For example, your board array is rather complicated. You could use local variables to store most of your state information for each move. Something like:

    sub solve { my $move = shift; ... other code ... solve($move+1,...); }
    Here, rather than putting the $move variable into your board structure, you're letting perl keep track of them for you on the stack. As you call solve, you get a new copy of $move, and when you return, you get the previous value back.

    Using local variables and recursion, you should be able to use an 8x8 array of integers to track which squares have been used, the rest being local variables.

    If you need another hint or two, let me know.!

    (Note: Just as an example of how using recursion can simplify things a bit, I cobbled together a quickie solution that's a little less than half the size of yours.)

    ...roboticus

      nbezalla:

      I recalled another amusing chess puzzle--specifically the "queens problem". It's another one that's easily solved with recursion. It might be too much of a hint, so I've put spoiler tags on it (below) so you don't see the solution to it if you don't want to. Anyway, the queens problem (on the offhand chance that you're unfamiliar with it) is basically to place eight queens on a chessboard such that none can attack another.

      My solution is:

      ...roboticus

Re: How to debug a long while loop
by roboticus (Canon) on May 17, 2007 at 14:36 UTC
    nbezalla:

    Okay ... now that I've answered your second question, I guess I should address the first one.

    Generally, when I debug a long-running while loop, I'll use one (or more) of the following techniques:

  • If each iteration is relatively quick and simple, I'll first use the perl debugger to step through the first few iterations to get a feel for things.
  • If there are plenty of alternate execution paths, I'll set a breakpoint in *all* of them, then start the program. As I reach each new breakpoint, I'll step through to the end of the loop, looking for something odd. When I hit the end of the loop, if I found nothing interesting in that path, I'll remove the breakpoint that I tripped and continue execution. After a while, you'll usually reach the point where the fault occurs relatively quickly.
  • Sometimes, I'll just pepper the loop with print statements showing the values of variables I'm concerned about, to see what's happening.
  • If the fault seems to occur with the same data each time, then I'll use the debugger and set the variables up to cause the fault immediately, then step through the code and see where my bug is.
  • I hope this is useful...

    ...roboticus

Re: How to debug a long while loop
by liverpole (Monsignor) on May 17, 2007 at 19:32 UTC

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (13)
As of 2014-09-17 12:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (74 votes), past polls