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 import cProfile
  25
  26 with open('enable1.txt') as f:
  27     words = [line.strip() for line in f]
  28
  29 words = set(w for w in words
  30             if len(w) >= 4
  31             if len(frozenset(w)) <= 7
  32             if 's' not in w)
  33
  34 word_sets = collections.defaultdict(set)
  35 for w in words:
  36     letters = frozenset(w)
  37     word_sets[letters].add(w)
  38
  39
  40 @dataclass(frozen=True)
  41 class Honeycomb():
  42     mandatory: str
  43     letters: frozenset
  44
  45     def __repr__(self):
  46         return f'{self.mandatory}|{"".join(sorted(self.letters - set(self.mandatory)))}'
  47
  48
  49 def present(target, honeycomb):
  50     return (   (honeycomb.mandatory in target)
  51            and target.issubset(honeycomb.letters)
  52            )
  53
  54
  55 def score(present_set):
  56     score = 0
  57     for w in word_sets[present_set]:
  58         if len(w) == 4:
  59             score += 1
  60         else:
  61             score += len(w)
  62     if len(present_set) == 7:
  63         score += len(word_sets[present_set]) * 7
  64     return score
  65
  66
  67 def score_honeycomb(honeycomb):
  68     return sum(sc for letters, sc in scored_sets.items()
  69                # if honeycomb.mandatory in letters
  70                # if letters.issubset(honeycomb.letters)
  71                if present(letters, honeycomb)
  72               )
  73
  74
  75 pangram_sets = [s for s in word_sets.keys() if len(s) == 7 if 's' not in s]
  76 print("pangram sets:", len(pangram_sets))
  77
  78 with open('pangaram_words.txt', 'w') as f:
  79     for s in pangram_sets:
  80         for w in word_sets[s]:
  81             f.write(f'{w}\n')
  82
  83 # +
  84 # ps_honeycombs = []
  85
  86 # for ps in pangram_sets:
  87 #     for mand in ps:
  88 #         ps_honeycombs.append(Honeycomb(mandatory=mand, letters=ps))
  89
  90 ps_honeycombs = [Honeycomb(mandatory=mand, letters=ps)
  91                  for ps in pangram_sets
  92                  for mand in ps]
  93 print(len(ps_honeycombs), "honeycombs")
  94 # -
  95
  96 partitioned_scored_sets = {l: {s: scored_sets[s] for s in scored_sets if l in s}
  97                            for l in string.ascii_lowercase}
  98
  99
 100 def partitioned_score_honeycomb(honeycomb):
 101     return sum(sc for letters, sc in partitioned_scored_sets[honeycomb.mandatory].items()
 102                if letters.issubset(honeycomb.letters)
 103               )
 104
 105
 106 # +
 107 # # # %%timeit
 108 best_honyecomb = max(ps_honeycombs, key=partitioned_score_honeycomb)
 109 print(best_honyecomb, partitioned_score_honeycomb(best_honyecomb))
 110 # -
 111
 112 # # %%timeit
 113 # best_honyecomb = max(ps_honeycombs, key=score_honeycomb)
 114 # print(best_honyecomb, partitioned_score_honeycomb(best_honyecomb))
 115
 116 # +
 117 # cProfile.run('max(ps_honeycombs, key=score_honeycomb)')
 118
 119
 120 # +
 121 # cProfile.run('max(ps_honeycombs, key=partitioned_score_honeycomb)')
 122 # -
 123
 124
 125