Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
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

In reply to Re: "Bookworm" solver project by TedPride
in thread "Bookworm" solver project by japhy

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others musing on the Monastery: (15)
    As of 2014-09-23 12:31 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (220 votes), past polls