word box

word_box.py

from copy import deepcopy
from collections import defaultdict
import random
import time

def load_dictionary():
    with open('dictionary.txt', mode='r') as fh:
        result = [w.strip() for w in fh]
    return result

def bucket_words(words, size):
    '''
    Bucket the words of len = size, by prefix for quicker finding later
    '''
    result = defaultdict(list)
    for word in words:
        if len(word) != size:
            continue
        for length in range(1,size):
            slice = word[0:length]
            result[slice].append(word)

    return result

def build_prefix(base):
    '''
    to make sure the words all align, new words need to begin with 
    the letters in each row, picked at the overall len of the base
    '''
    return ''.join(r[len(base)] for r in base)


def build(buckets, base):
    '''
    recursively build matrix
    takes list of base words and adds a new one of equal length and
    appropriate prefix
    '''
    size = len(base[-1])
    if len(base) == size:
        # got a square so we are done
        yield base
    else:
        prefix = build_prefix(base)
        for word in buckets[prefix]:
            if word in base:
                continue # skip words already in the matrix
            check = deepcopy(base)
            check.append(word)
            for result in build(buckets, check):
                yield result


def main():
    print('loading dictionary')
    words = load_dictionary()
    pick = random.choice(words)
    start = time.time()
    print('building from {}'.format(pick))
    print('loading buckets')
    buckets = bucket_words(words, len(pick))
    print('finding solutions')
    for count, solution in enumerate(build(buckets, [pick])):
        print('*--------*')
        print('\n'.join(solution))
        if count>10:
            break
    else:
        print('-> no solutions found')

    print('took {:2f}'.format(time.time()-start))

if __name__ == '__main__':
    main()