ipynb/Pickleball.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\">Peter Norvig, Updated Sept 2018</div>\n",
    "\n",
    "# Scheduling a Doubles Pickleball Tournament\n",
    "\n",
    "My friend Steve asked for help in creating a schedule for a round-robin doubles pickleball tournament with 8 or 9 players on 2 courts. (*To clarify:* [Pickleball](https://en.wikipedia.org/wiki/Pickleball) is a paddle/ball/net game played on a court that is smaller than tennis. In this type of tournament a player plays with a different partner in each game.) \n",
    "\n",
    "> Given *P* players and *C* available courts, create a **schedule**: a list of **rounds** of play, where each round consists of from 1 to *C* **games** played simultaneously. Each game pits one **pair** of players against another pair. The **criteria** for a schedule are:\n",
    "\n",
    "> 1. Each player should partner *with* each other player once (or as close to that as possible).\n",
    "2. Each player should play *against* each other player twice (or as close to that as possible).\n",
    "3. Each court should be filled each round (or as close to that as possible); in other words, fewer rounds are better.\n",
    "4. A player *cannot* be scheduled to play twice in the same round.\n",
    "\n",
    "For example, here's a schedule for *P*=8 players on *C*=2 courts. It says that in the first round, players 4 and 6 partner against 2 and 3 on one court, while 5 and 7 partner against 0 and 1 on the other court.\n",
    "\n",
    "    Round  1: | 4,6 vs 2,3 | 5,7 vs 0,1 |\n",
    "    Round  2: | 0,2 vs 1,3 | 4,5 vs 6,7 |\n",
    "    Round  3: | 5,6 vs 0,3 | 1,2 vs 4,7 |\n",
    "    Round  4: | 0,4 vs 3,6 | 2,7 vs 1,5 |\n",
    "    Round  5: | 0,5 vs 1,4 | 2,6 vs 3,7 |\n",
    "    Round  6: | 0,6 vs 2,5 | 1,7 vs 3,4 |\n",
    "    Round  7: | 3,5 vs 1,6 | 2,4 vs 0,7 |\n",
    "    \n",
    "This is a pretty good schedule&mdash;it is optimal according to criteria 1, 3, and 4, but it is not optimal in terms of number of times playing each opponent; for example players 1 and 5 play 3 times, not 2. We will see if we can do better. Our overall strategy is as follows:\n",
    "\n",
    "- To satisfy criterion 1, we will start with a list of all pairs of players. The function `all_pairs` creates this.\n",
    "- We will then call `make_games` to take these pairs and put them together into a list of games, strictly enforcing criterion 4 that a player can't be scheduled into both sides of the net in any one game.\n",
    "- Next we call `schedule` to take the list of games and put them into a schedule with up to *C* games played at the same time. We will again strictly enforce criterion 4, not allowing a player to appear on two courts at the same time.\n",
    "- If this approach does not result in everybody playing everyone else twice we will randomly swap a pair in one game with a pair in another game, and see if this improves things. Keep swapping *N* times.\n",
    "\n",
    "# Implementation\n",
    "\n",
    "Let's start with some imports and some choices for basic types:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from itertools   import combinations\n",
    "from collections import Counter\n",
    "import random\n",
    "random.seed('reproducible')\n",
    "\n",
    "Player   = int    # A player is an int: `1`\n",
    "Pair     = tuple  # A pair is a tuple of two players who are partners: `(1, 2)`\n",
    "Game     = list   # A game is a list of two pairs: `[(1, 2), (3, 4)]`\n",
    "Round    = tuple  # A round is a tuple of games: `([(1, 2), (3, 4)], [(5, 6), (7, 8)])`\n",
    "Schedule = list   # A schedule is a list of rounds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# All Pairs of Players\n",
    "\n",
    "We will generate all pairs of players (partners) like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def all_pairs(P: int) -> [Pair]: return list(combinations(range(P), 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_pairs(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 1),\n",
       " (0, 2),\n",
       " (0, 3),\n",
       " (0, 4),\n",
       " (0, 5),\n",
       " (1, 2),\n",
       " (1, 3),\n",
       " (1, 4),\n",
       " (1, 5),\n",
       " (2, 3),\n",
       " (2, 4),\n",
       " (2, 5),\n",
       " (3, 4),\n",
       " (3, 5),\n",
       " (4, 5)]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_pairs(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This looks good!\n",
    "\n",
    "# Placing Pairs into Games\n",
    "\n",
    "Now let's take those pairs and place them together into games. We'll choose one pair of players, `A`, to play against another pair `B`, making sure that between the two pairs there are four different players. Then we'll try to make `other_games` out of the remaining pairs. If we can't, we'll make a different choice for `B`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def make_games(pairs) -> [Game]:\n",
    "    \"Combine pairs of players into a list of games.\"\n",
    "    if len(pairs) < 2:\n",
    "        return []\n",
    "    A = pairs[0]\n",
    "    for B in pairs:\n",
    "        if len(set(A + B)) == 4:\n",
    "            game = [A, B]\n",
    "            other_games = make_games([p for p in pairs if p not in game])\n",
    "            if other_games is not None:\n",
    "                return [game] + other_games"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(0, 1), (2, 3)], [(0, 2), (1, 3)], [(0, 3), (1, 2)]]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_games(all_pairs(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(0, 1), (2, 3)],\n",
       " [(0, 2), (1, 3)],\n",
       " [(0, 3), (1, 2)],\n",
       " [(0, 4), (1, 5)],\n",
       " [(0, 5), (1, 4)],\n",
       " [(2, 4), (3, 5)],\n",
       " [(2, 5), (3, 4)]]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_games(all_pairs(6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The astute reader may have noticed that `all_pairs(6)` has 15 pairs, and from that we can only make 7 games, not 7.5. We must drop one of the pairs, meaning that two players will never partner with each other, and will end up playing one less game than everyone else. Since there are *P* &times; (*P*-1) / 2 pairs of *P* players, that means there are *P* &times; (*P*-1) / 4 games, which is a whole number when either *P* or *P*-1 is divisble by 4."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(0, 1), (2, 3)],\n",
       " [(0, 2), (1, 3)],\n",
       " [(0, 3), (1, 2)],\n",
       " [(0, 4), (1, 5)],\n",
       " [(0, 5), (1, 4)],\n",
       " [(0, 6), (1, 7)],\n",
       " [(0, 7), (1, 6)],\n",
       " [(2, 4), (3, 5)],\n",
       " [(2, 5), (3, 4)],\n",
       " [(2, 6), (3, 7)],\n",
       " [(2, 7), (3, 6)],\n",
       " [(4, 5), (6, 7)],\n",
       " [(4, 6), (5, 7)],\n",
       " [(4, 7), (5, 6)]]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_games(all_pairs(8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That looks good. \n",
    "\n",
    "# Scheduling Games onto Courts\n",
    "\n",
    "Now we need to schedule games onto courts in rounds, such that no player plays twice in any round, and we take as few rounds as possible. We'll define  `schedule(games, courts)` to produce a `list` of rounds, where each round is a tuple of up to `courts` games. We'll use a greedy approach to assigning games to rounds; this does *not* guarantee the shortest possible schedule."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def schedule(games, courts=2):\n",
    "    \"Schedule games onto courts; return a list of rounds.\"\n",
    "    games = list(games) # Don't modify the input\n",
    "    sched = []\n",
    "    while games:\n",
    "        round = []\n",
    "        # A round gets up to `courts` games, all with disjoint players.\n",
    "        for game in list(games):\n",
    "            if len(round) < courts and disjoint(players(round), players(game)):\n",
    "                round.append(game)\n",
    "                games.remove(game)\n",
    "        sched.append(Round(round))\n",
    "    return sched\n",
    "\n",
    "def disjoint(A, B): return not (A & B)\n",
    "\n",
    "def players(x):\n",
    "    \"The set of players in a pair, game, round, or schedule.\"\n",
    "    return ({x} if isinstance(x, Player) else set().union(*map(players, x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[([(0, 1), (2, 3)], [(4, 5), (6, 7)]),\n",
       " ([(0, 2), (1, 3)], [(4, 6), (5, 7)]),\n",
       " ([(0, 3), (1, 2)], [(4, 7), (5, 6)]),\n",
       " ([(0, 4), (1, 5)], [(2, 6), (3, 7)]),\n",
       " ([(0, 5), (1, 4)], [(2, 7), (3, 6)]),\n",
       " ([(0, 6), (1, 7)], [(2, 4), (3, 5)]),\n",
       " ([(0, 7), (1, 6)], [(2, 5), (3, 4)])]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "schedule(make_games(all_pairs(8)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That looks pretty good&mdash;we fit all the games into the minimum number of rounds. But the opponents are not evenly distributed. For example, player 0 and player 1 play against each other in every round except the first (where they are partners).\n",
    "\n",
    "How can we improve that? We could try *shuffling* the pairs before we make games. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[([(0, 6), (3, 5)],),\n",
       " ([(5, 6), (4, 7)],),\n",
       " ([(0, 4), (1, 5)],),\n",
       " ([(3, 4), (2, 7)],),\n",
       " ([(1, 3), (4, 6)], [(0, 2), (5, 7)]),\n",
       " ([(6, 7), (1, 2)],),\n",
       " ([(3, 7), (1, 4)], [(2, 6), (0, 5)]),\n",
       " ([(3, 6), (2, 4)],),\n",
       " ([(4, 5), (0, 1)],),\n",
       " ([(0, 7), (1, 6)],),\n",
       " ([(2, 5), (0, 3)],),\n",
       " ([(1, 7), (2, 3)],)]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def shuffled(iterable):\n",
    "    \"Return a shuffled list of the items in iterable.\"\n",
    "    items = list(iterable)\n",
    "    random.shuffle(items)\n",
    "    return items  \n",
    "\n",
    "schedule(make_games(shuffled(all_pairs(8))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Clearly that made things worse in terms of the number of rounds. But did it even out the distribution of opponents? I'll define a function, `report` to make it easier to see what is going on:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def report(sched):\n",
    "    \"Print information about this schedule.\"\n",
    "    for i, round in enumerate(sched, 1):\n",
    "        print('Round {:2}: | {} |'.format(i, games_str(round)))\n",
    "    games = sum(sched, ())\n",
    "    P = len(players(sched))\n",
    "    opp = opponents(games)\n",
    "    fmt = ('{:2X}|' + P * ' {}' + '   {:g}').format\n",
    "    print('\\nNumber of times each player plays against each opponent:\\n')\n",
    "    print('  |', *map('{:X}'.format, range(P)), ' Games')\n",
    "    print('--+' + '--' * P + '  -----')\n",
    "    for row in range(P):\n",
    "        counts = [opp[pairing(row, col)] for col in range(P)]\n",
    "        print(fmt(row, *[c or '-' for c in counts], sum(counts) / 2))\n",
    "        \n",
    "def games_str(round):\n",
    "    \"A string representing a round of games.\"\n",
    "    return ' | '.join('{:X},{:X} vs {:X},{:X}'\n",
    "                      .format(a, b, c, d) for ((a, b), (c, d)) in round)\n",
    "        \n",
    "def opponents(games):\n",
    "    \"A Counter of {(player, opponent): times_played}.\"\n",
    "    return Counter(pairing(p1, p2) for A, B in games for p1 in A for p2 in B)\n",
    "\n",
    "def pairing(p1, p2): return min(p1, p2), max(p1, p2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can compare the shuffled and non-shuffled versions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Round  1: | 0,1 vs 2,3 | 4,5 vs 6,7 |\n",
      "Round  2: | 0,2 vs 1,3 | 4,6 vs 5,7 |\n",
      "Round  3: | 0,3 vs 1,2 | 4,7 vs 5,6 |\n",
      "Round  4: | 0,4 vs 1,5 | 2,6 vs 3,7 |\n",
      "Round  5: | 0,5 vs 1,4 | 2,7 vs 3,6 |\n",
      "Round  6: | 0,6 vs 1,7 | 2,4 vs 3,5 |\n",
      "Round  7: | 0,7 vs 1,6 | 2,5 vs 3,4 |\n",
      "\n",
      "Number of times each player plays against each opponent:\n",
      "\n",
      "  | 0 1 2 3 4 5 6 7  Games\n",
      "--+----------------  -----\n",
      " 0| - 6 2 2 1 1 1 1   7\n",
      " 1| 6 - 2 2 1 1 1 1   7\n",
      " 2| 2 2 - 6 1 1 1 1   7\n",
      " 3| 2 2 6 - 1 1 1 1   7\n",
      " 4| 1 1 1 1 - 6 2 2   7\n",
      " 5| 1 1 1 1 6 - 2 2   7\n",
      " 6| 1 1 1 1 2 2 - 6   7\n",
      " 7| 1 1 1 1 2 2 6 -   7\n"
     ]
    }
   ],
   "source": [
    "report(schedule(make_games(all_pairs(8))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Round  1: | 1,4 vs 0,5 |\n",
      "Round  2: | 5,7 vs 3,4 |\n",
      "Round  3: | 3,5 vs 2,6 |\n",
      "Round  4: | 1,5 vs 2,7 |\n",
      "Round  5: | 3,6 vs 0,1 |\n",
      "Round  6: | 0,6 vs 2,3 |\n",
      "Round  7: | 6,7 vs 1,3 | 4,5 vs 0,2 |\n",
      "Round  8: | 4,6 vs 1,7 |\n",
      "Round  9: | 3,7 vs 2,4 |\n",
      "Round 10: | 4,7 vs 1,6 |\n",
      "Round 11: | 5,6 vs 0,3 |\n",
      "Round 12: | 2,5 vs 0,7 |\n",
      "Round 13: | 1,2 vs 0,4 |\n",
      "\n",
      "Number of times each player plays against each opponent:\n",
      "\n",
      "  | 0 1 2 3 4 5 6 7  Games\n",
      "--+----------------  -----\n",
      " 0| - 2 3 2 2 3 2 -   7\n",
      " 1| 2 - 1 1 3 1 3 3   7\n",
      " 2| 3 1 - 2 2 3 1 2   7\n",
      " 3| 2 1 2 - 1 2 4 2   7\n",
      " 4| 2 3 2 1 - 2 1 3   7\n",
      " 5| 3 1 3 2 2 - 1 2   7\n",
      " 6| 2 3 1 4 1 1 - 2   7\n",
      " 7| - 3 2 2 3 2 2 -   7\n"
     ]
    }
   ],
   "source": [
    "report(schedule(make_games(shuffled(all_pairs(8)))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that shuffling helps a lot in terms of evening out the opponents, but it does a bad job of filling both courts on each round. \n",
    "\n",
    "# `pickleball`: Improvement through Hillclimbing\n",
    "\n",
    "My strategy now is to start with a non-optimal schedule, and repeatedly try to improve it by randomly altering the games and seeing if this results in a better schedule. This is called a **hillclimbing** approach; the analogy is that we start out in a valley, take a step in a random direction, and if that is upward, keep going, otherwise step back and try again. Eventually you reach a peak. \n",
    "\n",
    "In this case I will be picking two games at random, and swapping one pair of partners in one game with one pair of partners in the other. If the swap makes things worse, discard it; if it makes things better, keep it. Either way, try `N` swaps. I measure \"better\" both in terms of minimal variation from the optimal distribution of opponents (as measured by `opp_difference(games, pairs)`) and in terms of the number of rounds (as measured by `len(sched)`). I keep track of both a list of `games` and a complete schedule, `sched`. I make random changes to the `games`, and then re-schedule the games after each change."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def pickleball(P, courts=2, N=100000):\n",
    "    \"Schedule games for P players on C courts by randomly swapping game opponents N times.\"\n",
    "    pairs = all_pairs(P)\n",
    "    games = make_games((pairs))\n",
    "    diff  = opp_difference(games, pairs)\n",
    "    sched = schedule(games, courts)\n",
    "    for _ in range(N):\n",
    "        # Randomly swap pairs from two games\n",
    "        ((i, j), _) = idx = indexes(games)\n",
    "        swap(games, idx)\n",
    "        diff2 = opp_difference(games, pairs)\n",
    "        # Keep the swap if better (or same); revert if worse\n",
    "        if (diff2 <= diff and len(schedule(games, courts)) <= len(sched) and\n",
    "            len(players(games[i])) == 4 == len(players(games[j]))):\n",
    "            sched, diff = schedule(games, courts), diff2\n",
    "        else:\n",
    "            swap(games, idx)\n",
    "    return sched\n",
    "\n",
    "def indexes(games):\n",
    "    \"Random indexes into games, and into sides of the net in each game.\"\n",
    "    sides = ((0, 0), (1, 1), (0, 1), (1, 0))\n",
    "    return random.sample(range(len(games)), 2), random.choice(sides)\n",
    "\n",
    "def swap(games, idx):\n",
    "    \"Swap the partners at games[g1][a] with games[g2][b].\"\n",
    "    (g1, g2), (a, b) = idx\n",
    "    games[g1][a], games[g2][b] = games[g2][b], games[g1][a]\n",
    "\n",
    "def opp_difference(games, pairs, optimal=2):\n",
    "    \"The total difference from an optimal distribution of opponents.\"\n",
    "    opp = opponents(games)\n",
    "    return sum(abs(opp[pair] - optimal) ** 3\n",
    "               for pair in pairs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 8 Player Tournament\n",
    "\n",
    "Let's create an 8-player tournament:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Round  1: | 0,1 vs 2,3 | 4,6 vs 5,7 |\n",
      "Round  2: | 4,5 vs 1,3 | 0,2 vs 6,7 |\n",
      "Round  3: | 0,3 vs 5,6 | 4,7 vs 1,2 |\n",
      "Round  4: | 2,7 vs 1,5 | 0,4 vs 3,6 |\n",
      "Round  5: | 0,5 vs 1,4 | 2,6 vs 3,7 |\n",
      "Round  6: | 1,7 vs 0,6 | 3,4 vs 2,5 |\n",
      "Round  7: | 0,7 vs 3,5 | 2,4 vs 1,6 |\n",
      "\n",
      "Number of times each player plays against each opponent:\n",
      "\n",
      "  | 0 1 2 3 4 5 6 7  Games\n",
      "--+----------------  -----\n",
      " 0| - 2 1 3 1 2 3 2   7\n",
      " 1| 2 - 3 1 3 2 1 2   7\n",
      " 2| 1 3 - 2 2 1 2 3   7\n",
      " 3| 3 1 2 - 2 3 2 1   7\n",
      " 4| 1 3 2 2 - 3 2 1   7\n",
      " 5| 2 2 1 3 3 - 1 2   7\n",
      " 6| 3 1 2 2 2 1 - 3   7\n",
      " 7| 2 2 3 1 1 2 3 -   7\n",
      "CPU times: user 29.4 s, sys: 487 ms, total: 29.9 s\n",
      "Wall time: 33 s\n"
     ]
    }
   ],
   "source": [
    "%time report(pickleball(8, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's pretty good, but not perfect. In a previous run I was luckier and achieved a perfect schedule for 8 players (where every player plays each opponent exactly twice): "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Round  1: | 1,6 vs 2,4 | 3,5 vs 7,0 |\n",
      "Round  2: | 1,5 vs 3,6 | 2,0 vs 4,7 |\n",
      "Round  3: | 2,3 vs 6,0 | 4,5 vs 1,7 |\n",
      "Round  4: | 4,6 vs 3,7 | 1,2 vs 5,0 |\n",
      "Round  5: | 1,0 vs 6,7 | 3,4 vs 2,5 |\n",
      "Round  6: | 2,6 vs 5,7 | 1,4 vs 3,0 |\n",
      "Round  7: | 2,7 vs 1,3 | 4,0 vs 5,6 |\n",
      "\n",
      "Number of times each player plays against each opponent:\n",
      "\n",
      "  | 0 1 2 3 4 5 6 7  Games\n",
      "--+----------------  -----\n",
      " 0| - 2 2 2 2 2 2 2   7\n",
      " 1| 2 - 2 2 2 2 2 2   7\n",
      " 2| 2 2 - 2 2 2 2 2   7\n",
      " 3| 2 2 2 - 2 2 2 2   7\n",
      " 4| 2 2 2 2 - 2 2 2   7\n",
      " 5| 2 2 2 2 2 - 2 2   7\n",
      " 6| 2 2 2 2 2 2 - 2   7\n",
      " 7| 2 2 2 2 2 2 2 -   7\n"
     ]
    }
   ],
   "source": [
    "report([\n",
    " ([(1, 6), (2, 4)], [(3, 5), (7, 0)]),\n",
    " ([(1, 5), (3, 6)], [(2, 0), (4, 7)]),\n",
    " ([(2, 3), (6, 0)], [(4, 5), (1, 7)]),\n",
    " ([(4, 6), (3, 7)], [(1, 2), (5, 0)]),\n",
    " ([(1, 0), (6, 7)], [(3, 4), (2, 5)]),\n",
    " ([(2, 6), (5, 7)], [(1, 4), (3, 0)]),\n",
    " ([(2, 7), (1, 3)], [(4, 0), (5, 6)]), \n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 9 Player Tournament\n",
    "\n",
    "For 9 players, I can fit the 18 games into 9 rounds, but some players play each other 1 or 3 times. I'll report the results of a previous run:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Round  1: | 1,7 vs 4,0 | 3,5 vs 2,6 |\n",
      "Round  2: | 2,7 vs 1,3 | 4,8 vs 6,0 |\n",
      "Round  3: | 5,0 vs 1,6 | 7,8 vs 3,4 |\n",
      "Round  4: | 7,0 vs 5,8 | 1,2 vs 4,6 |\n",
      "Round  5: | 3,8 vs 1,5 | 2,0 vs 6,7 |\n",
      "Round  6: | 1,4 vs 2,5 | 3,6 vs 8,0 |\n",
      "Round  7: | 5,6 vs 4,7 | 1,8 vs 2,3 |\n",
      "Round  8: | 1,0 vs 3,7 | 2,8 vs 4,5 |\n",
      "Round  9: | 3,0 vs 2,4 | 6,8 vs 5,7 |\n",
      "\n",
      "Number of times each player plays against each opponent:\n",
      "\n",
      "  | 0 1 2 3 4 5 6 7 8  Games\n",
      "--+------------------  -----\n",
      " 0| - 2 1 2 2 1 3 3 2   8\n",
      " 1| 2 - 3 3 2 2 1 2 1   8\n",
      " 2| 1 3 - 3 3 2 2 1 1   8\n",
      " 3| 2 3 3 - 1 1 1 2 3   8\n",
      " 4| 2 2 3 1 - 2 2 2 2   8\n",
      " 5| 1 2 2 1 2 - 3 2 3   8\n",
      " 6| 3 1 2 1 2 3 - 2 2   8\n",
      " 7| 3 2 1 2 2 2 2 - 2   8\n",
      " 8| 2 1 1 3 2 3 2 2 -   8\n"
     ]
    }
   ],
   "source": [
    "report([\n",
    " ([(1, 7), (4, 0)], [(3, 5), (2, 6)]),\n",
    " ([(2, 7), (1, 3)], [(4, 8), (6, 0)]),\n",
    " ([(5, 0), (1, 6)], [(7, 8), (3, 4)]),\n",
    " ([(7, 0), (5, 8)], [(1, 2), (4, 6)]),\n",
    " ([(3, 8), (1, 5)], [(2, 0), (6, 7)]),\n",
    " ([(1, 4), (2, 5)], [(3, 6), (8, 0)]),\n",
    " ([(5, 6), (4, 7)], [(1, 8), (2, 3)]),\n",
    " ([(1, 0), (3, 7)], [(2, 8), (4, 5)]),\n",
    " ([(3, 0), (2, 4)], [(6, 8), (5, 7)]) ])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 16 Player Tournament\n",
    "\n",
    "Let's jump to 16 players on 4 courts:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Round  1: | 0,1 vs 2,3 | 4,5 vs 6,7 | 8,9 vs D,E | C,F vs A,B |\n",
      "Round  2: | 0,2 vs 5,7 | 3,B vs 4,6 | 8,A vs 1,9 | C,D vs E,F |\n",
      "Round  3: | 0,3 vs 1,2 | 4,8 vs 5,9 | 6,A vs 7,B | C,E vs D,F |\n",
      "Round  4: | 0,4 vs B,C | 2,6 vs A,D | 8,E vs 1,5 | 3,7 vs 9,F |\n",
      "Round  5: | 0,5 vs 1,4 | 2,7 vs B,E | A,F vs 9,D | 8,C vs 3,6 |\n",
      "Round  6: | 0,6 vs 8,F | A,E vs 3,4 | 1,7 vs B,D | 2,5 vs 9,C |\n",
      "Round  7: | 0,7 vs A,C | B,F vs 3,5 | 8,D vs 2,4 | 1,6 vs 9,E |\n",
      "Round  8: | 0,9 vs 6,D | 2,B vs 1,8 | 4,E vs 3,A | 5,F vs 7,C |\n",
      "Round  9: | 0,A vs 6,E | 5,C vs 3,9 | 1,B vs 4,D | 7,F vs 2,8 |\n",
      "Round 10: | 0,B vs 1,A | 2,9 vs 4,F | 3,8 vs 7,D | 5,E vs 6,C |\n",
      "Round 11: | 0,C vs 1,D | 2,E vs 5,A | 4,B vs 3,F | 6,9 vs 7,8 |\n",
      "Round 12: | 0,D vs 5,B | 2,F vs 3,E | 6,8 vs 1,C | 4,A vs 7,9 |\n",
      "Round 13: | 0,E vs 3,D | 1,F vs 6,B | 4,9 vs 2,C | 5,8 vs 7,A |\n",
      "Round 14: | 0,F vs 9,A | 2,D vs 5,6 | 8,B vs 3,C | 4,7 vs 1,E |\n",
      "Round 15: | 0,8 vs 4,C | 6,F vs 2,A | 9,B vs 7,E | 1,3 vs 5,D |\n",
      "\n",
      "Number of times each player plays against each opponent:\n",
      "\n",
      "  | 0 1 2 3 4 5 6 7 8 9 A B C D E F  Games\n",
      "--+--------------------------------  -----\n",
      " 0| - 4 2 2 2 2 2 1 1 1 3 2 3 3 1 1   15\n",
      " 1| 4 - 2 2 2 2 2 1 3 1 1 4 1 3 2 -   15\n",
      " 2| 2 2 - 2 2 3 2 2 2 2 2 1 1 2 2 3   15\n",
      " 3| 2 2 2 - 3 2 1 1 2 1 1 3 2 2 3 3   15\n",
      " 4| 2 2 2 3 - 2 1 2 2 3 2 3 2 1 2 1   15\n",
      " 5| 2 2 3 2 2 - 2 3 2 2 1 1 3 2 2 1   15\n",
      " 6| 2 2 2 1 1 2 - 2 3 2 3 2 2 2 2 2   15\n",
      " 7| 1 1 2 1 2 3 2 - 3 3 3 3 1 1 2 2   15\n",
      " 8| 1 3 2 2 2 2 3 3 - 3 1 1 3 2 1 1   15\n",
      " 9| 1 1 2 1 3 2 2 3 3 - 3 - 2 2 2 3   15\n",
      " A| 3 1 2 1 2 1 3 3 1 3 - 2 1 1 3 3   15\n",
      " B| 2 4 1 3 3 1 2 3 1 - 2 - 2 2 1 3   15\n",
      " C| 3 1 1 2 2 3 2 1 3 2 1 2 - 2 2 3   15\n",
      " D| 3 3 2 2 1 2 2 1 2 2 1 2 2 - 3 2   15\n",
      " E| 1 2 2 3 2 2 2 2 1 2 3 1 2 3 - 2   15\n",
      " F| 1 - 3 3 1 1 2 2 1 3 3 3 3 2 2 -   15\n",
      "CPU times: user 2min 4s, sys: 977 ms, total: 2min 5s\n",
      "Wall time: 2min 8s\n"
     ]
    }
   ],
   "source": [
    "%time report(pickleball(P=16, courts=4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's a good schedule! It takes the minimum 15 rounds, and although not all counts are 2, most are in the 1 to 3 range."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Addendum: Counting Schedules\n",
    "\n",
    "A reader asked \"*couldn't you have tried all possible schedules?*\" That's a great question! As [Ken Thompson says](https://users.ece.utexas.edu/~adnan/pike.html), \"when in doubt, use brute force.\" How many possible schedules are there? \n",
    "\n",
    "- Assume a schedule with *R* rounds on *C* courts, with every court filled on every round.\n",
    "- That means there are *G* = *CR* games and 2*G* slots in the schedule for pairs to fill.\n",
    "- We can fill those slots with pairs in (2*G*)! ways.\n",
    "- But that over-counts, because order doesn't matter in the following three ways:\n",
    "  - The order of pairs within a game doesn't matter, so divide by 2*<sup>G</sup>*.\n",
    "  - The order of games within a round doesn't matter, so divide by *C*!*<sup>R</sup>*.\n",
    "  - The order of rounds within the schedule doesn't matter, so divide by *R*!.\n",
    "\n",
    "That gives us:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{4: 15.0,\n",
       " 5: 945.0,\n",
       " 8: 2.8845653137679503e+19,\n",
       " 9: 7.637693625347176e+27,\n",
       " 16: 8.78872489906208e+147,\n",
       " 17: 1.1985831550364023e+174}"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from math import factorial\n",
    "\n",
    "def schedules(P):\n",
    "    \"Number of possible schedules for P players with all courts full.\"\n",
    "    G = P * (P - 1) // 4 # Number of games\n",
    "    C = P // 4           # Number of courts\n",
    "    R = G // C           # Number of rounds\n",
    "    return factorial(2 * G) / 2 ** G / factorial(C) ** R / factorial(R)\n",
    "\n",
    "{P: schedules(P) \n",
    " for P in (4, 5, 8, 9, 16, 17)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that it would have been infeasible to try every schedule, even for *P*=8, let alone 9 or 16."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}