Data structures created some pretty intense code and I was surprised that the C++ solution was cleaner in some ways.

And dirtier in others ;)

For instance, this:

sub step {
    my ($dir, $r, $c) = @_;
    if ($dir == N)     {return (--$r, $c)}
    elsif ($dir == NE) {return (--$r, ++$c)}
    elsif ($dir == E)  {return ($r, ++$c)}
    elsif ($dir == SE) {return (++$r, ++$c)}
    elsif ($dir == S)  {return (++$r, $c)}
    elsif ($dir == SW) {return (++$r, --$c)}
    elsif ($dir == W)  {return ($r, --$c)}
    elsif ($dir == NW) {return (--$r, --$c)}
    else {
        die "Inside 'step': invalid param\n"
    }
}
[download]

This sub could easily be rewritten as a hash lookup (since it's just a big lookup table anyway):

our %step = ( N  => { R => -1, C =>  0 },
              NE => { R => -1, C => +1 },
              E  => { R =>  0, C => +1 },
              SE => { R => +1, C => +1 },
              S  => { R => +1, C =>  0 },
              SW => { R => +1, C => -1 },
              W  => { R =>  0, C => -1 },
              NW => { R => -1, C => -1 } 
            );
[download]

Then instead of this:

($rows, $cols) = step($dir, $rows, $cols);
[download]

use this:

$rows += $step{$dir}{R};
$cols += $step{$dir}{C};
[download]

For free, sub stepback is gone, and instead of the call use this:

$rows -= $step{$dir}{R};
$cols -= $step{$dir}{C};
[download]

[step and stepback are essentially the same.]

You don't need all of those use constant N => 0; either -- the string literal is just as good as a constant.

There are probably a few more optimizations that could be made. For instance, what if you're given a grid, but instead of "the" word list, your given a lexicon? Then in search, the inner loop:

for my $idx (0..$#words)
[download]

will take quite some time. [BTW, $#words doesn't refer to the sub's my $word, but to the my @words declared at file scope. Bonus points for knowing why ;) ]

The first optimization I would try would be to remove each entry from @words when the search is successful, and move the info to @words_found. Then later searches on @words would only look for the remaining words. This would also speed it up in the current incarnation, but perhaps only marginally.

-QM
--
Quantum Mechanics: The dreams stuff is made of