# Word Search (#107)

**URL:** <https://www.ruby-forum.com/t/word-search-107/81261>\
**Category:** Ruby\
**Created:** [January 6, 2007, 7:30pm UTC](https://www.ruby-forum.com/t/word-search-107/81261 "2007-01-06T19:30:47Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [January 6, 2007, 7:30pm UTC](https://www.ruby-forum.com/t/word-search-107/81261/1 "2007-01-06T19:30:47Z")

</div>

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  
there.  
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  
letters  
or even letters to points; one even works by performing board  
transformations.  
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 S., which begins like  
this:

class WordSearch

class Board \< Array

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

```

end

# …

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  
output  
format.

Let’s move on to the setup code:

# …

attr\_reader :board, :solution

# creates a new, empty solver

def initialize  
@board = Board.new  
@solution = Board.new  
end

# resets the solution

def reset  
@solution.clear  
@board.each {|row| @solution \<\< row.gsub(/./, ‘+’)}  
end

# …

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

uniform

# 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”  
end

# parses the board by reading lines from io until a blank line (or

EOF)

# is read.

def parse(io = ARGV)  
@board.clear  
while line = io.gets  
line = line.strip.upcase  
break if line == ‘’  
@board \<\< line  
end  
validate  
reset  
end

# …

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(),  
which  
just reads line by line filling the board object. Note that reset() is  
also  
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

updated

# 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)  
end  
end  
end  
end  
found  
end

# 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  
found  
end

# …

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  
the  
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  
obj.parse(io)  
obj  
end

def to\_s  
solution.to\_s  
end

end

# …

The class method parse() constructs an object and parses the board from  
the  
passed IO object. The instance method to\_s() can then be used to show  
final  
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  
end

# submit each word and show how many times it was found

for word in words.sort.uniq  
n = p.search(word)  
puts word + ’ was ’ + (n == 0 ? ‘not found’ :  
n == 1 ? ‘found once’ :  
“found #{n} times”)  
end

# 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  
called  
for each one. A found count is printed for each word as the search is  
made,  
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…