{
 "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
}