in reply to Word Search Puzzle

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

Replies are listed 'Best First'.
Re: Re: Word Search Puzzle
by Anonymous Monk on Jan 26, 2004 at 02:16 UTC
    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]
    Nice solution - eliminates nearly identical function. I guess I was following my original C++ code.

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

    I'm not clear on this :-)

    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 ;)

    oops!

[reply]
[d/l]
      You don't need all of those use constant N => 0; either -- the string literal is just as good as a constant.
      I'm not clear on this :-)
      You have 
      use constant N  => 0;

      [download]
      and later 
      if ($dir == N)     {return (--$r, $c)}
elsif ...
else {
    die "Inside 'step': invalid param\n"
}

      [download]
      use constant... essentially gives you a subroutine-ish entity (without a sigil). If you miss the constant declaration, you'll be looking for a subroutine definition for N, NE,, etc. Still, some people like this.

      The benefits of declaring these constants are:
      • difficult to accidentally reassign to constants
      • direction validation (with die...)
      • saving quotes in comparison (as in  if ( $dir eq "N" ))
      [Assuming that $dir is now a string.]

      The drawbacks are:
      • no obvious sub definition
      • constant isn't perfectly constant
      • constants aren't interpolated in double quoted strings
      [See use constant for a complete rundown.]

      I guess what I'm really saying is that it's unfair to compare a literal translation between C and Perl. Each have their idiosynchracies, and will fall short of the "ideal" on some scales.

      Someone here could probably write up a Perlish version of this that was easier to follow, easier to maintain, and perhaps did a few nifty tricks to boot. Though it might run slower than C. :)

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

[reply]
[d/l]
[select]
        First, thanks for your suggestions, QM. I did rewrite sections of the code that you pointed out, eliminated the constants and, in general, cleared up some of the fuzzy areas. Cut about 30 lines and the code was easier to follow.

        Chris

[reply]

In Section Cool Uses for Perl