crosswordsearch3.py

#!/usr/bin/env python3
import marisa_trie
from functools import partial


def get_five_letter_words_from_file(filename, occurences):
    words = []
    revwords = []
    with open(filename, 'r') as file:
        next(file)  # Skip the header line
        for line in file:
            columns = line.split()
            if len(columns) < 2 or len(columns[1]) != 5 or int(columns[2].replace(",", "")) < occurences:  # Check if there's a word in the line
                continue
            word = columns[1].lower()
            words.append(word)
            revwords.append(word[::-1])
    return words, revwords

words, revwords = get_five_letter_words_from_file('frequency-alpha-alldicts.txt', 10000000)
wordset = set(words)

trie = marisa_trie.Trie(words)
revtrie = marisa_trie.Trie(revwords)

guesses = [
    ["penis", "poops", "farts", "boobs"],
    ["voice", "pitch", "music", "upper"],
    ["april", "march", "vowel", "nvmbr", "dcmbr"],
    ["tries", "lucky", "grind", "labor", "death"],
    ["drugs", "cable", "grind"]
]

# ones with guesses first
order = sorted(range(len(guesses)), key=lambda i: (len(guesses[i]) == 0, len(guesses[i])))

print(order)

across = [
    "     ",
    "     ",
    "     ",
    "     ",
    "     "
]

down = [
    "     ",
    "     ",
    "     ",
    "     ",
    "     "
]


def get_constraints(i, a):
    if a:
        return down[0][i] + down[1][i] + down[2][i] + down[3][i] + down[4][i]
    else:
        return across[0][i] + across[1][i] + across[2][i] + across[3][i] + across[4][i]


def filter_word(constraint, word):
    for i in range(len(constraint)):
        if constraint[i] != " " and word[i] != constraint[i]:
            return False
    return True


def get_words(constraint):
    if " " not in constraint:  # no spaces
        if constraint in wordset:
            return [constraint]
        else:
            return []
    if constraint == "     ":  # no constraints
        return words
    index_l = 0
    index_r = 4
    for i in range(5):  # see how many left letters there are (for trie)
        if constraint[i] == " ":
            break
        index_l = i+1
    if index_l >= 3:  # 4 or 5 letters
        return trie.keys(constraint[0:index_l])
    if index_l == 2:  # 3 letters
        if constraint[4] != " ":  # check if 5th letter present, filter if so
            return filter(lambda x: constraint[4] == x[4], trie.keys(constraint[0:index_l]))
        return trie.keys(constraint[0:index_l])
    for i in range(4, -1, -1):  # see how many right letters there are (for revtrie)
        if constraint[i] == " ":
            break
        index_r = i-1
    if index_r <= 0:  # 4 or 5 right letters
        return map(lambda x: x[::-1], revtrie.keys(constraint[index_r:4:-1]))
    if index_r == 1:  # 3 right letters
        if constraint[0] != " ":  # check if 1st letter is present, filter if so
            return filter(lambda x: constraint[0] == x[0], map(lambda x: x[::-1], revtrie.keys(constraint[index_r:4:-1])))
        return map(lambda x: x[::-1], revtrie.keys(constraint[index_r:4:-1]))
    if index_r == 2 and index_l == 2:  # hole in middle, do set intersection on each trie
        return set(trie.keys(constraint[0:index_l])).intersection(set(map(lambda x: x[::-1], revtrie.keys(constraint[index_r:4:-1]))))
    if index_l == 1:  # one left letter, filter the trie results with the constraint
        return filter(partial(filter_word, constraint), trie.keys(constraint[0]))
    if index_r == 3:  # one right letter, filter the revtrie results with the constraint
        return filter(partial(filter_word, constraint), map(lambda x: x[::-1], revtrie.keys(constraint[index_r:4:-1])))
    # all trie speedups failed, just filter all the words
    # these are cases with 1 or 2 letters in the middle of the constraint
    return filter(partial(filter_word, constraint), words)


def word_generator(constraint, priority_words):
    for word in priority_words:
        if filter_word(constraint, word):
            yield word
    yield from get_words(constraint)


constraints0a = get_constraints(order[0], True)
for word0a in word_generator(constraints0a, guesses[order[0]]):
    across[order[0]] = word0a
    constraints0d = get_constraints(order[0], False)
    for word0d in word_generator(constraints0d, guesses[order[0]]):
        if word0d == word0a:
            continue
        down[order[0]] = word0d

        constraints1a = get_constraints(order[1], True)
        for word1a in word_generator(constraints1a, guesses[order[1]]):
            across[order[1]] = word1a
            constraints1d = get_constraints(order[1], False)
            for word1d in word_generator(constraints1d, guesses[order[1]]):
                if word1d == word1a:
                    continue
                down[order[1]] = word1d

                constraints2a = get_constraints(order[2], True)
                for word2a in word_generator(constraints2a, guesses[order[2]]):
                    across[order[2]] = word2a
                    constraints2d = get_constraints(order[2], False)
                    for word2d in word_generator(constraints2d, guesses[order[2]]):
                        if word2d == word2a:
                            continue
                        down[order[2]] = word2d

                        constraints3a = get_constraints(order[3], True)
                        for word3a in word_generator(constraints3a, guesses[order[3]]):
                            across[order[3]] = word3a
                            constraints3d = get_constraints(order[3], False)
                            for word3d in word_generator(constraints3d, guesses[order[3]]):
                                if word3d == word3a:
                                    continue
                                down[order[3]] = word3d

                                constraints4a = get_constraints(order[4], True)
                                for word4a in word_generator(constraints4a, guesses[order[4]]):
                                    across[order[4]] = word4a
                                    constraints4d = get_constraints(order[4], False)
                                    for word4d in word_generator(constraints4d, guesses[order[4]]):
                                        if word4d == word4a:
                                            continue
                                        down[order[4]] = word4d
                                        print("\n".join(across))
                                        print("-----")
                                        # print("\n".join(down))
                                        # print("=====")
                                        down[order[4]] = "     "
                                    across[order[4]] = "     "
                                down[order[3]] = "     "
                            across[order[3]] = "     "
                        down[order[2]] = "     "
                    across[order[2]] = "     "
                down[order[1]] = "     "
            across[order[1]] = "     "
        down[order[0]] = "     "
    across[order[0]] = "     "