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.
[…] Praxis – Word Search Solver By Remco Niemeijer Today’s Programming Praxis problem is about word search solvers. The provided solution is 77 lines, so […]
My Haskell solution (see http://bonsaicode.wordpress.com/2009/05/26/programming-praxis-word-search-solver/ for a version with comments):
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" [/sourcecode]
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 #
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
Oops, all the indenting disappeared! I obviously need to work out how to post code properly here – sorry…
Another attempt to post the above code:
GIVE ME A WORD SEARCH SOLVER!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!