ipynb/How To Count Things.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\">Peter Norvig, Updated Sept 2018</div>\n",
    "\n",
    "![the count](https://vignette.wikia.nocookie.net/muppet/images/9/90/CountCountsLP%282%29.jpg/revision/latest/scale-to-width-down/280?cb=20140628202329)\n",
    "\n",
    "# How to Count Things\n",
    "\n",
    "Sesame Street teaches us to easily count up to ten using our fingers. A computer doesn't have fingers, but it too can use brute force, enumerating things one by one, to easily count up to a billion or so.\n",
    "\n",
    "\n",
    "\n",
    "So in that sense, a billion is a small number. For really big numbers, like 10<sup>100</sup>, we need a better strategy: counting by **calculating** the number of things rather than **enumerating** them. This notebook describes some strategies for counting by **calculating**.\n",
    "\n",
    "# Problem 1: Counting Sub-cubes\n",
    "\n",
    "We'll start with a really simple counting problem:\n",
    "\n",
    "> Given a cube with ***n*** sub-cubes on a side, how many total sub-cubes are there?\n",
    "\n",
    "Here are two example cubes:\n",
    "\n",
    "|*n* = 3|*n* = 9|\n",
    "|-----|-----|\n",
    "| ![cube](https://qph.fs.quoracdn.net/main-qimg-a1eb70317e94431c265fb32c9ec2170f.webp) | ![cube](https://www.jugglingwholesale.com/media/catalog/product/cache/1/image/366x366/9df78eab33525d08d6e5fb8d27136e95/v/-/v-udoku.jpg) |\n",
    "\n",
    "\n",
    "For the *n* = 3 cube, we could use the **enumeration** strategy, pointing to each sub-cube with our finger and counting 1, 2, 3, ... 27. That wouldn't work as well for the *n* = 9 cube, and it would be completely infeasible for an *n* = 1000 cube. How can we count with a computer?\n",
    "\n",
    "First let's get some Python preliminaries out of the way: imports, and three utility functions:\n",
    "- `cat` concatenates strings into one big string\n",
    "- `quantify` (from [the `itertools` module recipes](https://docs.python.org/3/library/itertools.html)) counts how many things a predicate is true for.\n",
    "- `totalcount` totals up all the values in a Counter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Python 3.x imports, and some utilities\n",
    "\n",
    "from collections import Counter\n",
    "from functools   import lru_cache\n",
    "from itertools   import product, permutations, combinations\n",
    "from math        import factorial, inf # infinity\n",
    "import re\n",
    "\n",
    "cat = ''.join\n",
    "\n",
    "def quantify(iterable, predicate=bool) -> int: \n",
    "    \"Count the number of items in iterable for which the predicate is true.\"\n",
    "    return sum(map(predicate, iterable)) \n",
    "\n",
    "def totalcount(counter) -> int:\n",
    "    \"The sum of all the values in a Counter (or mapping).\"\n",
    "    return sum(counter.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is an **enumeration** strategy and a **calculation** strategy  for sub-cube counting:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def enumerate_subcubes(n) -> int: \n",
    "    return quantify(1 for width in range(n) \n",
    "                      for depth in range(n) \n",
    "                      for height in range(n))\n",
    "\n",
    "def calculate_subcubes(n) -> int: \n",
    "    return n ** 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The calculation strategy is *much* faster:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 6.4 s, sys: 79.7 ms, total: 6.48 s\n",
      "Wall time: 7.77 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "27000000"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time enumerate_subcubes(300)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 5 µs, sys: 1 µs, total: 6 µs\n",
      "Wall time: 9.06 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "27000000"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time calculate_subcubes(300)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "# Problem 2: Counting Student Records (Late/Absent/Present)\n",
    "\n",
    "A more difficult problem:\n",
    "\n",
    "> Students at a school must check in with the guidance counselor if they have two total absences, or three consecutive late days. Each student's attendance record consists of a string of 'A' for absent, 'L' for late, or 'P' for present. For example: \"LAPLPA\" requires a meeting (because there are two absences), and \"LAPLPL\" is OK (there are three late days, but they are not consecutive). How many attendance records of length *n* are OK?\n",
    "\n",
    "The **enumeration** strategy says: define what it means for a record to be `ok`, define all the strings of length *n*, and count how many of them are `ok`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 1,\n",
       " 1: 3,\n",
       " 2: 8,\n",
       " 3: 19,\n",
       " 4: 43,\n",
       " 5: 94,\n",
       " 6: 200,\n",
       " 7: 418,\n",
       " 8: 861,\n",
       " 9: 1753,\n",
       " 10: 3536}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def ok(record: str) -> bool: \n",
    "    \"Is this student record OK? (Not 2 abscences, nor 3 consecutive lates.)\"\n",
    "    return not re.search(r'A.*A|LLL', record)\n",
    "\n",
    "def all_strings(alphabet, n): \n",
    "    \"All length-n strings over the given alphabet.\"\n",
    "    return map(cat, product(alphabet, repeat=n))\n",
    "\n",
    "def enumerate_ok(n) -> int:\n",
    "    \"How many attendance records of length n are ok?\"\n",
    "    return quantify(all_strings('LAP', n), ok)\n",
    "\n",
    "{n: enumerate_ok(n) for n in range(11)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This looks good, but for large values of *n*\n",
    "I will need an efficient **calculation** strategy. Here's how I think about it:\n",
    "\n",
    "* I can't enumerate all the strings; there are too many of them. \n",
    "* Instead, I want to **divide and conquer**: divide the problem up into simpler subproblems, solve the subproblems, and combine them. A good way to divide this problem is to solve the case for *n* by first solving the case for *n*-1.\n",
    "* With the enumeration strategy, going from *n*-1 to *n*  multiplies the amount of work by 3 (because you have to consider any of three letters tacked on to the end of every possible record). \n",
    "* With the right divide and conquer strategy, we can get from *n*-1 to *n* with a constant amount of work. So the total complexity can be *O*(*n*) instead of *O*(3<sup>*n*</sup>). \n",
    "* (This divide and conquer strategy is sometimes called *[dynamic programming](https://en.wikipedia.org/wiki/Dynamic_programming)*, although some writers reserve the term *dynamic programming* for algorithms that explicitly store partial results in a table.)\n",
    "* How do I get from *n*-1 to *n*? I will keep track of a *summary* of all the `ok` strings of length *n*-1, and use that to quickly (in constant time) compute a summary of the `ok` strings of length *n*. \n",
    "* What is in the summary? A list of all `ok` strings is too much. A simple count of the number of `ok` strings is not enough. Instead, I need several different counts, for several different classes of strings. Each class is defined by the number of `'A'` characters in the string, and the number of consecutive `'L'` characters at the *end* of the string (because these are the two things that determine whether the string will be `ok` or not `ok` when I add a letter to the end).  So the summary can be represented as  a `Counter` of the form `{(A, L): count, ...}`. \n",
    "\n",
    "For *n* = 0, the summary is `{(0, 0): 1}`, because there is one string of length zero, the empty string, which has no `'A'` nor `'L'` in it. From there we can proceed in a \"bottom-up\" fashion to compute the total number of `ok` strings for the next value of `n`, using the function `next_summary`, which says that we can add an `'A'` to any string that doesn't already have one; we can add an `L` to any string that doesn't already end in 2 `'L'`s; and we can add a `'P'` to any string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "summary0 = Counter({(0, 0): 1})\n",
    "\n",
    "def next_summary(prev_summary: Counter) -> Counter:\n",
    "    \"Given a summary of the form {(A, L): count}, return summary for one letter more.\"\n",
    "    summary = Counter()\n",
    "    for (A, L), count in prev_summary.items():\n",
    "        if not A: summary[A+1, 0] += count # add an 'A'\n",
    "        if L < 2: summary[A, L+1] += count # add an 'L'\n",
    "        summary[A, 0] += count             # add a  'P'\n",
    "    return summary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({(0, 0): 1, (0, 1): 1, (1, 0): 1})"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next_summary(summary0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({(0, 0): 2, (0, 1): 1, (0, 2): 1, (1, 0): 3, (1, 1): 1})"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next_summary(_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({(0, 0): 4, (0, 1): 2, (0, 2): 1, (1, 0): 8, (1, 1): 3, (1, 2): 1})"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next_summary(_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's an implementation of `calculate_ok`, and a demonstration that it gets the same results as `enumerate_ok`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def calculate_ok(n) -> int:\n",
    "    \"How many strings of length n are ok?\"\n",
    "    summary = summary0\n",
    "    for _ in range(n):\n",
    "        summary = next_summary(summary)\n",
    "    return totalcount(summary) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 1,\n",
       " 1: 3,\n",
       " 2: 8,\n",
       " 3: 19,\n",
       " 4: 43,\n",
       " 5: 94,\n",
       " 6: 200,\n",
       " 7: 418,\n",
       " 8: 861,\n",
       " 9: 1753,\n",
       " 10: 3536}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{n: calculate_ok(n) for n in range(11)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But we can go way beyond what we could do with `enumerate_ok`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "744860152388838641467766615047636640123287960024109564468341118067976387620845421483777039844936500522445420732911099270409841757052659"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_ok(500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Alternative: Abstraction with `iterate`\n",
    "\n",
    "This pattern of repeatedly calling `next_summary` *n* times will be common in this notebook; we can encapsulate it in a function called `iterate` (after the Haskell function of that name) allowing us to implement a version of `calculate_ok` in one line:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def calculate_ok2(N): return totalcount(iterate(next_summary, summary0, N))\n",
    "\n",
    "def iterate(f, x, n):\n",
    "    \"Return f^n(x); for example, iterate(f, x, 3) == f(f(f(x))).\"\n",
    "    for _ in range(n):\n",
    "        x = f(x)\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "744860152388838641467766615047636640123287960024109564468341118067976387620845421483777039844936500522445420732911099270409841757052659"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_ok2(500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Alternative: Working Down\n",
    "\n",
    "As a third alternative, instead of working up from 0 to `n` we can work down from `n` to 0 (although we may run up against Python's recursion limit):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def calculate_ok3(n) -> int: return totalcount(nth_summary(n))\n",
    "    \n",
    "def nth_summary(n) -> Counter: \n",
    "    \"The {(A, L): count} summary for strings of length n.\"\n",
    "    return (summary0 if n == 0 else next_summary(nth_summary(n - 1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "744860152388838641467766615047636640123287960024109564468341118067976387620845421483777039844936500522445420732911099270409841757052659"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_ok3(500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A comparison:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 4.34 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "100 loops, best of 3: 6.26 ms per loop\n",
      "100 loops, best of 3: 9.52 ms per loop\n",
      "100 loops, best of 3: 5.52 ms per loop\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "7.448601523888386e+134"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 500\n",
    "%timeit calculate_ok(n)\n",
    "%timeit calculate_ok2(n)\n",
    "%timeit calculate_ok3(n)\n",
    "float(calculate_ok(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are over 10<sup>134</sup> ok strings of length 500, but it only takes a couple milliseconds to count them. Any of the three methods works equally well; use the approach you feel comfortable with."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 3: Counting Strings with Alphabetic First Occurences\n",
    "\n",
    "Here's another problem:\n",
    "\n",
    "> How many strings of length *k* can be formed such that the first occurrences of each character in the string forms a prefix of the alphabet?\n",
    "\n",
    "Let's first make sure we understand the problem, because the statement is a bit abstract and tricky. Given a string we have to pick out the first occurrences of characters (letters). For example, for the string `\"abba\"`, we read left-to-right, recording each time we see a letter for the first time; that gives us `\"ab\"` (the subsequent occurrences of `'a'` and `'b'` don't matter). Is that a prefix of the alphabet, `\"abcd...\"`? Yes it is. \n",
    "\n",
    "Here are some test cases&mdash;pairs of strings along with their first occurrences&mdash;labelled with `True` for valid strings and `False` for invalid:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "alpha_test_cases = {\n",
    "    True:  {('abba',   'ab'),\n",
    "            ('',       ''),\n",
    "            ('a',      'a'),\n",
    "            ('aaa',    'a'),\n",
    "            ('abc',    'abc'),\n",
    "            ('abac',   'abc'),\n",
    "            ('abbacabbadabba', 'abcd')},\n",
    "    False: {('b',      'b'),      # 'a' is missing\n",
    "            ('cab',    'cab'),    # 'c' is before 'ab'\n",
    "            ('abd',    'abd'),    # 'c' is missing\n",
    "            ('aback',  'abck'),   # 'k' is before 'd-j'\n",
    "            ('badcafe','badcfe'), # 'b' is before 'a', etc.\n",
    "            ('abecedarian', 'abecdrin')}} # 'e' is before 'cd', etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now to implement the code that can run these tests. Since *k* could be arbitrarily large, I will by default assume an alphabet consisting of the non-negative integers, not the letters. Here are the key concepts:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "integers = range(10 ** 100)\n",
    "letters  = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "def is_alpha_firsts(s, alphabet=integers) -> bool: \n",
    "    \"Do the first occurrences of `s` form a prefix of the alphabet?\"\n",
    "    pre = firsts(s)\n",
    "    return pre == list(alphabet[:len(pre)])   \n",
    "\n",
    "def firsts(s) -> list: \n",
    "    \"The first occurrences of each character, in the order they appear.\"\n",
    "    return sorted(set(s), key=lambda x: s.index(x))  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'll test this code on the examples I showed above by defining the function `alpha_test`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'pass'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def alpha_test(cases=alpha_test_cases):\n",
    "    \"Verify all the test cases.\"\n",
    "    for validity in cases:\n",
    "        for (s, s_firsts) in cases[validity]:\n",
    "            assert firsts(s) == list(s_firsts)\n",
    "            assert is_alpha_firsts(s, letters) == validity\n",
    "    return 'pass'\n",
    "\n",
    "alpha_test()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I can count the number of valid strings by enumerating all possible strings in the alphabet and checking each one with `is_alpha_firsts`. The complexity of this algorithm is $O(k^{k+1})$, because there are $k^k$ strings, and to validate a string requires looking at all $k$ characters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 1, 1: 1, 2: 2, 3: 5, 4: 15, 5: 52, 6: 203}"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def enumerate_alpha_firsts(k) -> int: \n",
    "    \"\"\"Enumerate all possible strings and count the number of valid ones.\"\"\"\n",
    "    all_strings = product(range(k), repeat=k)\n",
    "    return quantify(all_strings, is_alpha_firsts)\n",
    "\n",
    "{k: enumerate_alpha_firsts(k) for k in range(7)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's think about a **calculation** strategy that would be faster than the **enumeration** strategy.\n",
    "As with previous problems, I need a *summary* of the relevant information for strings of length *k*, to help me calculate the relevant information for length *k*+1. I know that if I have a valid string of length *k* with *m* distinct characters in it, then I can extend it by one character in *m* ways by repeating any of those *m* characters, or I can introduce a first occurrence of character number *m+1* (but I can do that in just 1 way). I can't validly introduce any other character. So a good summary would be a Counter of `{`*m*`: `*count*`}`, and we get this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def calculate_alpha_firsts(k): \n",
    "    \"Count the number of strings of length k that have alphabetic first character occurrences.\"\n",
    "    return totalcount(iterate(next_alpha_summary, {0: 1}, k))\n",
    "\n",
    "def next_alpha_summary(prev_summary) -> Counter:\n",
    "    \"Given a summary of the form {m: count}, return summary for one character more.\"\n",
    "    summary = Counter()\n",
    "    for m, c in prev_summary.items():\n",
    "        summary[m] += c * m # Add any of the m previously-used characters\n",
    "        summary[m + 1] += c # Add character number m+1\n",
    "    return summary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 1, 1: 1, 2: 2, 3: 5, 4: 15, 5: 52, 6: 203}"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{k: calculate_alpha_firsts(k) for k in range(7)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "29899013356824084214804223538976464839473928098212305047832737888945413625123259596641165872540391578300639147082986964028021802248993382881013411276574829121155811755170830666039838837273971971676782389800810361809319250755399325279656765435255999301529770267107281619733800281695881540007577899106878679451165492535930459233713316342551545242815802367257284852612201081016386308535990145447341800455472334713864080523978960296365736999295932080550928561633025800627524911700149562106895897725047744775812241800937310491797818107578233924187312824632629095993832334781713007323483688294825326897450386817327410532925074613888321264138083842196202242956001314953449497244271843922741908252107652201346933889741070435350690242062001522697855278356012055718392851567813397125419144780476479197990921602015873703820769182603836788465785093563686025690269802153802436873530877006737154523895273029510238745997356292232631282773748762989386003970214423843947094021177989737557020369751561595003372955621411858485959813344799967960196238368337022346946771703060269288691694028444791203978533454759410587065022546491518871238421560825907135885619221776405898771057270555581449229994215739476758785884545723062263992367750091319644861547658472282284005892044371587560711880627741139497818835632120761570174928529697397267899554407350161283097123211048049269727655279783900702416095132827766428865017653366696304131436690232979453876337599721772897049270230544262611264917393374756384152784943607952408782612639220380791445272655004475989064276373713608901650681165467490310898804916827069427310961109285035545084791339423266482359955663377201515204340817580915468489969181643341007197836481461051798995640789292580146918580703759556634019451731530034209189203377522668309771129566108101617727442045637098112678864654309987785463307376544339506878267267349348171320834971956806668304099159992067385998690820326902473886782781499414773179"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_alpha_firsts(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's a big number.\n",
    "\n",
    "# Alternative: Recursion\n",
    "\n",
    "Another way to keep track of the number of valid strings of length *k* with *m* distinct characters is with a recursive counting function, which I will call `C(k, m)`. There are three cases: \n",
    "\n",
    "- `C(0, 0)` is 1, because the empty string is valid (and contains no distinct characters). \n",
    "- `C(k, m)` is 0 when `k` is negative (because there is no such thing as a negative length string) or less than `m` (because a string can't contain more distinct characters than its length). \n",
    "- Otherwise, there are `m` ways to add an existing letter to each of the strings of length `k - 1`, and there is one way to add a new letter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@lru_cache(None)\n",
    "def C(k, m) -> int:\n",
    "    \"Count the number of valid strings of length k, that use m distinct characters.\"\n",
    "    return (1 if (k == m == 0)    else\n",
    "            0 if (k < 0 or k < m) else\n",
    "            m * C(k - 1, m) + C(k - 1, m - 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that I used `lru_cache`, to avoid having to re-compute intermediate results.\n",
    "\n",
    "Now I can define `calculate_alpha_firsts2(k)` as the sum of `C(k, m)` over all values of `m`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def calculate_alpha_firsts2(k) -> int: return sum(C(k, m) for m in range(k + 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's make sure the two calculations gives the same answers as the enumeration, at least for small values of $k$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all(enumerate_alpha_firsts(k) == calculate_alpha_firsts(k) == calculate_alpha_firsts2(k)\n",
    "    for k in range(7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 4: Counting Barcodes\n",
    "\n",
    "> Consider the barcode pictured below. A valid barcode consists of alternating black and white stripes, where each stripe is either 1, 2, or 3 units wide. The question is: for a box that is *n* units wide, how many different valid barcodes are there?\n",
    "\n",
    "![barcode](https://help.shopify.com/assets/manual/sell-in-person/hardware/barcode-scanner/1d-barcode-4fbf513f48675746ba39d9ea5078f377e5e1bb9de2966336088af8394b893b78.png)\n",
    "\n",
    "We'll represent a barcode as a string, such as `'BBWWWBBW'`. Each of the *n* characters in the string can be either `'B'` or `'W'`, but the string can't have 4 of the same character in a row. We'll start with the familiar enumerate-and-test strategy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def valid_barcode(code) -> bool: return 'BBBB' not in code and 'WWWW' not in code\n",
    "\n",
    "def all_barcodes(n): return map(cat, product('BW', repeat=n))\n",
    "\n",
    "def enumerate_barcodes(n) -> int: return quantify(all_barcodes(n), valid_barcode)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a table of counts for small values of *n*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 1,\n",
       " 1: 2,\n",
       " 2: 4,\n",
       " 3: 8,\n",
       " 4: 14,\n",
       " 5: 26,\n",
       " 6: 48,\n",
       " 7: 88,\n",
       " 8: 162,\n",
       " 9: 298,\n",
       " 10: 548,\n",
       " 11: 1008,\n",
       " 12: 1854}"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{n: enumerate_barcodes(n) for n in range(13)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see that the table starts out with the powers of two: 1, 2, 4, 8. That makes sense: each of the *n* positions in the barcode could be either black or white, so that's 2<sup>*n*</sup> barcodes. But barcodes with 4 or more of the same color in a row are invalid, so for *n* = 4, `'BBBB'` and `'WWWW'` are invalid, and we get 14 (not 16) valid barcodes. For *n* = 5 and up, the difference between 2<sup>*n*</sup> and the count of valid barcodes becomes larger.\n",
    "\n",
    "Now for a fast **calculation**. As before, we need a representation that summarizes the valid barcodes of length *n*. The key thing we need to know is how many barcode units of the same color are at the *end* of the barcode: if it is 1 or 2, then we can add another instance of the same color to the end; no matter what it is we can always add the opposite color (and then the barcode will end in just one unit of the same color)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 1,\n",
       " 1: 2,\n",
       " 2: 4,\n",
       " 3: 8,\n",
       " 4: 14,\n",
       " 5: 26,\n",
       " 6: 48,\n",
       " 7: 88,\n",
       " 8: 162,\n",
       " 9: 298,\n",
       " 10: 548,\n",
       " 11: 1008,\n",
       " 12: 1854}"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def calculate_barcodes(k): return totalcount(iterate(next_barcode_summary, {0: 1}, k))\n",
    "\n",
    "def next_barcode_summary(prev_summary) -> Counter:\n",
    "    \"Given a summary of the form {end: count}, return summary for one unit more.\"\n",
    "    summary = Counter()\n",
    "    for end, c in prev_summary.items():\n",
    "        if end < 3: \n",
    "            summary[end + 1] += c\n",
    "        summary[1] += c\n",
    "    return summary  \n",
    "\n",
    "{k: calculate_barcodes(k) for k in range(13)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Verify that enumeration and calculation do the same thing for small values of *n*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "assert all(enumerate_barcodes(n) == calculate_barcodes(n) for n in range(20))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Demonstrate that we can compute big numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3861431277625007961956955484353530119634001892816040917233932945064320273497370215771811960744678098449553175356862760450029708838175822242262792740296878964074883622671541479265048463512360941352413049264274485743297728357502930085506419846119753743423275462450713981257123756695327534235952507322555045959925039572403245743061549541274972562526816439217931608999532601457740681763142591939324781110768274782850152125981385364637513839024687081770052346957401052189529936883629883775724870785833452510126377097128195647948735625551805771200981065390268401761158588370204299868440790417559363818139283430755197453196664541025472104658523804014518931760254828135638415413408780736125999685589725526874318196976263624936793335541955083569139572617638693840543637407782446933562063756941909207810703824222697116352937601482868529114899390708691493432262019965964035273813939182009029538539757438413668036430833988535147478776959903569999055599703304516221455076523484352182404159659661240973630499557250950477386781288167303525408434907471599633608826344342446869378392685927230076723348547049789748491137890119623879128231595262082532286126660730784998797003448161418183918024344043613986269574364002761796194720086663633818066518383357158900007727428966795190669943187944515210398817044521469661682433819382541570464313514353180507280999817655346753846288267575488232309682752190042235927387740555053797529717247933281707578234957297940957985028202675009617273305705968728942732545640071819447202821044438874136038990729299397246489481363094787623333269036228204295737689912072742922999093173704662567170601571800655678495878408411165386708197339087266092115780445248022350264528021426918011958029075557108406192634108388793426193565093359228830473466263938925653882623387099940055081548579900911968982480432787324594136156465497071249090902373689488770079828664684036332439902542305885855063306802357476735193730805776865978477463443216064890685565824039494431583860044254937057151591772329166180799218273949130368000609439119706131185925513231524378443124711002954768565310478734594199963723940004083846148186188631535346393565417946059827530465095391420721324513264443555308798011729355327067365885381721113676766083967129134309202588682281325857855165574371421168078423586430302604691681703448297310856061359072019641696782664700526740970642410648738647199882852824774480069658314840218244137906558931392021855430239022442215072063184370394666755160595637651648014842470092745788026900633378764049390511584307920491613532339464196985013369306439276245475602674051266814071448421271626238787893306176669816773478303604652043427279626683524358370"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_barcodes(10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 5: Counting Rectangle Sets\n",
    "\n",
    "This problem is covered in depth in [another notebook](Golomb-puzzle.ipynb), so here I present just the part that has to do with counting things:\n",
    "\n",
    "> Say you’re given the following challenge: create a set of five rectangles that have sides of length 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10 units. You can combine sides in a variety of ways: for example, you could create a set of rectangles with dimensions 1 x 3, 2 x 4, 5 x 7, 6 x 8 and 9 x 10. How many different sets of five rectangles are possible?\n",
    "\n",
    "This is a basic [combinatorics](http://en.wikipedia.org/wiki/Combinatorics) problem. I will present *three* methods to calculate the number of sets. If all goes well they will give the same answer. The example set of rectangles given in the problem was\n",
    "\n",
    "     {1 × 3, 2 × 4, 5 × 7, 6 × 8, 9 × 10}\n",
    "    \n",
    "and in general it would be\n",
    "\n",
    "     {A × B, C × D, E × F, G × H, I × J}\n",
    "\n",
    "The question is: how many distinct ways can we assign the integers 1 through 10 to the variables A through J?\n",
    "    \n",
    "**Method 1: Count all permutations and divide by repetitions:** There are 10 variables to be filled, so there are 10! = 3,628,800 permutations.  But if we fill the first two variables with 1 × 3, that is the same rectangle as 3 × 1. So divide 10! by 2<sup>5</sup> to account for the fact that each of 5 rectangles can appear 2 ways.  Similarly, if we fill A and B with 1 × 3, that yields the same set as if we filled C and D with 1 × 3.  So divide again by 5! (the number of permutations of 5 things) to account for this.\n",
    "That gives us:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "945.0"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorial(10) / 2 ** 5 / factorial(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(It is always a relief when this \"count and divide\" method comes out to a whole number.)\n",
    "\n",
    "**Method 2: Count without repetitions**: in each rectangle of the example set the smaller component is listed first, and in each set, the rectangles with smaller first components are listed first. Without loss of generality, let's assume that all rectangle sets must be of this form, and count how many sets there are that respect this ordering.  We'll work from left to right.  How many choices are there for variable A?  *Only one!* A must always be 1, because we agreed that the smallest number comes first. Then, given A, there are 9 remaining choices for B.  For C, given A and B, there is again only one choice: C must be the smallest of the remaining 8 numbers.  That leaves 7 choices for D, 5 for F, 3 for H and 1 for J. So:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "945"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "9 * 7 * 5 * 3 * 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(It is always a relief when two methods give the same answer.)\n",
    "          \n",
    "**Method 3: Write a program to enumerate and check:** We'll generate all permutations of sides, and then check which ones are valid rectangle sets: they must have the first element of each pair less than the second (i.e. A < B, C < D, ...) and the pairs must be sorted, which is equivalent to saying their first elements are sorted (i.e. A < C < E < G < I)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "945"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def valid_rectangle_set(sides):\n",
    "    A,B, C,D, E,F, G,H, I,J = sides\n",
    "    return A < B and C < D and E < F and G < H and I < J and A < C < E < G < I\n",
    "\n",
    "quantify(permutations(range(1, 11)), valid_rectangle_set)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(It is a relief that once again we get the same answer.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 6: Counting Paths on a Grid\n",
    "\n",
    "> In a grid, how many paths are there from the upper left to the lower right corner, making only rightward or downward moves?\n",
    "     \n",
    "Here is an example 11 × 6 grid, with three of the possible paths:\n",
    "\n",
    "     ----------+     |..........     --+........\n",
    "     ..........|     |..........     ..+-+......\n",
    "     ..........|     +--+.......     ....+-+....\n",
    "     ..........|     ...|.......     ......+-+..\n",
    "     ..........|     ...|.......     ........|..\n",
    "     ..........|     ...+-------     ........+--\n",
    "     \n",
    "We can use the same three methods as the previous problem:\n",
    "\n",
    "**Method 1: Count all permutations and divide by repetitions:** Any path must consist of 10 right and 5 down moves, but they can appear in any order. Arranging 15 things in any order gives 15! = 1,307,674,368,000 possible paths. But that counts all the moves as being distinct, when actually the 10 right moves are indistinguishable, as are the 5 down moves, so we need to divide by the number of ways that they can be arranged. That gives us:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3003"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorial(15) // (factorial(10) * factorial(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Method 2: Count without repetitions**: Another way to look at it is that there will be 15 total moves, so start with all 15 being \"right\" moves and  then choose 5 of them to become \"down\" moves. So the answer is (15 choose 5), which happens to lead to the same formula we just used:\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3003"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def choose(n, k) -> int: return factorial(n) // (factorial(n - k) * factorial(k))\n",
    "\n",
    "choose(15, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Method 3: Write a program to count the paths:** The function `calculate_paths(start, goal)` counts the number of paths from the start location to the goal location, where a location is an `(x, y)` pair of integers.\n",
    "In general, the number of paths to the goal is the number of paths to the location just to the left of the goal, plus the number of paths to the location just above the goal. But there are two special cases: there is only one path (the empty path) when the start is equal to the goal, and there are zero paths when the goal is an illegal destination (one with a negative coordinate)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3003"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@lru_cache(None)\n",
    "def calculate_paths(start=(0, 0), goal=(5, 10)):\n",
    "    \"Number of paths to goal, using only 'right' and 'down' moves.\"\n",
    "    (x, y) = goal\n",
    "    return (1 if goal == start else\n",
    "            0 if x < 0 or y < 0 else\n",
    "            calculate_paths(start, (x - 1, y)) + \n",
    "            calculate_paths(start, (x, y - 1)))\n",
    "    \n",
    "calculate_paths()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Even though `calculate_paths` is slower than the `choose` calculation, it can still handle reasonably large grids:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "90548514656103281165404177077484163874504589675413336841320"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N = 100\n",
    "\n",
    "assert calculate_paths(goal=(N, N)) == choose(2 * N, N)\n",
    "\n",
    "calculate_paths(goal=(N, N))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why bother with the recursive function `calculate_paths` when the `choose` formula works so well? Good question. One reason is that the two different approaches validate each other by giving the same answer. Another reason is that we can modify `calculate_paths` to handle things that are hard to do with just the formula. For example, what if we have a grid with some obstacles in it?  I'll define a `Grid` constructor, which adopts the convention that the input is a string of rows, where a `'.'` character within a row is a passable square, and all other (non-whitespace) characters are impassible barriers. Then `calculate_grid_paths` finds the number of paths on a grid from start to goal (by default, from upper left to lower right):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Grid(text): return tuple(text.split())\n",
    "\n",
    "@lru_cache(None)\n",
    "def calculate_grid_paths(grid, start=(0, 0), goal=None):\n",
    "    \"Number of paths from start to goal on grid, using only 'right' and 'down' moves.\"\n",
    "    if goal is None: goal = (len(grid[-1]) - 1, len(grid) - 1) # bottom right\n",
    "    (x, y) = goal\n",
    "    return (1 if goal == start else\n",
    "            0 if x < 0 or y < 0 or grid[y][x] != '.' else\n",
    "            calculate_grid_paths(grid, start, (x - 1, y)) + \n",
    "            calculate_grid_paths(grid, start, (x, y - 1)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can verify that we get the same answer on the 11 by 6 empty grid:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3003"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_grid_paths(Grid(\"\"\"\n",
    "...........\n",
    "...........\n",
    "...........\n",
    "...........\n",
    "...........\n",
    "...........\n",
    "\"\"\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a grid where there are only two paths around the walls:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_grid_paths(Grid(\"\"\"\n",
    "...........\n",
    ".........|.\n",
    ".........|.\n",
    ".........|.\n",
    ".--------+.\n",
    "...........\n",
    "\"\"\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we put a hole in the wall, there should be many paths (but less than 3003 because most of the wall remains):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "167"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_grid_paths(Grid(\"\"\"\n",
    "...........\n",
    ".........|.\n",
    ".........|.\n",
    ".........|.\n",
    ".-------.+.\n",
    "...........\n",
    "\"\"\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are a couple of bigger examples, courtesy of [ascii-art-generator.org](https://www.ascii-art-generator.org/):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "626386545674738"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_grid_paths(Grid(\"\"\"\n",
    "....................................................................................................\n",
    "...................................NK0OkdddolcccccccccclloddxkO0XN..................................\n",
    "............................X0kdlc:cccccclodxllxxxkkxdloddolccccccccodkKN...........................\n",
    ".......................N0xl:cccllcco0.XXXXXX.l,O.NNNNo,kXXXXXXXNklllolccccokKN......................\n",
    "..................X.0dc::loool:,XXXdXXXXXXXXN:.X''X''X.dXXXXXXX.KcXX';coooolcclkX...................\n",
    ".................Kd.:cooo:'X.....'O.XXXXXXXXX;.........oXXXXXXXXXNo......X,lddoc:ckX................\n",
    "...............Oc,c.oc'..........l.XXXXXXXXXOX.........:NXXXXXXXXX0'.........X;oxoc;oK..............\n",
    ".............0c,lxl..............,O.XXXXXXXK;..........XlNXXXXXXXXlX............X;dxc,oX............\n",
    "...........Nx':xlX................X;dOKXX0d'.............,d0XK0xl'.................,xx;;O...........\n",
    "...........dXlk,......................XXXX.................XXX......................Xl0:xO..........\n",
    "..........OX:0:.......................................................................d0x;X.........\n",
    "..........lXdOX.......................................................................;XlXk.........\n",
    "..........lXdOX.......................................................................;XlXk.........\n",
    ".........XkX:0:...............XX....................................XX................dK,;K.........\n",
    "..........NoXlk,...........XoOKK0xc'.....X'..............XXX....X;okKXKO:X..........Xl0:Xk..........\n",
    "...........XoX:xcX.........o.XXXXXXNk:X,kNNO:..........Xl0NKoX'oK.XXXXXXX:.........'xk;,k...........\n",
    "...........X.k;'lo;X.......l.XXXXXXXX.XXXXXXNxX.......,O.XXX.XNXXXXXXXXXK,.......'oxc'cK............\n",
    ".............XNx;,:lc,.....Xd.XXXXXXXXXXXXXXX.O'.....cXXXXXXXXXXXXXXXXXX:.....Xcoo:,cO..............\n",
    "...............XNOl;;:c:;X..XlXXXXXXXXXXXXXXXXX0,..XoNXXXXXXXXXXXXXXX.O,..X;c.lc;:dK................\n",
    "..................XNkl:;;:::::oXXXXXXXXXXXXXXXXX0:'oNXXXXXXXXXXXXXXXNkc:cccc:..:d0..................\n",
    "......................NKko:;;;:lxOKX.XXXXXXXXXXXXNN.XXXXXXXXXXX..X0Odc::::cdOX......................\n",
    "...........................N0kdl:;;:;;:clodxxkkkkOOOOkkxxddolc::::;:cldOK...........................\n",
    "..................................XKOkxdolcc:;;::;;:::;::cllodxk0KN.................................\n",
    "....................................................................................................\n",
    "\"\"\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11468451846417028993973305727890751485"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_grid_paths(Grid(r\"\"\"\n",
    ".....................................................................................................\n",
    ".................WXK0kxdd.oooooooooodxOXW............................................................\n",
    "..........W0xdoooooooodxk.00KKKKK00OxdoolokXW........................................................\n",
    "..........Wk',xKXNW....................WXkollOW......................................................\n",
    "............0:c0W..........WNN.............NkccOW....................................................\n",
    ".............Xd:dN.........Nkooodk0XW........Nk:lKW..................................................\n",
    "..............W0lckN........WNKOxooooodk0NW....Xo:ckW................................................\n",
    "................WOccxX.............WX0xdoooodOKNWkc;dN.WKOK..........................................\n",
    "..................WOocoON................WXOxoododd:.ld:..cX.........................................\n",
    ".....................XxlloxKN..................NOl:'....;dKW.........................................\n",
    ".......................WXkoloooxO0XNNWWWNXK0k.oll;'...;ON............................................\n",
    "...........................WN0kdooooooooooooo.kKO;...dN......WN0kdocc.WW.clodk0NW....................\n",
    "....................NX0OkkkO0XWW...WWNNNW......Xc...xW...WXko;.....',.Nd.;'.....;lkKW................\n",
    "...............WXOo.;;::ccc::::cokKW..........Wx...oN..Nkc...,cdOKXNW....WNXKOdl;...;o0N.............\n",
    ".............Nkc,;c.OXW.....WX0xl:;:lkXW......X;.,d0.Xd'..;d0N..................WKkl'..,dKW..........\n",
    "..........WKo,,lONW..............WXkl:;cxKW......oNXd'..cON.........................NOl...lKW........\n",
    ".........Kl',xX......................W0dc::lkKo..cd;..c0W.............................WXd'..oX.......\n",
    ".......Nd''xN...........................WXOoc:'.....'kW..................................Xo..,.W.....\n",
    "......K:.lK.................................WNx'...;K.....................................W0;..xW....\n",
    "....W0,.xN..................................Nx...o0X........................................X:..xW...\n",
    "....0,.kW...................................WOcl.W...........................................X:.'O...\n",
    "...K;.xW.........................................................................................cN..\n",
    "..Nl.lN.......................................................................................Wl..k..\n",
    "..k.,K.........................................................................................k..oW.\n",
    ".Nc.oW............................................................................................cN.\n",
    ".K,.O..........................................................................................K,.:X.\n",
    ".k.;X..........................................................................................K,.:N.\n",
    ".x.:N..........................................................................................0'.lW.\n",
    ".d.cN..........................................................................................k.....\n",
    ".d.cN.........................................................................................Wo..O..\n",
    ".x.;X.........................................................................................K,.:X..\n",
    ".O.'0........................................................................................Wx..dW..\n",
    ".K,.x........................................................................................X;.,K...\n",
    ".Wl.cN......................................................................................Wd..dW...\n",
    "..O.'O......................................................................................0,.:X....\n",
    "..Nc.lN....................................................................................Nl..O.....\n",
    "...O'.k...................................................................................Wx..oW.....\n",
    "...Wd.;K..................................................................................0,.:X......\n",
    "....Xc.cN................................................................................X:.'0.......\n",
    ".....K,.oN..............................................................................No..xW.......\n",
    "......0,.dN............................................................................Wx..oW........\n",
    ".......0,.oN..............................................................................cN.........\n",
    "........0;.cX.........................................................................0,.;K..........\n",
    ".........Kc.;0W......................................................................X;..0...........\n",
    "..........Nd..dN....................................................................Xc...............\n",
    "...........W0;.;OW.................................................................Xc..kW............\n",
    ".............Nd'.c0W..............................................................K:..kW.............\n",
    "...............Xo..:ON..........................................................Nk'.;0W..............\n",
    ".................Xd'.,dKW.....................................................NO:..oX................\n",
    "...................Xx:..:d0N........................WNXK0000KKXNW.........WXO....c0W.................\n",
    ".....................WKx:'.,cdOKNW...........WNKOxol;'........'',;:cclllc.;......KW..................\n",
    "........................WXOo:,..';cloodddoolc;'..',;ldk00K000Okxoolc:::::.ldOXW......................\n",
    ".............................NKOxolc:;;,,;:ccodk0NWW.................................................\n",
    ".....................................WWWWW...........................................................\n",
    ".....................................................................................................\n",
    "\"\"\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can you verify that these last three answers are correct?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 7: Counting Positions in Fischerandom Chess\n",
    "\n",
    "> In this [variant](https://en.wikipedia.org/wiki/Chess960) of chess, the pieces are set up in a random but restricted fashion. The pawns are in their regular positions, and the major white pieces are placed randomly on the first rank, with two restrictions: the bishops must be placed on opposite-color squares, and the king must be placed between the rooks. The black pieces are set up to mirror the white pieces. How many starting positions are there?\n",
    "\n",
    "We can answer by generating all distinct permutations of the eight pieces and quantifying (counting) the number of permutations that are legal:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "960"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from statistics import median\n",
    "\n",
    "def legal_position(pieces):\n",
    "    \"Legal if bishops are on different colors, and king is between rooks.\"\n",
    "    B, R, K = map(pieces.index, 'BRK')\n",
    "    b, r    = map(cat(pieces).rindex, 'BR')\n",
    "    return (B % 2 != b % 2) and R < K < r or r < K < R\n",
    "\n",
    "quantify(set(permutations('RNBKQBNR')), legal_position)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[*Note:* initially I wrote `pieces.rindex` instead of `cat(pieces).rindex`, because I forgot that while tuples, lists and strings all have an `index` method, only strings have `rindex`.  How annoying! In Ruby, both strings and arrays have `index` and `rindex`. In  Java and Javascript, both strings and lists/arrays have both `indexOf` and `lastIndexOf`. What's wrong with Python?]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 8: Counting Change\n",
    "\n",
    "> How many ways are there to select coins that add up to a specified amount of money? For example, to make 10 cents with an unlimited number of coins of denomination 10, 5, and 1 cents, there are four ways: {10, 5+5, 5+1+1+1+1+1, 1+1+1+1+1+1+1+1+1+1}. \n",
    "\n",
    "For this problem there is no sense of advanccing from $k$ to $k$+1; instead we will need a recursive breakdown. Here are the cases:\n",
    "- There is one way to add up to zero cents (with no coins).\n",
    "- It is not possible to add up to a negative amount (because there are no negative coins).\n",
    "- It is not possible to add up to a positive amount if you don't have any coin denominations to do it.\n",
    "- In the general case,  you should add up the number of ways you can make change by using one coin of the first denomination, plus the number of ways you can do it by skipping the first denomination. If you use one coin of a denomination you are free to use another one, but once you skip a denomination, you can't go back to it later. That way, assuming we are looking at the largest denominations first, we will count 10+1, but we will not also count 1+10, which is as it should be."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "@lru_cache(None)\n",
    "def calculate_change(amount, denominations=(100, 50, 25, 10, 5, 1)):\n",
    "    return (1 if amount == 0 else\n",
    "            0 if amount < 0 or not denominations else\n",
    "            calculate_change(amount - denominations[0], denominations) + \n",
    "            calculate_change(amount, denominations[1:]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_change(11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "293"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_change(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "139599978000"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_change(9999)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 8b: Limited Change\n",
    "\n",
    "> The above assumed that you had a limitless supply of each denomination. What if you don't? \n",
    "\n",
    "I'll define `calculate_limited_change`, where, instead of specifying denominations, you specify actual coins, repeating the ones you have more than one of.  We use the same strategy, and if you skip a denomination, you can never use another coin of the same denomination. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@lru_cache(None)\n",
    "def calculate_limited_change(amount, coins):\n",
    "    return (1 if amount == 0 else\n",
    "            0 if amount < 0 or not coins else\n",
    "            calculate_limited_change(amount - coins[0], coins[1:]) + \n",
    "            calculate_limited_change(amount, tuple(c for c in coins if c != coins[0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_limited_change(10, (10, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_limited_change(10, (50, 25, 10, 10, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_limited_change(10, (10, 5, 1, 1, 1, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_limited_change(25, (25, 10, 10, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_limited_change(25, (25, 10, 5, 5, 5, 5, 1, 1, 1, 1)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 8c: Optimal Denominations\n",
    "\n",
    "The  *[July 20, 2018 Riddler](https://fivethirtyeight.com/features/damn-the-torpedoes-two-puzzles-ahead/)* poses this problem (which has a [Wikipedia](https://en.wikipedia.org/wiki/Change-making_problem) article and a [journal](https://cs.uwaterloo.ca/~shallit/Papers/change2.pdf) article):\n",
    "\n",
    "> I was recently traveling in Europe and struck by the number of coins the euro uses. They have 2 euro, 1 euro, 50 cent, 20 cent, 10 cent, 5 cent, 2 cent and 1 cent coins. This got me thinking: If Riddler Nation needed to make change (anywhere from 0.01 to 0.99) and was establishing its own denomination, what values of coins would be ideal to yield the smallest number of coins in any transaction? When picking values, let’s say we’re ditching the Europeans and limiting our denomination to four different coin denominations — replacing the current common American ones of penny, nickel, dime and quarter.  \n",
    "\n",
    "This is an optimization problem, not a counting problem, but it is related to the other coin/denomination problems here. Here's how I address the problem:\n",
    "- The function `totalcoins(denominations)` will give the total number of coins (taken from those denominations) that are\n",
    "required to make each amount of change from 1 to 99 cents (assuming optimal change choices).\n",
    "- The function `mincoins(amount, denominations)` computes this optimal number of coins for a given amount, or returns infinity if the amount cannot be made.\n",
    "- I know I'm going to need a 1 cent piece; otherwise I can't make 1 cent total.\n",
    "- That leaves 3 coins that could be anywhere from 2 to 99 cents; let's try all combinations (even though it will take a minute or two). \n",
    "- We'll report the candidate combination that has the minimum total number of coins.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1min 40s, sys: 5.93 s, total: 1min 46s\n",
      "Wall time: 1min 55s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(25, 18, 5, 1)"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def totalcoins(denominations) -> int: \n",
    "    \"The total number of coins needed to make change for all amounts up to 99 cents.\"\n",
    "    return sum(mincoins(a, denominations) for a in range(1, 100))\n",
    "\n",
    "@lru_cache(None)\n",
    "def mincoins(amount, denominations) -> int:\n",
    "    \"The minimum number of coins, taken from denominations, that add to amount.\"\n",
    "    return (0   if amount == 0 else\n",
    "            inf if not denominations or amount <  min(denominations) else\n",
    "            min(mincoins(amount, denominations[1:]),\n",
    "                mincoins(amount - denominations[0], denominations) + 1))\n",
    "\n",
    "candidates = ((L, M, S, 1) for S, M, L in combinations(range(2, 100), 3))\n",
    "\n",
    "%time min(candidates, key=totalcoins) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Interesting! This is almost the US system of coins; we just need to trade in the dime for an 18 cent piece."
   ]
  }
 ],
 "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}