A word search puzzle is a word game that consists of the letters of words placed in a rectangular grid. The objective of this puzzle is to find and mark all the words hidden inside the grid. The words may be placed horizontally left-to-right or right-to-left, or vertically top-down or bottom-up. Often a list of the hidden words is provided, and many word search puzzles have a theme to which all the hidden words are related. The same letter may be used in multiple hidden words. When reading letters that are used in none of the hidden words from left to right and from top to bottom, a new word is formed that holds as the solution of the puzzle.

word search
Finish the word search puzzle and find the hidden word (PUMICE).

Assignment

Define a class WordSearch that supports at least the following methods:

  1. An initialization method __init__ that takes three mandatory arguments: a number of rows $$r$$, a number of columns $$c$$ and a string $$s$$ that only contains letters. The initialization method must guarantee that each object of the class WordSearch has an attribute grid that represents a rectangular $$r \times c$$ grid which contains the given series of letters from left to right and from top to bottom. Take a look at the example given below, to see how the method should respond in case the given string $$s$$ contains less than $$rc$$ letters.

  2. A method rows that takes no arguments and returns the number of rows of the word search grid.

  3. A method columns that takes no arguments and returns the number of columns of the word search grid.

  4. A method __str__ that takes no arguments and returns a string representation of the word search puzzle. The successive lines of this string representation correspond to the rows of the grid, where all letters on a single row are printed one after the other.

  5. A method read that takes four mandatory arguments: i) a row index, ii) a column index, iii) a direction and iv) a length. Row and column indices start from zero. The method must return the word that is read from the grid in the given direction, starting at the cell in the given row and column. There are four possible directions in which words can be read from the grid, indicated by a pair of uppercase letters: LR (from left to right), RL (from right to left), TD (top-down), BU (bottom-up). The length of the word that must be read from the grid corresponds to the fourth argument passed to the method. The method must return an empty string in case no word can be read from the grid starting at the given position in the given direction (because reading runs against the borders of the grid).

  6. A method search that takes a string argument representing a word that needs to be searched in the grid of the word puzzle. The method must return in which direction and starting from which position the word can be read from the grid. The result must be returned as a tuple containing three elements: i) the row index of the starting position, ii) the column index of the starting position, and iii) the direction (as a string containing two uppercase letters). In searching the word in the grid, no distinction should be made between uppercase and lowercase letters. The method must return the value None in case the given word cannot be read from the grid in any of the four possible directions.

  7. A method solution that returns the solution of the word search puzzle as an uppercase string. A list of hidden words must be passed as an argument to the method. The solution is found by reading the letters from the grid that are used in none of the hidden words from left to right and from top to bottom. Note that it is possible that the given list contains words that are not found in the grid. As some letters in the grid may be used in multiple hidden words, the best approach to find the solution is to replace the hidden words that are found in the grid by lowercase letters. After this is done for all hidden words, the solution may be formed from the remaining uppercase letters. For the sample word search puzzle given above, the following grid is obtained after having converted all hidden words into lowercase letters. 

    tnilffut
elbramPl
Uarkosea
MtIelahs
Ciscoria
etininob
felsiteE
    From this grid, the solution of the word search puzzle reads as PUMICE.

Example

>>> puzzle = WordSearch(7, 8, 'TNILFFUTELBRAMPLUARKOSEAMTIELAHSCISCORIAETININOBFELSITEE')
>>> print(puzzle)
TNILFFUT
ELBRAMPL
UARKOSEA
MTIELAHS
CISCORIA
ETININOB
FELSITEE
>>> puzzle.read(5, 3, 'BU', 6)
'NCEKRL'
>>> puzzle.read(3, 4, 'LR', 5)
''
>>> puzzle.search('marble')
(1, 5, 'RL')
>>> puzzle.search('chalk')
>>> puzzle.solution(['shale', 'basalt', 'felsite', 'boninite', 'latite', 'tuff', 'scoria', 'marble', 'arkose', 'flint'])
'PUMICE'

>>> puzzle = WordSearch(7, 8, 'BASALT')
Traceback (most recent call last):
AssertionError: too few letters given