NEILB's Blog

The second challenge in this week's Perl Weekly Challenge is to write a solver for a wordsearch grid. I suggested this challenge to Mohammad, so I felt honour-bound to write up my solution.

Early into the COVID lockdown, two children in our street came up with two word search grids and put them through our door, with prizes offered for the most vegetables found in one grid, and jungle animals in the other. I spent a couple of minutes with a pencil, then decided to write a script.

This was a whipupitude challenge: write something quickly without worrying about performance. For every cell on the grid, look up, down, left right, and the four diagonal direction NW, NE, SW, SE.

We'll load the grid into a 2D array, and our wordlist into a hash, so we can quickly check whether something is a valid word. We might find the same word more than once in the grid, but we only want to print it once in the output, which immediately suggests we'll use a hash to hold the words we've found. So here's the main body of my script (without the boilerplate — see the full script for the gory details):

use File::Slurper qw/ read_lines /;

my @grid      = map { [split('',lc($_))] } read_lines($ARGV[0]);
my %is_a_word = map { lc($_) => 1        } read_lines($ARGV[1]);
my $num_cols  = int(@{ $grid[0] });
my $num_rows  = int(@grid);
my %found;

scan_grid_for_words();
print_words();

After posting this, I discovered that Mohammad included spaces in his grid file. To support that, we need to strip out all whitespace when loading the grid:

my @grid = map { s/\s+//g; [split('',lc($_))] } read_lines($ARGV[0]);

If I intended to share this script for others to use, I'd check that all lines in the grid were the same length, etc.

The grid scanner iterates over every cell in the grid, and on each cell it then checks the eight directions that words might be found along:

sub scan_grid_for_words {
   for (my $row = 0; $row < $num_rows; ++$row) {
      for (my $col = 0; $col < $num_cols; ++$col) {
         foreach my $row_delta (-1, 0, 1) {
            foreach my $col_delta (-1, 0, 1) {
               next if $row_delta == 0 && $col_delta == 0;
               scan_line_for_words($row, $col, $row_delta, $col_delta);
            }
         }
      }
   }
}

That's a lot of nested loops, so I might've added a scan_cell function, to break out the inner two loops, but the above is what I wrote first.

When scanning along a line from a cell, we build a string by concatenating each letter we see, checking whether we've a valid word at every step. So for the example below, starting at the R, we'll first find RED, and then four steps later we'll find REDWOOD.

And here's the function:

sub scan_line_for_words ($row, $col, $row_delta, $col_delta) {
    my $word = "";

    while (on_grid($row,$col)) {
        $word .= $grid[$row][$col];
        $found{$word}++ if $is_a_word{$word};
        $row += $row_delta;
        $col += $col_delta;
    }
}

And finally our two support functions:

sub on_grid ($row, $col) {
    return ($row < $num_rows && $row >= 0 && $col >= 0 && $col < $num_cols);
}

sub print_words {
    print "$_\n" for sort keys %found;
}

The full script is in this gist.

Mohammad said his solution found 54 words of length 5 or more. My script found 61, but my word list is a mashup of various word lists found online, and includes latin names for plants, and other things that don't appear in regular word lists.