99 lines
3.0 KiB
Python
Executable File
99 lines
3.0 KiB
Python
Executable File
#!/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")
|