Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW

Re: "Bookworm" solver project

by TedPride (Priest)
on Feb 04, 2008 at 02:45 UTC ( #665891=note: print w/ replies, xml ) Need Help??

in reply to "Bookworm" solver project

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.

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

Comment on Re: "Bookworm" solver project
Download Code

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://665891]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (8)
As of 2016-02-14 15:32 GMT
Find Nodes?
    Voting Booth?

    How many photographs, souvenirs, artworks, trophies or other decorative objects are displayed in your home?

    Results (470 votes), past polls