in reply to Depth First Search and Boggle

I think your algorithm has some problems. First, all words have to start with the same letter, as you only call dfs with 0, 0 initially, the rest just after adding a character. Second, you only print out a word if you cannot do a move - but of course prefixes of such a string are words too. But the big issue has to do with combinatorial explosion. The number of possible words found this way grows exponentially in the size of the board. It's doable for a 4x4 board, the number of possible words will be less than 2^16, but it will grow rapidly when you increase the size. You should take your dictionary and preprocess it to get all possible prefixes of valid words. And while you create your words while walking the board, stop as soon as your constructed word so far is not a valid prefix. No point in continueing if the first two letters are "QX". ;-)

Abigail

Replies are listed 'Best First'.
Re: Re: Depth First Search and Boggle
by smgfc (Monk) on Aug 15, 2002 at 18:19 UTC

    Maybe I should have included this in my post. Right now I have a hash of a hash of hash... where each character maps to a key. ex.

    hello equals $hash{h}{e}{l}{l}{o} = {}.

    I planned on walking through this hash as I went through the dfs sub, but wanted to get the sub correct before I made it more complicated. Same thing with the singular call to dfs. I figured it would easier to examine the output if I started from one point. I could have wrapped the initial dfs call inside two for loops, but in the intrest of getting dfs working I decided to start from one point only.

    Update: Here is my preprocess code, if you have any suggestions.

    my ($dict) = "/usr/share/dict/words";

open (FILE, $dict) or die ("Can't open $dict: $!\n");

while (<FILE>) {
    chomp;
    next if length() < 3;
    @char = split //, $_;
    $pointer = \%{$word_tree{$char[0]}};
    for (1 .. $#char) {
        $pointer = \%{$$pointer{$char[$_]}};
    }  
}

close (FILE);

    [download]
[reply]
[d/l]
Re: Re: Depth First Search and Boggle
by Anonymous Monk on Aug 15, 2002 at 15:53 UTC
    Another suggestion to improve your algorithm (especially if there is any kind of time limit ...such as your life expectancy :) is to look for shorter words first (breadth first search). No use chugging through permutations of letters trying to find words that start with arteriolosclero when you could move on and find a, as, ass, assai, assail, and assailant. Hope this helps. --Phil
[reply]

In Section Seekers of Perl Wisdom