{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "# SET\n",
    "\n",
    "How many cards are there? There are four features (color, shape, shading, and number of figures) on each card, and each feature can take one of three values.  So the number of cards is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "81"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "3 ** 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "How many sets are there?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1080.0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "81 * 80 * 1 / 6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "run_control": {}
   },
   "source": [
    "How many sets does each card participate in?  We need to look at the number of sets (1080) and the number of cards in a set (3), divided by the number of cards (81):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40.0"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1080 * 3 / 81"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "run_control": {}
   },
   "source": [
    "Note that each *pair* of cards participates in exactly one set.\n",
    "\n",
    "How many layouts of 12 cards are there? The answer is (81 choose 12):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "70724320184700.0"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from math import factorial as fact\n",
    "\n",
    "def C(n, k): \n",
    "    \"Number of ways of choosing k things from n things.\"\n",
    "    return fact(n) / fact(n-k) / fact(k)\n",
    "\n",
    "C(81, 12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "run_control": {}
   },
   "source": [
    "That's a lot of digits; hard to read. This should help:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "70.7243201847"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M = 10 ** 6  # Million\n",
    "T = 10 ** 12 # Trillion\n",
    "\n",
    "C(81, 12) / T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "70 trillion layouts. Of those some will have 6 sets, some more, some less.\n",
    "\n",
    "In a layout of 12 cards, how many triples (that could potentially be a set) are there?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "220.0"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C(12, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "run_control": {}
   },
   "source": [
    "So, what we're looking for is when exactly 6 of these are sets, and the other 214 are not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2173.5413336637"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C(1080, 6)  / T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "81"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import product\n",
    "\n",
    "feature = (1, 2, 3)\n",
    "\n",
    "Card = tuple\n",
    "\n",
    "cards = set(product(feature, feature, feature, feature))\n",
    "len(cards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [],
   "source": [
    "def match(card1, card2):\n",
    "    return Card(match_feature(card1[i], card2[i]) \n",
    "                for i in (0, 1, 2, 3))\n",
    "\n",
    "def match_feature(f1, f2):\n",
    "    return f1 if f1 == f2 else 6 - f1 - f2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 3, 1, 3)"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "match((1, 2, 3, 3),\n",
    "      (1, 1, 2, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "button": false,
    "collapsed": true,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "source": [
    "2173 trillion; even worse.\n",
    "\n",
    "How many layouts are there where:\n",
    "- The first six cards form no sets\n",
    "- The last six cards each form a set?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "246.7179"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "81 * 80 * (79 - 1) * (78 - 3) * (77 - 6) * (76 - 10) / fact(6) / M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.091475"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "15 * 21 * 28 * 36 * 45 * 55 / fact(6) / M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "All tests pass.\n",
      "\n",
      "Size |  Sets  | NoSets | Set:NoSet ratio for the instruction booklet\n",
      "-----+--------+--------+----------------\n",
      "  12 |     33 |      1 |   33:1\n",
      "  15 |  2,500 |      1 | 2500:1\n",
      "\n",
      "Size |  Sets  | NoSets | Set:NoSet ratio for initial layout\n",
      "-----+--------+--------+----------------\n",
      "  12 | 96,844 |  3,156 |   31:1\n",
      "  15 | 99,963 |     37 | 2702:1\n",
      "\n",
      "Size |  Sets  | NoSets | Set:NoSet ratio for game play\n",
      "-----+--------+--------+----------------\n",
      "  12 | 86,065 |  5,871 |   15:1\n",
      "  15 |  5,595 |     64 |   87:1\n",
      "  18 |     57 |      0 | inft:1\n",
      "\n",
      "Size |  Sets  | NoSets | Set:NoSet ratio for initial layout, but no sets before dealing last 3 cards\n",
      "-----+--------+--------+----------------\n",
      "  12 | 26,426 |  3,242 |    8:1\n",
      "  15 |  3,207 |     35 |   92:1\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import collections \n",
    "import itertools \n",
    "\n",
    "\"\"\"\n",
    "Game of Set                (Peter Norvig 2010-2015)\n",
    "\n",
    "How often do sets appear when we deal an array of cards?\n",
    "How often in the course of playing out the game?\n",
    "\n",
    "Here are the data types we will use:\n",
    "\n",
    "    card:    A string, such as '3R=0', meaning \"three red striped ovals\".\n",
    "    deck:    A list of cards, initially of length 81.\n",
    "    layout:  A list of cards, initially of length 12.\n",
    "    set:     A tuple of 3 cards.\n",
    "    Tallies: A dict: {12: {True: 33, False: 1}}} means a layout of size 12\n",
    "             tallied 33 sets and 1 non-set.\n",
    "\"\"\"\n",
    "\n",
    "#### Cards, dealing cards, and defining the notion of sets.\n",
    "\n",
    "CARDS = [number + color + shade + symbol \n",
    "         for number in '123' \n",
    "         for color  in 'RGP' \n",
    "         for shade  in '@O=' \n",
    "         for symbol in '0SD']\n",
    "\n",
    "def deal(n, deck): \n",
    "    \"Deal n cards from the deck.\"\n",
    "    return [deck.pop() for _ in range(n)]\n",
    "\n",
    "def is_set(cards):\n",
    "    \"Are these 3 cards a set? No if any feature has 2 values.\"\n",
    "    for f in range(4):\n",
    "        values = {card[f] for card in cards}\n",
    "        if len(values) == 2: \n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def find_set(layout):\n",
    "    \"Return a set found from this layout, if there is one.\"\n",
    "    for cards in itertools.combinations(layout, 3):\n",
    "        if is_set(cards):\n",
    "            return cards\n",
    "    return ()\n",
    "\n",
    "#### Tallying set:no-set ratio\n",
    "\n",
    "def Tallies(): \n",
    "    \"A data structure to keep track, for each size, the number of sets and no-sets.\"\n",
    "    return collections.defaultdict(lambda: {True: 0, False: 0})\n",
    "\n",
    "def tally(tallies, layout):\n",
    "    \"Record that a set was found or not found in a layout of given size; return the set.\"\n",
    "    s = find_set(layout)\n",
    "    tallies[len(layout)][bool(s)] += 1\n",
    "    return s\n",
    "            \n",
    "#### Three experiments\n",
    "\n",
    "def tally_initial_layout(N, sizes=(12, 15)):\n",
    "    \"Record tallies for N initial deals.\"\n",
    "    tallies = Tallies()\n",
    "    deck = list(CARDS)\n",
    "    for deal in range(N):\n",
    "        random.shuffle(deck)\n",
    "        for size in sizes:\n",
    "            tally(tallies, deck[:size])\n",
    "    return tallies\n",
    "\n",
    "def tally_initial_layout_no_prior_sets(N, sizes=(12, 15)):\n",
    "    \"\"\"Simulate N initial deals for each size, keeping tallies for Sets and NoSets,\n",
    "    but only when there was no set with 3 fewer cards.\"\"\"\n",
    "    tallies = Tallies()\n",
    "    deck = list(CARDS)\n",
    "    for deal in range(N):\n",
    "        random.shuffle(deck)\n",
    "        for size in sizes:\n",
    "            if not find_set(deck[:size-3]):\n",
    "                tally(tallies, deck[:size])\n",
    "    return tallies\n",
    "\n",
    "def tally_game_play(N):\n",
    "    \"Record tallies for the play of N complete games.\"\n",
    "    tallies = Tallies()\n",
    "    for game in range(N):\n",
    "        deck = list(CARDS)\n",
    "        random.shuffle(deck)\n",
    "        layout = deal(12, deck)\n",
    "        while deck:\n",
    "            s = tally(tallies, layout)\n",
    "            # Pick up the cards in the set, if any\n",
    "            for card in s: layout.remove(card)\n",
    "            # Deal new cards\n",
    "            if len(layout) < 12 or not s:\n",
    "                layout += deal(3, deck)    \n",
    "    return tallies\n",
    "\n",
    "def experiments(N):\n",
    "    show({12: [1, 33], 15: [1, 2500]}, \n",
    "         'the instruction booklet')\n",
    "    show(tally_initial_layout(N), \n",
    "         'initial layout')\n",
    "    show(tally_game_play(N // 25), \n",
    "         'game play')\n",
    "    show(tally_initial_layout_no_prior_sets(N), \n",
    "         'initial layout, but no sets before dealing last 3 cards')\n",
    "\n",
    "\n",
    "def show(tallies, label):\n",
    "    \"Print out the counts.\"\n",
    "    print()\n",
    "    print('Size |  Sets  | NoSets | Set:NoSet ratio for', label)\n",
    "    print('-----+--------+--------+----------------')\n",
    "    for size in sorted(tallies):\n",
    "        y, n = tallies[size][True], tallies[size][False]\n",
    "        ratio = ('inft' if n==0 else int(round(float(y)/n)))\n",
    "        print('{:4d} |{:7,d} |{:7,d} | {:4}:1'\n",
    "              .format(size, y, n, ratio))\n",
    "\n",
    "def test():\n",
    "    assert len(CARDS) == 81 == len(set(CARDS))\n",
    "    assert is_set(('3R=O', '2R=S', '1R=D'))\n",
    "    assert not is_set(('3R=0', '2R=S', '1R@D'))\n",
    "    assert find_set(['1PO0', '2G=D', '3R=0', '2R=S', '1R=D']) == ('3R=0', '2R=S', '1R=D')\n",
    "    assert not find_set(['1PO0', '2G=D', '3R=0', '2R=S', '1R@D'])\n",
    "    photo = '2P=0 3P=D 2R=0 3GO0 2POD 3R@D 2RO0 2ROS 1P@S 2P@0 3ROS 2GOD 2P@D 1GOD 3GOS'.split()\n",
    "    assert not find_set(photo)\n",
    "    assert set(itertools.combinations([1, 2, 3, 4], 3)) == {(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)}\n",
    "    print('All tests pass.')\n",
    "\n",
    "test()\n",
    "experiments(100000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "button": false,
    "collapsed": false,
    "deletable": true,
    "new_sheet": false,
    "run_control": {
     "read_only": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Size |  Sets  | NoSets | Set:NoSet ratio for the instruction booklet\n",
      "-----+--------+--------+----------------\n",
      "  12 |     33 |      1 |   33:1\n",
      "  15 |  2,500 |      1 | 2500:1\n",
      "\n",
      "Size |  Sets  | NoSets | Set:NoSet ratio for initial layout\n",
      "-----+--------+--------+----------------\n",
      "  12 |  9,696 |    304 |   32:1\n",
      "  15 |  9,995 |      5 | 1999:1\n",
      "\n",
      "Size |  Sets  | NoSets | Set:NoSet ratio for game play\n",
      "-----+--------+--------+----------------\n",
      "  12 |  8,653 |    542 |   16:1\n",
      "  15 |    513 |      5 |  103:1\n",
      "  18 |      5 |      0 | inft:1\n",
      "\n",
      "Size |  Sets  | NoSets | Set:NoSet ratio for initial layout, but no sets before dealing last 3 cards\n",
      "-----+--------+--------+----------------\n",
      "  12 |  2,630 |    294 |    9:1\n",
      "  15 |    293 |      1 |  293:1\n"
     ]
    }
   ],
   "source": [
    "experiments(10000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "run_control": {}
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}