gistfile1.txt

from marisa_trie import Trie

valid_squares = []

def recurse():
    for row in row_words:
        yield from recurse_col((row,), (), 1, 0)

def recurse_row(rows, cols, y, x):
    for i in range(y, H):
        sofar = "".join(col[i] for col in cols)
        if not row_trie.has_keys_with_prefix(sofar):
            return
    if y == H:
        if x == W:
            yield rows, cols
        else:
            yield from recurse_col(rows, cols, y, x)
        return
    sofar = "".join(col[y] for col in cols)
    for row in row_trie.iterkeys(sofar):
        yield from recurse_col(rows+(row,), cols, y+1, x)

def recurse_col(rows, cols, y, x):
    for i in range(x, W):
        sofar = "".join(row[i] for row in rows)
        if not col_trie.has_keys_with_prefix(sofar):
            return
    if x == W:
        if y == H:
            yield rows, cols
        else:
            yield from recurse_row(rows, cols, y, x)
        return
    sofar = "".join(row[x] for row in rows)
    for col in col_trie.iterkeys(sofar):
        yield from recurse_row(rows, cols+(col,), y, x+1)

H, W = 5, 7

row_words = [
    word
    for word in open("enable2.txt").read().splitlines()
    if len(word) == W
]
col_words = [
    word
    for word in open("enable2.txt").read().splitlines()
    if len(word) == H
]
print(len(row_words), len(col_words))
row_words = row_words
col_words = col_words
row_trie = Trie(row_words)
col_trie = Trie(col_words)

N = 0
for rows, cols in recurse():
    N += 1
    if N % 10000 == 0:
        print(N)
    if W == H:
        print(int(rows == cols))
    for word in rows:
        print(word)
    print("")
    transpose = lambda rows: tuple("".join(row[x] for row in rows) for x in range(len(rows[0])))
    correct = rows == transpose(cols) and cols == transpose(rows)
    if not correct:
        print("huh")
        break
    break
    if N > 10 and 1:
        break