{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:right\">Peter Norvig<br>21 March 2018</div>\n",
    "\n",
    "# `xkcd` Name Dominoes\n",
    "\n",
    "The March 21, 2018 `xkcd` comic (#1970) was [Name Dominoes](https://xkcd.com/1970/): domino tiles laid out as if in a game, but the tiles contain names of famous people rather than numbers. \n",
    "In [dominoes](https://en.wikipedia.org/wiki/Dominoes) each tile has two halves, and a tile can be legally placed only if  one half is adjacent to another tile half with the same number/name, and neither half is adjacent to a tile half with a different number/name. (Exception: the very first tile can be placed anywhere.) \n",
    "\n",
    "I will write a function to lay out tiles in a random, legal array.  First, the key data structures:\n",
    "\n",
    "- **`Tile`**: a tile is a 2-element tuple of names, like `('TIM', 'COOK')`.\n",
    "The tile `('FRANK LLOYD', 'WRIGHT')` has a space in the first name.\n",
    "- **`Name`**: a name (first name or last name) is a string.\n",
    "- **`Board(width, height)`**: a `Board` represents\n",
    "a width × height array of squares, initially `empty`, but  when we put a tile on the board,\n",
    "the first name covers one location and the last name covers an adjacent location, e.g. `board[0, 0], board[0, 1] = ('TIM', 'COOK')`. Implemented as a subtype of `dict` that keeps track of `width` and `height`.\n",
    "- **`Location`**: a location is an `(x, y)` pair of coordinates for a square on the board.\n",
    "\n",
    "Now I need a strategy to fill the board with tiles.  I will randomly place tiles one at a time, and to make things easier I will *not* consider removing a tile from the board and backtracking. Some more concepts and functions:\n",
    "\n",
    "- **`frontier`**: I'll maintain a *frontier*, a set of locations that are adjacent to tiles on the board, and thus are candidates for placing new tiles.\n",
    "- **`dominoes(tiles)`**: makes a board and places tiles on it, one at a time, until no more can be placed. Chooses a random tile for the first tile, then repeatedly calls `try_one` to legally place an additional tile, stopping when either there is no `frontier` left (meaning no place to legally place a tile) or no `tiles` left to place.\n",
    "- **`try_one(tiles, board, frontier)`**: pop a location off the frontier, and try to find some tile that can legally put one of its halves there; when found, `put` the tile there, and remove it from `tiles`.\n",
    "- **`legal(name, loc, board)`**: a name can be placed if the location is empty, and there are no conflicts with any neighboring location.\n",
    "- **`neighbors(loc, board)`**: returns the (up to 4) neighbors of a location that are on the board.\n",
    "- **`put_tile(board, loc0, loc1, tile, frontier)`**: places a tile on the board across `loc0` and `loc1`; update the `frontier` to say that the just-covered locations are no longer in the frontier, but the empty neighbors of the tile are.\n",
    "- **`shuffle(items)`**: used to randomize lists; calls `random.shuffle` and returns the result.\n",
    "\n",
    "# The Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "empty = None # An empty square\n",
    "\n",
    "class Board(dict):\n",
    "    \"A mapping from location to name.\"\n",
    "    def __init__(self, width, height): self.width, self.height = width, height\n",
    "    def __missing__(self, loc): return empty\n",
    "\n",
    "def dominoes(tiles, width=16, height=24):\n",
    "    \"Place as many tiles on board as possible (legally and randomly).\"\n",
    "    tiles    = shuffle(list(tiles))\n",
    "    board    = Board(width, height)\n",
    "    frontier = set()\n",
    "    m        = min(width, height) // 2\n",
    "    put_tile(board, (m, m), (m, m + 1), tiles.pop(), frontier) # Place first tile\n",
    "    while tiles and frontier:\n",
    "        try_one(tiles, board, frontier)\n",
    "    return board\n",
    "          \n",
    "def try_one(tiles, board, frontier):\n",
    "    \"Pop a frontier location, and try to place a tile on that location.\"\n",
    "    loc0 = frontier.pop()\n",
    "    for tile in shuffle(tiles):\n",
    "        for (name0, name1) in [tile, tile[::-1]]:\n",
    "            if legal(name0, loc0, board):\n",
    "                for loc1 in shuffle(neighbors(loc0, board)):\n",
    "                    if legal(name1, loc1, board):\n",
    "                        put_tile(board, loc0, loc1, (name0, name1), frontier)\n",
    "                        tiles.remove(tile)\n",
    "                        return tile\n",
    "                        \n",
    "def legal(name, loc, board):\n",
    "    \"Is it legal to place this name on this location on board?\"\n",
    "    return (board[loc] is empty and\n",
    "            all(board[nbr] is empty or board[nbr] == name\n",
    "                for nbr in neighbors(loc, board)))\n",
    "\n",
    "def neighbors(loc, board):\n",
    "    \"Neighbors of this location on the board.\"\n",
    "    x, y = loc\n",
    "    return [(x+dx, y+dy) for (dx, dy) in ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "            if 0 <= x+dx < board.width and 0 <= y+dy < board.height]\n",
    "\n",
    "def put_tile(board, loc0, loc1, tile, frontier): \n",
    "    \"Place the tile across the two locations, and update frontier.\"\n",
    "    board[loc0], board[loc1] = tile\n",
    "    frontier -= {loc0, loc1}\n",
    "    frontier |= {loc for loc in neighbors(loc0, board) + neighbors(loc1, board)\n",
    "                 if board[loc] is empty}\n",
    "                            \n",
    "def shuffle(items): random.shuffle(items); return items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(0, 0): 'RY',\n",
       " (1, 0): 'KE',\n",
       " (1, 1): 'KE',\n",
       " (2, 1): 'JO',\n",
       " (2, 2): 'JO',\n",
       " (3, 2): 'GR',\n",
       " (3, 3): 'GR',\n",
       " (3, 4): 'KE',\n",
       " (4, 4): 'KE',\n",
       " (4, 5): 'JA'}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tiles8 = [('BO', 'JA'), ('JA', 'PO'), ('JA', 'RY'), ('RY', 'KE'), \n",
    "          ('GR', 'KE'), ('GR', 'JO'), ('JA', 'KE'), ('KE', 'JO')]\n",
    "\n",
    "dominoes(tiles8, 6, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Pretty Output\n",
    "\n",
    "Technically, this is a legal solution, but there are two problems with it: One, it is not visual. Two, it doesn't say where each tile is: when three names come together, which of the outside names goes with the middle name?  To fix those two problems I will:\n",
    "\n",
    "- Define `plot_board(board)` to use `matplotlib` to plot the board, the names, and the tiles.\n",
    "- Modify the `Board` class and the `put` function so that the board maintains a list of `boxes` that surround each two-location rectangle that a tile occupies: `[loc0, loc1]`. The constant ϵ is the distance between two adjacent tiles; we want them to not-quite touch (as in the xkcd comic)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "ϵ = 0.06 # A small amount; the space between adjacent lines\n",
    "\n",
    "class Board(dict):\n",
    "    \"A mapping from location to name.\"\n",
    "    def __init__(self, width=16, height=24): \n",
    "        self.width, self.height, self.boxes = width, height, []\n",
    "    def __missing__(self, loc): return empty\n",
    "    \n",
    "def plot_board(board):\n",
    "    \"Plot the box and name for every tile, plus a big box around the board.\"\n",
    "    plt.figure(figsize=(board.width, board.height))\n",
    "    plt.subplots_adjust(left=ϵ, right=1-ϵ, top=1-ϵ, bottom=ϵ)\n",
    "    plt.axis('off')  \n",
    "    plt.axis('equal')\n",
    "    for box in board.boxes:\n",
    "        plot_box(box)\n",
    "    plot_box([(-2*ϵ, -2*ϵ), (board.width - 1 + 2*ϵ, board.height - 1 + 2*ϵ)])\n",
    "    for (x, y) in board:\n",
    "        plt.text(x + 0.5, y + 0.5, board[x, y], \n",
    "                 va='center', ha='center', fontsize=8)\n",
    "\n",
    "def plot_box(box):\n",
    "    \"Plot a box, which is a [loc0, loc1] pair.\"\n",
    "    Xs, Ys = {loc[0] for loc in box}, {loc[1] for loc in box}\n",
    "    x0, x1 = min(Xs), max(Xs) + 1 - ϵ\n",
    "    y0, y1 = min(Ys), max(Ys) + 1 - ϵ\n",
    "    plt.plot([x0, x1, x1, x0, x0], \n",
    "             [y0, y0, y1, y1, y0], 'k-')\n",
    "\n",
    "def put_tile(board, loc0, loc1, tile, frontier): \n",
    "    \"Place the tile across the two locations, and update frontier and boxes.\"\n",
    "    board[loc0], board[loc1] = tile\n",
    "    frontier -= {loc0, loc1}\n",
    "    frontier |= {loc for loc in neighbors(loc0, board) + neighbors(loc1, board)\n",
    "                 if board[loc] is empty}\n",
    "    board.boxes.append([loc0, loc1])       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 5704 characters]\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x110568940>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plot_board(dominoes(tiles8, 6, 6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# All the Names\n",
    "\n",
    "Now let's try all the names from the comic, courtesy of \n",
    " [explainxkcd](http://www.explainxkcd.com/wiki/index.php/1970:_Name_Dominoes), with a few typos corrected:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def name_tiles(text):\n",
    "    \"For each line of text, create a tile of ('First Name(s)', 'Lastname').\"\n",
    "    return [name.strip().rpartition(' ')[0::2]\n",
    "            for name in text.upper().split(',')]\n",
    "           \n",
    "xkcdtiles = name_tiles(\"\"\"Christian Campbell, Neve Campbell, Joe McCarthy, Eugene McCarthy, \n",
    "  Gene Vincent, Gene Kelly, Kate Hudson, Rock Hudson, Gordon Brown, James Brown, Jon Brown, \n",
    "  John Howard, Columbo, Chris Columbus, Christopher Columbus, Naomi Campbell, Joseph Campbell, \n",
    "  Joseph Smith, Frank Vincent, John Kelly, Katherine Johnson, The Rock, Chris Rock, Chris Isaac, \n",
    "  James Newton Howard, John Wayne, Howard Stern, Howard Hunt, Chris Hughes, Naomi Watts, \n",
    "  Naomi Klein, Kevin Kline, Francis Bacon, Francis Drake, Lyndon Johnson, Oscar The Grouch, \n",
    "  Oscar Isaac, Isaac Hayes, Isaac Newton, Wayne Newton, Wayne Knight, Helen Hunt, Helen Hughes, \n",
    "  James Watt, James Watt, Kevin Costner, Kevin Bacon, Kevin Love, Lisa Frank, Frank Drake, Drake, \n",
    "  Oscar de la Renta, Oscar de la Hoya, Sean Hayes, Wallace Shawn, Wayne Howard, Wayne Brady, \n",
    "  James Brady, Tom Brady, Helen Thomas, Tom Hanks, Hank Aaron, Aaron Carter, Stephen James, \n",
    "  Will Smith, Kevin Smith, Kevin James, Garfield, James Garfield, Warren Buffett, Jimmy Buffett, \n",
    "  Warren Beatty, Elizabeth Warren, Earl Warren, Elizabeth Kolbert, Stephen Colbert, \n",
    "  Charles Wallace, James Monroe, Marilyn Monroe, Hank Williams, William C. Williams, Steve Harvey,\n",
    "  Domino Harvey, Harvey Milk, James Saint James, Etta James, Jim Jones, James Earl Jones, \n",
    "  Charlie Parker, Ray Parker, Ray Charles, Charles Manson, Marilyn Manson, Robin Williams, \n",
    "  Billy D. Williams, Will Wright, Fats Domino, Bill Clinton, Jimmy John, Tom Jones, Tommy John, \n",
    "  Quincy Jones, James Earl Ray, Man Ray, Rachel Ray, Ray Allen, Tim Allen, Tim Cook, Tim Howard, \n",
    "  Robin Wright, Wilbur Wright, Fatty Arbuckle, Fat Joe, George Clinton, John Kerry, \n",
    "  Kerry Washington, John Irving, John Quincy Adams, John Adams, Amy Adams, Aimee Mann, Super Man, \n",
    "  Bat Man, Ayn Rand, Lily Allen, Paul Allen, Ron Howard, Howard Hughes, Joe Kennedy, George Bush, \n",
    "  George Washington, Washington Irving, Martha Washington, Ma Rainey, Jack Ma, Super Grover, \n",
    "  Jack Black, Rand Paul, Paul Ryan, Paul Simon, Ron Paul, John Hughes, Langston Hughes, \n",
    "  John F. Kennedy, Little Richard, Rich Little, Martha Stewart, Yo Yo Ma, Ma Bell, \n",
    "  Grover Cleveland Alexander, Grover Cleveland, Jack White, Jack Ryan, Debby Ryan, Carly Simon, \n",
    "  Carly Hughes, Charles Evans Hughes, John Williams, Little John, Stuart Little, Potter Stewart, \n",
    "  Kristen Stewart, Kristen Bell, Kristen Hooks, Alexander Graham Bell, Franklin Graham, \n",
    "  Lloyd Alexander, Meg White, Meg Ryan, Debbie Reynolds, John Reynolds, Carly Fiorina, \n",
    "  Grace Lee Boggs, Wade Boggs, William Safire, Prince William, Little Prince, Harry Potter, \n",
    "  James Potter, James Hook, James Dean, Aretha Franklin, Frank Lloyd Wright, Barry White, \n",
    "  Walter White, Walt Whitman, John Kelly, Grace Lee, Nancy Grace, Garnet, Prince, Prince Fielder, \n",
    "  Prince Harry, Harry Styles, John Dean, Benjamin Franklin, Harold Lloyd, Harold Ford, \n",
    "  Betty White, Meg Whitman, Christine Todd Whitman, Megyn Kelly, Grace Kelly, Grace Jones, \n",
    "  Jack Nicholson, Jack Ruby, Jack Russell, Harry Fielder, Harry Truman, Harry Jon Benjamin, \n",
    "  John Edward, Benjamin Harrison, Harrison Ford, Henry Ford, Betty Ford, Betty Friedan, \n",
    "  Chris Christie, Chris Pratt, Maggie Grace, Grace Hopper, Russell Crowe, Russ Smith, John Smith, \n",
    "  Justin Long, John Bel Edwards, John Candy, John Henry, Henry James, Bill James, Chris Cooper, \n",
    "  Chris Hemsworth, Chris Evans, Topher Grace, Van Morrison, Sheryl Crow, Sheryl Sandberg, \n",
    "  Cameron Crowe, Long John Silver, Olivia Newton John, Huey Long, John Edwards, Candy Crowley, \n",
    "  Aleister Crowley, James Fenimore Cooper, James Cook, Robert Frost, Bob Evans, Evan Taylor Jones,\n",
    "  James Cameron, Cam Newton, Cameron Diaz, Huey Newton, Huey Lewis, John Lewis, Jenny Lewis, \n",
    "  Ryan Lewis, Burt Reynolds, Alistair Cooke, Alistair Cookie, Cokie Roberts, John Roberts, \n",
    "  Robert Johnson, Robert E. Lee, Tommy Lee, Tommy Lee Jones, Etta James, John Oliver, \n",
    "  Ryan Reynolds, Alastair Reynolds, George Wallace\"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "270"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(xkcdtiles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('JAMES EARL', 'RAY'),\n",
       " ('BURT', 'REYNOLDS'),\n",
       " ('CHRISTOPHER', 'COLUMBUS'),\n",
       " ('KRISTEN', 'STEWART'),\n",
       " ('FAT', 'JOE'),\n",
       " ('HAROLD', 'LLOYD'),\n",
       " ('ISAAC', 'HAYES'),\n",
       " ('PAUL', 'RYAN'),\n",
       " ('GENE', 'KELLY'),\n",
       " ('MEGYN', 'KELLY')]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random.sample(xkcdtiles, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Approximate and Partial Matches\n",
    "\n",
    "Two tile halves match if they are an exact match, like \"ADAMS\" and \"ADAMS\", or if they are an **approximate match**, like \"AMY\" and \"AIMEE\". To accomodate this, you can manually define allowable approximate matches by making the global variable `synsets` (synonym sets) be a mapping from a name to the set of approximate matches it should match, which can be done like this:\n",
    "\n",
    "     synsets = synonyms(\"AMY=AIMEE, COOK=COOKE=COOKIE=COKIE, ...\")\n",
    "\n",
    "Another issue is  a **partial match**: in the comic, some tiles, like \"FRANK LLOYD WRIGHT\" are 3 squares wide, and some, like \"PRINCE\" are only one square wide. For simplicity, I chose to have all my tiles be 2 squares wide, but I still want `'LLOYD'` to match the first name of `('FRANK LLOYD', 'WRIGHT')`. To accomplish this, the second argument to `synonyms` is a list of tiles; the function will go through these and add synset entries for parts of first names,\n",
    "so that both `'FRANK'` and `'LLOYD'` will match `'FRANK LLOYD'`. As for \"PRINCE\", he gets represented as the tile `('', 'PRINCE')`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "\n",
    "def synonyms(text='', tiles=()): \n",
    "    \"synonyms('AMY=AIMEE') => dict(AMY={'AMY', 'AIMEE'}, AIMEE={'AMY', 'AIMEE'})\"\n",
    "    synsets = collections.defaultdict(set)\n",
    "    # Process `text`\n",
    "    for text1 in text.upper().split(','):\n",
    "        synset = set(text1.strip().split('='))\n",
    "        for s in synset:\n",
    "            synsets[s] |= synset\n",
    "    # Process `tiles`\n",
    "    for (first, last) in tiles:\n",
    "        for part in first.split():\n",
    "            synsets[part].add(first)\n",
    "            synsets[first].add(part)\n",
    "    return synsets\n",
    "\n",
    "synsets = synonyms(\"\"\"AMY=AIMEE, COOK=COOKE=COOKIE=COKIE, ALASTAIR=ALISTAIR, \n",
    "  COLUMBO=COLUMBUS, SAFIRE=SAPPHIRE=GARNET, GARNET=RUBY, CHARLIE=CHARLES, SEAN=SHAWN,\n",
    "  JIMMY=JAMES, MAN=MANN, JACK=JOHN, TOM=TOMMY, WILL=WILLIAM=WILLIAMS, ROBERT=ROBERTS=BOB, \n",
    "  CAM=CAMERON, OLIVER=OLIVIA, EDWARD=EDWARDS, RICH=RICHARD, CHRIS=CHRISTOPHER=TOPHER, \n",
    "  FAT=FATS=FATTY, WALT=WALTER, HANK=HANKS, CROW=CROWE, COLBERT=KOLBERT\"\"\", xkcdtiles)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "To make this work, I update `legal` to consult the `synsets` global variable for an approximate or partial matches, and while I'm changing `legal`, I'll also disallow a match between the empty first name of \"PRINCE\" with the empty first name of \"DRAKE\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def legal(name, loc, board):\n",
    "    \"Is it legal to place this value on this location on board?\"\n",
    "    return (board[loc] is empty and \n",
    "            all(board[nbr] is empty \n",
    "                or board[nbr] == name != '' \n",
    "                or board[nbr] in synsets[name]\n",
    "                for nbr in neighbors(loc, board)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Final Result (with Random Restart)\n",
    "\n",
    "The program sometimes gets stuck after placing relatively few tiles. I could modify the program to *back up* in this case, but it will be easier to just *give up* and restart with an empty board. I can restart multiple times, and accept the best board (the one on which the most tiles were placed):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 83704 characters]\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x11058c668>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def best(boards): return max(boards, key=lambda board: len(board.boxes))\n",
    "\n",
    "plot_board(best(dominoes(xkcdtiles) for _ in range(100)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Note:* I used a 16×24 square board while the xkcd comic used 27×35, but if I tried to fit 27 squares across then each tile would be smaller, and many names would overflow the sides of the dominoes too much. Here is the original xkcd comic:\n",
    "\n",
    "[![](https://imgs.xkcd.com/comics/name_dominoes_2x.png)](https://xkcd.com/1970/)\n",
    "\n",
    "# What's Next?\n",
    "\n",
    "I'm happy with the results, but here are some ideas for improvements, if you want something to work on:\n",
    "- Allow tiles that are 1 or 3 squares wide, like `('PRINCE',)` or `('FRANK', 'LLOYD', 'WRIGHT')`.\n",
    "- Print names vertically in tiles that are placed vertically, and upside down for tiles that are placed horizontally, but with the first name on the right.\n",
    "- Print shorter names with a bigger font and longer names with a smaller font.\n",
    "- Download a bunch of names from Wikipedia and fill a 200 × 300 board.\n",
    "- If you like xkcd try [regex golf](https://github.com/norvig/pytudes/blob/master/ipynb/xkcd1313.ipynb), and [part 2](https://github.com/norvig/pytudes/blob/master/ipynb/xkcd1313-part2.ipynb).\n"
   ]
  }
 ],
 "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": 2
}
