Golomb-Puzzle.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sol Golomb’s Rectangle Puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This problem by Solomon Golomb was presented by Gary Antonik in his 14/4/14 New York Times [Numberplay column](http://wordplay.blogs.nytimes.com/2014/04/14/rectangle):\n",
    "\n",
    "><i>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.\n",
    ">\n",
    ">1. How many different sets of five rectangles are possible?\n",
    ">\n",
    ">2. What are the maximum and minimum values for the total areas of the five rectangles?\n",
    ">\n",
    ">3. What other values for the total areas of the five rectangles are possible?\n",
    ">\n",
    ">4. Which sets of rectangles may be assembled to form a square?</i>\n",
    "\n",
    "To me, these are interesting questions because, first, I have a (slight) personal connection to Solomon Golomb (my former colleague at USC) and to Nelson Blachman (the father of my colleague Nancy Blachman), who presented the problem to  Antonik, and second, I find it interesting that the problems span the range from mathematical to computational. Let's answer them."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. How many different sets of five rectangles are possible?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a basic [combinatorics](http://en.wikipedia.org/wiki/Combinatorics) or counting problem. I will present *three* methods to count the sets. If all goes well they will give the same answer. The example set of rectangles given in the problem was\n",
    "\n",
    "> {1 &times; 3, 2 &times; 4, 5 &times; 7, 6 &times; 8, 9 &times; 10}\n",
    "    \n",
    "and in general it would be\n",
    "\n",
    "> {A &times; B, C &times; D, E &times; F, G &times; H, I &times; 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 &times; 3, that is the same rectangle as 3 &times; 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 &times; 3, that yields the same set as if we filled C and D with 1 &times; 3.  So divide again by 5! (the number of permutations of 5 things) to account for this.\n",
    "That gives us:\n",
    "\n",
    "> <a href=\"https://www.google.com/search?ie=UTF-8#q=10!+%2F+2%5E5+/+5!\">10! / 2<sup>5</sup> / 5!</a> = 945.  \n",
    "\n",
    "(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.  An alternate to \"count and divide\" is to count directly 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 (it will be 3 if the first rectangle was 1 &times; 2; otherwise it will be 2, but either way there is only one choice).  That leaves 7 choices for D, 5 for F, 3 for H and 1 for J. So:\n",
    "\n",
    "> 9 &times; 7 &times; 5 &times; 3 &times; 1 = 945.\n",
    "\n",
    "(It is always a relief when two methods give the same answer.)\n",
    "          \n",
    "**Method 3: Write a program to enumerate the sets:** We'll represent the 1 &times; 3 rectangle as the tuple `(1, 3)` and the example set of rectangles as the set\n",
    "\n",
    "    {(1, 3), (2, 4), (5, 7), (6, 8), (9, 10)}\n",
    "\n",
    "We'll write a program to generate all possible sets of rectangles, following method 2, and then just count how many there are. To implement method 2, the minimum side will always be the first element, A, in an (A, B) pair. We iterate through all possible values for B, and then join that pair with all possible rectangles made from the remaining sides. We also have to handle the case when there are no sides; then there is one possible set of rectangles: the empty set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rectangle_sets(sides):\n",
    "    \"Given a set of sides, list all distinct sets of rectangles that can be made.\"\n",
    "    if not sides:\n",
    "        return [ set() ]\n",
    "    else:\n",
    "        A = min(sides)\n",
    "        return [ {(A, B)} | other_rects\n",
    "                for B in sides if B is not A\n",
    "                for other_rects in rectangle_sets(sides - {A, B}) ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{(1, 2), (3, 4)}, {(1, 3), (2, 4)}, {(1, 4), (2, 3)}]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rectangle_sets({1, 2, 3, 4})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see above that there are three possible rectangle sets for 4 sides (the 1 can pair with any other side, and then a second rectangle can only be made one way from the remaining 2 sides). Below we count how many can be made with 10 sides:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "945"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sides = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}\n",
    "\n",
    "all_sets = rectangle_sets(sides)\n",
    "\n",
    "len(all_sets)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(It is a relief that once again we get the same answer, 945.)  \n",
    "\n",
    "I don't want to print all 945 sets, but let's peek at every 100th one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{(1, 2), (3, 4), (5, 6), (7, 8), (9, 10)},\n",
       " {(1, 2), (3, 10), (4, 8), (5, 6), (7, 9)},\n",
       " {(1, 3), (2, 10), (4, 6), (5, 7), (8, 9)},\n",
       " {(1, 4), (2, 10), (3, 5), (6, 8), (7, 9)},\n",
       " {(1, 5), (2, 9), (3, 8), (4, 6), (7, 10)},\n",
       " {(1, 6), (2, 9), (3, 5), (4, 7), (8, 10)},\n",
       " {(1, 7), (2, 9), (3, 4), (5, 8), (6, 10)},\n",
       " {(1, 8), (2, 7), (3, 9), (4, 5), (6, 10)},\n",
       " {(1, 9), (2, 7), (3, 5), (4, 6), (8, 10)},\n",
       " {(1, 10), (2, 7), (3, 4), (5, 8), (6, 9)}]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_sets[::100]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. What are the maximum and minimum values for the total areas of the five rectangles?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "I think I know this one, but I'm not completely sure.  I know that a rectangle with a fixed perimeter has maximum area when it is a square. My guess is that the maximum total area occurs when each rectangle is *almost* square: a 9 &times; 10 rectangle; 7 &times; 8; and so on.  So that would give us a maximum area of:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "190"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(1 * 2) + (3 * 4) + (5 * 6) + (7 * 8) + (9  * 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And the minimum area should be when the rectangles deviate the most from squares: a 1 &times; 10, and so on:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "110"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(1 * 10) + (2 * 9) + (3 * 8) + (4 * 7) + (5 * 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since I am not sure, I will double check by finding the rectangle sets with the min and max total areas:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def total_area(rectangles): return sum(w * h for (w, h) in rectangles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(1, 2), (3, 4), (5, 6), (7, 8), (9, 10)}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(all_sets, key=total_area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(1, 10), (2, 9), (3, 8), (4, 7), (5, 6)}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min(all_sets, key=total_area)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This verifies my intuitions. But I still don't completely understand the situation.  Suppose there are *N* sides that are not  consecutive integers.  Will the maximum total area always be formed by combining the two biggest sides, and so on?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. What other values for the total areas of the five rectangles are possible?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I have no idea how to figure this out mathematically from first principles, but it is easy to compute with the code we already have:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 177, 178, 179, 180, 181, 182, 183, 184, 186, 187, 190]\n"
     ]
    }
   ],
   "source": [
    "areas = {total_area(s) for s in all_sets}\n",
    "print(sorted(areas))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is there a more succint way to describe these values? Let's see ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{176, 185, 188, 189}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set(range(110, 191)) - areas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The answer is: \"All the integers between 110 and 190 inclusive, except 176, 185, 188, and 189.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Which sets of rectangles may be assembled to form a square?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The only way I can think about this is to write a program; I don't see any way to work it out by hand.  I do know that the total area will have to be a perfect square, and since the total area is between 110 and 191, that means either 121, 144, or 169:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(121, {(1, 6), (2, 9), (3, 10), (4, 8), (5, 7)}),\n",
       " (121, {(1, 6), (2, 10), (3, 8), (4, 9), (5, 7)}),\n",
       " (121, {(1, 6), (2, 10), (3, 9), (4, 7), (5, 8)}),\n",
       " (121, {(1, 7), (2, 10), (3, 6), (4, 9), (5, 8)}),\n",
       " (121, {(1, 8), (2, 6), (3, 10), (4, 9), (5, 7)}),\n",
       " (121, {(1, 8), (2, 7), (3, 10), (4, 6), (5, 9)}),\n",
       " (121, {(1, 8), (2, 9), (3, 7), (4, 6), (5, 10)}),\n",
       " (121, {(1, 8), (2, 10), (3, 5), (4, 9), (6, 7)}),\n",
       " (121, {(1, 9), (2, 7), (3, 6), (4, 10), (5, 8)}),\n",
       " (121, {(1, 9), (2, 7), (3, 8), (4, 6), (5, 10)}),\n",
       " (121, {(1, 9), (2, 7), (3, 10), (4, 5), (6, 8)}),\n",
       " (121, {(1, 9), (2, 8), (3, 6), (4, 7), (5, 10)}),\n",
       " (121, {(1, 10), (2, 5), (3, 9), (4, 8), (6, 7)}),\n",
       " (121, {(1, 10), (2, 8), (3, 7), (4, 5), (6, 9)}),\n",
       " (144, {(1, 3), (2, 9), (4, 10), (5, 7), (6, 8)}),\n",
       " (144, {(1, 3), (2, 10), (4, 7), (5, 9), (6, 8)}),\n",
       " (144, {(1, 3), (2, 10), (4, 8), (5, 7), (6, 9)}),\n",
       " (144, {(1, 5), (2, 6), (3, 8), (4, 10), (7, 9)}),\n",
       " (144, {(1, 7), (2, 4), (3, 8), (5, 9), (6, 10)}),\n",
       " (144, {(1, 7), (2, 9), (3, 5), (4, 6), (8, 10)}),\n",
       " (144, {(1, 9), (2, 5), (3, 7), (4, 6), (8, 10)}),\n",
       " (144, {(1, 9), (2, 6), (3, 5), (4, 7), (8, 10)}),\n",
       " (144, {(1, 10), (2, 4), (3, 5), (6, 8), (7, 9)}),\n",
       " (169, {(1, 2), (3, 5), (4, 9), (6, 10), (7, 8)}),\n",
       " (169, {(1, 2), (3, 7), (4, 6), (5, 10), (8, 9)}),\n",
       " (169, {(1, 2), (3, 7), (4, 9), (5, 6), (8, 10)}),\n",
       " (169, {(1, 2), (3, 8), (4, 5), (6, 10), (7, 9)}),\n",
       " (169, {(1, 3), (2, 5), (4, 8), (6, 9), (7, 10)}),\n",
       " (169, {(1, 3), (2, 7), (4, 5), (6, 10), (8, 9)}),\n",
       " (169, {(1, 3), (2, 7), (4, 8), (5, 6), (9, 10)}),\n",
       " (169, {(1, 4), (2, 5), (3, 7), (6, 9), (8, 10)}),\n",
       " (169, {(1, 5), (2, 3), (4, 9), (6, 7), (8, 10)}),\n",
       " (169, {(1, 5), (2, 4), (3, 8), (6, 7), (9, 10)}),\n",
       " (169, {(1, 5), (2, 7), (3, 4), (6, 8), (9, 10)}),\n",
       " (169, {(1, 6), (2, 3), (4, 8), (5, 7), (9, 10)})]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "perfect_squares = {i ** 2 for i in range(100)}\n",
    "\n",
    "sorted((total_area(s), s) \n",
    "       for s in all_sets if total_area(s) in perfect_squares)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "35"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So 35 out of 945 rectangle sets *might* be assembled into a square; we don't know yet if they *can* be. \n",
    "\n",
    "# Packing Rectangles into a Square\n",
    "\n",
    "I would like to see *how* the rectangles are packed into the square, not just *which* sets can be packed, so I'll need a data structure to hold information on which rectangle goes where, and a way to visually display the results.\n",
    "I'll represent a *Grid* as a two-dimensional array: a list of rows, each of which is a list of cells, with the idea that each cell will be covered by a rectangle by assigning `grid[y][x] = rect` (and the special rectangle `empty` will be used to mark a cell as uncovered). I only need to deal with square grids:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "empty = (0, 0)\n",
    "\n",
    "def Square(n):\n",
    "    \"Create an [n x n] grid of empty cells.\"\n",
    "    return [[empty for col in range(n)] \n",
    "            for row in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],\n",
       " [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],\n",
       " [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],\n",
       " [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],\n",
       " [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0)]]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Square(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's make a function to place a single rectangle onto a grid:  `place_rectangle_at((w, h), grid, (x0, y0))` places a rectangle of width *w* and height *h* onto a grid at position (x<sub>0</sub>, y<sub>0</sub>).  If the rectangle overlaps a non-empty cell, or goes off the grid, we return `None` to indicate that this is not a legal placement. If the rectangle does fit, we return a new grid with the new rectangle placed on it (we do not modify the original grid):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def place_rectangle_at(rect, grid, pos):\n",
    "    \"\"\"Place the rectangle of size (w, h) onto grid at position (x0, y0).\n",
    "    Return a new grid, or None if the rectangle cannot be placed.\"\"\"\n",
    "    (w, h)   = rect\n",
    "    (x0, y0) = pos\n",
    "    newgrid  = [row.copy() for row in grid] \n",
    "    for x in range(x0, x0+w):\n",
    "        for y in range(y0, y0+h):\n",
    "            if y >= len(grid) or x >= len(grid[y]) or newgrid[y][x] is not empty:\n",
    "                return None   \n",
    "            newgrid[y][x] = rect\n",
    "    return newgrid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(0, 0), (0, 0), (0, 0), (0, 0), (0, 0)],\n",
       " [(0, 0), (0, 0), (3, 4), (3, 4), (3, 4)],\n",
       " [(0, 0), (0, 0), (3, 4), (3, 4), (3, 4)],\n",
       " [(0, 0), (0, 0), (3, 4), (3, 4), (3, 4)],\n",
       " [(0, 0), (0, 0), (3, 4), (3, 4), (3, 4)]]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Place a 3 x 4 rectangle on a 5 x 5 square grid, 2 cells over and 1 down:\n",
    "place_rectangle_at((3, 4), Square(5), (2, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(2, 5), (2, 5), (0, 0), (0, 0), (0, 0)],\n",
       " [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],\n",
       " [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],\n",
       " [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],\n",
       " [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)]]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Place two rectangles on a grid\n",
    "grid0 = Square(5)\n",
    "grid1 = place_rectangle_at((3, 4), grid0, (2, 1))\n",
    "grid2 = place_rectangle_at((2, 5), grid1, (0, 0))\n",
    "grid2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(2, 5), (2, 5), (3, 1), (3, 1), (3, 1)],\n",
       " [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],\n",
       " [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],\n",
       " [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],\n",
       " [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)]]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Place a third rectangle that just barely fits\n",
    "place_rectangle_at((3, 1), grid2, (2, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "# Alternatively, try to place a third rectangle that does not fit\n",
    "print(place_rectangle_at((4, 1), grid2, (2, 0)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need a strategy for packing a set of rectangles onto a grid.  I know that many variants of [bin packing problems](http://en.wikipedia.org/wiki/Bin_packing_problem) are NP-hard, but we only have 5 rectangles, so it should be easy: just exhaustively try each rectangle in each possible position, and in both possible orientations (horizontal and vertical). But placing rectangles is commutative, so we can do this two ways:\n",
    "\n",
    "> Way 1: Considering the *rectangles* in a fixed order, try every possible *position* for each *rectangle*.\n",
    "\n",
    "or\n",
    "\n",
    "> Way 2: Considering the *positions* in a fixed order, try every possible *rectangle* for each *position*.\n",
    "\n",
    "In Way 1, we could pre-sort the rectangles (say, biggest first).  Then we try to put the biggest rectangle in all possible positions on the grid, and for each position that fits, try putting the second biggest rectangle in all remaining positions, and so on.  As a rough estimate, assume there are on average about 10 ways to place a rectangle.  Then this way will look at about 10<sup>5</sup> = 100,000 combinations.\n",
    "\n",
    "In Way 2, we consider the positions in some fixed order; say top-to-bottom, left-to right.  Take the first empty position (say, the upper left corner).  Try putting each of the rectangles there, and for each one that fits, try all possible rectangles in the next empty position, and so on. There are only 5! permutations of rectangles, and each rectangle can go either horizontaly or vertically, so we would have to consider 5! &times; 2<sup>5</sup> = 3840 combinations.  Since 3840 &lt; 100,000, I'll go with Way 2.  Here is a more precise description:\n",
    "\n",
    "> Way 2: To `pack` a set of rectangles onto a grid, find the first empty cell on the grid.  Try in turn all possible placements of any rectangle (in either orientation) at that position. For each one that fits, try to `pack` the remaining rectangles, and return the resulting grid if one of these packings succeeds.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pack(rectangles, grid):\n",
    "    \"\"\"Find a way to pack all rectangles onto grid and return the packed grid,\n",
    "    or return None if not possible.\"\"\"\n",
    "    if not rectangles:\n",
    "        return grid \n",
    "    pos = first_empty_cell(grid)\n",
    "    if grid and pos:\n",
    "        for (rectangles2, grid2) in rectangle_placements(rectangles, grid, pos):\n",
    "            solution = pack(rectangles2, grid2)\n",
    "            if solution:\n",
    "                return solution\n",
    "\n",
    "def rectangle_placements(rectangles, grid, pos):\n",
    "    \"Yield all (rectangles2, grid2) pairs that are the result of placing any rectangle at pos on grid.\"\n",
    "    for (w, h) in rectangles:\n",
    "        for rect in [(w, h), (h, w)]:\n",
    "            grid2 = place_rectangle_at(rect, grid, pos)\n",
    "            if grid2: \n",
    "                yield rectangles - {(w, h)}, grid2       \n",
    "                \n",
    "def first_empty_cell(grid):\n",
    "    \"The uppermost, leftmost empty cell.\"\n",
    "    for (y, row) in enumerate(grid):\n",
    "        for (x, cell) in enumerate(row):\n",
    "            if cell is empty:\n",
    "                return (x, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try a simple example that I know will fit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(2, 5), (2, 5), (3, 1), (3, 1), (3, 1)],\n",
       " [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],\n",
       " [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],\n",
       " [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)],\n",
       " [(2, 5), (2, 5), (3, 4), (3, 4), (3, 4)]]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pack({(1, 3), (2, 5), (3, 4)}, Square(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It works! But it is not pretty.\n",
    "\n",
    "# Colored Rectangles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It would be nicer to have a graphical display of colored rectangles. I will define the function `show` which displays a grid as colored rectangles, by calling upon `html_table`, which formats any grid into HTML text."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import HTML, display, clear_output\n",
    "\n",
    "def show(grid):\n",
    "    \"Display a colored HTML representation of this grid, unless it is None.\"\n",
    "    if grid:\n",
    "        display(html_table(grid, colored_cell))\n",
    "    \n",
    "def html_table(grid, cell_function='<td>{}'.format):\n",
    "    \"Return an HTML <table>, where each cell's contents comes from calling cell_function(grid[y][x])\"\n",
    "    return HTML('<table>{}</table>'\n",
    "                .format(cat('\\n<tr>' + cat(map(cell_function, row)) \n",
    "                        for row in grid)))\n",
    "\n",
    "def colored_cell(rect): \n",
    "    x, y = sorted(rect)\n",
    "    return '<td style=\"background-color:{}\">{}{}'.format(colors[x], x%10, y%10)\n",
    "\n",
    "colors = 'lightgrey yellow plum chartreuse cyan coral red olive slateblue lightgrey wheat'.split()\n",
    "\n",
    "cat = ''.join"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<tr><td style=\"background-color:plum\">25<td style=\"background-color:plum\">25<td style=\"background-color:yellow\">13<td style=\"background-color:yellow\">13<td style=\"background-color:yellow\">13\n",
       "<tr><td style=\"background-color:plum\">25<td style=\"background-color:plum\">25<td style=\"background-color:chartreuse\">34<td style=\"background-color:chartreuse\">34<td style=\"background-color:chartreuse\">34\n",
       "<tr><td style=\"background-color:plum\">25<td style=\"background-color:plum\">25<td style=\"background-color:chartreuse\">34<td style=\"background-color:chartreuse\">34<td style=\"background-color:chartreuse\">34\n",
       "<tr><td style=\"background-color:plum\">25<td style=\"background-color:plum\">25<td style=\"background-color:chartreuse\">34<td style=\"background-color:chartreuse\">34<td style=\"background-color:chartreuse\">34\n",
       "<tr><td style=\"background-color:plum\">25<td style=\"background-color:plum\">25<td style=\"background-color:chartreuse\">34<td style=\"background-color:chartreuse\">34<td style=\"background-color:chartreuse\">34</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# For example:\n",
    "show(pack({(1, 3), (2, 5), (3, 4)}, Square(5)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's much nicer to look at! Now we can show all the rectangles that are packable into a square:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:yellow\">12<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:yellow\">12<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<tr><td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60\n",
       "<tr><td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60\n",
       "<tr><td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60\n",
       "<tr><td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60\n",
       "<tr><td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60\n",
       "<tr><td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60\n",
       "<tr><td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60\n",
       "<tr><td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60\n",
       "<tr><td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:olive\">79<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60\n",
       "<tr><td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:yellow\">12<td style=\"background-color:yellow\">12<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60<td style=\"background-color:red\">60\n",
       "<tr><td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38\n",
       "<tr><td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38\n",
       "<tr><td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:cyan\">45<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38<td style=\"background-color:chartreuse\">38</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<tr><td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58\n",
       "<tr><td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58\n",
       "<tr><td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58\n",
       "<tr><td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58\n",
       "<tr><td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58<td style=\"background-color:coral\">58\n",
       "<tr><td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:yellow\">16\n",
       "<tr><td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:yellow\">16\n",
       "<tr><td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:yellow\">16\n",
       "<tr><td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:chartreuse\">39<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:yellow\">16\n",
       "<tr><td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:yellow\">16\n",
       "<tr><td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:plum\">20<td style=\"background-color:yellow\">16</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<tr><td style=\"background-color:plum\">28<td style=\"background-color:plum\">28<td style=\"background-color:yellow\">19<td style=\"background-color:yellow\">19<td style=\"background-color:yellow\">19<td style=\"background-color:yellow\">19<td style=\"background-color:yellow\">19<td style=\"background-color:yellow\">19<td style=\"background-color:yellow\">19<td style=\"background-color:yellow\">19<td style=\"background-color:yellow\">19\n",
       "<tr><td style=\"background-color:plum\">28<td style=\"background-color:plum\">28<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:plum\">28<td style=\"background-color:plum\">28<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:plum\">28<td style=\"background-color:plum\">28<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:plum\">28<td style=\"background-color:plum\">28<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:plum\">28<td style=\"background-color:plum\">28<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:plum\">28<td style=\"background-color:plum\">28<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:plum\">28<td style=\"background-color:plum\">28<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:cyan\">47<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:chartreuse\">36<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def pack_square(rectangles):\n",
    "    \"Pack rectangles into a square of appropriate size, if possible.\"\n",
    "    A = total_area(rectangles)\n",
    "    if A in perfect_squares:\n",
    "        return pack(rectangles, Square(int(A ** 0.5)))\n",
    "\n",
    "for s in all_sets:\n",
    "    show(pack_square(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So there are 4 sets of rectangles that work."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Animated Colored Rectangles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is gratifying to see the final results, and have the computation be so fast, but I'd like to get a better understanding of the process of finding the results.  I can try to visualize the process by *animating* the search that `pack` does: every time we successfully call `place_rectangle_at`, I can show the new grid, and then pause for a short period.  I accomplish this by modifying `pack` to take an optional argument, `animation`, which when false gives the same behavior as before, but when it is a number, pauses for that number of seconds in between displaying each step of the packing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "def pack(rectangles, grid, animation=False): \n",
    "    \"\"\"Find a way to pack all rectangles onto grid and return the packed grid,\n",
    "    or return None if not possible. \n",
    "    Pause `animation` seconds between displaying each rectangle placement if `animation` is not false.\"\"\"\n",
    "    if animation: \n",
    "        clear_output()\n",
    "        show(grid)\n",
    "        time.sleep(animation) \n",
    "    if not rectangles:\n",
    "        return grid \n",
    "    pos = first_empty_cell(grid)\n",
    "    if grid and pos:\n",
    "        for (rectangles2, grid2) in rectangle_placements(rectangles, grid, pos): \n",
    "            solution = pack(rectangles2, grid2, animation)\n",
    "            if solution:\n",
    "                return solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you are running this in a live IPython notebook (not in nbviewer), you can see for yourself by re-running this cell:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table>\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50<td style=\"background-color:coral\">50\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:yellow\">12<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:chartreuse\">37<td style=\"background-color:yellow\">12<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89\n",
       "<tr><td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:cyan\">46<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89<td style=\"background-color:slateblue\">89</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "pack({(1, 2), (3, 7), (4, 6), (5, 10), (8, 9)}, Square(13), 1);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Now For Something Completely Different: Cryptarithmetic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On April 28, Gary Antonik had another [Numberplay column](http://wordplay.blogs.nytimes.com/2014/04/28/num/) that quotes my friend Bill Gosper. (Gosper often presents more advanced puzzles in the [math-fun](http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun) mailing list.)  This puzzle was:\n",
    "\n",
    ">For the expression  N U M + B E R = P L A Y,\n",
    "\n",
    "> Which distinct numerals (each different) can be substituted for letters to make a valid expression?\n",
    "\n",
    "> How many solutions are there?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I tackled this type of problem (known as a [cryptarithmetic](http://mathworld.wolfram.com/Cryptarithmetic.html) or [alphametic](http://mathworld.wolfram.com/Alphametic.html) problem) in my Udacity class [CS 212](https://www.udacity.com/wiki/cs212/unit-2#cryptarithmetic). My approach was simple: try all permutations of digits replacing letters (that should be quick and easy&mdash;there can be at most 10 factorial or 3.6 million permutations), then for each one, use Python's `eval` function to see if the resulting string is a true expression.  The basic idea is simple, but there are complications to worry about:\n",
    "\n",
    "1. Math uses `=` and Python uses `==` for equality; we'll allow either one.\n",
    "2. The more detailed rules for these problems say that a number with a leading zero (like `012`) is illegal (but `0` itself is ok).\n",
    "3. By default, Python thinks that 3/2 is 1, because integer division rounds down.  But we can import \"proper\" division from the future.\n",
    "4. If we try to eval an expression like 1/0, Python raises an error; we'll have to handle it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import division\n",
    "import itertools\n",
    "import re\n",
    "\n",
    "def solve_all(formula):\n",
    "    \"\"\"Given a formula like 'NUM + BER = PLAY', fill in digits to solve it.\n",
    "    Input formula is a string; generate each digit-filled-in string.\"\"\"\n",
    "    formula = formula.replace(' = ', ' == ')\n",
    "    for exp in replace_letters(formula):\n",
    "        if valid(exp):\n",
    "            yield exp\n",
    "\n",
    "def replace_letters(formula):\n",
    "    \"Generate all possible replacements of letters with digits in formula.\"\n",
    "    letters = ''.join(set(re.findall('[A-Z]', formula)))\n",
    "    for digits in itertools.permutations('1234567890', len(letters)):\n",
    "        trans = str.maketrans(letters, ''.join(digits))\n",
    "        yield formula.translate(trans)\n",
    "\n",
    "def valid(exp):\n",
    "    \"Expression is valid iff it has no numbers with leading zero, and evals true.\"\n",
    "    try:\n",
    "        return not leading_zero(exp) and eval(exp)\n",
    "    except ArithmeticError:\n",
    "        return False\n",
    "    \n",
    "leading_zero = re.compile(r'\\b0[0-9]').search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'857 + 349 == 1206'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(solve_all('NUM + BER = PLAY'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 29 s, sys: 42.2 ms, total: 29.1 s\n",
      "Wall time: 29.1 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "96"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time len(list(solve_all('NUM + BER = PLAY')))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So there are 96 solutions, but it is a bit slow to find them all. For each of the permutations of digits, we substitute the digits for letters, and then call  `eval(exp)` on the resulting string.  The majority of time is spent inside `eval`.  But the expression is basically the same each time; we could save a lot of work if we eval the expression just once, yielding a Python function, and then call that function once for each permutation of digits.  In other words, we want to take an expression such as\n",
    "\n",
    "    \"NUM + BER == PLAY\"\n",
    "    \n",
    "and transform it into the Python function\n",
    "\n",
    "\n",
    "    lambda A,B,E,M,L,N,P,R,U,Y: (100*N+10*U+M) + (100*B+10*E+R) == (1000*P+100*L+10*A+Y)\n",
    "    \n",
    "Actually that's not quite right.  The rules are that the first letter of each multi-letter word (the \"N\" in \"NEW\"; the \"B\" in \"BER\"; and the \"P\" in \"PLAY\") cannot be a zero. So the function should be:\n",
    "\n",
    "    lambda A,B,E,M,L,N,P,R,U,Y: N and B and P and (100*N+10*U+M) + (100*B+10*E+R) == (1000*P+100*L+10*A+Y)\n",
    "\n",
    "In my Udacity class I show a solution to this problem; you can [go there](https://www.udacity.com/wiki/cs212/unit-2#rethinking-eval) or see it here. Here is the code to compile a formula (or expression) into a Python function: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compile_formula(formula, verbose=False):\n",
    "    \"\"\"Compile formula into a function.   Also return letters found, as a str,\n",
    "    in same order as parms of function. For example, 'YOU == ME**2' returns\n",
    "    (lambda Y,M,E,U,O: Y and M and ((100*Y+10*O+U) == (10*M+E)**2)), 'YMEUO'\"\"\"\n",
    "    formula      = formula.replace(' = ', ' == ')\n",
    "    letters      = ''.join(set(re.findall('[A-Z]', formula)))\n",
    "    firstletters = set(re.findall(r'\\b([A-Z])[A-Z]', formula))\n",
    "    body         = re.sub('[A-Z]+', compile_word, formula)\n",
    "    if firstletters:\n",
    "        body = '{} and ({})'.format(' and '.join(firstletters), body)\n",
    "    fn = 'lambda {}: {}'.format(','.join(letters), body)\n",
    "    if verbose: print(fn)\n",
    "    return eval(fn), letters\n",
    "\n",
    "def compile_word(matchobj):\n",
    "    \"Compile the word 'YOU' as '(100*Y + 10*O + U)'.\"\n",
    "    word = matchobj.group()\n",
    "    terms = reversed([mult(10**i, L) for (i, L) in enumerate(reversed(word))])\n",
    "    return '(' + '+'.join(terms) + ')'\n",
    "\n",
    "def mult(factor, var): return var if factor == 1 else str(factor) + '*' + var"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda Y,M,E,O,U: Y and M and ((100*Y+10*O+U) == (10*M+E)**2)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(<function __main__.<lambda>>, 'YMEOU')"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compile_formula(\"YOU == ME**2\", verbose=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lambda L,A,Y,P,M,E,R,U,B,N: P and B and N and ((100*N+10*U+M) + (100*B+10*E+R) == (1000*P+100*L+10*A+Y))\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(<function __main__.<lambda>>, 'LAYPMERUBN')"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compile_formula(\"NUM + BER == PLAY\", verbose=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def faster_solve_all(formula):\n",
    "    \"\"\"Given a formula like 'ODD + ODD == EVEN', fill in digits to solve it.\n",
    "    Input formula is a string; output is a digit-filled-in string or None.\n",
    "    Capital letters are variables. This version precompiles the formula; only one eval per formula.\"\"\"\n",
    "    fn, letters = compile_formula(formula)\n",
    "    for digits in itertools.permutations((1,2,3,4,5,6,7,8,9,0), len(letters)):\n",
    "        try:\n",
    "            if fn(*digits):\n",
    "                yield replace_all(formula, letters, digits)\n",
    "        except ZeroDivisionError: \n",
    "            pass\n",
    "        \n",
    "def replace_all(text, olds, news):\n",
    "    \"Replace each occurence of each old in text with the corresponding new.\"\n",
    "    # E.g. replace_all('A + B', ['A', 'B'], [1, 2]) == '1 + 2'\n",
    "    for (old, new) in zip(olds, news):\n",
    "        text = text.replace(str(old), str(new))\n",
    "    return text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'857 + 349 = 1206'"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(faster_solve_all('NUM + BER = PLAY'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.75 s, sys: 3.29 ms, total: 1.76 s\n",
      "Wall time: 1.76 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "96"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time len(list(faster_solve_all('NUM + BER = PLAY')))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We get the same answer, but 15 times faster."
   ]
  }
 ],
 "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.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}