## Word Search Solver

### May 26, 2009

Input to the word search solver is the puzzle matrix and a list of words. The `matrix` type is provided by the Standard Prelude, as well as a `for` macro that simplifies the code. Here is the data given in the exercise:

```(define puzzle   #( #( #\F #\Y #\Y #\H #\N #\R #\D )      #( #\R #\L #\J #\C #\I #\N #\U )      #( #\A #\A #\W #\A #\A #\H #\R )      #( #\N #\T #\K #\L #\P #\N #\E )      #( #\C #\I #\L #\F #\S #\A #\P )      #( #\E #\O #\G #\O #\T #\P #\N )      #( #\H #\P #\O #\L #\A #\N #\D )))```

`(define words '("ITALY" "HOLLAND" "POLAND" "SPAIN" "FRANCE" "JAPAN" "TOGO" "PERU"))`

We work in proper top-down fashion; the outer-most function `search-list` searches for a list of words, calling an inner function `search` to search for a single word:

```(define (search-list puzzle words)   (do ((words words (cdr words)))       ((null? words))     (search puzzle (car words))))```

`Search`, in turn, calls `search-place` to check if a word is found starting at a particular row/column location in a particular direction, in each of eight possible directions:

```(define (search puzzle word)   (for (r 0 (matrix-rows puzzle))     (for (c 0 (matrix-cols puzzle))       (or (search-place puzzle word r c -1 0)           (search-place puzzle word r c -1 1)           (search-place puzzle word r c 0 1)           (search-place puzzle word r c 1 1)           (search-place puzzle word r c 1 0)           (search-place puzzle word r c 1 -1)           (search-place puzzle word r c 0 -1)           (search-place puzzle word r c -1 -1)))))```

`Search-place` performs the actual search, calling `found` to display any word that it finds:

```(define (search-place puzzle word r c r-diff c-diff)   (let loop ((i r) (j c) (ws (string->list word)))     (cond ((null? ws) (found word r c r-diff c-diff))           ((not (and (< -1 i (matrix-rows puzzle))                      (< -1 j (matrix-cols puzzle)))) #f)           ((char=? (car ws) (matrix-ref puzzle i j))             (loop (+ i r-diff) (+ j c-diff) (cdr ws)))           (else #f))))```

`Found` is simply tedious:

```(define (found word r c r-diff c-diff)   (display word)   (display " row ")   (display (+ r 1))   (display " column ")   (display (+ c 1))   (if (= r-diff 1) (display " down"))   (if (= r-diff -1) (display " up"))   (if (= c-diff 1) (display " right"))   (if (= c-diff -1) (display " left"))   (newline)   #t)```

And here’s the final result:

```> (search-list puzzle words) ITALY row 5 column 2 up HOLLAND row 7 column 1 up right POLAND row 7 column 2 right SPAIN row 5 column 5 up FRANCE row 1 column 1 down JAPAN row 2 column 3 down right TOGO row 6 column 5 left PERU row 5 column 7 up```

You can see the program at http://programmingpraxis.codepad.org/odsy7y6L.

Pages: 1 2

### 8 Responses to “Word Search Solver”

1. [...] Praxis – Word Search Solver By Remco Niemeijer Today’s Programming Praxis problem is about word search solvers. The provided solution is 77 lines, so [...]

2. Remco Niemeijer said

```import Data.List
import Data.Map (Map, fromList, member, keys, (!))
import Text.Printf

dirs :: [(String, (Int, Int) -> (Int, Int))]
dirs = zip ["down right", "up right", "right", "down left",
"up left", "left", "down", "up"] \$
[\(x,y) -> (x+h, y+v) | h <- [1,-1,0], v <- [1,-1,0]]

toGrid :: [[a]] -> Map (Int, Int) a
toGrid = fromList . concat .
zipWith (\y -> zipWith (\x c -> ((x,y), c)) [1..]) [1..]

found :: (Eq a, Ord k) => k -> (k -> k) -> Map k a -> [a] -> Bool
found pos dir g w = isPrefixOf w . map (g !) .
takeWhile (flip member g) \$ iterate dir pos

findWord :: Map (Int, Int) Char -> String -> String
findWord g w = head [printf "%s row %d column %d %s" w y x ds |
(x,y) <- keys g, (ds, dir) <- dirs,
found (x,y) dir g w]

puzzle :: [String]
puzzle = ["FYYHNRD",
"RLJCINU",
"AAWAAHR",
"NTKLPNE",
"CILFSAP",
"EOGOTPN",
"HPOLAND"]

main :: IO ()
main = mapM_ (putStrLn . findWord (toGrid puzzle)) \$ words
"ITALY HOLLAND POLAND SPAIN FRANCE JAPAN TOGO PERU"
```
3. Rich Hrkins said

A Python RE-heavy solution:

```#!/usr/bin/env python
"""
Do the word search, using standard input for the puzzle and the arguments
for words.  For example if /tmp/x.txt is:

F Y Y H N R D
R L J C I N U
A A W A A H R
N T K L P N E
C I L F S A P
E O G O T P N
H P O L A N D

and the program is saved as /tmp/x.py, then (under UNIX) the solutions can
be generated using:

/tmp/x.py ITALY HOLLAND POLAND SPAIN FRANCE JAPAN TOGO PERU # </tmp/x.txt

Which will output:

ITALY at row 5 column 2 up
HOLLAND at row 7 column 1 up right
POLAND at row 7 column 2 right
SPAIN at row 5 column 5 up
FRANCE at row 1 column 1 down
JAPAN at row 2 column 3 down right
TOGO at row 6 column 5 left
PERU at row 5 column 7 up
"""

import re, sys

# Get the stdin and word list.  We prepare standard in by removing all spaces
# and joining all the pieces together into one long line.  However, we keep
# the lines so that we can calulate the width of the puzzle.
lines = list(''.join(line.strip().split()) for line in sys.stdin)
puzzle = ''.join(lines)
words = sys.argv[1:]
patterns = []
width = len(lines[0])
spacer = '.' * (width - 1)

# Apply all possible regulard expressions.  Each line will yield either None
# or a match object.  If None, keep going.  If a match, we'll stop iterating
# (so that we don't pay any penality if we find a match).
def seek(word):
yield re.search(word, puzzle)
yield re.search(''.join(reversed(word)), puzzle)
yield re.search(spacer.join(word), puzzle)
yield re.search(spacer.join(''.join(reversed(word))), puzzle)
yield re.search((spacer + '.').join(word), puzzle)
yield re.search((spacer + '.').join(''.join(reversed(word))), puzzle)
yield re.search(spacer[1:].join(word), puzzle)
yield re.search(spacer[1:].join(''.join(reversed(word))), puzzle)

# Define the directions that words could be found within.
dirs = ('right', 'left', 'down', 'up',
'down right', 'up left', 'down left', 'up right')

# Scan the words.  For each, interate through the seek() output.
for word in words:
for index, match in enumerate(seek(word)):
if match is not None:
# A match was found.  The position used depends on whether the
# match was a forward or reverse match.  All odd numbers are
# reversed and use the end position, all even are forward and use
# the start position.
pos = match.end() - 1 if index % 2 else match.start()

# Calculate the row and column based on the position and width of
# the puzzle.
row = pos / width + 1
column = pos % width + 1

# Emit the solution and move on to the next work, ignoring any
# remaining regular expressions that haven't been tried yet.
print '%s at row %d column %d %s' % (word, row, column, dirs[index])
break
else:
# Note that we didn't find it.

```
4. Here’s a python approach which puts each letter into a tuple with its row and column numbers, making it easy to retrieve the words’ locations after we have scrambled the grid looking for matches. No RE’s, just uses the “in” construct.

#!/usr/bin/python
# -*- coding: utf-8 -*-

puzzle=”’F Y Y H N R D
R L J C I N U
A A W A A H R
N T K L P N E
C I L F S A P
E O G O T P N
H P O L A N D
”’
clues = ['ITALY', 'HOLLAND', 'POLAND', 'SPAIN',
'FRANCE', 'JAPAN', 'TOGO', 'PERU']

puzzle = puzzle.replace(‘ ‘,”)
length = puzzle.index(‘\n’)
#Make a list of tuples containing each letter and its row and column
left = [(letter, divmod(index, length+1))
for index, letter in enumerate (puzzle)]
#Reorder the list to represent each reading direction
right = [i for i in reversed(left)]

down = []
for i in range(length):
for j in range(i, len(left), length+1):
down.append(left[j])
down.append(‘\n’)

up = [i for i in reversed(down)]

right_down =[]
for i in range(length):
for j in range(i, len(left), length):
right_down.append(left[j])
right_down.append(‘\n’)

left_up = [i for i in reversed(right_down)]

left_down = []
for i in range(length):
for j in range(i, len(left), length + 2):
left_down.append(left[j])
left_down.append(‘\n’)

right_up = [i for i in reversed(left_down)]

lines = {‘left’:left, ‘right’:right, ‘up’:up, ‘down’:down,
‘left down’:left_down, ‘left up’:left_up,
‘right down’:right_down, ‘right up’:right_up}

for word in clues:
for k,v in lines.items():
string = ”.join([i[0] for i in v])
if word in string:
loc = v[string.index(word)][1]
print word, ‘row’, loc[0]+1, ‘column’, loc[1]+1, k

5. Oops, all the indenting disappeared! I obviously need to work out how to post code properly here – sorry…

6. Another attempt to post the above code:

```#!/usr/bin/python
# -*- coding: utf-8 -*-

puzzle='''F Y Y H N R D
R L J C I N U
A A W A A H R
N T K L P N E
C I L F S A P
E O G O T P N
H P O L A N D
'''
clues = ['ITALY', 'HOLLAND', 'POLAND', 'SPAIN',
'FRANCE', 'JAPAN', 'TOGO', 'PERU']

puzzle = puzzle.replace(' ','')
length = puzzle.index('\n')
#Make a list of tuples containing each letter and its row and column
left = [(letter, divmod(index, length+1))
for  index, letter in enumerate (puzzle)]
#Reorder the list to represent each reading direction
right = [i for i in reversed(left)]

down = []
for i in range(length):
for j in range(i, len(left), length+1):
down.append(left[j])
down.append('\n')

up = [i for i in reversed(down)]

right_down =[]
for i in range(length):
for j in range(i, len(left), length):
right_down.append(left[j])
right_down.append('\n')

left_up = [i for i in reversed(right_down)]

left_down = []
for i in range(length):
for j in range(i, len(left), length + 2):
left_down.append(left[j])
left_down.append('\n')

right_up = [i for i in reversed(left_down)]

lines =  {'left':left, 'right':right,  'up':up, 'down':down,
'left down':left_down, 'left up':left_up,
'right down':right_down, 'right up':right_up}

for word in clues:
for k,v in lines.items():
string = ''.join([i[0] for i in v])
if word in string:
loc = v[string.index(word)][1]
print word, 'row', loc[0]+1, 'column', loc[1]+1, k
```
7. ```An improved (shorter, more efficient) version of the above:

#!/usr/bin/python
# -*- coding: utf-8 -*-

puzzle='''F Y Y H N R D
R L J C I N U
A A W A A H R
N T K L P N E
C I L F S A P
E O G O T P N
H P O L A N D
'''
clues = ['ITALY', 'HOLLAND', 'POLAND', 'SPAIN',
'FRANCE', 'JAPAN', 'TOGO', 'PERU']

puzzle = puzzle.replace(' ','')
length = puzzle.index('\n')+1
#Make a list of tuples containing each letter and its row and column
letters = [(letter, divmod(index, length))
for  index, letter in enumerate (puzzle)]
#Reorder the list to represent each reading direction,
#and add them all to a dictionary
lines = {}
offsets = {'down':0, 'right down':-1, 'left down':1}
for direction, offset in offsets.items():
lines[direction] = []
for i in range(length):
for j in range(i, len(letters), length + offset):
lines[direction].append(letters[j])
lines[direction].append('\n')
lines['left']  = letters
lines['right'] = [i for i in reversed(letters)]
lines['up'] = [i for i in reversed(lines['down'])]
lines['left up'] = [i for i in reversed(lines['right down'])]
lines['right up'] = [i for i in reversed(lines['left down'])]
#Make strings from the letters, find the words in them and retrieve
#their original locations
for direction, tup in lines.items():
string = ''.join([i[0] for i in tup])
for word in clues:
if word in string:
location = tup[string.index(word)][1]
print word, 'row', location[0]+1, 'column', location[1]+1, direction
```
8. Emily said

GIVE ME A WORD SEARCH SOLVER!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!