note
TedPride
By request from robinsj, here's a much neater version. Given, it can be optimized to run a lot faster, for instance by working out partials and killing off paths that don't lead to a word, or by looking ahead to see if there's a letter (saves you one level of function depth), but this should still run in around 2 minutes for the max depth of 10.
<code>
use strict;
my $depth = 10; ### Max word length, longer takes more time
my (%words, @board, %results, $width, $height);
my ($handle, $p, $x, $y);
### Load words from file, one word per line
open ($handle, 'dictionary.txt');
while (<$handle>) {
chomp; $words{$_} = 1;
}
close ($handle);
### Load board data
while (<DATA>) {
chomp;
push @board, [split //, $_];
### Maximum board width
$width = $#{$board[-1]} if $#{$board[-1]} > $width;
}
### Board height
$height = $#board;
### Traverse from each possible starting point
for $x (0..$width) {
for $y (0..$height) {
traverse($x, $y, '');
}
}
### Display longest 10 results
my $c = 10;
for (sort { length($b) <=> length($a) || $a cmp $b } keys %results) {
print "$_\n";
exit if !--$c;
}
sub traverse {
my ($x, $y, $word) = @_;
### Letter used up or out of bounds
return if !$board[$y][$x] || $board[$y][$x] eq ' ';
$word .= $board[$y][$x];
$results{$word} = () if $words{$word};
if (length($word) < $depth) {
$board[$y][$x] = undef;
if ($x > 0 && $y > 0) {
traverse($x-1, $y-1, $word);
}
if ($x < $width && $y > 0) {
traverse($x+1, $y-1, $word);
}
if ($x < $width - 1) {
traverse($x+2, $y, $word);
}
if ($x < $width && $y < $height) {
traverse($x+1, $y+1, $word);
}
if ($x > 0 && $y < $height) {
traverse($x-1, $y+1, $word);
}
if ($x > 1) {
traverse($x-2, $y, $word);
}
$board[$y][$x] = substr($word, -1, 1);
}
}
__DATA__
A J S B K
B O X G
B K T C L
A P Y H
C T U D M
H O R I
D M I E N
I R A J
E N W F O
</code>
455038
455038