Dec 23 2007

perl: Word Search Generator

Published by at 11:26 am under Programming

Main Loop

Now it’s time to follow the logic we laid out earlier. We are going to define a 2D array called @grid which will contain the puzzle we are working on. So $grid[6][7] will contain the letter at column 6, row 7 of the puzzle. We also will use another array called @temp_grid.

Here is a physical world analogy which may help. Think of @grid as being written on a piece of paper, and we are using ink to write on it. And think of @temp_grid as being a sheet of clear plastic which we write on with an erasable marker, laid on top of the paper. We will try to place each word onto the plastic, keeping in mind that we can see the already placed words written on the paper beneath it. After each failed attempt we erase everything on the plastic and start again. When we do succeed in placing a word, we transfer it from the plastic over to the paper, erase the plastic, and move on to the next word. Things written on the paper are final and never get erased.

So here it goes, the main bit of code for placing the words into the puzzle. Keep in mind the manual logic we laid out earlier, since we are trying to follow the same steps.

# initialize a grid full of empty cells
@grid = empty_grid($size_x-1, $size_y-1);

# loop thru all the words in the list randomly
for $this_word (shuffle(@words)) {
  $placed=0; $tries=0;
  while ($placed == 0 && $tries < $max_attempts) { 
    $x=int(rand $size_x); $y=int(rand $size_y);
    if ($grid[$x][$y] == '' || 
        $grid[$x][$y] == substr($this_word,0,1)) {
      for $direction (shuffle(split(',',$directions))) {      
        @temp_grid = empty_grid($size_x-1, $size_y-1);
        foreach ($position=0;$position($size_x-1) || 
             $curr_y<0 || $curr_y>($size_y-1)) { 
            last; # outside the bounds of the grid
          }
# first chance, is the target cell empty?
          if ($grid[$curr_x][$curr_y] eq '') {
            $temp_grid[$curr_x][$curr_y]=$this_char;
          } else {
# second chance - does the target cell contain the letter in question?
            if ($grid[$curr_x][$curr_y] eq $this_char) {
              $temp_grid[$curr_x][$curr_y]=$this_char;
            } else {          
              last; # failed second chance also
            }
          }
# if we reached the end of the word, transfer it to the real grid          
          if($position == length($this_word)-1) { 
            for $i (0..$size_x-1) {
              for $j (0..$size_y-1) {
                if($temp_grid[$i][$j] eq '') {
                } else {
                  $grid[$i][$j]=$temp_grid[$i][$j];
                }
              }
            }
            $placed=1; 
            $placedword{$this_word}='Y';
          }
        }
        if ($placed == 1 ) { 
          last; # the word was placed, no need to check other directions
        } 
      }      
    }
    $tries++;
  }
}
  
print 'placed ' . scalar(keys %placedword) . ' out of ' . eval($#words+1) . ' words' . "\n";

Figure 7 – Placing Words on the Grid

We take all the @words we read from the config file, randomize them (59), and then try to place each one onto the grid. We pick a random starting cell (62). Right off the bat, if the starting cell isn’t blank (63) or equal to the first letter of the word (64), there isn’t any need to go further. But if it is, then we look at all the possible directions randomly (65).

As mentioned, @grid represents our final puzzle, and @temp_grid is empty except for the one word we are working on. We start by clearing the temp grid (66), then going through each letter in the word (67). We keep track of the new cell we are looking at (69,70) by using the inc_x and inc_y hashes, and if we go past the edges of the grid we know we have failed (73). When putting letters into @temp_grid, we first look at @grid to see if the cell is available. An empty cell is always available (76), but if the cell is not empty it may be available if it happens to contain the same letter that we are trying to place (80).

The variable $tries keeps track of how many times we try to place a specific word and fail. Once we have tried a certain number of times with no luck, we give up on the word and continue with the next one (61). This is a bit of laziness on my part, there are better, more complete ways to have handled this.

If we can get all the way through a word, then we copy all non-empty cells from @temp_grid to the real @grid (88-95), and begin again with the next word. We also maintain a hash of the words placed, with the key being the word itself (97). When done, I print a single line back to the command window, showing how many words were placed (109).

Well that is really the hardest part of this program. It can take a list of words and fit them into a grid, using the parameters we gave it. Next up – generating the output.

Pages: 1 2 3 4 5 6 7

3 responses so far

Please do not load this page directly. Thanks!