letterboxed.py

# heinous zen koan: solve problem with as few indents as possible
import sys
import numpy as np
import itertools

def solve(puzzle):
    other_sides = [set(puzzle[(i+1)%4] + puzzle[(i+2)%4] + puzzle[(i+3)%4]) for i in range(4)]
    letter_neighbors = {letter: other_sides[index] for (index, side_string) in enumerate(puzzle) for letter in side_string}
    constructible = lambda word: len(word) >= 3 and all([(first in letter_neighbors) and (second in letter_neighbors[first]) for (first, second) in zip(word, word[1:])])
    constructible_words = set(filter(constructible, map(lambda x: x.rstrip(), open('dictionary.txt', 'r'))))
    dominates = lambda first, second: first[0] == second[0] and first[-1] == second[-1] and all([c in first for c in second])
    dominated_words = set([second for (first, second) in itertools.permutations(constructible_words, 2) if dominates(first, second)])
    words = sorted(constructible_words - dominated_words)
    letters_index = {c: i for (i, c) in enumerate(sorted("".join(puzzle)))}
    bitsets = [np.bitwise_or.reduce([(1 << letters_index[c]) for c in word]) for word in words]
    graph = {i: set([j for j in range(len(words)) if i != j and words[i][-1] == words[j][0]]) for i in range(len(words))}
    paths = lambda node, depth: [[node]] if depth == 0 else [[node] + path for neighbor in graph[node] for path in paths(neighbor, depth-1) if node not in path]
    depth = 1
    while True:
        for path in (path_collection for root in graph.keys() for path_collection in paths(root, depth)):
            value = np.bitwise_or.reduce([bitsets[element] for element in path])
            if value >= 4095:
                print([words[ix] for ix in path])
                return
        depth += 1

if __name__ == "__main__":
    if len(sys.argv) != 5:
        print("Input format: python3 letterboxed.py [TOP] [RIGHT] [BOTTOM] [LEFT]")
        exit(0)
    solve(sys.argv[1:])

# mrdmnd@DESKTOP-L66AT6T:~$ python3 letterboxed.py INP VEX AMR TOH
# ['PHENOMENA', 'AVIATRIX']