17_02_2023.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4df263c2",
   "metadata": {},
   "source": [
    "# Riddler Classic Feb 17th 2023 ♦️♠️♣️♥️"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a779c4f",
   "metadata": {},
   "source": [
    "[Riddler puzzle page](https://fivethirtyeight.com/features/how-many-rectangles-can-you-make/)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "447a1397",
   "metadata": {},
   "source": [
    "There’s a version of solitaire played in southern Italy with a deck of 40 Neapolitan cards, with `four suits numbered from 1 to 10`. The deck is shuffled and then cards are turned over one at a time. Flipping over the first card you say “one,” the second card “two” and the third card “three.” You repeat this, saying “one” for the fourth card, “two” for the fifth card and “three” for the sixth card. You continue your way through the deck, until you at last say “one” for the 40th card.\n",
    "\n",
    "If at any point the number you say matches the value of the card you flip over, you lose.\n",
    "\n",
    "*What is your probability of winning the game?*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffb9d3ab",
   "metadata": {},
   "source": [
    "## Calcs with pen and paper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "375792f7",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-02-17T16:16:45.272656Z",
     "start_time": "2023-02-17T16:16:45.239972Z"
    }
   },
   "outputs": [],
   "source": [
    "from functools import cache\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59a7a3c7",
   "metadata": {},
   "source": [
    "Let us compute the number of \"favorable\" cases over the total number of possibilities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "32930c75",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-02-17T15:15:26.326514Z",
     "start_time": "2023-02-17T15:15:26.261337Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'View the sequence we say as 1231231231231231231231231231231231231231 (if we win; else it is interrupted before reaching the 40th card)'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nb_full_seq, remainder = divmod(40, 3)\n",
    "f'View the sequence we say as {\"123\"*nb_full_seq + \"12\"[:remainder]} (if we win; else it is interrupted before reaching the 40th card)'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "098eeadb",
   "metadata": {},
   "source": [
    "### Number of total possible cases"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca77113f",
   "metadata": {},
   "source": [
    "The total number of ways to populate the length-40 list is: $\\frac{40!}{4!^{10}}$. This is because there are in total factorial(40) ways, to which we then need to discard the suits as all that matters is the number on the card. And so, ten unique numbers repeated four times gets you the denominator, factorial(4) to the power of 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "d47dbc33",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-02-17T16:18:12.272707Z",
     "start_time": "2023-02-17T16:18:12.197522Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Total nb of possibilities: 12868639981414579848070084500000000'"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@cache\n",
    "def factorial(n: int) -> int:\n",
    "    \"\"\"Returns the factorial computed recursively\"\"\"\n",
    "    assert n >= 0\n",
    "    return 1 if n in (0, 1) else factorial(n-1) * n\n",
    "\n",
    "nb_total = factorial(40) // (factorial(4) ** 10)\n",
    "f'Total nb of possibilities: {nb_total}'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8692427",
   "metadata": {},
   "source": [
    "### Number of favorable cases"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "1c04f343",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-02-17T15:30:49.139467Z",
     "start_time": "2023-02-17T15:30:49.098131Z"
    }
   },
   "outputs": [],
   "source": [
    "@cache\n",
    "def binom_coeff(k:int, n:int) -> int:\n",
    "    'Computes and returns the binomial coefficient \"k among n\" as the French say'\n",
    "    assert 0 <= k <= n\n",
    "    return factorial(n) // (factorial(k) * factorial(n-k))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f0f1773",
   "metadata": {},
   "source": [
    "A winning sequence is a sequence in which:\n",
    "- the four 1s were placed on a spot other than 1 in the sequence above (\"one, two, three, one, two...\")\n",
    "- the four 2s were placed on a spot other than 2 in the sequence above (\"one, two, three, one, two...\")\n",
    "- the four 3s were placed on a spot other than 3 in the sequence above (\"one, two, three, one, two...\")\n",
    "\n",
    "(**little gotcha**: there are 14 '1' spots but 13 '2' and 13 '3' spots)\n",
    "\n",
    "Let us study each possible case and use binomial coefficients to compute the number of valid such cases:\n",
    "\n",
    "$\\binom{n}{k}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "ca4cabd8",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-02-17T18:17:18.912850Z",
     "start_time": "2023-02-17T18:17:18.588615Z"
    }
   },
   "outputs": [],
   "source": [
    "def compute_all_possibilities():\n",
    "    \"\"\"Place the 1s then the 2s then the 3s.\n",
    "    The value 1s can be placed on spots with index 2 or 3\n",
    "    The value 2s can be placed on spots with index 1 or 3\n",
    "    The value 3s can be placed on spots with index 1 or 2\n",
    "    \"\"\"\n",
    "    total_nb_possibilities = 0\n",
    "    # convention: value_index e.g.: one_two means the card numbered on an index spelled out \"two\"\n",
    "    for i in range(5):\n",
    "        one_two = i\n",
    "        one_three = 4 - one_two\n",
    "        for j in range(5):\n",
    "            two_one = j\n",
    "            two_three = 4 - two_one\n",
    "            for k in range(5):\n",
    "                three_one = k\n",
    "                three_two = 4 - three_one\n",
    "\n",
    "                total_nb_possibilities += (\n",
    "                    binom_coeff(one_two, 13)\n",
    "                    * binom_coeff(one_three, 13)\n",
    "                    * binom_coeff(two_one, 14)\n",
    "                    * binom_coeff(two_three, 13 - one_three)\n",
    "                    * binom_coeff(three_one, 14 - two_one)\n",
    "                    * binom_coeff(three_two, 13 - one_two)\n",
    "                    * (factorial(40 - 3 * 4) // factorial(4) ** 7)\n",
    "                )\n",
    "    return total_nb_possibilities"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "bc01e322",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-02-17T18:17:18.986600Z",
     "start_time": "2023-02-17T18:17:18.969644Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'nb_favorable=106899864027355684640752897500000'"
      ]
     },
     "execution_count": 110,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nb_favorable = compute_all_possibilities()\n",
    "f'{nb_favorable=}'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbd5dbcc",
   "metadata": {},
   "source": [
    "### Getting the answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "id": "002fdf78",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-02-17T18:17:22.663413Z",
     "start_time": "2023-02-17T18:17:22.616206Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.008307005571819934"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "win_proba = nb_favorable / nb_total\n",
    "win_proba"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48a2c686",
   "metadata": {},
   "source": [
    "## Simulation with Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "17bb33b2",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-02-17T18:17:38.278307Z",
     "start_time": "2023-02-17T18:17:38.266948Z"
    }
   },
   "outputs": [],
   "source": [
    "SAID = np.tile(np.arange(1,4), 14)[:-2] # the array representing \"one, two, three, one, two three\"\n",
    "DECK = np.tile(np.arange(1,11), 4) # an ordered deck (1 to 40 included)\n",
    "\n",
    "def play() -> bool:\n",
    "    \"\"\"Simulates one game and returns whether it is won\"\"\"\n",
    "    np.random.shuffle(DECK)\n",
    "    return DECK[DECK == SAID].shape[0] == 0\n",
    "\n",
    "def montecarlo(n_sim: int = 1_000_000) -> float:\n",
    "    \"\"\"Runs `n_sim` simulations of the abovecoded game and returns the % of won games\"\"\"\n",
    "    return sum(play() for _ in range(n_sim)) / n_sim"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "da7c597d",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-02-17T18:17:46.455582Z",
     "start_time": "2023-02-17T18:17:38.569871Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 7.88 s, sys: 0 ns, total: 7.88 s\n",
      "Wall time: 7.87 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.008296"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "montecarlo()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23958514",
   "metadata": {},
   "source": [
    "Simulations show a winning rate of `around 0.8 %`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ef258a6",
   "metadata": {},
   "source": [
    "## ChatGPT output, from the exact prompt provided (it's not ready to replace humans yet!)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b1b9dad",
   "metadata": {},
   "source": [
    "### First ChatGPT try:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5a01c3b",
   "metadata": {},
   "source": [
    "To win the game, you must go through the entire deck without any of the cards you flip over matching the number that you say. The probability of this happening can be calculated using the product rule of probability, which states that the probability of two independent events occurring together is the product of their individual probabilities.\n",
    "\n",
    "The probability of the first card not matching is 39/40, since there are 39 cards that don't match out of a total of 40 cards. Similarly, the probability of the second card not matching is also 39/40, since one card has already been removed from the deck. The probability of the third card not matching is 38/40, since there are now only 38 cards remaining that don't match. Continuing in this way, the probability of not losing on the 40th card is 1/4, since there are four cards remaining in the deck that would cause you to lose.\n",
    "\n",
    "So, the probability of winning the game can be calculated as follows:\n",
    "\n",
    "(39/40) x (39/40) x (38/40) x ... x (2/4) x (1/4) ≈ 0.00039\n",
    "\n",
    "Therefore, the probability of winning the game is approximately 0.00039, or `0.039%`. In other words, you have a very low chance of winning this version of solitaire."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "842f667e",
   "metadata": {},
   "source": [
    "### Second chatGPT try:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2dfb2c78",
   "metadata": {},
   "source": [
    "The probability of winning this game can be found by calculating the probability of not losing on each turn, and then multiplying these probabilities together for all 40 turns.\n",
    "\n",
    "For the first card, there are 4 cards (out of 40) that would cause you to lose, so the probability of not losing on the first turn is 36/40.\n",
    "\n",
    "For the second card, there are again 4 cards (out of 39) that would cause you to lose, so the probability of not losing on the second turn is 35/39.\n",
    "\n",
    "Similarly, for the third card, the probability of not losing is 34/38, and so on.\n",
    "\n",
    "Multiplying all of these probabilities together gives:\n",
    "\n",
    "(36/40) * (35/39) * (34/38) * ... * (4/8) * (3/7) * (2/6) * (1/5)\n",
    "\n",
    "This simplifies to:\n",
    "\n",
    "(3/4) * (7/9) * (17/19) * ... * (1/2) * (3/7) * (1/3) * (1/5)\n",
    "\n",
    "Using a calculator, this product is approximately 0.128, or about 12.8%.\n",
    "\n",
    "Therefore, the probability of winning the game is approximately `87.2%`"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.0"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}