Longest word (from a list of words) which can be found in the input grid while making a KNIGHT's stride

find_longest.py

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

'''
Find longest word (from a list of words) which can be found in the
input grid while making a KNIGHT's stride.
'''


from collections import defaultdict
from os.path import isfile
from string import punctuation
from re import compile, findall
from sys import argv


KNIGHT_MOVES = [
    (-2, -1), (-2, +1),
    (+2, -1), (+2, +1),
    (-1, -2), (-1, +2),
    (+1, -2), (+1, +2)]
PATTERN = compile(r'[A-Za-z]+')


def find_word(grid, row, col, word):
    '''
    Recursively searches for 'word' in the grid. The motion of cursor depends
    on the value generated by 'KNIGHT_MOVES'. With every recursive step, a
    character from the beginning (of 'word') is stripped and tested against the
    character pointed to by grid[row][col]. If either (row, col) fall outside
    'grid', or the characters don't match, the search is abandoned. The search
    concludes when all the characters from 'word' are processed.
    '''
    if not word:
        return True
    if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]) or\
            grid[row][col] != word[0]:
        return False
    return any([find_word(grid, row + x, col + y, word[1:])
                for x, y in KNIGHT_MOVES])


def word_lookup(grid, words):
    '''
    Main driver function for finding which words (from the list 'words')
    are present in the 'grid'.
    '''
    for word in words:
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == word[0]:
                    if find_word(grid, row, col, word):
                        return word


def normalize(data):
    '''
    Given an either a list of list or a list of string, it converts all the
    constituents to lowercase.
    '''
    if all([data, type(data) == list, type(data[0]) == list]):
        for row in range(len(data)):
            for col in range(len(data[0])):
                data[row][col] = data[row][col].lower()
    elif all([data, type(data) == list, type(data[0]) == str]):
        for i in range(len(data)):
            data[i] = data[i].lower()
    return data


def generate_words(fname):
    '''
    Provided the absolute file-path as 'fname', this functions breaks the
    contents into words and returns a dictionary where key is the length
    of words encountered and value is a set of words which are as long as
    the key.
    '''
    words = defaultdict(set)
    if isfile(fname):
        with open(fname) as file_input:
            for line in file_input:
                line = line.strip()
                if line:
                    for punc in punctuation:
                        line = line.replace(punc, '')
                    for word in findall(PATTERN, line):
                        words[len(word)].add(word.lower())
    return words

if __name__ == '__main__':
    GRID1 = [
      # Populate at will.
    ]

    WORDS1 = ["algol", "fortran", "simula"]
    GRID1 = normalize(GRID1)
    WORDS1 = normalize(WORDS1)
    print word_lookup(GRID1, sorted(WORDS1, key=len, reverse=True))

    GRID2 = [
       # Populate at will.
    ]

    if len(argv) == 2:
        WORDS2 = generate_words(argv[1])
        GRID2 = normalize(GRID2)
        for word_len in sorted(WORDS2, reverse=True):
            result = word_lookup(GRID2, WORDS2[word_len])
            if result:
                print result
                break
    else:
        print 'Invalid number of arguments passed. The program expects'
        print 'absolute file-path of the Love’s Labour’s Lost'