honeycomb_puzzle_bits.py

   1 # ---
   2 # jupyter:
   3 #   jupytext:
   4 #     formats: ipynb,py:light
   5 #     text_representation:
   6 #       extension: .py
   7 #       format_name: light
   8 #       format_version: '1.5'
   9 #       jupytext_version: 1.11.1
  10 #   kernelspec:
  11 #     display_name: Python 3 (ipykernel)
  12 #     language: python
  13 #     name: python3
  14 # ---
  15
  16 # # Honeycomb letter puzzle
  17 # 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/).
  18 #
  19
  20 import string
  21 import collections
  22 from dataclasses import dataclass
  23 import itertools
  24 import ctypes
  25 import cProfile
  26
  27 with open('enable1.txt') as f:
  28     words = [line.strip() for line in f]
  29
  30 words = set(w for w in words
  31             if len(w) >= 4
  32             if len(frozenset(w)) <= 7
  33             if 's' not in w)
  34
  35 word_sets = collections.defaultdict(set)
  36 for w in words:
  37     letters = frozenset(w)
  38     word_sets[letters].add(w)
  39
  40
  41 def encode(letters):
  42     encoded = 0
  43     for l in string.ascii_lowercase:
  44         encoded <<= 1
  45         if l in letters:
  46             encoded |= 1
  47     return encoded
  48
  49
  50 def decode(letter_bits):
  51     letters = set()
  52     for l in string.ascii_lowercase:
  53         e = encode(l)
  54         if (e & letter_bits):
  55             letters.add(l)
  56     return letters
  57
  58
  59 def subset(this, that):
  60     return this & that == this
  61
  62
  63 @dataclass(frozen=True, init=False)
  64 class Honeycomb():
  65     mandatory: int
  66     letters: int
  67
  68     def __init__(self, mandatory, letters):
  69         object.__setattr__(self, 'mandatory', encode(mandatory))
  70         object.__setattr__(self, 'letters', encode(letters))
  71
  72     def __repr__(self):
  73         return f'{"".join(decode(self.mandatory))}|{"".join(sorted(decode(self.letters) - set(decode(self.mandatory))))}'
  74
  75
  76 def present(target, honeycomb):
  77     return (subset(honeycomb.mandatory, target)
  78            and subset(target, honeycomb.letters))
  79
  80
  81 def score(present_set):
  82     score = 0
  83     for w in word_sets[present_set]:
  84         if len(w) == 4:
  85             score += 1
  86         else:
  87             score += len(w)
  88     if len(present_set) == 7:
  89         score += len(word_sets[present_set]) * 7
  90     return score
  91
  92
  93 scored_sets = {s: score(s) for s in word_sets}
  94 encoded_scored_sets = {encode(s): scored_sets[s] for s in scored_sets}
  95
  96
  97 def raw_score_honeycomb(honeycomb):
  98     return sum(sc for letters, sc in scored_sets.items()
  99                # if honeycomb.mandatory in letters
 100                # if letters.issubset(honeycomb.letters)
 101                if present(letters, honeycomb)
 102               )
 103
 104
 105 def score_honeycomb(honeycomb):
 106     return sum(sc for letters, sc in encoded_scored_sets.items()
 107                # if honeycomb.mandatory in letters
 108                # if letters.issubset(honeycomb.letters)
 109                if present(letters, honeycomb)
 110               )
 111
 112
 113 pangram_sets = [s for s in word_sets.keys() if len(s) == 7 if 's' not in s]
 114
 115 with open('pangaram_words.txt', 'w') as f:
 116     for s in pangram_sets:
 117         for w in word_sets[s]:
 118             f.write(f'{w}\n')
 119
 120 # +
 121 # ps_honeycombs = []
 122
 123 # for ps in pangram_sets:
 124 #     for mand in ps:
 125 #         ps_honeycombs.append(Honeycomb(mandatory=mand, letters=ps))
 126
 127 ps_honeycombs = [Honeycomb(mandatory=mand, letters=ps)
 128                  for ps in pangram_sets
 129                  for mand in ps]
 130 # -
 131
 132 partitioned_scored_sets = {encode(l): {s: encoded_scored_sets[s]
 133                                for s in encoded_scored_sets
 134                                if subset(encode(l), s)}
 135                            for l in string.ascii_lowercase}
 136
 137
 138 def partitioned_score_honeycomb(honeycomb):
 139     return sum(sc for letters, sc in partitioned_scored_sets[honeycomb.mandatory].items()
 140                if subset(letters, honeycomb.letters)
 141               )
 142
 143
 144 # +
 145 # # %%timeit
 146 best_honyecomb = max(ps_honeycombs, key=partitioned_score_honeycomb)
 147 print(best_honyecomb, partitioned_score_honeycomb(best_honyecomb))
 148 # -
 149
 150 # # %%timeit
 151 # best_honyecomb = max(ps_honeycombs, key=score_honeycomb)
 152 # print(best_honyecomb, score_honeycomb(best_honyecomb))
 153
 154 # +
 155 # cProfile.run('max(ps_honeycombs, key=score_honeycomb)')
 156
 157
 158 # +
 159 # cProfile.run('max(ps_honeycombs, key=partitioned_score_honeycomb)')
 160 # -
 161
 162