Commits

Anonymous committed 35ffdf1

Moved the trunk to its correct place under src.

Comments (0)

Files changed (24)

+Relax, this is not GPL software, but rather it is distributed under the
+public domain. It means it can be linked against anything, converted to
+any different license, freely used and distributed, and anything else
+without any restrictions whatsoever. No Strings Attached!<tm>
+
+The software comes "as is" and has no warranty of any kind. The authors
+assume no responsibility for the consequences of any use of this software.
+The following disclaimer (taken from X11 License, which is very
+similar to a public domain software) applies to this software:
+
+<<<
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
+OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
+IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY 
+CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 
+TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 
+SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+>>>
+
+Well, enjoy!
+
+        Shlomi Fish
+At the command-line, type:
+
+perl Makefile.PL
+make
+
+To prepare the package for installation and then:
+
+make install
+
+to install it.
+
+COPYING
+INSTALL
+MANIFEST
+Makefile.PL
+lm-solve.spec
+lm-solve.spec.in
+lib/Games/LMSolve/Alice.pm
+lib/Games/LMSolve/Base.pm
+lib/Games/LMSolve/Input.pm
+lib/Games/LMSolve/Minotaur.pm
+lib/Games/LMSolve/Numbers.pm
+lib/Games/LMSolve/Tilt/Base.pm
+lib/Games/LMSolve/Tilt/Multi.pm
+lib/Games/LMSolve/Tilt/RedBlue.pm
+lib/Games/LMSolve/Tilt/Single.pm
+lib/Games/LMSolve/Plank/Base.pm
+lib/Games/LMSolve/Plank/Hex.pm
+lm-solve
+README
+TODO
+prepare_package.sh
+get-version.pl
+scripts/gen_use_test.pl
+t/00use.t
+META.yml                                Module meta-data (added by MakeMaker)
+use ExtUtils::MakeMaker;
+
+WriteMakefile(
+    'NAME' => 'Games::LMSolve',
+    'DISTNAME' => 'Games-LMSolve',
+    'EXE_FILES' => ["lm-solve"],
+    'VERSION_FROM' => 'lib/Games/LMSolve/Base.pm',
+    );
+
+use lib './lib';
+require Games::LMSolve::Base;
+
+my $version = $Games::LMSolve::Base::VERSION;
+print "Generating the RPM SPEC file\n";
+open I, "<lm-solve.spec.in";
+open O, ">lm-solve.spec";
+while (<I>)
+{
+    s!\[\[VERSION\]\]!$version!g;
+    print O $_;
+}
+close(O);
+close(I);
+
+This is LM-Solve, a command-line program to automaticalluy solve
+some types of the Logic Mazes presented on the Logic Mazes site
+(http://www.logicmazes.com/).
+
+Read the file INSTALL to learn how to install the program, and then
+you can invoke the program by using the "lm-solve" executable.
+(type "man lm-solve" to get more help).
+
+The LM-Solve homepage is:
+
+http://vipe.technion.ac.il/~shlomif/lm-solve/
+
+LM-Solve was written by Shlomi Fish (shlomif@vipe.technion.ac.il).
+
+Have fun!
+
+* Put on CPAN
+
+* Implement other scans such as A*, etc.
+
+* Support the hex plank swamps
+
+* Implement support for No U-Turn and Changing Rules Number Mazes.
+
+* Document the moves that are being outputted to the screen.
+
+* Modularize the code:
+    - An API
+
+
+#!/usr/bin/perl -w
+
+use strict;
+
+use lib './lib';
+
+require Games::LMSolve::Base;
+
+print $Games::LMSolve::Base::VERSION;
+

lib/Games/LMSolve/Alice.pm

+package Games::LMSolve::Alice;
+
+use strict;
+
+use Games::LMSolve::Base qw(%cell_dirs);
+
+use vars qw(@ISA);
+
+@ISA=qw(Games::LMSolve::Base);
+
+
+my %cell_flags =
+    (
+        'ADD' => 1,
+        'SUB' => -1,
+        'GOAL' => 0,
+        'START' => 1,
+        'BLANK' => 0,
+    );
+
+sub input_board
+{
+    my $self = shift;
+
+    my $filename = shift;
+
+    my $spec = 
+    {
+        'dims' => {'type' => "xy(integer)", 'required' => 1},
+        'layout' => {'type' => "layout", 'required' => 1},
+    };
+
+    my $input_obj = Games::LMSolve::Input->new();
+    my $input_fields = $input_obj->input_board($filename, $spec);
+
+    my ($width, $height) = @{$input_fields->{'dims'}->{'value'}}{'x','y'};
+
+    my (@board);
+    
+    my $line;
+    my $line_number=0;
+    my $lines_ref = $input_fields->{'layout'}->{'value'};
+
+    my $read_line = sub {
+        if (scalar(@$lines_ref) == $line_number)
+        {
+            return 0;
+        }
+        $line = $lines_ref->[$line_number];
+        $line_number++;
+        return 1;
+    };
+
+    my $gen_exception = sub {
+        my $text = shift;
+        die "$text on $filename at line " . 
+            ($input_fields->{'layout'}->{'line_num'} + $line_number + 1) . 
+            "!\n";
+    };
+
+
+    my ($y,$x);
+    my ($start_x,$start_y);
+
+    $y = 0;
+    $x = 0;
+
+    INPUT_LOOP: while ($read_line->())
+    {
+        while (length($line) > 0)
+        {
+            $line =~ s/^\s+//;
+            if ($line =~ /\S/)
+            {                
+                if ($line =~ /^\[([^\]]*)\]/)
+                {
+                    my $flags_string = uc($1);
+                    my @flags = (split(/,/, $flags_string));
+                    my @dirs = (grep { exists($cell_dirs{$_}) } @flags);
+                    my @flag_flags = (grep { exists($cell_flags{$_}) } @flags);
+                    my @unknown_flags = 
+                        (grep 
+                            { 
+                                (!exists($cell_dirs{$_})) && 
+                                (!exists($cell_flags{$_}))
+                            }
+                            @flags
+                        );
+                    if (scalar(@unknown_flags))
+                    {
+                        $gen_exception->("Unknown Flags on Cell (" . join(",", @unknown_flags) . ")");
+                    }
+                    $board[$y][$x] =
+                        {
+                            'dirs' => { map { $_ => $cell_dirs{$_} } @dirs },
+                            'flags' => { map { $_ => $cell_flags{$_} } @flag_flags },
+                        };
+
+                    if (exists($board[$y][$x]->{'flags'}->{'START'}))
+                    {
+                        if (defined($start_x))
+                        {
+                            $gen_exception->("Two starts were defined!\n");
+                        }
+                        $start_x = $x;
+                        $start_y = $y;
+                    }
+                    $x++;                    
+                    if ($x == $width)
+                    {
+                        $x = 0;
+                        $y++;
+                        if ($y == $height)
+                        {
+                            last INPUT_LOOP;
+                        }
+                    }
+                    $line =~ s/^.*?\]//;
+                }
+                elsif ($line =~ /^#/)
+                {
+                    # Do nothing - it's a comment
+                    $line = "";
+                }
+                else
+                {
+                    $gen_exception->("Junk at Line");
+                }
+            }
+        }
+    }
+
+    if ($y != $height)
+    {
+        $gen_exception->("Input Terminated Prematurely after reading y=$y x=$x");
+    }
+
+    if (! defined($start_x))
+    {
+        $gen_exception->("The Starting Position was not defined anywhere");
+    }
+
+    $self->{'height'} = $height;
+    $self->{'width'} = $width;
+    $self->{'board'} = \@board;
+
+    return [ $start_x, $start_y, 1 ];
+}
+
+# A function that accepts the expanded state (as an array ref)
+# and returns an atom that represents it.
+sub pack_state
+{
+    my $self = shift;
+    my $state_vector = shift;
+    return pack("ccc", @{$state_vector});
+}
+
+# A function that accepts an atom that represents a state 
+# and returns an array ref that represents it.
+sub unpack_state
+{
+    my $self = shift;
+    my $state = shift;
+    return [ unpack("ccc", $state) ];
+}
+
+# Accept an atom that represents a state and output a 
+# user-readable string that describes it.
+sub display_state
+{
+    my $self = shift;
+    my $state = shift;
+    my ($x, $y, $d) = @{ $self->unpack_state($state) };
+    return sprintf("X = %i ; Y = %i ; d = %i", $x+1, $y+1, $d);
+}
+
+# This function checks if a state it receives as an argument is a
+# dead-end one.
+sub check_if_unsolveable
+{
+    my $self = shift;
+    my $coords = shift;
+    return ($coords->[2] == 0);    
+}
+
+sub check_if_final_state
+{
+    my $self = shift;
+
+    my $coords = shift;
+    return exists($self->{'board'}->[$coords->[1]][$coords->[0]]->{'flags'}->{'GOAL'})
+}
+
+# This function enumerates the moves accessible to the state.
+# If it returns a move, it still does not mean that it is a valid 
+# one. I.e: it is possible that it is illegal to perform it.
+sub enumerate_moves
+{
+    my $self = shift;
+
+    my $coords = shift;
+    return keys(%{$self->{'board'}->[$coords->[1]][$coords->[0]]->{'dirs'}});
+}
+
+# This function accepts a state and a move. It tries to perform the
+# move on the state. If it is succesful, it returns the new state.
+#
+# Else, it returns undef to indicate that the move is not possible.
+sub perform_move
+{
+    my $self = shift;
+
+    my $coords = shift;
+    my $m = shift;
+
+    my $offsets = [ map { $_  * $coords->[2] } @{$cell_dirs{$m}} ];
+    my @new_coords = @$coords;
+    $new_coords[0] += $offsets->[0];
+    $new_coords[1] += $offsets->[1];
+
+    my $new_cell = $self->{'board'}->[$new_coords[1]][$new_coords[0]]->{'flags'};
+    
+    # Check if we are out of the bounds of the board.
+    if (($new_coords[0] < 0) || ($new_coords[0] >= $self->{'width'}) ||
+        ($new_coords[1] < 0) || ($new_coords[1] >= $self->{'height'}) ||
+        exists($new_cell->{'BLANK'})
+       )
+    {
+        return undef;
+    }
+    
+    if (exists($new_cell->{'ADD'}))
+    {
+        $new_coords[2]++;
+    }
+    elsif (exists($new_cell->{'SUB'}))
+    {
+        $new_coords[2]--;
+    }
+
+    return [ @new_coords ];
+}
+
+1;
+

lib/Games/LMSolve/Base.pm

+package Games::LMSolve::Base;
+
+use strict;
+
+use Getopt::Long;
+
+use vars qw($VERSION);
+
+$VERSION = '0.7.8';
+
+use Exporter;
+
+use vars qw(@ISA @EXPORT_OK);
+
+@ISA=qw(Exporter);
+
+@EXPORT_OK=qw(%cell_dirs);
+
+no warnings qw(recursion);
+
+use vars qw(%cell_dirs);
+
+%cell_dirs = 
+    (
+        'N' => [0,-1],
+        'NW' => [-1,-1],
+        'NE' => [1,-1],
+        'S' => [0,1],
+        'SE' => [1,1],
+        'SW' => [-1,1],
+        'E' => [1,0],
+        'W' => [-1,0],
+    );
+
+sub new
+{
+    my $class = shift;
+
+    my $self = {};
+
+    bless $self, $class;
+
+    $self->initialize(@_);
+
+    return $self;    
+}
+
+sub initialize
+{
+    my $self = shift;
+
+    $self->{'state_collection'} = { };
+    $self->{'cmd_line'} = { };
+
+    $self->{'num_iters'} = 0;
+
+    return 0;
+}
+
+sub die_on_abstract_function
+{
+    my ($package, $filename, $line, $subroutine, $hasargs,
+        $wantarray, $evaltext, $is_require, $hints, $bitmask) = caller(1);
+    die ("The abstract function $subroutine() was " . 
+        "called, while it needs to be overrided by the derived class.\n");
+}
+
+sub input_board
+{
+    return &die_on_abstract_function();
+}
+
+# A function that accepts the expanded state (as an array ref)
+# and returns an atom that represents it.
+sub pack_state
+{
+    return &die_on_abstract_function();
+}
+
+# A function that accepts an atom that represents a state 
+# and returns an array ref that represents it.
+sub unpack_state
+{
+    return &die_on_abstract_function();
+}
+
+# Accept an atom that represents a state and output a 
+# user-readable string that describes it.
+sub display_state
+{
+    return &die_on_abstract_function();
+}
+
+# This function checks if a state it receives as an argument is a
+# dead-end one.
+sub check_if_unsolveable
+{
+    return &die_on_abstract_function();
+}
+
+sub check_if_final_state
+{
+    return &die_on_abstract_function();
+}
+
+# This function enumerates the moves accessible to the state.
+# If it returns a move, it still does not mean that this move is a valid 
+# one. I.e: it is possible that it is illegal to perform it.
+sub enumerate_moves
+{
+    return &die_on_abstract_function();
+}
+
+# This is a function that should be overrided in case
+# rendering the move into a string is non-trivial.
+sub render_move
+{
+    my $self = shift;
+
+    my $move = shift;
+
+    return $move;
+}
+
+# This function accepts a state and a move. It tries to perform the
+# move on the state. If it is succesful, it returns the new state.
+#
+# Else, it returns undef to indicate that the move is not possible.
+sub perform_move
+{
+    return &die_on_abstract_function();
+}
+
+sub set_run_time_states_display
+{
+    my $self = shift;
+    my $states_display = shift;
+
+    if (! $states_display)
+    {
+        $self->{'cmd_line'}->{'rt_states_display'} = undef;
+    }
+    else
+    {
+        $self->{'cmd_line'}->{'rt_states_display'} = 1;
+        $self->{'run_time_display_callback'} = $states_display;
+    }
+
+    return 0;
+}
+
+sub solve_brfs_or_dfs
+{
+    my $self = shift;
+    my $state_collection = $self->{'state_collection'};
+    my $initial_state = shift;
+    my $is_dfs = shift;
+    my %args = @_;
+    
+    my $run_time_display = $self->{'cmd_line'}->{'rt_states_display'};
+    my $rtd_callback = $self->{'run_time_display_callback'};
+    my $max_iters = $args{'max_iters'} || (-1);
+    my $not_check_iters = ($max_iters < 0);
+    
+    my (@queue, $state, $coords, $depth, @moves, $new_state);
+
+    push @queue, $initial_state;
+
+    my $num_iters = $self->{'num_iters'};
+    my @ret;
+
+    while (scalar(@queue) && 
+           (
+               $not_check_iters || 
+               ($max_iters > $num_iters)
+           )
+          )
+    {
+        if ($is_dfs)
+        {
+            $state = pop(@queue);
+        }
+        else
+        {
+            $state = shift(@queue);
+        }
+        $coords = $self->unpack_state($state);
+        $depth = $state_collection->{$state}->{'d'};
+
+        $num_iters++;
+
+        # Output the current state to the screen, assuming this option
+        # is set.
+        if ($run_time_display)
+        {
+            $rtd_callback->(
+                $self,
+                'depth' => $depth,
+                'state' => $coords,
+                'move' => $state_collection->{$state}->{'m'},
+                'num_iters' => $num_iters,
+            );
+            # print ((" " x $depth) . join(",", @$coords) . " M=" . $self->render_move($state_collection->{$state}->{'m'}) ."\n");
+        }
+        
+        if ($self->check_if_unsolveable($coords))
+        {
+            next;
+        }
+
+        if ($self->check_if_final_state($coords))
+        {
+            @ret = ("solved", $state);
+            goto Return;
+        }
+        
+        @moves = $self->enumerate_moves($coords);
+
+        foreach my $m (@moves)
+        {
+            my $new_coords = $self->perform_move($coords, $m);
+            # Check if this move leads nowhere and if so - skip to the next move.
+            if (!defined($new_coords))
+            {
+                next;
+            }
+            
+            $new_state = $self->pack_state($new_coords);
+            if (! exists($state_collection->{$new_state}))
+            {
+                $state_collection->{$new_state} = 
+                    {
+                        'p' => $state, 
+                        'm' => $m, 
+                        'd' => ($depth+1)
+                    };
+                push @queue, $new_state;
+            }
+        }
+    }
+
+    @ret = ("unsolved", undef);
+    
+    Return:
+
+    $self->{'num_iters'} = $num_iters;
+
+    return @ret;
+}
+
+sub run_length_encoding
+{
+    my @moves = @_;
+    my @ret = ();
+
+    my $prev_m = shift(@moves);
+    my $count = 1;
+    my $m;
+    while ($m = shift(@moves))
+    {
+        if ($m eq $prev_m)
+        {
+            $count++;            
+        }
+        else
+        {
+            push @ret, [ $prev_m, $count];
+            $prev_m = $m;
+            $count = 1;
+        }
+    }
+    push @ret, [$prev_m, $count];
+
+    return @ret;    
+}
+
+my %scan_functions =
+(
+    'dfs' => sub {
+        my $self = shift;
+        my $initial_state = shift;
+
+        return $self->solve_brfs_or_dfs($initial_state, 1, @_);
+    },
+    'brfs' => sub {
+        my $self = shift;
+        my $initial_state = shift;
+
+        return $self->solve_brfs_or_dfs($initial_state, 0, @_);
+    },
+);
+
+
+sub solve_state
+{
+    my $self = shift;
+    
+    my $initial_coords = shift;
+    
+    my $state = $self->pack_state($initial_coords);
+    $self->{'state_collection'}->{$state} = {'p' => undef, 'd' => 0};
+
+    return 
+        $scan_functions{$self->{'cmd_line'}->{'scan'}}->(
+            $self,
+            $state,
+            @_
+        );
+}
+
+sub solve_file
+{
+    my $self = shift;
+    
+    my $filename = shift;
+
+    my $initial_coords = $self->input_board($filename);
+
+    return $self->solve_state($initial_coords);
+}
+
+sub display_solution
+{
+    my $self = shift;
+
+    my @ret = @_;
+
+    my $state_collection = $self->{'state_collection'};
+
+    my $output_states = $self->{'cmd_line'}->{'output_states'};
+    my $to_rle = $self->{'cmd_line'}->{'to_rle'};
+
+    my $echo_state = 
+        sub {
+            my $state = shift;
+            return $output_states ? 
+                ($self->display_state($state) . ": Move = ") :
+                "";
+        };    
+
+    print $ret[0], "\n";
+
+    if ($ret[0] eq "solved")
+    {
+        my $key = $ret[1];
+        my $s = $state_collection->{$key};
+        my @moves = ();
+        my @states = ($key);
+
+        while ($s->{'p'})
+        {
+            push @moves, $s->{'m'};
+            $key = $s->{'p'};
+            $s = $state_collection->{$key};
+            push @states, $key;
+        }
+        @moves = reverse(@moves);
+        @states = reverse(@states);
+        if ($to_rle)
+        {
+            my @moves_rle = &run_length_encoding(@moves);
+            my ($m, $sum);
+
+            $sum = 0;
+            foreach $m (@moves_rle)
+            {            
+                print $echo_state->($states[$sum]) . $self->render_move($m->[0]) . " * " . $m->[1] . "\n";
+                $sum += $m->[1];
+            }
+        }
+        else
+        {
+            my ($a);
+            for($a=0;$a<scalar(@moves);$a++)
+            {
+                print $echo_state->($states[$a]) . $self->render_move($moves[$a]) . "\n";
+            }            
+        }
+        if ($output_states)
+        {
+            print $self->display_state($states[$a]), "\n";
+        }
+    }
+}
+
+sub _default_rtd_callback
+{
+    my $self = shift;
+
+    my %args = @_;
+    print ((" " x $args{depth}) . join(",", @{$args{state}}) . " M=" . $self->render_move($args{move}) ."\n");
+}
+
+sub main
+{
+    my $self = shift;
+
+    # This is a flag that specifies whether to present the moves in Run-Length
+    # Encoding.
+    my $to_rle = 1;
+    my $output_states = 0;
+    my $scan = "brfs";
+    my $run_time_states_display = 0;
+
+    #my $p = Getopt::Long::Parser->new();
+    if (! GetOptions('rle!' => \$to_rle, 
+        'output-states!' => \$output_states,
+        'method=s' => \$scan,
+        'rtd!' => \$run_time_states_display,
+        ))
+    {
+        die "Incorrect options passed!\n"
+    }
+
+    if (!exists($scan_functions{$scan}))
+    {
+        die "Unknown scan \"$scan\"!\n";
+    }
+
+    $self->{'cmd_line'}->{'to_rle'} = $to_rle;
+    $self->{'cmd_line'}->{'output_states'} = $output_states;
+    $self->{'cmd_line'}->{'scan'} = $scan;
+    $self->set_run_time_states_display($run_time_states_display && \&_default_rtd_callback);
+
+    my $filename = shift(@ARGV) || "board.txt";
+
+    my @ret = $self->solve_file($filename);
+
+    $self->display_solution(@ret);
+}
+
+1;
+

lib/Games/LMSolve/Input.pm

+package Games::LMSolve::Input::Scalar::FH;
+
+sub TIEHANDLE
+{
+    my $class = shift;
+    my $self = {};
+    my $buffer = shift;
+    $self->{'lines'} = [ reverse(my @a = ($buffer =~ /([^\n]*(?:\n|$))/sg)) ];
+    bless $self, $class;
+    return $self;
+}
+
+sub READLINE
+{
+    my $self = shift;
+    return pop(@{$self->{'lines'}});
+}
+
+sub EOF
+{
+    my $self = shift;
+    return (scalar(@{$self->{'lines'}}) == 0);
+}
+
+package Games::LMSolve::Input;
+
+use strict;
+
+use English;
+
+sub new
+{
+    my $class = shift;
+
+    my $self = {};
+
+    bless $self, $class;
+
+    $self->initialize(@_);
+
+    return $self;
+}
+
+sub initialize
+{
+    my $self = shift;
+
+    return 0;
+}
+
+sub input_board
+{
+    my $self = shift;
+
+    my $file_spec = shift;
+
+    my $spec = shift;
+
+    my $ret = {};
+
+    my $file_ref;
+
+    local (*I);
+
+    my $filename_str;
+
+    if (ref($file_spec) eq "")
+    {
+        my $filename = $file_spec;
+        open(I, "<$filename") ||
+            die "Failed to read \"$filename\" : $OS_ERROR";
+
+        $file_ref = \*I;
+        $filename_str = ($filename eq "-") ? 
+            "standard input" : 
+            "\"$filename\"";
+    }
+    elsif (ref($file_spec) eq "GLOB")
+    {
+        $file_ref = $file_spec;
+        $filename_str = "FILEHANDLE";
+    }
+    elsif (ref($file_spec) eq "SCALAR")
+    {
+        tie(*I, "Games::LMSolve::Input::Scalar::FH", $$file_spec);
+        $file_ref = \*I;
+        $filename_str = "BUFFER";
+    }
+    else
+    {
+        die "Unknown file specification passed to input_board!";
+    }
+    
+    # Now we have the filehandle *$file_ref opened.
+
+    my $line;
+    my $line_num = 0;
+
+    my $read_line = sub {
+        if (eof(*{$file_ref}))
+        {
+            return 0;
+        }
+        $line = readline(*{$file_ref});
+        $line_num++;
+        chomp($line);
+        return 1;
+    };
+
+    my $gen_exception = sub {
+        my $text = shift;
+        close(*{$file_ref});
+        die "$text on $filename_str at line $line_num!\n";
+    };
+
+    my $xy_pair = "\\(\\s*(\\d+)\\s*\\,\\s*(\\d+)\\s*\\)";
+
+    while ($read_line->())
+    {
+        # Skip if this is an empty line
+        if ($line =~ /^\s*$/)
+        {
+            next;
+        }
+        # Check if we have a "key =" construct
+        if ($line =~ /^\s*(\w+)\s*=/)
+        {
+            my $key = lc($1);
+            # Save the line number for safekeeping because a layout or
+            # other multi-line value can increase it.
+            my $key_line_num = $line_num;
+            
+            
+
+            if (! exists ($spec->{$key}))
+            {
+                $gen_exception->("Unknown key \"$key\"");
+            }
+            if (exists($ret->{$key}))
+            {
+                $gen_exception->("Key \"$key\" was already inputted!\n");
+            }
+            # Strip anything up to and including the equal sign
+            $line =~ s/^.*?=\s*//;
+            my $type = $spec->{$key}->{'type'};
+            my $value;
+            if ($type eq "integer")
+            {
+                if ($line =~ /^(\d+)\s*$/)
+                {
+                    $value = $1;
+                }
+                else
+                {
+                    $gen_exception->("Key \"$key\" expects an integer as a value");
+                }
+            }
+            elsif ($type eq "xy(integer)")
+            {
+                if ($line =~ /^\(\s*(\d+)\s*,\s*(\d+)\s*\)\s*$/)
+                {
+                    $value = { 'x' => $1, 'y' => $2 };
+                }
+                else
+                {
+                    $gen_exception->("Key \"$key\" expects an (x,y) integral pair as a value");
+                }
+            }
+            elsif ($type eq "array(xy(integer))")
+            {
+                
+                if ($line =~ /^\[\s*$xy_pair(\s*\,\s*$xy_pair)*\s*\]\s*$/)
+                {                    
+                    my @elements = ($line =~ m/$xy_pair/g);
+                    my @pairs;
+                    while (scalar(@elements))
+                    {
+                        my $x = shift(@elements);
+                        my $y = shift(@elements);
+                        push @pairs, { 'x' => $x, 'y' => $y };
+                    }
+                    $value = \@pairs;
+                }
+                else
+                {
+                    $gen_exception->("Key \"$key\" expects an array of integral (x,y) pairs as a value");
+                }
+            }
+            elsif ($type eq "array(start_end(xy(integer)))")
+            {
+                my $se_xy_pair = "\\(\\s*$xy_pair\\s*->\\s*$xy_pair\\s*\\)";
+                if ($line =~ /^\[\s*$se_xy_pair(\s*\,\s*$se_xy_pair)*\s*\]\s*$/)
+                {
+                    my @elements = ($line =~ m/$se_xy_pair/g);
+                    my @pairs;
+                    while (scalar(@elements))
+                    {
+                        my ($sx,$sy,$ex,$ey) = @elements[0 .. 3];
+                        @elements = @elements[4 .. $#elements];
+                        push @pairs, 
+                            { 
+                                'start' => { 'x'=>$sx , 'y'=>$sy }, 
+                                'end' => { 'x' => $ex, 'y' => $ey }
+                            };
+                    }
+                    $value = \@pairs;
+                }
+                else
+                {
+                    $gen_exception->("Key \"$key\" expects an array of integral (sx,sy) -> (ex,ey) start/end x,y pairs as a value");                    
+                }
+            }
+            elsif ($type eq "layout")
+            {
+                if ($line =~ /^<<\s*(\w+)\s*$/)
+                {
+                    my $terminator = $1;
+                    my @lines = ();
+                    my $eof = 1;
+                    while ($read_line->())
+                    {
+                        if ($line =~ /^\s*$terminator\s*$/)
+                        {
+                            $eof = 0;
+                            last;
+                        }
+                        push @lines, $line;
+                    }
+                    if ($eof)
+                    {
+                        $gen_exception->("End of file reached before the terminator (\"$terminator\") for key \"$key\" was found");
+                    }
+                    $value = \@lines;
+                }
+                else
+                {
+                    $gen_exception->("Key \"$key\" expects a layout specification (<<TERMINATOR_STRING)");
+                }
+            }
+            else
+            {
+                $gen_exception->("Unknown type \"$type\"!");
+            }
+
+            $ret->{$key} = { 'value' => $value, 'line_num' => $key_line_num };
+        }
+    }
+
+    close(*{$file_ref});
+
+    foreach my $key (keys(%$spec))
+    {
+        if ($spec->{$key}->{'required'})
+        {
+            if (!exists($ret->{$key}))
+            {
+                die "The required key \"$key\" was not specified on $filename_str!\n";
+            }
+        }
+    }
+    
+    return $ret;
+}
+
+sub input_horiz_vert_walls_layout
+{
+    my $self = shift;
+
+    my $width = shift;
+    my $height = shift;
+    my $lines_ptr = shift;
+
+    my (@vert_walls, @horiz_walls);
+    
+    my $line;
+    my $line_num = 0;
+    my $y;
+
+    my $get_next_line = sub {
+        my $ret = $lines_ptr->{'value'}->[$line_num];
+        $line_num++;
+
+        return $ret;
+    };
+
+    my $gen_exception = sub {
+        my $msg = shift;
+        die ($msg . " at line " . ($line_num+$lines_ptr->{'line_num'}+1));
+    };
+    
+
+    my $input_horiz_wall = sub {
+        $line = $get_next_line->();
+        if (length($line) != $width)
+        {
+            $gen_exception->("Incorrect number of blocks");
+        }
+        if ($line =~ /([^ _\-])/)
+        {
+            $gen_exception->("Incorrect character \'$1\'");
+        }
+        push @horiz_walls, [ (map { ($_ eq "_") || ($_ eq "-") } split(//, $line)) ];
+    };
+
+    my $input_vert_wall = sub {
+        $line = $get_next_line->();
+        if (length($line) != $width+1)
+        {
+            $gen_exception->("Incorrect number of blocks");
+        }
+        if ($line =~ /([^ |])/)
+        {
+            $gen_exception->("Incorrect character \'$1\'");
+        }
+        push @vert_walls, [ (map { $_ eq "|" } split(//, $line)) ];
+    };
+    
+
+
+    for($y=0;$y<$height;$y++)
+    {
+        $input_horiz_wall->();
+        $input_vert_wall->();
+    }
+    $input_horiz_wall->();    
+
+    return (\@horiz_walls, \@vert_walls);
+}
+
+1;
+
+

lib/Games/LMSolve/Minotaur.pm

+package Games::LMSolve::Minotaur;
+
+use strict;
+
+use Games::LMSolve::Base;
+
+use Games::LMSolve::Input;
+
+use vars qw(@ISA);
+
+@ISA=qw(Games::LMSolve::Base);
+
+sub input_board
+{
+    my $self = shift;
+    my $filename = shift;
+
+    my $spec = 
+    {
+        (map { $_ => { 'type' => "xy(integer)", 'required' => 1} } (qw(dims thes mino exit))),
+        'layout' => { 'type' => "layout", 'required' => 1},
+    };
+
+    my $input_obj = Games::LMSolve::Input->new();
+    my $input_fields = $input_obj->input_board($filename, $spec);
+    
+    my ($width, $height) = @{$input_fields->{'dims'}->{'value'}}{'x','y'};    
+    my ($thes_x, $thes_y) = @{$input_fields->{'thes'}->{'value'}}{'x','y'};
+    my ($mino_x, $mino_y) = @{$input_fields->{'mino'}->{'value'}}{'x','y'};
+    my ($exit_x, $exit_y) = @{$input_fields->{'exit'}->{'value'}}{'x','y'};
+
+    if (($thes_x >= $width) || ($thes_y >= $height))
+    {
+        die "Theseus is out of bounds of the board in file \"$filename\"!\n";
+    }
+
+    if (($mino_x >= $width) || ($mino_y >= $height))
+    {
+        die "The minotaur is out of bounds of the board in file \"$filename\"!\n";
+    }
+    
+    if (($exit_x >= $width) || ($exit_y >= $height))
+    {
+        die "The exit is out of bounds of the board in file \"$filename\"!\n";
+    }
+
+    my ($horiz_walls, $vert_walls) = 
+        $input_obj->input_horiz_vert_walls_layout($width, $height, $input_fields->{'layout'});
+
+    $self->{'width'} = $width;
+    $self->{'height'} = $height;
+    $self->{'exit_x'} = $exit_x;
+    $self->{'exit_y'} = $exit_y;
+    $self->{'horiz_walls'} = $horiz_walls;
+    $self->{'vert_walls'} = $vert_walls;
+
+    return [ $thes_x, $thes_y, $mino_x, $mino_y ];
+}
+
+sub mino_move
+{
+    my $self = shift;
+    my $horiz_walls = $self->{'horiz_walls'};
+    my $vert_walls = $self->{'vert_walls'};
+
+    my ($thes_x, $thes_y, $mino_x, $mino_y) = @_; 
+    for(my $t=0;$t<2;$t++)
+    {
+        if (($thes_x < $mino_x) && (! $vert_walls->[$mino_y][$mino_x]))
+        {
+            $mino_x--;
+        }
+        elsif (($thes_x > $mino_x) && (! $vert_walls->[$mino_y][$mino_x+1]))
+        {
+            $mino_x++;
+        }
+        elsif (($thes_y < $mino_y) && (! $horiz_walls->[$mino_y][$mino_x]))
+        {
+            $mino_y--;
+        }
+        elsif (($thes_y > $mino_y) && (! $horiz_walls->[$mino_y+1][$mino_x]))
+        {
+            $mino_y++;
+        }
+    }
+    return ($mino_x, $mino_y);
+}
+
+
+# A function that accepts the expanded state (as an array ref)
+# and returns an atom that represents it.
+sub pack_state
+{
+    my $self = shift;
+    my $state_vector = shift;
+    return pack("cccc", @{$state_vector});
+}
+
+# A function that accepts an atom that represents a state 
+# and returns an array ref that represents it.
+sub unpack_state
+{
+    my $self = shift;
+    my $state = shift;
+    return [ unpack("cccc", $state) ];
+}
+
+# Accept an atom that represents a state and output a 
+# user-readable string that describes it.
+sub display_state
+{
+    my $self = shift;
+    my $state = shift;
+    my ($x, $y, $mx,$my) = (map { $_ + 1} @{ $self->unpack_state($state) });
+    return sprintf("Thes=(%i,%i) Mino=(%i,%i)", $x, $y, $mx,$my);
+}
+
+# This function checks if a state it receives as an argument is a
+# dead-end one.
+sub check_if_unsolveable
+{
+    my $self = shift;
+    my $coords = shift;
+    return (($coords->[0] == $coords->[2]) && ($coords->[1] == $coords->[3]));
+}
+
+sub check_if_final_state
+{
+    my $self = shift;
+
+    my $coords = shift;
+
+    return (($coords->[0] == $self->{'exit_x'}) && ($coords->[1] == $self->{'exit_y'}));
+}
+
+
+
+# This function enumerates the moves accessible to the state.
+# If it returns a move, it still does not mean that it is a valid 
+# one. I.e: it is possible that it is illegal to perform it.
+sub enumerate_moves
+{
+    my $self = shift;
+
+    my $horiz_walls = $self->{'horiz_walls'};
+    my $vert_walls = $self->{'vert_walls'};
+    
+    my $coords = shift;
+
+    my ($thes_x, $thes_y) = @$coords[0..1];
+    
+    my @moves;
+
+    if (! $vert_walls->[$thes_y][$thes_x])
+    {
+        push @moves, "l";
+    }
+    if (! $vert_walls->[$thes_y][$thes_x+1])
+    {
+        push @moves, "r";
+    }
+    if (! $horiz_walls->[$thes_y][$thes_x])
+    {
+        push @moves, "u";
+    }
+    if (! $horiz_walls->[$thes_y+1][$thes_x])
+    {
+        push @moves, "d";
+    }
+    push @moves, "w";
+
+    return @moves;
+    
+}
+
+my %translate_moves = 
+    (
+        "u" => [0, -1], 
+        "d" => [0, 1], 
+        "l" => [-1,0], 
+        "r" => [1,0],
+        "w" => [0,0],
+    );
+
+# This function accepts a state and a move. It tries to perform the
+# move on the state. If it is succesful, it returns the new state.
+#
+# Else, it returns undef to indicate that the move is not possible.
+sub perform_move
+{
+    my $self = shift;
+
+    my $coords = shift;
+    my $m = shift;
+
+    my $offsets = $translate_moves{$m};
+    my @new_coords = @$coords;
+    $new_coords[0] += $offsets->[0];
+    $new_coords[1] += $offsets->[1];
+    (@new_coords[2 .. 3]) = $self->mino_move(@new_coords);
+
+    return \@new_coords;
+}
+
+1;
+

lib/Games/LMSolve/Numbers.pm

+package Games::LMSolve::Numbers;
+
+use strict;
+
+use Games::LMSolve::Base;
+
+use vars qw(@ISA);
+
+@ISA=qw(Games::LMSolve::Base);
+
+my %cell_dirs = 
+    (
+        'N' => [0,-1],
+        'S' => [0,1],
+        'E' => [1,0],
+        'W' => [-1,0],
+    );
+
+sub input_board
+{
+    my $self = shift;
+
+    my $filename = shift;
+
+    my $spec = 
+    {
+        'dims' => {'type' => "xy(integer)", 'required' => 1},
+        'start' => {'type' => "xy(integer)", 'required' => 1},
+        'layout' => {'type' => "layout", 'required' => 1},
+    };
+
+    my $input_obj = Games::LMSolve::Input->new();
+    my $input_fields = $input_obj->input_board($filename, $spec); 
+    my ($width, $height) = @{$input_fields->{'dims'}->{'value'}}{'x','y'};
+    my ($start_x, $start_y) = @{$input_fields->{'start'}->{'value'}}{'x','y'};
+    my (@board);
+    
+    my $line;
+    my $line_number=0;
+    my $lines_ref = $input_fields->{'layout'}->{'value'};
+
+    my $read_line = sub {
+        if (scalar(@$lines_ref) == $line_number)
+        {
+            return 0;
+        }
+        $line = $lines_ref->[$line_number];
+        $line_number++;
+        return 1;
+    };
+
+    my $gen_exception = sub {
+        my $text = shift;
+        die "$text on $filename at line " . 
+            ($input_fields->{'layout'}->{'line_num'} + $line_number + 1) . 
+            "!\n";
+    };
+
+    my $y = 0;
+
+    INPUT_LOOP: while ($read_line->())
+    {
+        if (length($line) != $width)
+        {
+            $gen_exception->("Incorrect number of cells");
+        }
+        if ($line =~ /([^\d\*])/)
+        {
+            $gen_exception->("Unknown cell type $1");
+        }
+        push @board, [ split(//, $line) ];
+        $y++;
+        if ($y == $height)
+        {
+            last;
+        }
+    }
+
+    if ($y != $height)
+    {
+        $gen_exception->("Input terminated prematurely after reading $y lines");
+    }
+
+    if (! defined($start_x))
+    {
+        $gen_exception->("The starting position was not defined anywhere");
+    }
+
+    $self->{'height'} = $height;
+    $self->{'width'} = $width;
+    $self->{'board'} = \@board;
+
+    return [ $start_x, $start_y];
+}
+
+# A function that accepts the expanded state (as an array ref)
+# and returns an atom that represents it.
+sub pack_state
+{
+    my $self = shift;
+    my $state_vector = shift;
+    return pack("cc", @{$state_vector});
+}
+
+# A function that accepts an atom that represents a state 
+# and returns an array ref that represents it.
+sub unpack_state
+{
+    my $self = shift;
+    my $state = shift;
+    return [ unpack("cc", $state) ];
+}
+
+# Accept an atom that represents a state and output a 
+# user-readable string that describes it.
+sub display_state
+{
+    my $self = shift;
+    my $state = shift;
+    my ($x, $y) = @{ $self->unpack_state($state) };
+    return sprintf("X = %i ; Y = %i", $x+1, $y+1);
+}
+
+# This function checks if a state it receives as an argument is a
+# dead-end one.
+sub check_if_unsolveable
+{
+    # One can always proceed from here.
+    return 0;
+}
+
+sub check_if_final_state
+{
+    my $self = shift;
+
+    my $coords = shift;
+    return $self->{'board'}->[$coords->[1]][$coords->[0]] eq "*";
+}
+
+# This function enumerates the moves accessible to the state.
+# If it returns a move, it still does not mean that it is a valid 
+# one. I.e: it is possible that it is illegal to perform it.
+sub enumerate_moves
+{
+    my $self = shift;
+
+    my $coords = shift;
+
+    my $x = $coords->[0];
+    my $y = $coords->[1];
+
+    my $step = $self->{'board'}->[$y][$x];
+
+    my @moves;
+    
+    if ($x + $step < $self->{'width'})
+    {
+        push @moves, "E";
+    }
+
+    # The ranges are [0 .. ($width-1)] and [0 .. ($height-1)]
+    if ($x - $step >= 0)
+    {
+        push @moves, "W";
+    }
+
+    if ($y + $step < $self->{'height'})
+    {
+        push @moves, "S";
+    }
+
+    if ($y - $step >= 0)
+    {
+        push @moves, "N";
+    }
+    
+    return @moves;   
+}
+
+# This function accepts a state and a move. It tries to perform the
+# move on the state. If it is succesful, it returns the new state.
+#
+# Else, it returns undef to indicate that the move is not possible.
+sub perform_move
+{
+    my $self = shift;
+
+    my $coords = shift;
+    my $m = shift;
+
+    my $step = $self->{'board'}->[$coords->[1]][$coords->[0]];
+
+    my $offsets = [ map { $_  * $step } @{$cell_dirs{$m}} ];
+    my @new_coords = @$coords;
+    $new_coords[0] += $offsets->[0];
+    $new_coords[1] += $offsets->[1];
+
+    return [ @new_coords ];
+}
+
+1;
+

lib/Games/LMSolve/Plank/Base.pm

+package Games::LMSolve::Plank::Base;
+
+use strict;
+
+use vars qw(@ISA);
+
+use Games::LMSolve::Base qw(%cell_dirs);
+
+@ISA=qw(Games::LMSolve::Base);
+
+use Games::LMSolve::Input;
+
+sub initialize
+{
+    my $self = shift;
+
+    $self->SUPER::initialize(@_);
+
+    $self->{'dirs'} = [qw(E W S N)];
+}
+
+sub input_board
+{
+    my $self = shift;
+
+    my $filename = shift;
+
+    my $spec =
+    {
+        'dims' => { 'type' => "xy(integer)", 'required' => 1, },
+        'planks' => { 'type' => "array(start_end(xy(integer)))", 
+                      'required' => 1,
+                    },
+        'layout' => { 'type' => "layout", 'required' => 1,},        
+    };
+
+    my $input_obj = Games::LMSolve::Input->new();
+
+    my $input_fields = $input_obj->input_board($filename, $spec);
+    my ($width, $height) = @{$input_fields->{'dims'}->{'value'}}{'x','y'};
+    my ($goal_x, $goal_y);
+
+    if (scalar(@{$input_fields->{'layout'}->{'value'}}) < $height)
+    {
+        die "Incorrect number of lines in board layout (does not match dimensions";
+    }
+    my @board;
+    my $lines = $input_fields->{'layout'}->{'value'};
+    for(my $y=0;$y<$height;$y++)
+    {
+        my $l = [];
+        if (length($lines->[$y]) < $width)
+        {
+            die "Too few characters in board layout in line No. " . ($input_fields->{'layout'}->{'line_num'}+$y+1);
+        }
+        my $x = 0;
+        foreach my $c (split(//, $lines->[$y]))
+        {
+            push @$l, ($c ne " ");
+            if ($c eq "G")
+            {
+                if (defined($goal_x))
+                {
+                    die "Goal was defined twice!";
+                }
+                ($goal_x, $goal_y) = ($x, $y);
+            }
+            $x++;
+        }
+        push @board, $l;        
+    }
+    if (!defined($goal_x))
+    {
+        die "The Goal was not defined in the layout";
+    }
+    
+    my $planks_in = $input_fields->{'planks'}->{'value'};
+
+    my @planks;
+
+    my $get_plank = sub {
+        my $p = shift;
+
+        my ($start_x, $start_y) = ($p->{'start'}->{'x'},  $p->{'start'}->{'y'});
+        my ($end_x, $end_y) = ($p->{'end'}->{'x'},  $p->{'end'}->{'y'});
+
+        my $check_endpoints = sub {
+            if (! $board[$start_y]->[$start_x])
+            {
+                die "Plank cannot be placed at point ($start_x,$start_y)!";
+            }
+            if (! $board[$end_y]->[$end_x])
+            {
+                die "Plank cannot be placed at point ($end_x,$end_y)!";
+            }
+        };        
+
+        my $plank_str = "Plank ($start_x,$start_y) ==> ($end_x,$end_y)";
+
+        if (($start_x >= $width) || ($end_x >= $width) || 
+            ($start_y >= $height) || ($end_y >= $height))
+        {
+            die "$plank_str is out of the boundaries of the board";
+        }
+
+        if ($start_x == $end_x)
+        {
+            if ($start_y == $end_y)
+            {
+                die "$plank_str has zero length!";
+            }
+            $check_endpoints->();
+            if ($start_y > $end_y)
+            {
+                ($start_y, $end_y) = ($end_y, $start_y);
+            }
+            foreach my $y (($start_y+1) .. ($end_y-1))
+            {
+                if ($board[$y]->[$start_x])
+                {
+                    die "$plank_str crosses logs!"
+                }
+            }
+            return { 'len' => ($end_y-$start_y), 'start' => { 'x' => $start_x, 'y' => $start_y}, 'dir' => "S"};
+        }
+        elsif ($start_y == $end_y)
+        {
+            $check_endpoints->();
+            if ($start_x > $end_x)
+            {
+                ($start_x, $end_x) = ($end_x, $start_x);
+            }
+            foreach my $x (($start_x+1) .. ($end_x-1))
+            {
+                if ($board[$start_y]->[$x])
+                {
+                    die "$plank_str crosses logs!"
+                }
+            }
+            return { 'len' => ($end_x-$start_x), 'start' => { 'x' => $start_x, 'y' => $start_y}, 'dir' => "E" };
+        }
+        elsif (($end_x-$start_x) == ($end_y - $start_y))
+        {
+            $check_endpoints->();
+            if ($start_x > $end_x)
+            {
+                ($start_x, $end_x) = ($end_x, $start_x);
+                ($start_y, $end_y) = ($end_y, $start_y);
+            }
+            foreach my $i (1 .. ($end_x-$start_x-1))
+            {
+                if ($board[$start_y+$i]->[$start_x+$i])
+                {
+                    die "$plank_str crosses logs!"
+                }
+            }
+            if (! grep { $_ eq "SE" } @{$self->{'dirs'}})
+            {
+                die "$plank_str is not aligned horizontally or vertically.";
+            }
+            return 
+                { 
+                    'len' => ($end_x - $start_x), 
+                    'start' => 
+                        { 
+                            'x' => $start_x,
+                            'y' => $start_y,
+                        },
+                    'dir' => "SE",
+                };
+        }
+        else
+        {
+            die "$plank_str is not aligned horizontally or vertically.";
+        }
+    };
+    
+    foreach my $p (@$planks_in)
+    {
+        push @planks, $get_plank->($p);
+    }
+
+    $self->{'width'} = $width;
+    $self->{'height'} = $height;
+    $self->{'goal_x'} = $goal_x;
+    $self->{'goal_y'} = $goal_y;
+    $self->{'board'} = \@board;
+    $self->{'plank_lens'} = [ map { $_->{'len'} } @planks ];
+    
+    my $state = [ 0,  (map { ($_->{'start'}->{'x'}, $_->{'start'}->{'y'}, (($_->{'dir'} eq "E") ? 0 : ($_->{'dir'} eq "SE") ? 2 : 1)) } @planks) ];
+    $self->process_plank_data($state);
+
+    #{
+    #    use Data::Dumper;
+    #
+    #    my $d = Data::Dumper->new([$self, $state], ["\$self", "\$state"]);
+    #    print $d->Dump();
+    #}
+
+    return $state;
+}
+
+sub process_plank_data
+{
+    my $self = shift;
+
+    my $state = shift;
+
+    my $active = $state->[0];
+
+    my @planks = 
+        (map 
+            { 
+                { 
+                    'len' => $self->{'plank_lens'}->[$_], 
+                    'x' => $state->[$_*3+1], 
+                    'y' => $state->[$_*3+1+1], 
+                    'dir' => $state->[$_*3+2+1],
+                    'active' => 0,
+                } 
+            } 
+            (0 .. (scalar(@{$self->{'plank_lens'}}) - 1))
+        );
+
+   
+    foreach my $p (@planks)
+    {
+        my $p_dir = $p->{'dir'};
+        my $dir = ($p_dir == 0) ? "E" : ($p_dir == 1) ? "S" : "SE";
+        $p->{'dir'} = $dir;
+    
+        $p->{'end_x'} = $p->{'x'} + $cell_dirs{$dir}->[0] * $p->{'len'};
+        $p->{'end_y'} = $p->{'y'} + $cell_dirs{$dir}->[1] * $p->{'len'};
+    }
+
+    # $ap is short for active plank
+    my $ap = $planks[$active];
+    $ap->{'active'} = 1;
+
+    my (@queue);
+    push @queue, [$ap->{'x'}, $ap->{'y'}], [$ap->{'end_x'}, $ap->{'end_y'}];
+    undef($ap);
+    while (my $point = pop(@queue))
+    {
+        my ($x,$y) = @$point;
+        foreach my $p (@planks)
+        {
+            if ($p->{'active'})
+            {
+                next;
+            }
+            if (($p->{'x'} == $x) && ($p->{'y'} == $y))
+            {
+                $p->{'active'} = 1;
+                push @queue, [$p->{'end_x'},$p->{'end_y'}];
+            }
+            if (($p->{'end_x'} == $x) && ($p->{'end_y'} == $y))
+            {
+                $p->{'active'} = 1;
+                push @queue, [$p->{'x'},$p->{'y'}];
+            }
+        }
+    }
+    foreach my $i (0 .. $#planks)
+    {
+        if ($planks[$i]->{'active'})
+        {
+            $state->[0] = $i;
+            return \@planks;
+        }
+    }
+}
+
+sub pack_state
+{
+    my $self = shift;
+
+    my $state_vector = shift;
+    return pack("c*", @$state_vector);
+}
+
+sub unpack_state
+{
+    my $self = shift;
+    my $state = shift;
+    return [ unpack("c*", $state) ];
+}
+
+sub display_state
+{
+    my $self = shift;
+    my $state = shift;
+
+    my $plank_data = $self->process_plank_data($state);
+
+    my @strings;
+    foreach my $p (@$plank_data)
+    {
+        push @strings, sprintf("(%i,%i) -> (%i,%i) %s", $p->{'x'}, $p->{'y'}, $p->{'end_x'}, $p->{'end_y'}, ($p->{'active'} ? "[active]" : ""));
+    }
+    return join(" ; ", @strings);
+}
+
+sub check_if_unsolveable
+{
+    return 0;
+}
+
+sub check_if_final_state
+{
+    my $self = shift;
+
+    my $state = shift;
+
+    my $plank_data = $self->process_plank_data($state);
+
+    my $goal_x = $self->{'goal_x'};
+    my $goal_y = $self->{'goal_y'};
+
+    return (scalar(grep { (($_->{'x'} == $goal_x) && ($_->{'y'} == $goal_y)) || 
+                  (($_->{'end_x'} == $goal_x) && ($_->{'end_y'} == $goal_y)) 
+                }
+                @$plank_data) > 0);
+}
+
+sub enumerate_moves
+{
+    my $self = shift;
+
+    my $state = shift;
+
+    my $plank_data = $self->process_plank_data($state);
+
+    # Declare some accessors
+    my $board = $self->{'board'};
+    my $width = $self->{'width'};
+    my $height = $self->{'height'};
+
+    my $dirs_ptr = $self->{'dirs'};
+
+    my @moves;
+
+    for my $to_move_idx (0 .. $#$plank_data)
+    {
+        my $to_move = $plank_data->[$to_move_idx];
+        my $len = $to_move->{'len'};
+        if (!($to_move->{'active'}))
+        {
+            next;
+        }
+        foreach my $move_to (@$plank_data)
+        {
+            if (!($move_to->{'active'}))
+            {
+                next;
+            }
+            for my $point ([$move_to->{'x'}, $move_to->{'y'}], [$move_to->{'end_x'}, $move_to->{'end_y'}])
+            {
+                my ($x, $y) = @$point;
+                DIR_LOOP: for my $dir (@$dirs_ptr) # (qw(E W S N))
+                {
+                    # Find the other ending points of the plank
+                    my $other_x = $x + $cell_dirs{$dir}->[0] * $len;
+                    my $other_y = $y + $cell_dirs{$dir}->[1] * $len;
+                    # Check if we are within bounds
+                    if (($other_x < 0) || ($other_x >= $width))
+                    {
+                        next;
+                    }
+                    if (($other_y < 0) || ($other_y >= $height))
+                    {
+                        next;
+                    }
+
+                    # Check if there is a stump at the other end-point
+                    if (! $board->[$other_y]->[$other_x])
+                    {
+                        next;
+                    }
+
+                    # Check the validity of the intermediate points.
+                    for(my $offset = 1 ; $offset < $len ; $offset++)
+                    {
+                        my $ix = $x + $cell_dirs{$dir}->[0] * $offset;
+                        my $iy = $y + $cell_dirs{$dir}->[1] * $offset;
+                        
+                        if ($board->[$iy]->[$ix])
+                        {
+                            next DIR_LOOP;
+                        }
+                        # Check if another plank has this point in between
+                        my $collision_plank_idx = 0;
+                        for my $plank (@$plank_data)
+                        {
+                            # Make sure we don't test a plank against
+                            # a collisions with itself.
+                            if ($collision_plank_idx == $to_move_idx)
+                            {
+                                next;
+                            }
+                            my $p_x = $plank->{'x'};
+                            my $p_y = $plank->{'y'};
+                            my $plank_dir = $plank->{'dir'};
+                            for my $i (0 .. $plank->{'len'})
+                            {
+                                if (($p_x == $ix) && ($p_y == $iy))
+                                {
+                                    next DIR_LOOP;
+                                }
+                            }
+                            continue
+                            {
+                                $p_x += $cell_dirs{$plank_dir}->[0];
+                                $p_y += $cell_dirs{$plank_dir}->[1];
+                            }
+                        }
+                        continue
+                        {
+                            $collision_plank_idx++;
+                        }
+                    }
+
+                    # A perfectly valid move - let's add it.
+                    push @moves, { 'p' => $to_move_idx, 'x' => $x, 'y' => $y, 'dir' => $dir };
+                }
+            }
+        }
+    }
+
+    return @moves;
+}
+
+sub perform_move
+{
+    my $self = shift;
+
+    my $state = shift;
+    my $m = shift;
+
+    my $plank_data = $self->process_plank_data($state);
+
+    my ($x,$y,$p,$dir) = @{$m}{qw(x y p dir)};
+    my $dir_idx;
+    if ($dir eq "S")
+    {
+        $dir_idx = 1;
+    }
+    elsif ($dir eq "E")
+    {
+        $dir_idx = 0;
+    }
+    elsif ($dir eq "N")
+    {
+        $dir_idx = 1;
+        $y -= $self->{'plank_lens'}->[$p];
+    }
+    elsif ($dir eq "W")
+    {
+        $dir_idx = 0;
+        $x -= $self->{'plank_lens'}->[$p];
+    }
+    elsif ($dir eq "NW")
+    {
+        $dir_idx = 2;
+        $y -= $self->{'plank_lens'}->[$p];
+        $x -= $self->{'plank_lens'}->[$p];        
+    }
+    elsif ($dir eq "SE")
+    {
+        $dir_idx = 2;
+    }
+
+    my $new_state = [ @$state ];
+
+    @$new_state[0] = $p;
+    @$new_state[(1+$p*3) .. (1+$p*3+2)] = ($x,$y,$dir_idx);
+
+    $self->process_plank_data($new_state);
+    
+    return $new_state;
+}
+
+sub render_move
+{
+    my $self = shift;
+
+    my $move = shift;
+
+    if ($move)
+    {
+        return sprintf("Move the Plank of Length %i to (%i,%i) %s", $self->{'plank_lens'}->[$move->{'p'}], @{$move}{qw(x y dir)});
+    }
+    else
+    {
+        return "";
+    }
+}

lib/Games/LMSolve/Plank/Hex.pm

+package Games::LMSolve::Plank::Hex;
+
+use strict;
+
+use vars qw(@ISA);
+
+use Games::LMSolve::Plank::Base;
+
+@ISA=qw(Games::LMSolve::Plank::Base);
+
+sub initialize
+{
+    my $self = shift;
+
+    $self->SUPER::initialize(@_);
+
+    $self->{'dirs'} = [qw(E W S N SE NW)];
+}
+
+1;
+

lib/Games/LMSolve/Tilt/Base.pm

+package Games::LMSolve::Tilt::Base;
+
+use strict;
+
+use vars qw(@ISA);
+
+use Games::LMSolve::Base;
+