from __future__ import print_function
from collections import deque
from string import ascii_lowercase
from pprint import pprint
import re


def is_word(word_candidate):
    """
    Return true if the given candidate is a word.

    Namely, a candidate is a word if it comprises letters, and is
    optionally terminated with whitespace.
    """
    word_pattern = r'^\w+[\r\n\t ]*$'
    return (re.match(word_pattern, word_candidate) is not None)


def longest_word_of_subwords(wordset, **kwargs):
    start_words = kwargs.get('start_words', [("a", []),
                                             ("i", [])])
    longest_words = start_words
    Q = deque(start_words)

    while len(Q) > 0:
        t = Q.pop()
        w, parents = t
        if w in wordset:
            # update longest words if applicable
            if len(w) > len(longest_words[0][0]):
                longest_words = [t]
            elif len(w) == len(longest_words[0][0]):
                longest_words.append(t)

            for i in range(len(w)+1):
                for c in ascii_lowercase:
                    Q.append((''.join([w[:i], c, w[i:]]), parents + [w]))
    return longest_words

if __name__ == '__main__':
    with open('words.txt', 'r') as f:
        wordset = set([line.strip(' \t\r\n') for line in f if is_word(line)])
    # word list loading sanity check
    print('Number of words: %d' % (len(wordset),))
    print('Longest word: %d chars' % (max([len(w) for w in wordset]),))

    words = longest_word_of_subwords(wordset)
    pprint(words)
    print('yay!')
