#!/usr/bin/perl -w

use strict;

#####
# Layouts of boggle/word racer boards
#####

my (%layout) = (
    "word_racer_1" => [
                        [1,1,1,1],
                        [1,1,1,1],
                        [1,1,1,1],
                        [1,1,1,1]
                      ],
    "word_racer_2" => [
                        [0,0,1,1,0,0],
                        [0,1,1,1,1,0],
                        [1,1,1,1,1,1],
                        [1,1,1,1,1,1],
                        [0,1,1,1,1,0],
                        [0,0,1,1,0,0]
                      ],
    "word_racer_3" => [
                        [1,1,1,1,0,0],
                        [1,1,1,1,0,0],
                        [1,1,1,1,1,1],
                        [1,1,1,1,1,1],
                        [0,0,1,1,1,1],
                        [0,0,1,1,1,1]
                      ],
    "word_racer_4" => [ 
                        [1,1,1,1,1,1],
                        [1,1,1,1,1,1],
                        [1,1,0,0,1,1],
                        [1,1,0,0,1,1],
                        [1,1,1,1,1,1],
                        [1,1,1,1,1,1]
                      ]
);

#####
# get/check configuration
#####

my ($sqrt_2) = sqrt(2);

my ($min_length) = 3;

my ($which_layout) = "word_racer_1";

die "No such layout $which_layout\n" unless exists $layout{ $which_layout };

my (@board) = @{$layout{ $which_layout }};

my ($input) = "tnlehrayvsrtjesn";

die "Malformed input\n" if $input =~ /[^a-z]/;

my (@data) = split //, $input;

#####
# Initialize board
#####
my ($x, $y, %letter_position);

for ($y = 0; $y <= $#board; $y++) {
    for ($x = 0; $x <= $#{$board[$y]}; $x++) {
        die "Data smaller then layout\n" if $#data == -1;
        next if $board[$y][$x] == 0;

        $board[$y][$x] = shift @data;

        push @{ $letter_position{ $board[$y][$x] } }, [$x, $y];
    }
}
die "Data longer then layout\n" unless $#data == -1;

#####
# Open the dictionary
#####

my ($file_dict) = "/usr/share/dict/words_processed";

open (DICT, "<", $file_dict)
    or die "Can't open $file_dict: $!\n";

#####
# Check wether the word is in the board
#####

my (@word, $index, %invalid, %notouch, %path);


while (<DICT>) {
    chomp;
    $_ = lc;
    next if length() < $min_length or /[^$input]/;
    @word = split //;

    %invalid = ();
    %path = ();

    INDEX: for ($index = 0; $index <= $#word; $index++) {

        if ($index == $#word) {
            print join '', @word;
            print "\n";
            last;
        }

        foreach (@{ $letter_position{$word[$index]} }) {
            my ($x_one, $y_one) = @{$_};
            last if exists $invalid{$index}{$x_one . $y_one};
            $path{$x_one . $y_one} = 1;

            foreach (@{ $letter_position{$word[$index+1]} }) {
               my ($x_two, $y_two) = @{$_};

               next if exists $notouch{$x_one . $y_one . $x_two . $y_two};
               next if exists $invalid{$index+1}{$x_two . $y_two};
               next if exists $path{$x_two . $y_two};

               my ($dist) = sqrt( (($x_one - $x_two)**2) + (($y_one - $y_two)**2) );

               unless ($dist == 1 or $dist == $sqrt_2) {
                   $notouch{$x_one . $y_one . $x_two . $y_two} = 1;
                   next;
               }
               next INDEX;
            }

            $invalid{$index}{$x_one . $y_one} = 1;
        }
        last;
    }
}

#####
# Cleanup
#####
close (DICT);