Topic: Computers When code re-use is bad

(link)

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

back to main

<-
 Topic:    
->

Powered by Personal Weblog.

March 2024
Sun Mon Tue Wed Thu Fri Sat
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
Feb   Apr

[RSS]

 


 


Dave Holland <dave@biff.org.uk>
$Id: index.php,v 1.75 2010-07-09 22:15:04 dave Exp $