In line 30 my ($x, $y, %visited, $word) = @_ you are assigning to a hash. If @_ contains 3|5|7...elements, the first two will go into $x, $y and the rest (odd number) will be assigned to %visited and $word will always be undefined.

You should either put $word before %visited or pass in a hashref.

I understand that, but i never pass 3|5|7... elements to dfs. I either call it

dfs(0, 0, %visited, $word)

or

dfs($x + $$_[0], $y + $$_[1], %visited, $word)

so there shouldnt be any problem with odd numbers of elements getting passed to dfs. Beyond that passing by reference would create alot more work to maintain seperate visited and work variables for the different branches in the search.

The point is that all your parameters, including %visited get flattened and passed as a single list:

($x, $y, key1,val1,key2,val2,...,$word)

Inside dfs(), Perl has no way to tell that the last value ($word) is not an element of the list that must be assigned to %visited, so it attempts to assign that too. Hence the odd number of elements.

$word will never be assigned a value.

Swap the order of %visited and $word inside dfs() and when you call dfs() and your code will (probably) work!

---

What's this about a "crooked mitre"? I'm good at woodwork!

Here's a hint.
print "'$_'\n" foreach @_ at the start of your sub (before the assignment).
See what is happening here? You will get a printout like:
'0'
'0'
''
hmm.. not quite what you wanted I think. You are only passing 3 defined values into the sub. Two 0's and one "". Because your hash is undefined, it doesn't show up in the @_ list.

Just looking at this bit of code, it looks like you are trying to do the "right" thing by use'ing strict and passing your variables around to your subroutine. The thing is, if your variables have no value, then there is no reason to pass them. In fact, looking at it,there is absolutely no reason to define %visited or $word in the "main" code at all

In this bit of code, I would personally work more like

...
dfs(0,0);
...

sub dfs {
  my ($x,$y,$word,%visited) = @_; #no error here!
  ... process code ...
  dfs($x,$y,$word,%visited); #recursion call
}
[download]

See the differences? First, because we only pass 2 defined values in the first call to dfs, we only assign to $x and $y. This is fine, because we don't use $word or %visited before we assign to them. Hence, we aren't using an undef'd variable. Nor are we assigning "" to the hash. Second, in subsequent calls, we pass the hash last

BrowserUk is completely right in this. Using an assignment like in your code, you will almost always end up with an odd value assignment. You could almost call an assignment to a hash (or an array for that matter) greedy, because it will always take up the "rest" of @_, if you need to pass variables and a hash or an array, always put the hash/array last in the assignment list. If you need to pass two lists (eg 2 arrays, or a hash and an array) you MUST pass by reference.

Abigail

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]

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

Anyway, here's the code:

#!/usr/bin/perl
    
use strict;
use warnings 'all';
        
my $dict = "/usr/share/dict/words";
        
my %prefix;
my %valid;
my %found;
my $board;
     
sub preprocess;
sub init_board;
sub find_words;

preprocess $dict;
init_board;
 
foreach my $x (0 .. @$board - 1) {
    foreach my $y (0 .. @{$board -> [$x]}) {
        find_words $x, $y, "", [];
    }
}
    
                  
                 
sub preprocess {
    my $file = shift;
    open my $fh => $file or die "Failed to open $file: $!\n";
    local $_;
  LINE:
    while (<$fh>) {
        chomp;
        $_ = lc;
        next if /[^a-z]/;
        $valid {$_} = 1;
        while (length) {
            next LINE if $prefix {$_} ++;
            chop;
        }  
    }
}

     
sub init_board {
    local $_;  
    push @$board => [lc =~ /[a-z]/g] while <DATA>;
}


sub find_words {
    my ($x, $y, $word, $seen) = @_;
    
    return unless $x >= 0 && $y >= 0 &&
                  exists $board -> [$x] && exists $board -> [$x] [$y] 
+&&
                 !$seen -> [$x] [$y];
    
    $word .= $board -> [$x] [$y];
                 
    return unless $prefix {$word};
    
    print "$word\n" if $valid {$word} && !$found {$word} ++; 
    
    $seen -> [$x] [$y] = 1;
        
    foreach my $dx (-1 .. 1) {
        foreach my $dy (-1 .. 1) {
            find_words $x + $dx, $y + $dy, $word, $seen if $dx || $dy;
        }
    }
}
           
     
__DATA__
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
[download]

bag
chide
fag
gab
hi
hid
hide
him
hint
in
mid
no
to
ton
tons
up

Abigail

It would be even better if there was a way to make it do plurals.

Either use a dictionary that already has plurals in it, or use the following preprocess function:

use Lingua::EN::Inflect qw /PL/;
sub preprocess {
    my $file = shift;
    open my $fh => $file or die "Failed to open $file: $!\n";
    local $_;  
  LINE:
    while (<$fh>) {
        chomp;
        $_ = lc;
        next if /[^a-z]/;
      WORD:
        foreach ($_, PL ($_)) {
            $valid {$_} = 1;
            while (length) {
                next WORD if $prefix {$_} ++;
                chop;
            }
        }
    }
}
[download]

Abigail

Note to anyone testing this algorithm out, it works well except for a small bug.

Because the $seen matrix is being passed into sub-calls by reference, any changes to it will still be there when the recursive find_words call returns. That messes up further calls to find_words because the seen-matrix is lying, in a sense.

To fix it, just add this line as the last line of the find_words sub (outside of the two for-loops), so that the seen-matrix is properly reset for a given call's ancestors:

    $seen->[ $x ][ $y ] = 0;
[download]

LoL

cLive ;-)

--
seek(JOB,$$LA,0);