Forum: Ruby Word Search (#107)

Announcement (2017-05-07): is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see and for other Rails- und Ruby-related community platforms.
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2007-01-06 19:30
(Received via mailing list)
I had a few moments this weekend and sat down to work this problem.  I
was quite
surprised to find it tougher than I had expected.  I fiddled around for
about an
hour trying to find a solution I felt was elegant, but never really got
Luckily, we have many submitters smarter than me.

Almost all of the solutions this week took different approaches and they
are all
quite interesting.  This doesn't seem to be one of those problems we
have a
standard approach for.  Some solutions did a boring search using X and Y
coordinates; others started by building a map of points in the puzzle to
or even letters to points; one even works by performing board
I'm going to show the basic X and Y search in this summary, but the
other method
were equally interesting and well worth a look.

Let's talk about the solution from Bob Showalter, which begins like

  class WordSearch

   class Board < Array

     def to_s
       collect {|s| s.split(//).join(' ')}.join("\n")


   # ...

Here we see an Array subclass with a trivial modification.  Board
objects are
just two-dimensional Arrays that know how to draw themselves in the quiz

Let's move on to the setup code:

   # ...

   attr_reader :board, :solution

   # creates a new, empty solver
   def initialize
     @board =
     @solution =

   # resets the solution
   def reset
     @board.each {|row| @solution << row.gsub(/./, '+')}

   # ...

Here we have the initialization for two Board objects.  One will hold
the actual
board, or puzzle object, and the other the solution-in-progress.
reset() gives
us hints at the solution object structure, which is cleared to a board
full of
plus characters.

The board is loaded with the following code:

   # ...

   # checks that the board contains only letters and that it has a
   # rectangular shape
   def validate
     @board.size > 0 or raise "Board has no rows"
     @board.grep(/[^A-Z]/).empty? or raise "Board contains non-letters"
     w = @board.collect {|row| row.size}.uniq
     w.size == 1 or raise "Board rows are not all the same length"
     w.first > 0 or raise "Board has no columns"

   # parses the board by reading lines from io until a blank line (or
   # is read.
   def parse(io = ARGV)
     while line = io.gets
       line = line.strip.upcase
       break if line == ''
       @board << line

   # ...

validate() is just a reality check for the board.  It verifies that we
have some
rows, those rows contain letters, there are columns in each row, and in
fact the
same number of columns.  That check is run towards the end of parse(),
just reads line by line filling the board object.  Note that reset() is
called to prepare the solution object.

The real work comes in the methods that search for words:

   # ...

   # search for word. returns number of times found.  solution is
   # with all occurences.
   def search(word)
     found = 0
     0.upto(board.size-1) do |y|
       0.upto(board[y].size-1) do |x|
         [-1, 0, 1].each do |dy|
           [-1, 0, 1].each do |dx|
             next if dx == 0 and dy == 0
             found += 1 if search_for(word.strip.upcase, x, y, dx, dy)

   # search for word in board starting at position (x,y) and moving in
   # direction (dx,dy). returns true if found, false if not found.
   def search_for(word, x, y, dx, dy)
     return false if x < 0                 or
                     x >= board.first.size or
                     y < 0                 or
                     y >= board.size
     return false if board[y][x] != word[0]
     prev = solution[y][x]
     solution[y][x] = board[y][x]
     return true if word.length <= 1
     found = search_for(word[1,word.length-1], x + dx, y + dy, dx, dy)
     solution[y][x] = prev unless found

   # ...

The search() method manages the hunt for a single term.  It's a trivial
brute-force find from every starting square in all eight directions.
The method
maintains and returns a count, for all occurrences found during the
search.  The
actual letter match is handed off to search_for() though.

In search_for() a recursive search is used to find letter by letter.
The tricky
part here is that the solution object is modified as we search, assuming
we will
find the word.  This means that an extra walk isn't needed to update the
solution later, but it also means the code must revert the changes to
solution object if the word isn't found.  Those are the gymnastics you
see in
the second half of the method.

The next two methods wrap an interface around these calls:

   # ...

   # creates a new puzzle by parsing the board from io. see
   # WordSearch#parse
   def self.parse(io = ARGF)
     obj = new

   def to_s


  # ...

The class method parse() constructs an object and parses the board from
passed IO object.  The instance method to_s() can then be used to show
results, after one or more calls to search().

The solution ends with code to kick-off the process:

  # ...

  # parse the board first
  p = WordSearch.parse

  # parse the words until a blank line is read
  words = []
  while line = ARGF.gets
   line = line.strip.upcase
   break if line == ''
   words += line.gsub(',', ' ').split

  # submit each word and show how many times it was found
  for word in words.sort.uniq
   n =
   puts word + ' was ' + (n == 0 ? 'not found'  :
                          n == 1 ? 'found once' :
                                   "found #{n} times")

  # show the solution
  puts p

Here we see the WordSearch object constructed and the board parsed out
of the
input.  The remainder of the input is divided into words and search() is
for each one.  A found count is printed for each word as the search is
then the final solution is displayed.

  + + + M + + + + + +
  + + + + Y + + + + +
  T H A N K S + + + +
  O + + + + + + + + +
  + L L A + T H E + +
  + + + + C + + + + +
  + + S O L V E R S +
  + + + + e + + + + +
  + + + + V + + + + +
  + + + + E + + + + +
  + + + + R + + + + +

Tomorrow we have a new word game, so stay tuned...
This topic is locked and can not be replied to.