Code Golf: Word Search Solver
- by Maxim Z.
Note: This is my first Code Golf challenge/question, so I might not be using the correct format below. I'm not really sure how to tag this particular question, and should this be community wiki? Thanks!
This Code Golf challenge is about solving word searches!
A word search, as defined by Wikipedia, is:
A word search, word find, word seek,
word sleuth or mystery word puzzle is
a word game that is letters of a word
in a grid, that usually has a
rectangular or square shape. The
objective of this puzzle is to find
and mark all the words hidden inside
the box. The words may be
horizontally, vertically or
diagonally. Often a list of the hidden
words is provided, but more
challenging puzzles may let the player
figure them out. Many word search
puzzles have a theme to which all the
hidden words are related.
The word searches for this challenge will all be rectangular grids with a list of words to find provided. The words can be written vertically, horizontally, or diagonally.
Input/Output
The user inputs their word search and then inputs a word to be found in their grid. These two inputs are passed to the function that you will be writing. It is up to you how you want to declare and handle these objects.
Using a strategy described below or one of your own, the function finds the specific word in the search and outputs its starting coordinates (simply row number and column number) and ending coordinates. If you find two occurrences of the word, you must output both's set of coordinates.
Example
Input:
A I Y R J J Y T A S V Q T Z E
X B X G R Z P W V T B K U F O
E A F L V F J J I A G B A J K
R E S U R E P U S C Y R S Y K
F B B Q Y T K O I K H E W G N
G L W Z F R F H L O R W A R E
J A O S F U E H Q V L O A Z B
J F B G I F Q X E E A L W A C
F W K Z E U U R Z R T N P L D
F L M P H D F W H F E C G W Z
B J S V O A O Y D L M S T C R
B E S J U V T C S O O X P F F
R J T L C V W R N W L Q U F I
B L T O O S Q V K R O W G N D
B C D E J Y E L W X J D F X M
Word to find: codegolf
Output:
row 12, column 8 --> row 5, column 1
Strategies
Here are a few strategies you might consider using. It is completely up to you to decide what strategy you want to use; it doesn't have to be in this list.
Looking for the first letter of the word; on each occurrence, looking at the eight surrounding letters to see whether the next letter of the word is there.
Same as above, except looking for a part of a word that has two of the same letter side-by-side.
Counting how often each letter of the alphabet is present in the whole grid, then selecting one of the least-occurring letters from the word you have to find and searching for the letter. On each occurrence of the letter, you look at its eight surrounding letters to see whether the next and previous letters of the word is there.
