Le compte est bon.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align: right\">Paul Novaes<br>August 2018</div> \n",
    "\n",
    "# Le compte est bon\n",
    "\n",
    "[Le compte est bon](https://en.wikipedia.org/wiki/Des_chiffres_et_des_lettres#Le_compte_est_bon_&#40;%22the_total_is_right%22&#41;) (\"The total is right\") is a French TV show where the goal is to get as close as possible to some target number by using 6 randomly drawn numbers and the 4 arithmetic operations.\n",
    "\n",
    "For example, if the target is __383__ and the numbers are __1, 3, 7, 7, 9, 25__, one possible solution (not necessarily the best) is: \n",
    "\n",
    "$$25 \\times (7 + 9) - 7 \\times (3 - 1) = 386$$\n",
    "\n",
    "In this notebook, we write a program that finds the best solution, using the least amount of numbers. We then explore some possible variations of the original game and estimate their difficulty.\n",
    "\n",
    "__Note: This notebook takes around 10 minutes to render.__\n",
    "\n",
    "## Rules of the Game\n",
    "\n",
    "* The target is a random number between $101$ and $999$.\n",
    "* The 6 other numbers are drawn at random, without replacement from: $$\\{1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,25,50,75,100\\}$$\n",
    "* Each of the 6 numbers can only be used once, and not all numbers need to be used.\n",
    "* Temporary and final results have to be positive integers.\n",
    "\n",
    "## Random draw\n",
    "\n",
    "Python's random.sample function makes drawing a random game very easy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "# For consistency.\n",
    "random.seed(0)\n",
    "\n",
    "def draw(n = 6, lo = 101, hi = 999, cards = [1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,25,50,75,100]):\n",
    "    target = random.randint(lo, hi)\n",
    "    return target, sorted(random.sample(cards, n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "target: 965, cards: [1, 5, 7, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "target, cards = draw()\n",
    "print('target: ', target, ', cards: ', cards, sep = '')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Best solution with exactly n cards\n",
    "\n",
    "We can solve this problem recursively as follows. \n",
    "\n",
    "If there is just 1 card, use that card. Otherwise, if we have $n > 1$ cards:\n",
    "* choose 2 of the cards $a$ and $b$ and 1 of the operators $op$\n",
    "* replace $a$ and $b$ by $a$ op $b$\n",
    "* solve the problem on the resulting $n - 1$ cards\n",
    "\n",
    "Note that $a+b$ and $a \\times b$ are commutative and $a - b$ and $a \\div b$ are only allowed if $a \\geq b$. Since there are ${n \\choose 2}$ ways of choosing 2 cards and 4 ways of choosing 1 operator, the total number of operations $N(n)$ verifies, for $n > 2$:\n",
    "\n",
    "$$N(n) \\leq 4{n \\choose 2} N(n-1)$$\n",
    "\n",
    "The first values are:\n",
    "\n",
    "\\begin{align*}\n",
    "N(2) & \\leq & 4 \\\\\n",
    "N(3) & \\leq & 48 \\\\\n",
    "N(4) & \\leq & 1152 \\\\\n",
    "N(5) & \\leq & 46080 \\\\\n",
    "N(6) & \\leq & 2764800\n",
    "\\end{align*}\n",
    "\n",
    "Though large, these numbers are __not too__ large and we can do an extensive search."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Returns the best solution using all cards.\n",
    "def solve_using_all(target, cards, ops = ['+', '-', '*', '/']):\n",
    "    count = len(cards)\n",
    "    assert count > 0\n",
    "    if len(cards) == 1:        \n",
    "        return cards[0], [cards[0]]\n",
    "    best_reached = 0\n",
    "    best_solution = []\n",
    "    # Choose 2 cards and 1 operator.\n",
    "    for i in range(count):\n",
    "        for j in range(i + 1, count):\n",
    "            for k in ops:\n",
    "                a = cards[i]\n",
    "                b = cards[j]\n",
    "                new_cards = list(cards)\n",
    "                del new_cards[j], new_cards[i]\n",
    "                if a < b: a, b = b, a\n",
    "                if k == '+': result = a + b\n",
    "                if k == '-': result = a - b\n",
    "                if k == '*': result = a * b\n",
    "                if k == '/':\n",
    "                    if b > 0 and a % b == 0:\n",
    "                        result = a // b\n",
    "                    else:\n",
    "                        continue\n",
    "                new_cards.append(result)\n",
    "                reached, solution = solve_using_all(target, new_cards, ops)\n",
    "                if abs(reached - target) < abs(best_reached - target):\n",
    "                    best_reached = reached\n",
    "                    best_solution = [[a, k, b, '=', result]]\n",
    "                    best_solution.extend(solution)\n",
    "                if reached == target:\n",
    "                    return best_reached, best_solution\n",
    "    return best_reached, best_solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "515 [4, 5, 6, 8, 9, 10]\n",
      "[[6, '*', 4, '=', 24], [24, '-', 10, '=', 14], [14, '*', 8, '=', 112], [112, '-', 9, '=', 103], [103, '*', 5, '=', 515], 515]\n"
     ]
    }
   ],
   "source": [
    "target, cards = draw()\n",
    "print(target, cards)\n",
    "best_reached, best_solution = solve_using_all(target, cards)\n",
    "print(best_solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or we can print the solution in a more natural way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 * 4 = 24 \n",
      "24 - 10 = 14 \n",
      "14 * 8 = 112 \n",
      "112 - 9 = 103 \n",
      "103 * 5 = 515 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "def print_solution(solution):\n",
    "    for operation in solution:\n",
    "        if type(operation) is int:\n",
    "            if len(solution) == 1:\n",
    "                print(operation)\n",
    "        else:\n",
    "            for token in operation:\n",
    "                print(token, end = ' ')\n",
    "        print()\n",
    "\n",
    "print_solution(best_solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Some Unit Tests__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test(target, cards, expect):\n",
    "    reached, solution = solve_using_all(target, cards)\n",
    "    assert(abs(target - reached) == abs(target - expect))\n",
    "\n",
    "def unit_tests():\n",
    "    test(1, [1], 1)\n",
    "    test(1, [2], 2)\n",
    "    test(1, [3], 3)\n",
    "    test(10, [1, 1], 2)\n",
    "    test(10, [1, 1, 1], 3)\n",
    "    test(10, [1, 1, 1, 1], 4)\n",
    "    test(10, [1, 1, 1, 1, 1], 6)\n",
    "    test(10, [1, 1, 1, 1, 1, 1], 9)\n",
    "    test(5, [1, 1, 1, 1, 1, 1], 5)\n",
    "    test(1, [1, 1, 1, 1, 1, 1], 1)\n",
    "    test(2, [1, 1, 1, 1, 1, 1], 2)\n",
    "\n",
    "unit_tests()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shortest Solution\n",
    "\n",
    "Now that we know how to compute the best solution that uses exactly $n$ cards, we can compute, among the best solutions, the shortest one. We use again a brute force approach by looking at subsets with 1, 2, 3, 4, 5 and 6 elements. In total, the number of operations is bounded by\n",
    "\n",
    "$${6 \\choose 2}N(2) + {6 \\choose 3}N(3) + {6 \\choose 4}N(4) + {6 \\choose 5}N(5) + {6 \\choose 6}N(6) = 3059580$$ \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Returns the number of 1's in the binary representation of n.\n",
    "def count_1_bits(n):\n",
    "    count = 0\n",
    "    while n > 0:\n",
    "        if n & 1 != 0:\n",
    "            count += 1\n",
    "        n = n >> 1\n",
    "    return count\n",
    "\n",
    "# Returns a subset of a set, by using mask to select its elements.\n",
    "def make_subset(set, mask):\n",
    "    subset = []\n",
    "    index = 0\n",
    "    while mask > 0:\n",
    "        if mask & 1 != 0:\n",
    "            subset.append(set[index])\n",
    "        index += 1\n",
    "        mask = mask >> 1\n",
    "    return subset\n",
    "\n",
    "# Returns the best solution using as few cards as possible.\n",
    "def solve_using_any(target, all_cards, ops = ['+', '-', '*', '/']):\n",
    "    best_reached = 0\n",
    "    best_solution = []\n",
    "    n = len(all_cards)\n",
    "    # Solve the problem with 1 card first, then 2, then 3...\n",
    "    for num_cards in range(1, n + 1):\n",
    "        for mask in range(2 ** n):\n",
    "            if count_1_bits(mask) == num_cards:\n",
    "                cards = make_subset(all_cards, mask)\n",
    "                reached, solution = solve_using_all(target, cards, ops)\n",
    "                if abs(reached - target) < abs(best_reached - target):\n",
    "                    best_reached = reached\n",
    "                    best_solution = solution\n",
    "                if reached == target:\n",
    "                    return best_reached, best_solution\n",
    "    return best_reached, best_solution\n",
    "\n",
    "# Alias.\n",
    "def solve(target, cards, ops = ['+', '-', '*', '/']):\n",
    "    return solve_using_any(target, cards, ops)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Some Unit Tests__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_shortest(target, cards, expect, length):\n",
    "    reached, solution = solve(target, cards)\n",
    "    assert(abs(target - reached) == abs(target - expect))\n",
    "    assert(length == len(solution))\n",
    "    \n",
    "def unit_tests_shortest():\n",
    "    test_shortest(1, [1], 1, 1)\n",
    "    test_shortest(1, [2], 0, 0)\n",
    "    test_shortest(1, [3], 0, 0)\n",
    "    test_shortest(10, [1, 1], 2, 2)\n",
    "    test_shortest(10, [1, 1, 1], 3, 3)\n",
    "    test_shortest(10, [1, 1, 1, 1], 4, 4)\n",
    "    test_shortest(10, [1, 1, 1, 1, 1], 6, 5)\n",
    "    test_shortest(10, [1, 1, 1, 1, 1, 1], 9, 6)\n",
    "    test_shortest(5, [1, 1, 1, 1, 1, 1], 5, 5)\n",
    "    test_shortest(1, [1, 1, 1, 1, 1, 1], 1, 1)\n",
    "    test_shortest(2, [1, 1, 1, 1, 1, 1], 2, 2)\n",
    "\n",
    "unit_tests_shortest()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solving our original game"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "target = 383\n",
      "cards = [1, 3, 7, 7, 9, 25]\n",
      "\n",
      "9 + 3 = 12 \n",
      "25 + 7 = 32 \n",
      "32 * 12 = 384 \n",
      "384 - 1 = 383 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "target, cards = 383, [1, 3, 7, 7, 9, 25]\n",
    "print('target =', target)\n",
    "print('cards =', cards)\n",
    "print()\n",
    "reached, solution = solve(target, cards)\n",
    "print_solution(solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Most difficult game\n",
    "\n",
    "[http://patquoi.free.fr/lcpdb/](http://patquoi.free.fr/lcpdb/) defines the most difficult game as the game that:\n",
    "* can be solved in 1 way only\n",
    "* requires all the 6 cards\n",
    "* and, among the games that verify the first 2 conditions, has the highest intermediary result\n",
    "\n",
    "and concludes, after trying all the possibilities, that it is:\n",
    "* target: 653\n",
    "* cards: {10, 10, 25, 50, 75, 100}\n",
    "\n",
    "Let's solve this game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "50 * 10 = 500 \n",
      "500 - 10 = 490 \n",
      "490 * 100 = 49000 \n",
      "49000 - 25 = 48975 \n",
      "48975 / 75 = 653 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "target, cards = 653, [10, 10, 25, 50, 75, 100]\n",
    "reached, solution = solve(target, cards)\n",
    "print_solution(solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Variations\n",
    "\n",
    "With the rules of the original show, around 93% of the games can be solved exactly. \n",
    "\n",
    "We now investigate how changing the rules affects the odds. For each variation, we will play 100 random games and compute how many we can solve exactly. Since the sample is relatively small, the estimate will be rough but it will give us a way of comparing different variations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def score(count = 100, n = 6, lo = 101, hi = 999, \n",
    "          cards = [1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,25,50,75,100], \n",
    "          ops = ['+', '-', '*', '/']):\n",
    "    success = 0\n",
    "    random.seed(0)\n",
    "    for i in range(count):\n",
    "        target, drawn = draw(n, lo, hi, cards)\n",
    "        reached, solution = solve(target, drawn, ops)\n",
    "        if reached == target:\n",
    "            success += 1\n",
    "    return str(success * 100 // count) + '%'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Original rules__\n",
    "\n",
    "With the original rules, around 93 percent of games can be solved. Since we use a small sample of 100 random games, our estimate below is a little off, but close enough:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "original rules:  90%\n"
     ]
    }
   ],
   "source": [
    "default_score = score()\n",
    "print(\"original rules: \", default_score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Changing the number of cards drawn__\n",
    "\n",
    "Unsurprisingly, the more cards we draw the easier the game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 cards: 0%\n",
      "3 cards: 1%\n",
      "4 cards: 15%\n",
      "5 cards: 45%\n",
      "6 cards: 90%\n",
      "7 cards: 100%\n"
     ]
    }
   ],
   "source": [
    "print(\"2 cards:\", score(n = 2))\n",
    "print(\"3 cards:\", score(n = 3))\n",
    "print(\"4 cards:\", score(n = 4))\n",
    "print(\"5 cards:\", score(n = 5))\n",
    "print(\"6 cards:\", default_score)\n",
    "print(\"7 cards:\", score(n = 7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Limiting the set of operations__\n",
    "\n",
    "Not all operators are equal, $\\times$ is essential while $\\div$ is seldom necessary:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no * op: 3%\n",
      "no + op: 57%\n",
      "no - op: 72%\n",
      "no / op: 89%\n",
      "all ops: 90%\n"
     ]
    }
   ],
   "source": [
    "print(\"no * op:\", score(ops = ['+', '-', '/']))\n",
    "print(\"no + op:\", score(ops = ['-', '*', '/']))\n",
    "print(\"no - op:\", score(ops = ['+', '*', '/']))\n",
    "print(\"no / op:\", score(ops = ['+', '-', '*']))\n",
    "print(\"all ops:\", default_score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Varying the target range__\n",
    "\n",
    "Bigger targets are quite a bit more difficult to reach:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "target range 101-400:  99%\n",
      "target range 401-700:  91%\n",
      "target range 701-999:  81%\n"
     ]
    }
   ],
   "source": [
    "print(\"target range 101-400: \", score(lo=101, hi=400))\n",
    "print(\"target range 401-700: \", score(lo=401, hi=700))\n",
    "print(\"target range 701-999: \", score(lo=701, hi=999))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Because, bigger targets are more difficult to reach, it appears the distribution of cards in the original game is not ideal. Drawing cards from $\\{1,2,3,4,5,6,7,8,9,10,25,50,75,100\\}$ would make the game easier across targets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alternate distribution:  99%\n"
     ]
    }
   ],
   "source": [
    "print(\"alternate distribution: \", score(cards = [1,2,3,4,5,6,7,8,9,10,25,50,75,100]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## \"Countdown\"\n",
    "\n",
    "The British version of \"Le compte est bon\" is [Countdown](https://en.wikipedia.org/wiki/Countdown_%28game_show%29). This version allows players to vary the distribution by choosing the number of \"large\" cards.\n",
    "\n",
    "Players choose a number $k$ between 0 and 4. Then, randomly,\n",
    "* $k$ \"large\" cards are drawn from $\\{25,50,75,100\\}$\n",
    "* and $6-k$ \"small\" cards are drawn from $\\{1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10\\}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 large cards: 77%\n",
      "1 large cards: 97%\n",
      "2 large cards: 100%\n",
      "3 large cards: 97%\n",
      "4 large cards: 87%\n"
     ]
    }
   ],
   "source": [
    "def draw_countdown(k):\n",
    "    assert k >= 0 and k <= 4\n",
    "    large_set = [25,50,75,100]\n",
    "    small_set = [1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10]\n",
    "    target = random.randint(101, 999)\n",
    "    drawn = random.sample(large_set, k)\n",
    "    drawn.extend(random.sample(small_set, 6 - k))\n",
    "    return target, sorted(drawn)\n",
    "    \n",
    "\n",
    "def score_countdown(count = 100, k = 0):\n",
    "    success = 0\n",
    "    random.seed(0)\n",
    "    for i in range(count):\n",
    "        target, drawn = draw_countdown(k)\n",
    "        reached, solution = solve(target, drawn)\n",
    "        if reached == target:\n",
    "            success += 1\n",
    "    return str(success * 100 // count) + '%'\n",
    "\n",
    "for i in range(0,5):\n",
    "    print(i, \"large cards:\", score_countdown(k = i))"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}