X-Git-Url: https://git.njae.me.uk/?a=blobdiff_plain;f=honeycomb_puzzle_bits.py;fp=honeycomb_puzzle_bits.py;h=de0098ed9989a5f190c1e77bdb5333df9f83caec;hb=978aa4af1b4a8753d0cd04f7fcceaf6d899bca79;hp=0000000000000000000000000000000000000000;hpb=68b4df6b83ce0f6bea2379d3f46d7296dd36a3c9;p=honeycomb-puzzle.git

diff --git a/honeycomb_puzzle_bits.py b/honeycomb_puzzle_bits.py
new file mode 100644
index 0000000..de0098e
--- /dev/null
+++ b/honeycomb_puzzle_bits.py
@@ -0,0 +1,162 @@
+# ---
+# jupyter:
+#   jupytext:
+#     formats: ipynb,py:light
+#     text_representation:
+#       extension: .py
+#       format_name: light
+#       format_version: '1.5'
+#       jupytext_version: 1.11.1
+#   kernelspec:
+#     display_name: Python 3 (ipykernel)
+#     language: python
+#     name: python3
+# ---
+
+# # Honeycomb letter puzzle
+# Solving the puzzle as posted on [FiveThirtyEight](https://fivethirtyeight.com/features/can-you-solve-the-vexing-vexillology/), also solved by [David Robinson](http://varianceexplained.org/r/honeycomb-puzzle/).
+#
+
+import string
+import collections
+from dataclasses import dataclass
+import itertools
+import ctypes
+import cProfile
+
+with open('enable1.txt') as f:
+    words = [line.strip() for line in f]
+
+words = set(w for w in words 
+            if len(w) >= 4
+            if len(frozenset(w)) <= 7
+            if 's' not in w)
+
+word_sets = collections.defaultdict(set)
+for w in words:
+    letters = frozenset(w)
+    word_sets[letters].add(w)
+
+
+def encode(letters):
+    encoded = 0
+    for l in string.ascii_lowercase:
+        encoded <<= 1
+        if l in letters:
+            encoded |= 1
+    return encoded
+
+
+def decode(letter_bits):
+    letters = set()
+    for l in string.ascii_lowercase:
+        e = encode(l)
+        if (e & letter_bits):
+            letters.add(l)
+    return letters
+
+
+def subset(this, that):
+    return this & that == this
+
+
+@dataclass(frozen=True, init=False)
+class Honeycomb():
+    mandatory: int
+    letters: int
+    
+    def __init__(self, mandatory, letters):
+        object.__setattr__(self, 'mandatory', encode(mandatory))
+        object.__setattr__(self, 'letters', encode(letters))
+            
+    def __repr__(self):
+        return f'{"".join(decode(self.mandatory))}|{"".join(sorted(decode(self.letters) - set(decode(self.mandatory))))}'
+
+
+def present(target, honeycomb):
+    return (subset(honeycomb.mandatory, target)
+           and subset(target, honeycomb.letters))
+
+
+def score(present_set):
+    score = 0
+    for w in word_sets[present_set]:
+        if len(w) == 4:
+            score += 1
+        else:
+            score += len(w)
+    if len(present_set) == 7:
+        score += len(word_sets[present_set]) * 7
+    return score
+
+
+scored_sets = {s: score(s) for s in word_sets}
+encoded_scored_sets = {encode(s): scored_sets[s] for s in scored_sets}
+
+
+def raw_score_honeycomb(honeycomb):
+    return sum(sc for letters, sc in scored_sets.items() 
+               # if honeycomb.mandatory in letters
+               # if letters.issubset(honeycomb.letters)
+               if present(letters, honeycomb)
+              )
+
+
+def score_honeycomb(honeycomb):
+    return sum(sc for letters, sc in encoded_scored_sets.items() 
+               # if honeycomb.mandatory in letters
+               # if letters.issubset(honeycomb.letters)
+               if present(letters, honeycomb)
+              )
+
+
+pangram_sets = [s for s in word_sets.keys() if len(s) == 7 if 's' not in s]
+
+with open('pangaram_words.txt', 'w') as f:
+    for s in pangram_sets:
+        for w in word_sets[s]:
+            f.write(f'{w}\n')
+
+# +
+# ps_honeycombs = []
+
+# for ps in pangram_sets:
+#     for mand in ps:
+#         ps_honeycombs.append(Honeycomb(mandatory=mand, letters=ps))
+
+ps_honeycombs = [Honeycomb(mandatory=mand, letters=ps) 
+                 for ps in pangram_sets
+                 for mand in ps]
+# -
+
+partitioned_scored_sets = {encode(l): {s: encoded_scored_sets[s] 
+                               for s in encoded_scored_sets 
+                               if subset(encode(l), s)}
+                           for l in string.ascii_lowercase}
+
+
+def partitioned_score_honeycomb(honeycomb):
+    return sum(sc for letters, sc in partitioned_scored_sets[honeycomb.mandatory].items() 
+               if subset(letters, honeycomb.letters)
+              )
+
+
+# +
+# # %%timeit
+best_honyecomb = max(ps_honeycombs, key=partitioned_score_honeycomb)
+print(best_honyecomb, partitioned_score_honeycomb(best_honyecomb))
+# -
+
+# # %%timeit
+# best_honyecomb = max(ps_honeycombs, key=score_honeycomb)
+# print(best_honyecomb, score_honeycomb(best_honyecomb))
+
+# +
+# cProfile.run('max(ps_honeycombs, key=score_honeycomb)')
+
+
+# +
+# cProfile.run('max(ps_honeycombs, key=partitioned_score_honeycomb)')
+# -
+
+