5:25pm, Thursday 12 February 2004
I recently got hold of a copy of "Maze" by Christopher Manson and I wanted to solve the maze.
So in the spirit of laziness and doing as little as possible, I reached for Perl's Graph::Directed module and asked it for the shortest path. 1.5GB of RAM and some time later, it still hadn't found the solution! So I put together my own quick deepest-first path finder, which found the solution in less then a second. Bah.
The solution, by the way, is:
inwards route: 1 26 30 42 4 29 17 45
outwards route: 45 23 8 12 39 4 15 37 20 1
Obligatory pretty map of the maze (produced with neato):
Quick and dirty maze solver:
#!/usr/bin/perl if($#ARGV!=1) { die "usage: $0 start end\n"; } $start=shift; $end=shift; while(<>) { chomp; @a=split(/ /,$_); $b=shift(@a); $exits{$b}=[ @a ]; $visited{$b}=0; } $best=999; @route=(); &try_from($start); if($best==999) { print "no route found\n"; } else { print "best route: ",join(" ",@bestroute),"\n"; print "length=",$#bestroute," steps\n"; } exit(0); sub try_from { my $where=shift; $visited{$where}=1; my $i; push @route,$where; if($where==$end) { if($#route<$best) { print "found a route: ",join(" ",@route),"\n"; print "length=",$#route," steps\n"; $best=$#route; @bestroute=@route; } } foreach $i (@{$exits{$where}}) { next if ($visited{$i}); &try_from($i); } pop @route; $visited{$where}=0; }