{
"cells": [
{
"cell_type": "markdown",
"id": "951180ec",
"metadata": {},
"source": [
"# Honeycomb letter puzzle\n",
"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/).\n"
]
},
{
"cell_type": "code",
"execution_count": 45,
"id": "6f6fa3e7",
"metadata": {},
"outputs": [],
"source": [
"import string\n",
"import collections\n",
"from dataclasses import dataclass\n",
"import itertools\n",
"import cProfile"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "88f00e4c",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"172820"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"with open('enable1.txt') as f:\n",
" words = [line.strip() for line in f]"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "1e75fba2",
"metadata": {},
"outputs": [],
"source": [
"words = set(w for w in words \n",
" if len(w) >= 4\n",
" if len(frozenset(w)) <= 7\n",
" if 's' not in w)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "e1f9b35e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"21661"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"word_sets = collections.defaultdict(set)\n",
"for w in words:\n",
" letters = frozenset(w)\n",
" word_sets[letters].add(w)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "267130ba",
"metadata": {},
"outputs": [],
"source": [
"@dataclass(frozen=True)\n",
"class Honeycomb():\n",
" mandatory: str\n",
" letters: frozenset\n",
" \n",
" def __repr__(self):\n",
" return f'{self.mandatory}|{\"\".join(sorted(self.letters - set(self.mandatory)))}'"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "bb848e88",
"metadata": {},
"outputs": [],
"source": [
"def present(target, honeycomb):\n",
" return ( (honeycomb.mandatory in target) \n",
" and target.issubset(honeycomb.letters)\n",
" )"
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "3c6f212e",
"metadata": {},
"outputs": [],
"source": [
"def score(present_set):\n",
" score = 0\n",
" for w in word_sets[present_set]:\n",
" if len(w) == 4:\n",
" score += 1\n",
" else:\n",
" score += len(w)\n",
" if len(present_set) == 7:\n",
" score += len(word_sets[present_set]) * 7\n",
" return score"
]
},
{
"cell_type": "code",
"execution_count": 22,
"id": "78d423a5",
"metadata": {},
"outputs": [],
"source": [
"def score_honeycomb(honeycomb):\n",
" return sum(sc for letters, sc in scored_sets.items() \n",
" # if honeycomb.mandatory in letters\n",
" # if letters.issubset(honeycomb.letters)\n",
" if present(letters, honeycomb)\n",
" )"
]
},
{
"cell_type": "code",
"execution_count": 30,
"id": "febee1c1",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"pangram sets: 7986\n"
]
}
],
"source": [
"pangram_sets = [s for s in word_sets.keys() if len(s) == 7 if 's' not in s]\n",
"print(\"pangram sets:\", len(pangram_sets))"
]
},
{
"cell_type": "code",
"execution_count": 31,
"id": "54a06bdf",
"metadata": {},
"outputs": [],
"source": [
"with open('pangaram_words.txt', 'w') as f:\n",
" for s in pangram_sets:\n",
" for w in word_sets[s]:\n",
" f.write(f'{w}\\n')"
]
},
{
"cell_type": "code",
"execution_count": 32,
"id": "007d3404",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"55902 honeycombs\n"
]
}
],
"source": [
"# ps_honeycombs = []\n",
"\n",
"# for ps in pangram_sets:\n",
"# for mand in ps:\n",
"# ps_honeycombs.append(Honeycomb(mandatory=mand, letters=ps))\n",
"\n",
"ps_honeycombs = [Honeycomb(mandatory=mand, letters=ps) \n",
" for ps in pangram_sets\n",
" for mand in ps]\n",
"print(len(ps_honeycombs), \"honeycombs\")"
]
},
{
"cell_type": "code",
"execution_count": 38,
"id": "914fece8",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"26"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"partitioned_scored_sets = {l: {s: scored_sets[s] for s in scored_sets if l in s} \n",
" for l in string.ascii_lowercase}"
]
},
{
"cell_type": "code",
"execution_count": 39,
"id": "f1454ccd",
"metadata": {},
"outputs": [],
"source": [
"def partitioned_score_honeycomb(honeycomb):\n",
" return sum(sc for letters, sc in partitioned_scored_sets[honeycomb.mandatory].items() \n",
" if letters.issubset(honeycomb.letters)\n",
" )"
]
},
{
"cell_type": "code",
"execution_count": 40,
"id": "7380dbd6",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"r|aegint 3898\n",
"r|aegint 3898\n",
"r|aegint 3898\n",
"r|aegint 3898\n",
"r|aegint 3898\n",
"r|aegint 3898\n",
"r|aegint 3898\n",
"r|aegint 3898\n",
"1min 25s ± 2.51 s per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
]
}
],
"source": [
"# # %%timeit\n",
"# best_honyecomb = max(ps_honeycombs, key=partitioned_score_honeycomb)\n",
"# print(best_honyecomb, partitioned_score_honeycomb(best_honyecomb))"
]
},
{
"cell_type": "code",
"execution_count": 44,
"id": "0239b444-1240-4744-8547-c41367527785",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"r|aegint 3898\n",
"r|aegint 3898\n",
"r|aegint 3898\n",
"r|aegint 3898\n",
"r|aegint 3898\n",
"r|aegint 3898\n",
"r|aegint 3898\n",
"r|aegint 3898\n",
"5min 38s ± 4.58 s per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
]
}
],
"source": [
"# %%timeit\n",
"best_honyecomb = max(ps_honeycombs, key=score_honeycomb)\n",
"print(best_honyecomb, partitioned_score_honeycomb(best_honyecomb))"
]
},
{
"cell_type": "code",
"execution_count": 46,
"id": "7e4173b4-26a9-4198-b572-d57db321fe94",
"metadata": {
"lines_to_next_cell": 2
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1612136594 function calls in 589.284 seconds\n",
"\n",
" Ordered by: standard name\n",
"\n",
" ncalls tottime percall cumtime percall filename:lineno(function)\n",
" 55902 0.316 0.000 589.070 0.011 1101428662.py:1(score_honeycomb)\n",
" 1846420 257.034 0.000 588.167 0.000 1101428662.py:2(<genexpr>)\n",
"1210893222 276.103 0.000 331.132 0.000 1250517269.py:1(present)\n",
" 1 0.000 0.000 589.284 589.284 <string>:1(<module>)\n",
" 1 0.000 0.000 589.284 589.284 {built-in method builtins.exec}\n",
" 1 0.214 0.214 589.284 589.284 {built-in method builtins.max}\n",
" 55902 0.567 0.000 588.733 0.011 {built-in method builtins.sum}\n",
" 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
"399229242 55.030 0.000 55.030 0.000 {method 'issubset' of 'frozenset' objects}\n",
" 55902 0.021 0.000 0.021 0.000 {method 'items' of 'dict' objects}\n",
"\n",
"\n"
]
}
],
"source": [
"# cProfile.run('max(ps_honeycombs, key=score_honeycomb)')"
]
},
{
"cell_type": "code",
"execution_count": 47,
"id": "8f2de1b8-6a09-44eb-af7b-3e16c902859f",
"metadata": {
"lines_to_next_cell": 2
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 401243372 function calls in 150.954 seconds\n",
"\n",
" Ordered by: standard name\n",
"\n",
" ncalls tottime percall cumtime percall filename:lineno(function)\n",
" 55902 0.226 0.000 150.835 0.003 346452243.py:1(partitioned_score_honeycomb)\n",
" 1846420 86.829 0.000 150.189 0.000 346452243.py:2(<genexpr>)\n",
" 1 0.000 0.000 150.954 150.954 <string>:1(<module>)\n",
" 1 0.000 0.000 150.954 150.954 {built-in method builtins.exec}\n",
" 1 0.119 0.119 150.954 150.954 {built-in method builtins.max}\n",
" 55902 0.407 0.000 150.596 0.003 {built-in method builtins.sum}\n",
" 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
"399229242 63.360 0.000 63.360 0.000 {method 'issubset' of 'frozenset' objects}\n",
" 55902 0.013 0.000 0.013 0.000 {method 'items' of 'dict' objects}\n",
"\n",
"\n"
]
}
],
"source": [
"# cProfile.run('max(ps_honeycombs, key=partitioned_score_honeycomb)')"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4c3a5684-346b-4cf7-b238-391f9a6ba2dd",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"jupytext": {
"formats": "ipynb,py:light"
},
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.8"
}
},
"nbformat": 4,
"nbformat_minor": 5
}