Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options

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

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://665891]
[Corion]: erix: Yeah, I just found that it has no documentation at all on how to circumvent/ eliminate "1+n SELECTs" by building a local hash... I guess I have to make ->has_many do the hash lookup instead of doing the SQL query. But as the problem ...
[Corion]: ... has only manifested itself so far through the puzzled questions of other bystanders, I won't go deeper at this time. But the DBIx::Class documentation could well do with a document on how to make "it" (that is, ORMs in general) faster ;)
[Corion]: I find that DBIx::Class, like most ORMs makes things easy until they become performance critical and then makes it horribly hard to change things because the design is highly inflexible if you don't already know about the problems of 1+n :-/
[choroba]: that's why I don't like similar libraries. They pretend you don't have to learn SQL, but in the end, you have to learn how SQL plus to overcome their own limitations
[Corion]: "Just write the proper SQL beforehand" is of course the appropriate solution, but if you did that, you wouldn't/couldn't use DBIx::Class either. At least not in an obvious (to me) way.
choroba scratches a "how"
[Corion]: choroba: Exactly... But maybe that's just because I'm old and grumpy ;)
[Corion]: But maybe that could also be a nice talk, how to restructure your DBIx::Class-based app to remove 1+n-style query patterns
[Corion]: In theory, that should be easy because you should have the "where" clause from part 1 of the patterns and then do the corresponding single select using that where clause to select all rows in one go for the n other parts.
[Corion]: But in practice I don't see any obvious places documented in DBIx::Class where one would do that and then just feed hash lookups instead of DB lookups for ->has_many results

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (7)
As of 2017-09-25 11:11 GMT
Find Nodes?
    Voting Booth?
    During the recent solar eclipse, I:

    Results (279 votes). Check out past polls.