ipynb/Countdown.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"float:right\"><i>Peter Norvig<br>5 January 2016<br>revised 18 May 2018</i></span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "# Four 4s, Five 5s, and Countdown to 2016\n",
    "\n",
    "On January 1, 2016 Alex Bellos [posed](http://www.theguardian.com/science/2016/jan/04/can-you-solve-it-complete-the-equation-10-9-8-7-6-5-4-3-2-1-2016) this New Year's puzzle:\n",
    "\n",
    "\n",
    "> Fill in the blanks so that this equation makes arithmetical sense:\n",
    ">\n",
    "> `10 ␣ 9 ␣ 8 ␣ 7 ␣ 6 ␣ 5 ␣ 4 ␣ 3 ␣ 2 ␣ 1 = 2016`\n",
    ">\n",
    "> You are allowed to use *only* the four basic arithmetical operations: +, -, &times;, ÷. But brackets (parentheses) can be used wherever needed. So, for example, the solution could begin\n",
    ">\n",
    "> `(10 + 9) * (8` ...  or  `10 + (9 * 8)` ...\n",
    "\n",
    "Let's see if we can solve this puzzle, and some of the related ones from Alex's [first](http://www.theguardian.com/science/2016/jan/04/can-you-solve-it-complete-the-equation-10-9-8-7-6-5-4-3-2-1-2016) and [second](http://www.theguardian.com/science/2016/jan/04/did-you-solve-it-complete-the-equation-10-9-8-7-6-5-4-3-2-1-2016) post.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "# Four Operations, No Brackets\n",
    "\n",
    "We'll start with a  simpler version of the puzzle: a countdown with no brackets.   \n",
    "\n",
    "There are nine blanks,  each of which can be filled by one of four operators, so there are 9<sup>4</sup> = 262,144 possibilities, few enough that we can enumerate them all, using `itertools.product` to get sequences of operators, and then `str.format` to plug them into blanks, and then `eval` to evaluate the string:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "from functools import lru_cache # Used later\n",
    "from collections import Counter, defaultdict # Used later"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('+', '+', '+', '+', '+', '+', '+', '+', '+')"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ops = next(product(('+', '-', '*', '/'), repeat=9))\n",
    "ops"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'10+9+8+7+6+5+4+3+2+1'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'10{}9{}8{}7{}6{}5{}4{}3{}2{}1'.format(*ops)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eval(_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to catch errors such as dividing by zero, so I'll define a wrapper function, `evaluate`, to do that, and I'll define `simple_countdown` to put the pieces together:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "def evaluate(exp):\n",
    "    \"eval(exp), or None if there is an arithmetic error.\"\n",
    "    try:\n",
    "        return eval(exp)\n",
    "    except ArithmeticError:\n",
    "        return None\n",
    "\n",
    "def simple_countdown(target, operators=('+', '-', '*', '/')):\n",
    "    \"All solutions to the countdown puzzle (with no brackets).\"\n",
    "    exps = ('10{}9{}8{}7{}6{}5{}4{}3{}2{}1'.format(*ops)\n",
    "            for ops in product(operators, repeat=9))\n",
    "    return [exp for exp in exps if evaluate(exp) == target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "simple_countdown(2016)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "Too bad; we did all that work and didn't find a solution. What years *can* we find solutions for? I'll modify `simple_countdown` to take a collection of target years rather than a single one, and return a dict of the form `{year: 'expression'}` for each expression that evaluates to one of the target years. I'll also generalize it to allow any format string, not just the countdown string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1981: '10*9*8+7*6*5*4*3/2+1',\n",
       " 1979: '10*9*8+7*6*5*4*3/2-1',\n",
       " 1980: '10*9*8+7*6*5*4*3/2/1',\n",
       " 2019: '10*9*8*7/6/5*4*3+2+1',\n",
       " 2017: '10*9*8*7/6/5*4*3+2-1',\n",
       " 2018: '10*9*8*7/6/5*4*3+2/1',\n",
       " 2015: '10*9*8*7/6/5*4*3-2+1',\n",
       " 2013: '10*9*8*7/6/5*4*3-2-1',\n",
       " 2014: '10*9*8*7/6/5*4*3-2/1'}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def simple_countdown(targets, operators=('+', '-', '*', '/'), \n",
    "                      fmt='10{}9{}8{}7{}6{}5{}4{}3{}2{}1'):\n",
    "    \"All solutions to the countdown puzzle (with no brackets).\"\n",
    "    exps = (fmt.format(*ops)\n",
    "            for ops in product(operators, repeat=fmt.count('{}')))\n",
    "    return {int(evaluate(exp)): exp for exp in exps if evaluate(exp) in targets}\n",
    "\n",
    "simple_countdown(range(1900, 2100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "Interesting: in the 20th and 21st centuries, there are only two \"golden eras\" where the bracketless countdown equation works: the three year period centered on 1980, and the seven year period that is centered on 2016, but omits 2016. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "# Four Operations, With Brackets\n",
    "\n",
    "Now we return to the original problem. Can I make use of what I have so far? Well, my second version of `simple_countdown` accepts different format strings, so I could give it all possible bracketed format strings and let it fill in all possible operator combinations. How long would that take? I happen to remember that the number of bracketings of *n* operands is the nth [Catalan number](https://oeis.org/A000108), which I looked up and found to be 4862. A single call to `simple_countdown` took about 2 seconds, so we could do 4862 calls in about 160 minutes. That's not terrible, but (a) it would still take work to generate all the bracketings, and (b) I think I can find another way that is much faster.\n",
    "\n",
    "I'll restate the problem as: given the sequence of numbers (10, 9, ... 1), create an expression whose value is 2016.\n",
    "But to get there I'll solve a more general problem: given any sequence of numbers, like `(10, 9, 8)`, what `{value: expression}` pairs can I make with them?\n",
    "I'll define  `expressions(numbers)` to return a dict of `{value: expression}` \n",
    "for all expressions (strings) whose numeric value is `value`, and can be made from `numbers`, for example:\n",
    "\n",
    "    expressions((10,)) ⇒ {10: '10'}\n",
    "    expressions((9, 8)) ⇒ {1: '(9-8)', 1.125: '(9/8)', 17: '(9+8)', 72: '(9*8)'}\n",
    "\n",
    "I'll use the idea of [dynamic programming](https://en.wikipedia.org/wiki/Dynamic_programming): break the problem down into simpler subparts, compute an answer for each subpart, and remember intermediate results so we don't need to re-compute them later. How do we break the problem into parts? `expressions((10, 9, 8))` should consist of all the ways of splitting `(10, 9, 8)` into two parts, finding all the expressions that can be made with each part, and combining pairs of expressions with any of the four operators:\n",
    "\n",
    "    expressions((10, 9, 8)) ⇒ {11: '(10+(9-8))', 27: '(10+(9+8))', 720: '(10*(9*8))', ...}\n",
    "\n",
    "First the function `splits`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "c10 = (10, 9, 8, 7, 6, 5, 4, 3, 2, 1)\n",
    "\n",
    "def splits(sequence):\n",
    "    \"Split sequence into two non-empty parts, in all ways.\"\n",
    "    return [(sequence[:i], sequence[i:]) \n",
    "            for i in range(1, len(sequence))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[((10,), (9, 8, 7, 6, 5, 4, 3, 2, 1)),\n",
       " ((10, 9), (8, 7, 6, 5, 4, 3, 2, 1)),\n",
       " ((10, 9, 8), (7, 6, 5, 4, 3, 2, 1)),\n",
       " ((10, 9, 8, 7), (6, 5, 4, 3, 2, 1)),\n",
       " ((10, 9, 8, 7, 6), (5, 4, 3, 2, 1)),\n",
       " ((10, 9, 8, 7, 6, 5), (4, 3, 2, 1)),\n",
       " ((10, 9, 8, 7, 6, 5, 4), (3, 2, 1)),\n",
       " ((10, 9, 8, 7, 6, 5, 4, 3), (2, 1)),\n",
       " ((10, 9, 8, 7, 6, 5, 4, 3, 2), (1,))]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "splits(c10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "Now the function `expressions`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "@lru_cache(None)\n",
    "def expressions(numbers: tuple) -> dict:\n",
    "    \"Return {value: expr} for all expressions that can be made from numbers.\"\n",
    "    if len(numbers) == 1: \n",
    "        return {numbers[0]: str(numbers[0])}\n",
    "    else: \n",
    "        result = {}\n",
    "        for (Lnums, Rnums) in splits(numbers):\n",
    "            for (L, R) in product(expressions(Lnums), expressions(Rnums)):\n",
    "                Lexp =  '(' + expressions(Lnums)[L]\n",
    "                Rexp =        expressions(Rnums)[R] + ')'\n",
    "                result[L * R] = Lexp + '*' + Rexp\n",
    "                result[L - R] = Lexp + '-' + Rexp\n",
    "                result[L + R] = Lexp + '+' + Rexp\n",
    "                if R != 0: \n",
    "                    result[L / R] = Lexp + '/' + Rexp\n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "For example, at one point in a call to `expressions((10, 9, 8))` we would have:\n",
    "\n",
    "     Lnums, Rnums = (10),   (9, 8)\n",
    "     L,     R     = 10,     1\n",
    "     Lexp,  Rexp  = '(10',  '(9-8))'\n",
    "\n",
    "This would lead to us adding the following four entries to `result`:\n",
    "\n",
    "     result[10] = '(10*(9-8))'\n",
    "     result[9]  = '(10-(9-8))'\n",
    "     result[11] = '(10+(9-8))'\n",
    "     result[10] = '(10/(9-8))'\n",
    "     \n",
    "The decorator `@lru_cache` takes care of storing the intermediate results. Rather than catching errors, we just avoid division by 0.\n",
    "\n",
    "Let's give it a try:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{10: '10'}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expressions((10,))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{72: '(9*8)', 1: '(9-8)', 17: '(9+8)', 1.125: '(9/8)'}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expressions((9, 8))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{720: '((10*9)*8)',\n",
       " -62: '(10-(9*8))',\n",
       " 82: '((10*9)-8)',\n",
       " 0.1388888888888889: '((10/9)/8)',\n",
       " 10: '(10/(9-8))',\n",
       " 9: '((10-9)+8)',\n",
       " 11: '((10+9)-8)',\n",
       " 170: '(10*(9+8))',\n",
       " -7: '((10-9)-8)',\n",
       " 27: '((10+9)+8)',\n",
       " 0.5882352941176471: '(10/(9+8))',\n",
       " 11.25: '((10*9)/8)',\n",
       " 8.875: '(10-(9/8))',\n",
       " 11.125: '(10+(9/8))',\n",
       " 8.88888888888889: '((10/9)*8)',\n",
       " 98: '((10*9)+8)',\n",
       " 8: '((10-9)*8)',\n",
       " 0.125: '((10-9)/8)',\n",
       " 152: '((10+9)*8)',\n",
       " 2.375: '((10+9)/8)',\n",
       " -6.888888888888889: '((10/9)-8)',\n",
       " 9.11111111111111: '((10/9)+8)'}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expressions((10, 9, 8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "That looks reasonable. Let's solve the whole puzzle.\n",
    "\n",
    "# Countdown to 2016: A Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 29.9 s, sys: 833 ms, total: 30.7 s\n",
      "Wall time: 30.8 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'(((((((((10*9)+8)*7)-6)-5)-4)*3)+2)+1)'"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time expressions(c10)[2016]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "We have an answer! And in seconds, not hours, thanks to dynamic programming! Here are solutions for nearby years:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{2010: '((((((10+(((9*8)-7)*6))*5)+4)+3)+2)+1)',\n",
       " 2011: '((((((10+9)*8)+7)*(6+(5*(4/3))))-2)-1)',\n",
       " 2012: '((((((10+9)*8)+7)*(6+(5*(4/3))))-2)/1)',\n",
       " 2013: '((((((10+9)*8)+7)*(6+(5*(4/3))))-2)+1)',\n",
       " 2014: '(((((((10+((9*8)*7))-6)-5)*4)+3)-2)+1)',\n",
       " 2015: '(((((((((10*9)+8)*7)-6)-5)-4)*3)+2)/1)',\n",
       " 2016: '(((((((((10*9)+8)*7)-6)-5)-4)*3)+2)+1)',\n",
       " 2017: '(((10*(((9*8)-((7*6)/(5+4)))*3))-2)-1)',\n",
       " 2018: '(((10*(((9*8)-((7*6)/(5+4)))*3))-2)/1)',\n",
       " 2019: '(((10*(((9*8)-((7*6)/(5+4)))*3))-2)+1)',\n",
       " 2020: '(((((10+((9+((8+7)*6))*5))*4)+3)-2)-1)',\n",
       " 2021: '((((((((10-9)+(8*7))*6)-5)*4)*3)/2)-1)',\n",
       " 2022: '((((((((10-9)+(8*7))*6)-5)*4)*3)/2)/1)',\n",
       " 2023: '(((((((10*9)*(8+7))/6)*(5+4))-3)+2)-1)',\n",
       " 2024: '(((((((10*9)*(8+7))/6)*(5+4))-3)+2)/1)',\n",
       " 2025: '(((((((10*9)*(8+7))/6)*(5+4))-3)+2)+1)'}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{y: expressions(c10)[y] for y in range(2010, 2026)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "# Counting Solutions\n",
    "\n",
    "Alex Bellos had another challenge:  \n",
    "\n",
    "> I was half hoping a computer scientist would let me know exactly how many solutions [to the Countdown problem] there are with only the four basic operations. Maybe someone will. \n",
    "\n",
    "As it stands, my program can't answer that question, because I only keep one expression for each value. \n",
    "\n",
    "Also, I'm not sure what it means to be a distinct solution. For example, are `((10+9)+8)` and `(10+(9+8))` different, or are they same, because they both are equivalent to `(10+9+8)`? Similarly, are `((3-2)-1)` and `(3-(2+1)` different, or the same because they both are equivalent to `(3 + -2 + -1)`? I think the notion of \"distinct solution\" is just inherently ambiguous. My choice is to count each of these as distinct: every expression has exactly ten numbers, nine operators, and nine pairs of brackets, and if an expression differs in any character, it is different. But I won't argue with anyone who prefers a different definition of \"distinct solution.\"\n",
    "\n",
    "So how can I count expressions? One approach would be to go back to enumerating every equation (all 4862 &times; 4<sup>9</sup> = 1.2 bilion of them) and checking which ones equal 2016. That would take about 40 hours with my Python program. A better approach is to mimic `expressions`, but to make a table of counts, rather than expression strings. I want:\n",
    "\n",
    "    counts[(10, 9, 8)][27] == 2\n",
    "    \n",
    "because there are 2 ways to make 27 with the numbers `(10, 9, 8)`, namely, `((10+9)+8)` and `(10+(9+8))`. And in general, if there are `Lcount` ways to make `L` using `Lnums` and `Rcount` ways to make `R` using `Rnums` then there are `Lcount * Rcount` ways of making `L * R` using `Lnums` followed by `Rnums`. So we have:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "@lru_cache(None)\n",
    "def counts(numbers: tuple) -> Counter:\n",
    "    \"Return a Counter of {value: count} for every value that can be made from numbers.\"\n",
    "    if len(numbers) == 1: # Only one way to make an expression out of a single number\n",
    "        return Counter(numbers)\n",
    "    else: \n",
    "        result = Counter()\n",
    "        for (Lnums, Rnums) in splits(numbers):\n",
    "            for L in counts(Lnums):\n",
    "                for R in counts(Rnums):\n",
    "                    count = counts(Lnums)[L] * counts(Rnums)[R]\n",
    "                    result[L + R] += count\n",
    "                    result[L - R] += count\n",
    "                    result[L * R] += count\n",
    "                    if R != 0:\n",
    "                        result[L / R] += count\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({4: 2, 0: 1, 1.0: 1})"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counts((2, 2)) # corresponds to {0: '2-2', 1.0: '2/2', 4: '2+2' or '2*2'}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counts((10, 9, 8))[27] # (10+9)+8 or 10+(9+8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "Looks good to me. Now let's see if we can answer the question."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30066"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counts(c10)[2016]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "This says there are 30,066 distinct expressions for 2016. \n",
    "\n",
    "**But we're forgetting about round-off error.**\n",
    "\n",
    "Let's find all the values that are very near to `2016`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{2016.0000000000002: 5792,\n",
       " 2016.0: 30066,\n",
       " 2015.9999999999995: 1930,\n",
       " 2015.999999999997: 15,\n",
       " 2016.0000000000005: 510,\n",
       " 2016.0000000000018: 264,\n",
       " 2016.0000000000023: 12,\n",
       " 2015.9999999999998: 5868,\n",
       " 2015.9999999999993: 14,\n",
       " 2016.000000000002: 18,\n",
       " 2015.999999999999: 10}"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{y: counts(c10)[y] \n",
    " for y in counts(c10)\n",
    " if abs(y - 2016) < 1e-10}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "I suspect that all of these actually should be exactly 2016. \n",
    "To be absolutely sure, I could re-do the calculations using exact rational arithmetic, as provided by the `fractions.Fraction` data type. From experience I know that would be an order of magnitude slower, so instead I'll just add up the counts:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "44499"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(_.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "I have more confidence in this answer, 44,499, than in 30,066, but I wouldn't accept it as definitive until it was independently verified and passed an extensive test suite. And of course, if you have a different definition of \"distinct solution,\" you will get a different answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Four 4s\n",
    "\n",
    "Alex Bellos continues with a related puzzle:\n",
    "    \n",
    "> The most famous “fill in the gaps in the equation” puzzle is known as the [four fours](https://en.wikipedia.org/wiki/Four_fours), because every equation is of the form\n",
    ">\n",
    "> `4 ␣ 4 ␣ 4 ␣ 4 = X.`\n",
    ">\n",
    ">In the classic form of the puzzle you must find a solution for X = 0 to 9 using just addition, subtraction, multiplication and division.\n",
    "\n",
    "This puzzle goes back to a [1914 publication](https://archive.org/details/mathematicalrecr00ball) by the \"most famous\" mathematician/magician W. W. Rouse Ball. The solution is easy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: '(((4-4)-4)+4)',\n",
       " 1: '(((4/4)-4)+4)',\n",
       " 2: '((4/(4+4))*4)',\n",
       " 3: '(((4+4)+4)/4)',\n",
       " 4: '(((4-4)/4)+4)',\n",
       " 5: '(((4*4)+4)/4)',\n",
       " 6: '(((4+4)/4)+4)',\n",
       " 7: '((4-(4/4))+4)',\n",
       " 8: '(((4+4)/4)*4)',\n",
       " 9: '(((4/4)+4)+4)'}"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{i: expressions((4, 4, 4, 4))[i] for i in range(10)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that I didn't do anything special to take advantage of the fact that in `(4, 4, 4, 4)` the digits are all the same. Happily, `lru_cache` does that for me automatically! If I split that into `(4, 4)` and `(4, 4)`, when it comes time to do the second half of the split, the result will already be in the cache, and so won't be recomputed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# New Mathematical Operations\n",
    "\n",
    "Bellos then writes:\n",
    "    \n",
    "> If you want to show off, you can introduce **new mathematical operations** such as powers, square roots, concatenation and decimals, ... or use the factorial symbol, `!`.\n",
    "\n",
    "Bellos is suggesting the following operations:\n",
    "\n",
    "- **Powers**: `(4 ^ 4)` is 4 to the fourth power, or 256.\n",
    "- **Square roots:** `√4` is the square root of 4, or 2.\n",
    "- **Concatenation:** `44` is forty-four.\n",
    "- **Decimals:** `4.4` is four and four tenths.\n",
    "- **Factorials** `4!` is 4 × 3 × 2 × 1, or 24.\n",
    "\n",
    "There are some complications to deal with:\n",
    "\n",
    "- **Irrationals**: `√2` is an irrational number; so we can't do exact rational arithmetic.\n",
    "- **Imaginaries**: `√-1` is an imaginary number; do we want to deal with that?\n",
    "- **Overflow**: `(10. ^ (9. ^ 8.))`, as a `float`, gives an `OverflowError`.\n",
    "- **Out of memory**: [`(10 ^ (9 ^ (8 * 7)))`](http://www.wolframalpha.com/input/?i=10+%5E+9+%5E+56), as an `int`, gives an `OutOfMemoryError` (even if your memory uses every atom on Earth).\n",
    "- **Infinite expressions**: We could add an infinite number of square root and/or factorial signs to any expression: `√√√√√√(4!!!!!!!!)`...\n",
    "- **Round-off error**: `(49*(1/49))` evaluates to `0.9999999999999999`, not `1`.\n",
    "\n",
    "We could try to manage this with *symbolic algebra*, perhaps using [SymPy](http://www.sympy.org/en/index.html), but that seems complicated, so instead I will make some arbitrary decisions:\n",
    "\n",
    "- Use floating point approximations for everything, rational or irrational.\n",
    "- Disallow irrationals.\n",
    "- Disallow overflow errors (a type of arithmetic error).\n",
    "- Put limits on what is allow for exponentiation.\n",
    "- Allow only two nested unary operations to avoid infinite expressions.\n",
    "\n",
    "I'll define the function `do` to do an arithmetic computation, catch any errors, and try to correct round-off errors. The idea is that since my expressions start with integers, any result that is very close to an integer is probably actually that integer. So I'll correct `(49*(1/49))` to be `1.0`. Of course, an expression like `(1+(10^-99))` is also very close to `1.0`, but it should not be rounded off. Instead, I'll try to avoid such expressions by silently dropping any value that is outside the range of 10<sup>-10</sup> to 10<sup>10</sup> (except of course I will accept an exact 0)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "from operator import add, sub, mul, truediv\n",
    "from math import sqrt, factorial\n",
    "\n",
    "def do(op, *args): \n",
    "    \"Return op(*args), trying to correct for roundoff error, or `None` on Error or too big/small.\"\n",
    "    try:\n",
    "        val = op(*args)\n",
    "        return (val        if val == 0 else\n",
    "                None       if isinstance(val, complex) else\n",
    "                None       if not (1e-10 < abs(val) < 1e10) else\n",
    "                round(val) if abs(val - round(val)) < 1e-12 else \n",
    "                val)\n",
    "    except (ArithmeticError, ValueError):\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert do(truediv, 12, 4) == 3 and do(truediv, 12, 0) == None\n",
    "assert do(mul, 49, do(truediv, 1, 49)) == 1\n",
    "assert do(pow, 10, -99) == None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'll take this opportunity to refactor `expressions` to have these subfunctions:\n",
    "- `digit_expressions(result, numbers)`: returns a dict like {0.44: '.44', 4.4: '4.4', 44.0: '44'}\n",
    "- `add_unary_expressions(result)`: add expressions like `√44` and `4!` to `result` and return `result`. \n",
    "- `add_binary_expressions(result, numbers)`: add expressions like `4+√44` and `4^4` to `result` and return `result`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "@lru_cache(None)\n",
    "def expressions(numbers: tuple) -> dict:\n",
    "    \"Return {value: expr} for all expressions that can be made from numbers.\"\n",
    "    return add_unary_expressions(add_binary_expressions(digit_expressions(numbers), numbers))\n",
    "\n",
    "def digit_expressions(digits: tuple) -> dict:\n",
    "    \"All ways of making numbers from these digits (in order), and a decimal point.\"\n",
    "    D = ''.join(map(str, digits))\n",
    "    exps = [(D[:i] + '.' + D[i:]).rstrip('.')\n",
    "            for i in range(len(D) + 1)\n",
    "            if not (D.startswith('0') and i > 1)]\n",
    "    return {float(exp): exp for exp in exps}\n",
    "      \n",
    "def add_binary_expressions(result: dict, numbers: tuple) -> dict:\n",
    "    \"Add binary expressions by splitting numbers and combining with an op.\"\n",
    "    for (Lnums, Rnums) in splits(numbers):\n",
    "        for (L, R) in product(expressions(Lnums), expressions(Rnums)):\n",
    "            Lexp = '(' + expressions(Lnums)[L]\n",
    "            Rexp =       expressions(Rnums)[R] + ')'\n",
    "            assign(result, do(truediv, L, R), Lexp + '/' + Rexp)\n",
    "            assign(result, do(mul,     L, R), Lexp + '*'  + Rexp)\n",
    "            assign(result, do(add,     L, R), Lexp + '+'  + Rexp)\n",
    "            assign(result, do(sub,     L, R), Lexp + '-'  + Rexp)\n",
    "            if -10 <= R <= 10 and (L > 0 or int(R) == R):\n",
    "                assign(result, do(pow, L, R), Lexp + '^' + Rexp)\n",
    "    return result\n",
    "                \n",
    "def add_unary_expressions(result: dict, nesting_level=2) -> dict:\n",
    "    \"Add unary expressions: -v, √v and v! to result\"\n",
    "    for _ in range(nesting_level):\n",
    "        for v in tuple(result):\n",
    "            exp = result[v]\n",
    "            if -v not in result:\n",
    "                assign(result, -v, '-' + exp)\n",
    "            if 0 < v <= 100 and 120 * v == round(120 * v): \n",
    "                assign(result, sqrt(v), '√' + exp)\n",
    "            if 3 <= v <= 6 and v == int(v):\n",
    "                assign(result, factorial(v), exp + '!')\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The  function `assign` will silently drop expressions whose value is `None`, and if two expressions have the same value, `assign` keeps the one with the lower \"weight\"&mdash;a measure of the characters in the expression. This shows simpler expressions in favor of complex ones: for four 4s, the entry for `0` will be `44-44`, not something like `-√((-√4*--4)*(-√4--√4))`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def assign(result: dict, value: float, exp: str): \n",
    "    \"Assign result[value] = exp, unless we already have a lighter exp or value is None.\"\n",
    "    if (value is not None \n",
    "        and (value not in result or weight(exp) < weight(result[value]))): \n",
    "        result[value] = exp\n",
    "        \n",
    "PENALTIES = defaultdict(int, {'√':7, '!':5, '.':1, '^':3, '/':1, '-':1})\n",
    "        \n",
    "def weight(exp: str) -> int: return len(exp) + sum(PENALTIES[c] for c in exp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "I'll define a function to print a table of consecutive integers (starting at 0) that can be made by a sequence of numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "def show(numbers: tuple, upto=10000, clear=True):\n",
    "    \"\"\"Print expressions for integers from 0 up to limit or the first unmakeable integer.\"\"\"\n",
    "    if clear: expressions.cache_clear() # To free up memory\n",
    "    print('{:,} entries for {}\\n'.format(len(expressions(numbers)), numbers))\n",
    "    for i in range(upto + 1): \n",
    "        if i not in expressions(numbers):\n",
    "            return i\n",
    "        print('{:4} = {}'.format(i, unbracket(expressions(numbers)[i])))\n",
    "              \n",
    "def unbracket(exp: str) -> str:\n",
    "    \"Strip outer parens from exp, if they are there\"\n",
    "    return (exp[1:-1] if exp.startswith('(') and exp.endswith(')') else exp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "705,959 entries for (4, 4, 4, 4)\n",
      "\n",
      "   0 = 44-44\n",
      "   1 = 44/44\n",
      "   2 = 4*(4/(4+4))\n",
      "   3 = (4+(4+4))/4\n",
      "   4 = 4+(4*(4-4))\n",
      "   5 = (4+(4*4))/4\n",
      "   6 = 4+((4+4)/4)\n",
      "   7 = (44/4)-4\n",
      "   8 = 4+(4*(4/4))\n",
      "   9 = 4+(4+(4/4))\n",
      "  10 = 44/4.4\n",
      "  11 = (4/4)+(4/.4)\n",
      "  12 = (4+44)/4\n",
      "  13 = 4!-(44/4)\n",
      "  14 = (4+(.4*4))/.4\n",
      "  15 = 4+(44/4)\n",
      "  16 = .4*(44-4)\n",
      "  17 = (4/4)+(4*4)\n",
      "  18 = .4+(.4*44)\n",
      "  19 = (4+(4-.4))/.4\n",
      "  20 = 4*(4+(4/4))\n",
      "  21 = (4+4.4)/.4\n",
      "  22 = √4*(44/4)\n",
      "  23 = ((4*4!)-4)/4\n",
      "  24 = 4+(4+(4*4))\n",
      "  25 = (4+(4*4!))/4\n",
      "  26 = (4/.4)+(4*4)\n",
      "  27 = 4+(4!-(4/4))\n",
      "  28 = 44-(4*4)\n",
      "  29 = 4+(4/(.4*.4))\n",
      "  30 = (4+(4+4))/.4\n",
      "  31 = 4!+((4+4!)/4)\n",
      "  32 = (4*4)+(4*4)\n",
      "  33 = 4!+((4-.4)/.4)\n",
      "  34 = 44-(4/.4)\n",
      "  35 = 4!+(44/4)\n",
      "  36 = 44-(4+4)\n",
      "  37 = ((.4+4!)/.4)-4!\n",
      "  38 = 44-(4!/4)\n",
      "  39 = ((4*4)-.4)/.4\n",
      "  40 = 44-√(4*4)\n",
      "  41 = (.4+(4*4))/.4\n",
      "  42 = √4+(44-4)\n",
      "  43 = 44-(4/4)\n",
      "  44 = 4+(44-4)\n",
      "  45 = 44+(4/4)\n",
      "  46 = 4+(44-√4)\n",
      "  47 = 4!+(4!-(4/4))\n",
      "  48 = 4*(4+(4+4))\n",
      "  49 = 44+(√4/.4)\n",
      "  50 = (4+(4*4))/.4\n",
      "  51 = (.4+(4!-4))/.4\n",
      "  52 = 4+(4+44)\n",
      "  53 = 4!+(4!+(√4/.4))\n",
      "  54 = 44+(4/.4)\n",
      "  55 = 44/(.4+.4)\n",
      "  56 = 4*(4+(4/.4))\n",
      "  57 = ((.4+4!)/.4)-4\n",
      "  58 = ((4^4)-4!)/4\n",
      "  59 = (4!/.4)-(4/4)\n",
      "  60 = 44+(4*4)\n",
      "  61 = (4/4)+(4!/.4)\n",
      "  62 = (4*(4*4))-√4\n",
      "  63 = ((4^4)-4)/4\n",
      "  64 = (4+4)*(4+4)\n",
      "  65 = (4+(4^4))/4\n",
      "  66 = √4+(4*(4*4))\n",
      "  67 = √4+((√4+4!)/.4)\n",
      "  68 = 4+(4*(4*4))\n",
      "  69 = (4+(4!-.4))/.4\n",
      "  70 = (4!+(4^4))/4\n",
      "  71 = (4!+4.4)/.4\n",
      "  72 = 4+(4!+44)\n",
      "CPU times: user 9.72 s, sys: 88.3 ms, total: 9.81 s\n",
      "Wall time: 9.84 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "73"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time show((4, 4, 4, 4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "We can also solve the \"2016 with four fours\" puzzle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'(4!*(4!+(4!/.4)))'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expressions((4, 4, 4, 4))[2016]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "In a [separate video](https://www.youtube.com/embed/Noo4lN-vSvw), Alex Bellos shows  how to form **every** integer from 0 to infinity using four 4s, if the square root and `log` functions are allowed. The solution comes from Paul Dirac (although [Dirac originally developed it](https://nebusresearch.wordpress.com/2014/04/18/how-dirac-made-every-number/) for the \"four 2s\" problem).\n",
    "\n",
    "Donald Knuth has [conjectured](https://www.tandfonline.com/doi/abs/10.1080/0025570X.1964.11975546) that with floor, square root and factorial, you can make any positive integer with just **one** 4.\n",
    "\n",
    "Below are some popular variants:\n",
    "\n",
    "# Four 2s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "109,747 entries for (2, 2, 2, 2)\n",
      "\n",
      "   0 = 22-22\n",
      "   1 = 22/22\n",
      "   2 = 2+(2*(2-2))\n",
      "   3 = (2+(2*2))/2\n",
      "   4 = .2*(22-2)\n",
      "   5 = 2+(2+(2/2))\n",
      "   6 = 2*(2+(2/2))\n",
      "   7 = 2+(2/(.2*2))\n",
      "   8 = 2+(2+(2*2))\n",
      "   9 = (22/2)-2\n",
      "  10 = 22/2.2\n",
      "  11 = (2/2)+(2/.2)\n",
      "  12 = (2+22)/2\n",
      "  13 = 2+(22/2)\n",
      "  14 = 2+(2+(2/.2))\n",
      "  15 = (2+(2/2))/.2\n",
      "  16 = 2*(2*(2*2))\n",
      "  17 = 22-(√.2^-2)\n",
      "  18 = 22-(2*2)\n",
      "  19 = (2+(2-.2))/.2\n",
      "  20 = 22-√(2*2)\n",
      "  21 = 22-(2/2)\n",
      "  22 = 2+(22-2)\n",
      "  23 = 22+(2/2)\n",
      "  24 = 2*(2+(2/.2))\n",
      "  25 = 2/(.2*(.2*2))\n",
      "  26 = 2+(2+22)\n",
      "  27 = 22+(√.2^-2)\n",
      "  28 = 2+(2+(2*2)!)\n",
      "  29 = 2+(2+(.2^-2))\n",
      "  30 = (2+(2*2))/.2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "31"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "show((2, 2, 2, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Four 9s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "539,849 entries for (9, 9, 9, 9)\n",
      "\n",
      "   0 = 99-99\n",
      "   1 = 99/99\n",
      "   2 = (99/9)-9\n",
      "   3 = (9+(9+9))/9\n",
      "   4 = 9-(9/(.9+.9))\n",
      "   5 = √9+((9+9)/9)\n",
      "   6 = ((9+(9+9))/9)!\n",
      "   7 = 9-((9+9)/9)\n",
      "   8 = ((9*9)-9)/9\n",
      "   9 = 9+(9*(9-9))\n",
      "  10 = 99/9.9\n",
      "  11 = 9+((9+9)/9)\n",
      "  12 = (9+99)/9\n",
      "  13 = 9+(√9+(9/9))\n",
      "  14 = 9+(9/(.9+.9))\n",
      "  15 = 9+((9+9)/√9)\n",
      "  16 = 9+((9/.9)-√9)\n",
      "  17 = 9+(9-(9/9))\n",
      "  18 = 99-(9*9)\n",
      "  19 = 9+(9+(9/9))\n",
      "  20 = 9+(99/9)\n",
      "  21 = (9+9.9)/.9\n",
      "  22 = 9+(√9+(9/.9))\n",
      "  23 = √9+((9+9)/.9)\n",
      "  24 = (99/√9)-9\n",
      "  25 = 9+(√9!+(9/.9))\n",
      "  26 = (9*√9)-(9/9)\n",
      "  27 = 9+(9+√(9*9))\n",
      "  28 = 9+(9+(9/.9))\n",
      "  29 = 9+((9+9)/.9)\n",
      "  30 = (9+(9+9))/.9\n",
      "  31 = (.9+(9*√9))/.9\n",
      "  32 = (99-√9)/√9\n",
      "  33 = √9*(99/9)\n",
      "  34 = (√9+99)/√9\n",
      "  35 = (√9!+99)/√9\n",
      "  36 = 9+(9+(9+9))\n",
      "  37 = (9/.9)+(9*√9)\n",
      "  38 = √9!*(√9+(√9/.9))\n",
      "  39 = 9+(9*(√9/.9))\n",
      "  40 = (9+(9*√9))/.9\n",
      "  41 = (.9+(√9!*√9!))/.9\n",
      "  42 = 9+(99/√9)\n",
      "  43 = √9+(√9!*(√9!/.9))\n",
      "  44 = (9*√9!)-(9/.9)\n",
      "  45 = 9*(9/(.9+.9))\n",
      "  46 = (9/.9)+(√9!*√9!)\n",
      "  47 = √9*(9+(√9!/.9))\n",
      "  48 = √9!*(9-(9/9))\n",
      "  49 = 9+(√9!*(√9!/.9))\n",
      "  50 = ((9*√9!)-9)/.9\n",
      "  51 = 9*(9-(√9/.9))\n",
      "  52 = √9!*(9-(√9/9))\n",
      "  53 = (9*√9!)-(9/9)\n",
      "  54 = 9*((9+9)/√9)\n",
      "  55 = 99/(.9+.9)\n",
      "  56 = √9!*(9+(√9/9))\n",
      "  57 = √9*(9+(9/.9))\n",
      "  58 = √9!*(9+(√9!/9))\n",
      "  59 = ((9*√9!)-.9)/.9\n",
      "  60 = √9*((9+9)/.9)\n",
      "  61 = (.9+(9*√9!))/.9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "62"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "show((9, 9, 9, 9))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Four 5s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "202,937 entries for (5, 5, 5, 5)\n",
      "\n",
      "   0 = 55-55\n",
      "   1 = 55/55\n",
      "   2 = (5/5)+(5/5)\n",
      "   3 = (5+(5+5))/5\n",
      "   4 = ((5*5)-5)/5\n",
      "   5 = 5+(5*(5-5))\n",
      "   6 = (55/5)-5\n",
      "   7 = 5+((5+5)/5)\n",
      "   8 = 5.5+(.5*5)\n",
      "   9 = 5+(5-(5/5))\n",
      "  10 = 55/5.5\n",
      "  11 = 5.5+5.5\n",
      "  12 = (5+55)/5\n",
      "  13 = .5+(.5*(5*5))\n",
      "  14 = 5+((5-.5)/.5)\n",
      "  15 = (5*5)-(5+5)\n",
      "  16 = 5+(55/5)\n",
      "  17 = 5+(5!/(5+5))\n",
      "  18 = (5-.5)/(.5*.5)\n",
      "  19 = (5+(5-.5))/.5\n",
      "  20 = 5+(5+(5+5))\n",
      "  21 = (5+5.5)/.5\n",
      "  22 = 55/(.5*5)\n",
      "  23 = .5+(5*(5-.5))\n",
      "  24 = (5*5)-(5/5)\n",
      "  25 = .5*(55-5)\n",
      "  26 = (5/5)+(5*5)\n",
      "  27 = (.5*55)-.5\n",
      "  28 = .5+(.5*55)\n",
      "  29 = (5!+(5*5))/5\n",
      "  30 = 55-(5*5)\n",
      "  31 = 55-(5!/5)\n",
      "  32 = ((5+5)/5)^5\n",
      "  33 = .5*(5!*.55)\n",
      "  34 = 5+(5+(5!/5))\n",
      "  35 = 5+(5+(5*5))\n",
      "  36 = (5!+(.5*5!))/5\n",
      "  37 = (.5^-5)+√(5*5)\n",
      "  38 = ((5!/5)-5)/.5\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "39"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "show((5, 5, 5, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Five 5s "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7,624,387 entries for (5, 5, 5, 5, 5)\n",
      "\n",
      "   0 = 5*(55-55)\n",
      "CPU times: user 2min 19s, sys: 1.04 s, total: 2min 20s\n",
      "Wall time: 2min 21s\n"
     ]
    }
   ],
   "source": [
    "%time show((5, 5, 5, 5, 5), False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "\n",
    "# Countdown to 2018\n",
    "\n",
    "One  more thing: On January 1 2018, [Michael Littman](http://cs.brown.edu/~mlittman/) posted this:\n",
    "\n",
    "> 2+0+1×8, 2+0-1+8, (2+0-1)×8, |2-0-1-8|, -2-0+1×8, -(2+0+1-8), sqrt(|2+0-18|), 2+0+1^8, 20-18, 2^(0×18), 2×0×1×8... Happy New Year!\n",
    "\n",
    "Can we replicate that countdown? For 2018 and for following years?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10,303 entries for (2, 0, 1, 8)\n",
      "\n",
      "   0 = 2*(0*18)\n",
      "   1 = 2^(0*18)\n",
      "   2 = 20-18\n",
      "   3 = 2.0+(1^8)\n",
      "   4 = 20*(1-.8)\n",
      "   5 = -2+((0-1)+8)\n",
      "   6 = (2*(0-1))+8\n",
      "   7 = ((2*0)-1)+8\n",
      "   8 = (2*0)+(1*8)\n",
      "   9 = (2*0)+(1+8)\n",
      "  10 = 2.0+(1*8)\n"
     ]
    }
   ],
   "source": [
    "show((2,0,1,8), 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14,957 entries for (2, 0, 1, 9)\n",
      "\n",
      "   0 = 2*(0*19)\n",
      "   1 = 20-19\n",
      "   2 = 2+(0*19)\n",
      "   3 = 2+(0.1+.9)\n",
      "   4 = (2*0)+(1+√9)\n",
      "   5 = 20/(1+√9)\n",
      "   6 = -2+((0-1)+9)\n",
      "   7 = (2*(0-1))+9\n",
      "   8 = ((2*0)-1)+9\n",
      "   9 = (2*0)+(1*9)\n",
      "  10 = 20-(1+9)\n"
     ]
    }
   ],
   "source": [
    "show((2,0,1,9), 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we run into a problem. For the year 2020,  the two zeroes don't give us much to work with, and we can't make all the integers in the countdown. But I can turn a 0 into a 1 with `cos(0)`; maybe that will be enough? Let's try it. I'll modify `add_unary_expressions` to assign values for `sin` and `cos`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import sin, cos\n",
    "\n",
    "def add_unary_expressions(result: dict, nesting_level=2) -> dict:\n",
    "    \"Add unary expressions: -v, √v and v! to result dict.\"\n",
    "    for _ in range(nesting_level):\n",
    "        for v in tuple(result):\n",
    "            exp = result[v]\n",
    "            if -v not in result:\n",
    "                assign(result, -v, '-' + exp)\n",
    "            if 0 < v <= 100 and 120 * v == round(120 * v): \n",
    "                assign(result, sqrt(v), '√' + exp)\n",
    "            if 3 <= v <= 6 and v == int(v):\n",
    "                assign(result, factorial(v), exp + '!')\n",
    "            if abs(v) in (0, 45, 90, 180):\n",
    "                assign(result, sin(v), 'sin(' + exp + ')')\n",
    "                assign(result, cos(v), 'cos(' + exp + ')')\n",
    "    return result\n",
    "\n",
    "PENALTIES.update(s=1, i=1, n=1, c=1, o=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8,195 entries for (2, 0, 2, 0)\n",
      "\n",
      "   0 = 202*0\n",
      "   1 = 20/20\n",
      "   2 = 2+(0*20)\n",
      "   3 = 2+(.02^0)\n",
      "   4 = .20*20\n",
      "   5 = (2^0)/.20\n",
      "   6 = 2*(cos(0)+2.0)\n",
      "   7 = 2+(cos(0)/.20)\n",
      "   8 = 2^(cos(0)+2.0)\n",
      "   9 = (20/2)-cos(0)\n",
      "  10 = 2/0.20\n"
     ]
    }
   ],
   "source": [
    "show((2, 0, 2, 0), 10, clear=True) # Clear the cache so we get new results for (2, 0) etc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "38,875 entries for (2, 0, 2, 1)\n",
      "\n",
      "   0 = 2*(0*21)\n",
      "   1 = -20+21\n",
      "   2 = 2+(0*21)\n",
      "   3 = 2+((0*2)+1)\n",
      "   4 = 2.0*(2*1)\n",
      "   5 = 2.0+(2+1)\n",
      "   6 = 2.0*(2+1)\n",
      "   7 = 2+(0.2^-1)\n",
      "   8 = 2.0^(2+1)\n",
      "   9 = (20/2)-1\n",
      "  10 = 20/(2*1)\n"
     ]
    }
   ],
   "source": [
    "show((2, 0, 2, 1), 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What's Next?\n",
    "\n",
    "One exercise would be adding even more operators, such as:\n",
    "\n",
    "- **Floor and Ceiling**: `⌊5.5⌋` = 5, `⌈5.5⌉` = 6\n",
    "- **Nth root**: `3√8` = 2\n",
    "- **Percent**: `5%` = 5/100\n",
    "- **Repeating decimal**: `.4...` = .44444444... = 4/9\n",
    "- **Double factorial**: `9!!` = 9 × 7 × 5 × 3 × 1 = 945\n",
    "- **Gamma function**: `Γ(n)` = (n − 1)!\n",
    "- **Prime counting function**: `π(n)` = number of primes ≲ n; `π(5)` = 3\n",
    "- **Transcendental functions**: besides `sin` and `cos`, there's `log`, `tan`, `arcsin`, ...\n",
    "\n",
    "In the [xkcd forum](http://forums.xkcd.com/viewtopic.php?f=14&t=116813&start=280) they got up to 298 for five fives, using the double factorial and π functions. What would you like to do?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}