ipynb/Orderable Cards.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\"><i>Peter Norvig<br>October 2018</i></div>\n",
    "\n",
    "# Properly Ordered Card Hands\n",
    "\n",
    "The 538 Riddler [presented](https://fivethirtyeight.com/features/who-will-capture-the-most-james-bonds/) this problem by Matt Ginsberg:\n",
    "    \n",
    "> *You play so many card games that you’ve developed a very specific organizational obsession. When you’re dealt your hand, you want to organize it such that the cards of a given suit are grouped together and, if possible, such that no suited groups of the same color are adjacent. (Numbers don’t matter to you.) Moreover, when you receive your randomly ordered hand, you want to achieve this organization with a single motion, moving only one adjacent block of cards to some other position in your hand, maintaining the original order of that block and other cards, except for that one move.*\n",
    "\n",
    "> *Suppose you’re playing pitch, in which a hand has six cards. What are the odds that you can accomplish your obsessive goal? What about for another game, where a hand has N cards, somewhere between 1 and 13?*\n",
    "\n",
    "# Brute Force Versus Cleverness\n",
    "\n",
    "The first thing to decide is how many `N`-card hands are there? If there are only a few, I could just enumerate them all and count how many are orderable. If there are a lot, I'll have to be more clever. The answer is (52 choose `N`), so we have:\n",
    "\n",
    "- 6 cards: 20,358,520 hands\n",
    "- 13 cards: 635,013,559,600 hands \n",
    "\n",
    "That's a lot. Time for a small dose of cleverness. \n",
    "\n",
    "# Abstract Hands: Suits\n",
    "\n",
    "I notice that the problem says *\"Numbers don’t matter,\"* so I can abstract away from *cards* to *suits*: instead of saying that the first card in this hand is the seven of spades, I can just say it is a spade. Then there are only 4<sup>N</sup> abstract hands (for N &le; 13), so we have:\n",
    "\n",
    "- 6 cards: 4,096 abstract hands\n",
    "- 13 cards: 67,108,864 abstract hands\n",
    "\n",
    "That's a big improvement! \n",
    "\n",
    "Now let's start coding. There are two red suits and two black suits, so I'll represent the four suits as `'rRbB'`.  I'll represent an abstract hand as a string of suits: `'rrBrbr'` is a 6-card hand. \n",
    "\n",
    "# Deals: Hands and their Probabilities\n",
    "\n",
    "I'll define `deals(N)` to return a dict of all possible abstract hands of length `N`, each mapped to the probability of the hand. \n",
    "\n",
    "With actual hands, every hand has the same probability, because every card is equally likely to be the next card dealt. But with abstract hands, the probability of the next suit depends on how many cards of that suit have already been dealt. If I've already dealt the 12 cards `'rrrrrrrrrrrr'`, then the probability of the next card being an `'r'` is 1/40, and the probability of it being a `'b'` is 13/40. So as I build up the abstract hands, I'll need to keep track of the number of remaining cards of each suit.\n",
    "\n",
    "I'll use `Fraction` to get exact arithmetic and `lru_cache` to avoid repeated computations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from fractions import Fraction\n",
    "from functools import lru_cache\n",
    "\n",
    "one   = Fraction(1)\n",
    "suits = 'rbRB'\n",
    "\n",
    "@lru_cache()\n",
    "def deals(N):\n",
    "    \"A dict of {hand: probability} for all hands of length N.\"\n",
    "    if N == 0:\n",
    "        return {'': one}\n",
    "    else:\n",
    "        return {hand + suit: p * (13 - hand.count(suit)) / (52 - len(hand))\n",
    "                for (hand, p) in deals(N - 1).items()\n",
    "                for suit in suits}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'BB': Fraction(1, 17),\n",
       " 'BR': Fraction(13, 204),\n",
       " 'Bb': Fraction(13, 204),\n",
       " 'Br': Fraction(13, 204),\n",
       " 'RB': Fraction(13, 204),\n",
       " 'RR': Fraction(1, 17),\n",
       " 'Rb': Fraction(13, 204),\n",
       " 'Rr': Fraction(13, 204),\n",
       " 'bB': Fraction(13, 204),\n",
       " 'bR': Fraction(13, 204),\n",
       " 'bb': Fraction(1, 17),\n",
       " 'br': Fraction(13, 204),\n",
       " 'rB': Fraction(13, 204),\n",
       " 'rR': Fraction(13, 204),\n",
       " 'rb': Fraction(13, 204),\n",
       " 'rr': Fraction(1, 17)}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "deals(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is that right? Yes it is. The probability of `'BB'` is 1/17, beause the probability of the first `'B'` is 13/52 or 1/4, and when we deal the second card, one `'B'` is gone, so the probability is 12/51, so that simplifies to 1/4 &times; 12/51 = 3/51 = 1/17. The probability of `'BR'` is 13/204, because the probability of the `'R'` is 13/51, and 1/4 &times; 13/51 = 13/204.\n",
    "\n",
    "# More Abstraction: Collapsed Runs\n",
    "\n",
    "Now for a second abstraction: an abstract hand can be *collapsed* by replacing a run of cards of the same suit with a single card, so that `'BBBBBrrrrBBBB'` collapses to `'BrB'`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def collapse(hand):\n",
    "    \"Collapse runs of adjacent identical suits with a single suit.\"\n",
    "    return ''.join(hand[i] for i in range(len(hand)) if i == 0 or hand[i] != hand[i-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'BrB'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "collapse('BBBBBrrrrBBBB')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From now on I'll just say *hand* rather than *abstract hand* for `'BBBBBrrrrBBBB'`, and I'll use the term *sequence* (or the abbreviation *seq*) for the collapsed version, `'BrB'`.\n",
    "\n",
    "\n",
    "# Properly Ordered Hands\n",
    "\n",
    "A hand is considered properly `ordered` if *\"the cards of a given suit are grouped together and, if possible, such that no suited groups of the same color are adjacent.\"* I was initially confused about the meaning of *\"if possible\";* Matt Ginsberg confirmed it means *\"if it is possible to separate the colors in any number of moves\"*, and thus that the hand `'BBBbbb'` is properly ordered, because it is not possible to separate the two black suits, while `'BBBbbR'` is not properly ordered, because the red card could be inserted between the two black runs.\n",
    "\n",
    "A hand is properly ordered if and only if its collapsed sequence is properly ordered, and a sequence is properly ordered if each suit appears only once, and either all the colors are the same, or suits of the same color don't appear adjacent to each other."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def ordered(hand):\n",
    "    \"Properly ordered if each suit run appears only once, and same color suits not adjacent.\"\n",
    "    seq = collapse(hand)\n",
    "    return once_each(seq) and (len(colors(seq)) == 1 or not adjacent_colors(seq))\n",
    "                                 \n",
    "def adjacent_colors(seq): \n",
    "    \"Do two suits of the same color appear next to each other in seq?\"\n",
    "    return any(pair in seq for pair in ('rR', 'Rr', 'Bb', 'bB'))\n",
    "\n",
    "def once_each(seq): return len(seq) == len(set(seq))\n",
    "\n",
    "def colors(seq):    return set(seq.casefold())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ordered('BBBRbb')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ordered('BBBbbR') "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Moving Cards to Make a Hand Ordered\n",
    "\n",
    "I won't try to be clever here; the abstractions got us down to a small enough number of abstract hands that I can use brute force from here on. I'll say that a collapsed sequence is `orderable` if any of the possible `moves` of a block of cards makes the hand `ordered`. I'll find all possible `moves`, by finding all possible `splits` of the cards into a middle block of cards flanked by (possibly empty) left and right sequences; then all possible `inserts` of the block back into the rest of the cards.  I'll define `orderable_probability(N)` to give the probability that a random `N`-card hand is orderable.\n",
    "Since many hands will collapse to the same sequence, I'll throw a `lru_cache` onto `orderable` so that it won't have to repeat computations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "@lru_cache(None)\n",
    "def orderable(seq): \n",
    "    \"Can this collapsed sequence be put into proper order in one move?\"\n",
    "    return any(ordered(m) for m in moves(seq))\n",
    "\n",
    "def orderable_probability(N):\n",
    "    \"What's the probability that an N-card hand is orderable?\"\n",
    "    return sum(p for (hand, p) in deals(N).items() if orderable(collapse(hand)))\n",
    "\n",
    "def moves(seq):\n",
    "    \"All possible ways of moving a single block of cards.\"\n",
    "    return {collapse(s) for (L, block, R) in splits(seq)\n",
    "            for s in inserts(block, L + R)}\n",
    "\n",
    "def inserts(block, others):\n",
    "    \"All ways of inserting a block into the other cards.\"\n",
    "    return [others[:i] + block + others[i:]\n",
    "            for i in range(len(others) + 1)]\n",
    "\n",
    "def splits(seq):\n",
    "    \"All ways of splitting a hand into a non-empty block flanked by left and right parts.\"\n",
    "    return [(seq[:i], seq[i:j], seq[j:])\n",
    "            for i in range(len(seq))\n",
    "            for j in range(i + 1, len(seq) + 1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# First Answer\n",
    "\n",
    "Here's the answer for 6 cards:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "51083/83895\n"
     ]
    }
   ],
   "source": [
    "print(orderable_probability(6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And an easier-to-read answer for everything up to  6 cards:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0:   0.0% = 0\n",
      " 1: 100.0% = 1\n",
      " 2: 100.0% = 1\n",
      " 3: 100.0% = 1\n",
      " 4: 100.0% = 1\n",
      " 5:  85.2% = 213019/249900\n",
      " 6:  60.9% = 51083/83895\n"
     ]
    }
   ],
   "source": [
    "def report(Ns):\n",
    "    \"Show the probability of orderability, for each N in Ns.\"\n",
    "    for N in Ns:\n",
    "        P = orderable_probability(N)\n",
    "        print('{:2}: {:6.1%} = {}'.format(N, float(P), P))\n",
    "        \n",
    "report(range(7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's make sure that each `deals(N)` covers everything: that I got all 4<sup>N</sup> hands, and that the probabilities sum to 1:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for N in range(7):\n",
    "    assert len(deals(N)) == 4 ** N\n",
    "    assert sum(deals(N).values()) == 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Getting to `N` = 13: Less Brute Force\n",
    "\n",
    "So far so good, but if we want to get to 13-card hands, we would have to handle 4<sup>13</sup> = 67,108,864 `deals`, which would take a long time. But after playing with sequences for a while, I discovered two key properties that can speed things up:\n",
    "\n",
    "1. **An orderable sequence can have at most 7 runs.** We know that a properly ordered hand can have at most 4 runs. But a move can reduce the number of runs by at most 3:  one run can be reduced when we remove the block (if the cards on either side of the block are the same), and two more can be reduced when we re-insert the block (if the left and right ends match the surrounding suits). Here's an example of moving a block [bracketed] to reduce the number of runs from 6 to 3:\n",
    "\n",
    "       bRB[bR]B   =>   b[bR]RBB  =   bRB\n",
    "       \n",
    "2. **Adding a suit to the end of an unorderable sequence can't make it orderable.** To show that, take an unordered sequence, and see what happens if you take the extra suit and insert it anywhere in the sequence. If the sequence was unordered because it repeats a suit, adding a suit can't fix that. If it was unordered because suits of the same color are adjacent, then adding a suit of the other color *could* fix that: `'bBR'` could be fixed by inserting a `'r'` to get `'brBR'`. But here's the catch: `'bBR'` is not unorderable. And if we are going to insert a new suit between two others, that means that the original sequence must have had at most three suits (because when we add one, we can't get more than four suits in an ordered sequence), and *every* three-suit sequence is orderable.  And if that argument doesn't convince you, below I look at all the sequences from `deals(7)` (which we know is the longest length we need to look at) and show that if a sequence is not orderable, then no matter what suit you add to it, the result is not orderable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for seq in {collapse(hand) for hand in deals(7)}:\n",
    "    if not orderable(seq):\n",
    "        for suit in suits:\n",
    "            assert not orderable(seq + suit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'll redefine `deals(N)` to hold only orderable hands, redefine `orderable(seq)` to immediately reject sequences longer than 7, and redefine `orderable_probability(N)` to just add up the probabilities in `deals(N)`, since they're all orderable now."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@lru_cache()\n",
    "def deals(N):\n",
    "    \"A dict of {hand: probability} for all orderable hands of length N.\"\n",
    "    if N == 0:\n",
    "        return {'': one}\n",
    "    else:\n",
    "        return {hand + suit: p * (13 - hand.count(suit)) / (52 - len(hand))\n",
    "                for (hand, p) in deals(N - 1).items()\n",
    "                for suit in suits\n",
    "                if orderable(collapse(hand + suit))}\n",
    "    \n",
    "@lru_cache(None)\n",
    "def orderable(seq): \n",
    "    \"Can this collapsed sequence be put into proper order in one move?\"\n",
    "    return len(seq) <= 7 and any(ordered(m) for m in moves(seq))\n",
    "\n",
    "def orderable_probability(N):\n",
    "    \"What's the probability that an N-card hand is orderable?\"\n",
    "    return sum(deals(N).values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Final Answer\n",
    "\n",
    "We're finaly ready to go up to `N` = 13:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0: 100.0% = 1\n",
      " 1: 100.0% = 1\n",
      " 2: 100.0% = 1\n",
      " 3: 100.0% = 1\n",
      " 4: 100.0% = 1\n",
      " 5:  85.2% = 213019/249900\n",
      " 6:  60.9% = 51083/83895\n",
      " 7:  37.3% = 33606799/90047300\n",
      " 8:  20.2% = 29210911/144718875\n",
      " 9:   9.9% = 133194539/1350709500\n",
      "10:   4.4% = 367755247/8297215500\n",
      "11:   1.9% = 22673450197/1219690678500\n",
      "12:   0.7% = 1751664923/238130084850\n",
      "13:   0.3% = 30785713171/11112737293000\n",
      "CPU times: user 14.4 s, sys: 236 ms, total: 14.6 s\n",
      "Wall time: 14.9 s\n"
     ]
    }
   ],
   "source": [
    "%time report(range(14))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Caches\n",
    "\n",
    "Let's look at the cache for  `orderable(seq)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "CacheInfo(hits=1438512, misses=1540, maxsize=None, currsize=1540)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "orderable.cache_info()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So we looked at over a million hands, but only 1540 different collapsed sequences. And once we hit `N` = 7, we've seen all the sequences we're ever going to see. From `N` = 8 and up, almost all the computation goes into computing the probability of each hand, and collapsing the hand into a sequence, not into deciding the orderability of each sequence.\n",
    "\n",
    "We also save a lot of space in the `deals(N)` caches. Instead of storing all 4<sup>13</sup> hands for `deals(13)`, the `report` above says that just 0.3% of the hands are orderable, so we reduced the cache size by a factor of 300.\n",
    "\n",
    "# Unit Tests\n",
    "\n",
    "To gain confidence in this project, here are some unit tests. Before declaring my answers definitively correct, I would want a lot more tests, and some independent code reviews."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def test():\n",
    "    assert deals(1) == {'B': 1/4, 'R': 1/4, 'b': 1/4, 'r': 1/4}\n",
    "    assert ordered('BBBBBrrrrBBBB') is False\n",
    "    assert ordered('BBBBBrrrrRRRR') is False\n",
    "    assert ordered('BBBbbr') is False # Bb\n",
    "    assert ordered('BBBbbrB') is False # two B's\n",
    "    assert ordered('BBBbbb') \n",
    "    assert ordered('BBBbbbB') is False # two B's\n",
    "    assert ordered('BBBBBrrrrbbbb')\n",
    "    assert colors('BBBBBrrrrbbbb') == {'r', 'b'}\n",
    "    assert once_each('Bb')\n",
    "    assert once_each('BbR')\n",
    "    assert adjacent_colors('BBBbbR')\n",
    "    assert not adjacent_colors('BBBBBrrrrBBBB')\n",
    "    assert collapse('BBBBBrrrrBBBB') == 'BrB'\n",
    "    assert collapse('brBBrrRR') == 'brBrR'\n",
    "    assert collapse('bbbbBBBrrr') == 'bBr'\n",
    "    assert moves('bRb') == {'Rb', 'bR', 'bRb'}\n",
    "    assert moves('bRBb') == {\n",
    "        'BbR', 'BbRb', 'RBb', 'RbBb', 'bBRb', 'bBbR', 'bRB', 'bRBb', 'bRbB'}\n",
    "    assert inserts('BB', '....') == [\n",
    "        'BB....', '.BB...', '..BB..', '...BB.', '....BB']\n",
    "    assert splits('123') == [('', '1', '23'), ('', '12', '3'), ('', '123', ''),\n",
    "                             ('1', '2', '3'), ('1', '23', ''), ('12', '3', '')]\n",
    "    assert orderable('bBr') # move 'r' between 'bB'\n",
    "    assert orderable('bBrbRBr') # move 'bRB' after first 'b' to get 'bbRBBrr'\n",
    "    assert orderable('bBrbRBrb') is False\n",
    "    return True\n",
    "\n",
    "test()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}