Word Search Solver

May 26, 2009

Word search puzzles are a popular time-wasting pasttime. To redeem some of that lost time, we will write a program to search puzzles. For instance, given a problem like

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 list of words ITALY, HOLLAND, POLAND, SPAIN, FRANCE, JAPAN, TOGO, and PERU, you should find words at the following locations:

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

Your task is to write a word search solver. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

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

    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"
    
  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.
            print "%s not found" % word
    
    
  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!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 637 other followers

%d bloggers like this: