honeycomb_puzzle.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
  25
  26 def only_letters(text):
  27     return ''.join([c.lower() for c in text if c in string.ascii_letters])
  28
  29
  30 only_letters('Hell!o')
  31
  32 with open('/usr/share/dict/british-english') as f:
  33     words = [line.rstrip() for line in f]
  34 len(words)
  35
  36 with open('enable1.txt') as f:
  37     words = [line.rstrip() for line in f]
  38 len(words)
  39
  40 words = set(only_letters(w)
  41             for w in words
  42             if len(only_letters(w)) >= 4
  43             if len(frozenset(only_letters(w))) <= 7
  44             if 's' not in w)
  45
  46 len(words)
  47
  48 word_sets = collections.defaultdict(set)
  49 for w in words:
  50     letters = frozenset(w)
  51     word_sets[letters].add(w)
  52 len(word_sets)
  53
  54 word_sets[frozenset('elephant')]
  55
  56
  57 @dataclass(frozen=True)
  58 class Honeycomb():
  59     mandatory: str
  60     letters: frozenset
  61
  62     def __repr__(self):
  63         return f'{self.mandatory}|{"".join(sorted(self.letters - set(self.mandatory)))}'
  64
  65
  66 honeycomb = Honeycomb(mandatory='g', letters=frozenset('apxmelg'))
  67 honeycomb
  68
  69
  70 def present(honeycomb, target):
  71     return (honeycomb.mandatory in target) and target.issubset(honeycomb.letters)
  72
  73
  74 present_sets = [s for s in word_sets if present(honeycomb, s)]
  75 len(present_sets)
  76
  77 present_sets
  78
  79 for s in present_sets:
  80     print(word_sets[s])
  81
  82
  83 def score(present_set):
  84     score = 0
  85     for w in word_sets[present_set]:
  86         if len(w) == 4:
  87             score += 1
  88         else:
  89             score += len(w)
  90     if len(present_set) == 7:
  91         score += len(word_sets[present_set]) * 7
  92     return score
  93
  94
  95 sum(score(present_set) for present_set in present_sets)
  96
  97 set('megaplex') in words
  98
  99 scored_sets = {s: score(s) for s in word_sets}
 100
 101 for s in present_sets:
 102     print(s, word_sets[s], score(s), scored_sets[s])
 103
 104
 105 def score_honeycomb(honeycomb):
 106     return sum(sc for letters, sc in scored_sets.items()
 107                if honeycomb.mandatory in letters
 108                if letters.issubset(honeycomb.letters)
 109 #                if present(honeycomb, letters)
 110               )
 111
 112
 113 score_honeycomb(honeycomb)
 114
 115 # +
 116 # hcs = []
 117
 118 # for mand in 'abcde':
 119 #     remaining = set('abcde') - set(mand)
 120 #     for others in itertools.combinations(remaining, r=3):
 121 #         hcs.append(Honeycomb(mandatory=mand, letters=frozenset(others) | frozenset(mand)))
 122
 123 # print(len(hcs))
 124
 125 # +
 126 # hcs
 127
 128 # +
 129 # honeycombs = []
 130
 131 # for mand in string.ascii_lowercase:
 132 #     remaining = set(string.ascii_lowercase) - set(mand)
 133 #     for others in itertools.combinations(remaining, r=6):
 134 #         honeycombs.append(Honeycomb(mandatory=mand, letters=frozenset(others) | frozenset(mand)))
 135
 136 # print(len(honeycombs))
 137
 138 # +
 139 # honeycombs = []
 140
 141 # candidate_letters = set(string.ascii_lowercase)
 142 # candidate_letters.remove('s')
 143 # candidate_letters = frozenset(candidate_letters)
 144
 145 # for mand in candidate_letters:
 146 #     remaining = candidate_letters - set(mand)
 147 #     for others in itertools.combinations(remaining, r=6):
 148 #         honeycombs.append(Honeycomb(mandatory=mand, letters=frozenset(others) | frozenset(mand)))
 149
 150 # print(len(honeycombs))
 151
 152 # +
 153 # [(h, score_honeycomb(h)) for h in honeycombs[:5]]
 154
 155 # +
 156 # # %%timeit
 157 # max(honeycombs, key=score_honeycomb)
 158 # -
 159
 160 pangram_sets = [s for s in word_sets.keys() if len(s) == 7 if 's' not in s]
 161 len(pangram_sets)
 162
 163 # +
 164 ps_honeycombs = []
 165
 166 for ps in pangram_sets:
 167     for mand in ps:
 168         ps_honeycombs.append(Honeycomb(mandatory=mand, letters=ps))
 169
 170 print(len(ps_honeycombs))
 171
 172 # +
 173 # # %%timeit
 174 # max(ps_honeycombs, key=score_honeycomb)
 175
 176 # +
 177 ##  1 a,e,g,i,n,r,t r       3898
 178 ##  2 a,e,g,i,n,r,t n       3782
 179 ##  3 a,e,g,i,n,r,t e       3769
 180 # -
 181
 182 score_honeycomb(Honeycomb('r', frozenset('aeginrt')))
 183
 184 score_honeycomb(Honeycomb('n', frozenset('aeginrtn')))
 185
 186 score_honeycomb(Honeycomb('e', frozenset('aeginrte')))
 187
 188 partitioned_scored_sets = {l: {s: scored_sets[s] for s in scored_sets if l in s}
 189                            for l in string.ascii_lowercase}
 190 len(partitioned_scored_sets)
 191
 192
 193 def partitioned_score_honeycomb(honeycomb):
 194     return sum(sc for letters, sc in partitioned_scored_sets[honeycomb.mandatory].items()
 195                if letters.issubset(honeycomb.letters)
 196               )
 197
 198
 199 # # %%timeit
 200 print(max(ps_honeycombs, key=partitioned_score_honeycomb))
 201
 202 # +
 203 # partitioned_score_honeycomb(Honeycomb('a', 'abc'))
 204
 205 # +
 206 # max(len(partitioned_scored_sets[k]) for k in partitioned_scored_sets)
 207
 208 # +
 209 # len(scored_sets)
 210 # -
 211
 212