#!/usr/bin/env python3

import timeit
from copy import copy

letter_index = []
letters_ordered = []
solutions = []
bitv_to_words = {}
word_bits = []


def getbits(word):
    bitv = 0
    for c in word:
        bitv = bitv | (1 << (ord(c) - ord("a")))
    return bitv


def findwords(current_bitv: int, matched_words_i: int, matched_words: list[int], last_checked_letter: int, skipped: bool):
    global bitv_to_words, word_bits, solutions, letter_index, letters_ordered
    if matched_words_i == 5:
        solutions.append(copy(matched_words))
        return

    #new_matched_words = []
    for i in range(last_checked_letter, 26):
        letter = letters_ordered[i]
        letterv = 1 << letter
        if current_bitv & letterv:
            continue
        for w in letter_index[i]:
            if current_bitv & w:
                continue

            matched_words[matched_words_i] = w
            findwords(current_bitv | w, matched_words_i + 1, matched_words, i + 1, skipped)

        if skipped:
            break
        skipped = True


def main():
    global bitv_to_words, word_bits, solutions, letter_index, letters_ordered
    bitv_to_words = {}
    word_bits = []
    solutions = []
    letter_frequency = dict.fromkeys([chr(i + ord("a")) for i in range(26)], 0)
    with open("words_alpha.txt", encoding="utf-8") as f:
        for l in f.readlines():
            l = l.strip()
            if len(l) != 5:
                continue
            lower = l.lower()
            bitv = getbits(lower)
            # bit_count is Python 3.10 only
            #if bitv.bit_count() != 5:
            #    continue
            if bin(bitv).count("1") != 5:
                continue
            if bitv in bitv_to_words:
                continue
            bitv_to_words[bitv] = l
            word_bits.append(bitv)
            for c in l:
                letter_frequency[c] = letter_frequency[c] + 1
    ordered_letters = sorted(letter_frequency.keys(), key=letter_frequency.get)
    print(f"letter frequency (least to most): {ordered_letters}")
    reverse_ordered_letters = [0] * 26
    for i, l in enumerate(ordered_letters):
        reverse_ordered_letters[ord(l) - ord("a")] = i
    letters_ordered = list(map(lambda x: ord(x) - ord("a"), ordered_letters))

    letter_index = [[] for _ in range(26)]
    for w in word_bits:
        bin_str = bin(w)[2:]
        min_ = 27
        for i, b in enumerate(bin_str[::-1]):
            if b == "1":
                min_ = min(min_, reverse_ordered_letters[i])
        letter_index[min_].append(w)

    findwords(0, 0, [0]*5, 0, False)
    print(f"Found {len(solutions)} solutions")
    with open("solutions.txt", "w", encoding="utf-8") as f:
        for sol in solutions:
            f.write(" ".join(map(bitv_to_words.get, sol)))
            f.write("\n")
    print("Written solutions.txt")


if __name__ == "__main__":
    N = 5
    results = timeit.repeat(main, repeat=N, number=1)
    print(f"All results: {results}")
    print(f"Maximum run time: {max(results)} seconds")
    print(f"Minimum run time: {min(results)} seconds")