I happened on a nice solution to detect errors in a circular list. I
immediately had to think of how many times this already happened to me in
computer-Go, so I thought I'd share it here.
Raise your hand if you have code like this:
int start = stone;
do
{
// Do something to stone ...
stone = next[stone];
}
while (stone!=start);
The next array acts like a circular list, so a chain of stones can be
conveniently traversed from any point in the chain.
Now put your hand down if you never had your program stuck in an infinite
loop because you made a silly mistake somewhere else, and the list is not a
perfect circle anymore but more like a 'P'. Anyone who put their hand down?
Then you're smarter than me. Or less sloppy at least.
If you're lucky enough to be running in a debugger, you can pause it and
observe it's stuck in this loop. Although occasionally it just happened to
be in that loop legitimately and you waste a few minutes stepping trough
it. Now if you make a small modification:
int start = stone;
int runner = stone;
do
{
// Do something to stone ...
stone = next[stone];
assert(stone==xy || stone != (runner = next[next
[runner]]));
}
while (stone!=start);
it will throw an assertion error as soon as the list has a P shape. Of
course it still doesn't tell you where the error is caused, but at least it
doesn't cause an infinite loop anymore. To detect where the error occurs,
you can insert an "assert(isListConsistent(stone))" statement anywhere you
modify the next array, where the inconsistent function does the same as
above:
boolean isListConsistent(int start)
{
int current = start;
int runner = start;
do
{
current = next[current];
if (current!=start && current == (runner = next[next[runner]]))
return false;
}
while (current!=start);
return true;
}
Generally I find it fairly easy to track down these type of bugs. But still
the trick above would have saved me quite some time in the past. So I hope
it's of any use to anyone here.
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
