ipynb/RiddlerLottery.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align:right\"><i>Peter Norvig<br>Nov 2019<br>revised May 2021</i></div>\n",
    "\n",
    "# Riddler Lottery\n",
    "\n",
    "The 538 Riddler [poses](https://fivethirtyeight.com/features/can-you-decode-the-riddler-lottery/) this problem:\n",
    "\n",
    "> Five friends are playing the [Riddler Lottery](https://fivethirtyeight.com/features/can-you-decode-the-riddler-lottery/), in which each player selects exactly five integers from 1 to 70. After they all picked their numbers,\n",
    "1. The first player states that no number was selected by two or more players. \n",
    "2. The second player observes that all the selected numbers are composite (i.e., not prime). \n",
    "3. The third player points out that each selected number has at least two distinct prime factors. \n",
    "4. The fourth player notes that each player's 5 numbers multiply to the same product. \n",
    "5. The fifth player is left speechless. \n",
    ">\n",
    "> That leads to two questions:\n",
    "> - What is the unique product, $P$, that each player's 5 numbers multiply together to?\n",
    "> - In how many different ways could the selections be made so that the statements above are true?\n",
    "\n",
    "#  Analysis\n",
    "\n",
    "As an example, consider a version of the problem where each player selects 2 numbers, not 5. Here is one solution:\n",
    "\n",
    "      \n",
    "|Player |Selection| Product |Prime Factors|\n",
    "|-|-|-|-|\n",
    "|1  |   6, 60 | 360  |   {2, 3}, {2, 3, 5}\n",
    "|2  |  10, 36 | 360  |   {2, 5}, {2, 3}\n",
    "|3  |  12, 30 | 360  |   {2, 3}, {2, 3, 5}\n",
    "|4  |  15, 24 | 360  |   {3, 5}, {2, 3}\n",
    "|5  |  18, 20 | 360  |   {2, 3}, {2, 5}\n",
    "\n",
    "\n",
    "\n",
    "The key concepts:\n",
    "\n",
    "- **Numbers**: The integers from 1 to 70. \n",
    "- **Selection**: A sorted tuple of numbers, e.g. `(6, 60)` for 2 numbers, or `(12, 15, 20, 28, 30)` for 5.\n",
    "- **Candidate**: A set of 5 selections e.g. `{(6, 60), (10, 36), (12, 30), (15, 24), (18, 21)}`.\n",
    "- **Solution**: A candidate that satisfies statements 1–4.\n",
    "- **Distinct prime factors**: `factors(20) == {2, 5}` and  `factors(9) == {3}`, so 20 is valid but not 9.\n",
    "- **Product**: the result of multiplying numbers together, e.g. `prod((6, 60)) == 360`.\n",
    "\n",
    "An implementation of the key concepts:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import *\n",
    "\n",
    "numbers   = range(1, 71)\n",
    "Selection = Tuple[int, ...] # 5 ints in the full puzzle\n",
    "Candidate = Set[Selection]\n",
    "Solution  = Set[Selection]\n",
    "\n",
    "def factors(n) -> Set[int]:\n",
    "    \"\"\"The set of distinct prime factors of n.\"\"\"\n",
    "    if n == 1:\n",
    "        return set()\n",
    "    else:\n",
    "        p = next(i for i in range(2, n + 1) if n % i == 0)\n",
    "        return {p, *factors(n // p)}\n",
    "    \n",
    "def prod(numbers: Iterable[int]) -> int:\n",
    "    \"\"\"The product of a collection of numbers.\"\"\"\n",
    "    result = 1\n",
    "    for n in numbers:\n",
    "        result *= n\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Brute force solution?\n",
    "\n",
    "Could we generate every possible candidate, and test each one? There are (70 choose 5)<sup>5</sup> or [about](https://www.google.com/search?q=%2870+choose+5%29^5) $10^{35}$ candidate solutions, so: **NO**.  \n",
    "\n",
    "We'll have to be more clever. I have three ideas; I will consider only:\n",
    "\n",
    "- Numbers with at least 2 prime factors.\n",
    "- Factors with at least 5 valid numbers.\n",
    "- Sets of 25 numbers whose product is a fifth power."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Numbers with at least 2 prime factors\n",
    "\n",
    "Every valid numbers must have at least two distinct prime factors (by statement 3):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "41"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numbers = [n for n in numbers if len(factors(n)) >= 2]\n",
    "\n",
    "len(numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Good! We got it down from 70 to 41 valid numbers.\n",
    "\n",
    "# Factors with at least 5 valid numbers\n",
    "\n",
    "All five players make a selection with the same product (by statement 4). Therefore, if one player selects a number that has the factor $p$, then that player's product will be divisible by $p$, and therefore every player must select some number that has the factor $p$, otherwise their product would be different.\n",
    "\n",
    "For example, the valid numbers with 11 as a factor are {22, 33, 44, 55, 66}, so if one player selects one of those numbers, then the other players must select the others.\n",
    "\n",
    "The valid numbers with 13 as a factor are {26, 39, 52, 65}, so no player can select any of those numbers, because there aren't enough of them for all five players.\n",
    "\n",
    "So let's count  how many valid numbers each prime factor appears in:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({2: 29,\n",
       "         3: 20,\n",
       "         5: 12,\n",
       "         7: 8,\n",
       "         11: 5,\n",
       "         13: 4,\n",
       "         17: 3,\n",
       "         19: 2,\n",
       "         23: 2,\n",
       "         29: 1,\n",
       "         31: 1})"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Counter(p for n in numbers for p in factors(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Only the prime factors `{2, 3, 5, 7, 11}` have a count of at least 5. Let's update the set of valid numbers to contain only numbers made from valid factors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "28"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "valid_factors = {2, 3, 5, 7, 11}\n",
    "\n",
    "numbers = [n for n in numbers if factors(n).issubset(valid_factors)]\n",
    "\n",
    "len(numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great! Now we're down to 28 numbers! \n",
    "\n",
    "# Sets of 25 numbers whose product is a fifth power\n",
    "\n",
    "The five players will together select 25 of these 28 valid numbers, and since there are only (28 choose 25) = 3,276 combinations of 25 numbers, we can quickly check to see which ones might lead to  solutions, according to this reasoning:\n",
    "- Every player's selection of 5 numbers has the same product, which we are calling $P$.\n",
    "- Therefore the product of all 25 numbers in a solution must be $P^5$ (although we don't yet know what $P$ is).\n",
    "- A set of 25 numbers whose product is not a perfect fifth power **cannot** lead to any solutions.\n",
    "- A set of 25 numbers whose product is a perfect fifth power **might** lead to solution(s).\n",
    "\n",
    "We can check which combinations of 25 numbers multiply to a fifth power:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "def is_fifth_power(i: int) -> bool: return i == round(i ** (1/5)) ** 5\n",
    "\n",
    "result = [c for c in combinations(numbers, 25) if is_fifth_power(prod(c))]\n",
    "\n",
    "len(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There's only one combination of 25 numbers that works! \n",
    "\n",
    "That's good news; we can use the `result` to update `numbers` and compute  $P$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers = result[0]\n",
    "P = round(prod(numbers) ** (1/5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Answer to the first question"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19958400"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**19,958,400** is \"the unique product $P$ that each player's 5 numbers multiply to.\" \n",
    "\n",
    "At this point we know the 25 numbers  that will form any solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 10 12 14 15 18 20 21 22 24 28 30 33 36 40 42 44 45 48 50 54 55 56 60 66\n"
     ]
    }
   ],
   "source": [
    "print(*numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, we haven't found any solutions yet and we don't know how many solutions there are."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Finding solutions\n",
    "\n",
    "`solutions(numbers, P, r)` will search through combinations of `numbers` to generate all solutions such that every selection in the solution consists of `r` numbers with product $P$. \n",
    "\n",
    "`solutions` yields the empty solution if there are no numbers remaining to choose from. Otherwise it considers each way to combine a `first` selection with a set of `rest` selections, where the `first` is any `r` numbers and the `rest` is any set of selections formed from the numbers that \n",
    "were not used in `first`, and are lexicographically greater than `first` (so that we don't generate multiple permutations of the same solution). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solutions(numbers, P, r=5) -> Iterator[Solution]:\n",
    "    \"\"\"Yield solutions that are selections of `r` `numbers` with product `P`.\"\"\"\n",
    "    if not numbers:\n",
    "        yield set()\n",
    "    else:\n",
    "        yield from ({first, *rest}\n",
    "            for first in combinations(numbers, r)\n",
    "            if prod(first) == P\n",
    "            for rest in solutions([n for n in numbers \n",
    "                                   if n > first[0] and n not in first], P, r))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can very quickly find a solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.12 ms, sys: 2 µs, total: 2.12 ms\n",
      "Wall time: 2.12 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{(6, 15, 56, 60, 66),\n",
       " (10, 14, 48, 54, 55),\n",
       " (12, 18, 42, 44, 50),\n",
       " (20, 21, 33, 36, 40),\n",
       " (22, 24, 28, 30, 45)}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time next(solutions(numbers, P))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But it takes longer (about 6 seconds) to find all the solutions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 6.36 s, sys: 13 ms, total: 6.37 s\n",
      "Wall time: 6.37 s\n"
     ]
    }
   ],
   "source": [
    "%time all_solutions = list(solutions(numbers, P))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Answer to the second question"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12781"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(all_solutions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**12,781** is \"how many different ways could the selections be made so that the statements are true.\" \n",
    "\n",
    "(There is some ambiguity about what \"different\" means: 12,781 is the answer if you think of a set of players each choosing a set of numbers. If the ordering of the players matters, multiply by $5! = 120$, and if the ordering of the numbers in each selection matters, multiply by $5!^5$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# To do\n",
    "\n",
    "- You could explore solutions with different numbers of players (default 5), selected numbers per player (default 5), range of valid numbers (default 1 to 70), and minimum number of distinct factors for selected numbers (default 2).\n",
    "\n",
    "\n",
    "- You could answer the trivia question \"why didn't I just import [`numpy.prod`](https://numpy.org/doc/stable/reference/generated/numpy.prod.html)?\"\n",
    "\n",
    "\n",
    "- If 6 seconds is too long to wait, you could speed up `solutions` by changing from the generate-and-test approach of looking at all `combinations(numbers, r)` and then checking to see if the product is `P`, to an incremental approach that only considers partial results that could lead to a product `P`.\n",
    "\n",
    "\n",
    "- You could implement a completely different approach to solving the problem (actually the one I thought of first): \n",
    "  1. Get the valid numbers down to 28.\n",
    "  2. Consider all (28 choose 5) = 98,280 possible selections of 5 numbers.\n",
    "  3. Group selections by their products, e.g., a dict: `{19958400: [(6, 15, 56, 60, 66), ...]}`.\n",
    "  4. For each product in the dict that has at least 5 selections in its list:\n",
    "    - Find all combinations of 5 selections that consist of  distinct numbers. \n",
    "    \n",
    "\n",
    "- You could add more unit tests to the following meager test suite:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_solution(candidate) -> bool:\n",
    "    \"\"\"Is this a valid solution?\"\"\"\n",
    "    numbers  = [n for selection in candidate for n in selection]\n",
    "    products = {prod(selection) for selection in candidate}\n",
    "    return (len(numbers) == len(set(numbers))               # Statement 1\n",
    "            and all(len(factors(n)) >= 2 for n in numbers)  # Statement 3\n",
    "            and len(products) == 1)                         # Statement 4\n",
    "\n",
    "assert factors(9) == {3}\n",
    "assert factors(10) == {2, 5}\n",
    "assert factors(42) == {2, 3, 7}\n",
    "assert factors(41) == {41}\n",
    "assert factors(1) == set()\n",
    "assert factors(168000) == {2, 3, 5, 7}\n",
    "\n",
    "assert prod([2, 3, 7]) == 42\n",
    "assert prod([41]) == 41\n",
    "assert prod([]) == 1\n",
    "assert prod([2, 3, 2, 5, 2, 5, 2, 5, 2, 7, 2]) == 168000\n",
    "\n",
    "assert     is_fifth_power(100000)\n",
    "assert     is_fifth_power(1234567890 ** 5)\n",
    "assert not is_fifth_power(99999)\n",
    "assert not is_fifth_power(1234567890 ** 5 + 1)\n",
    "\n",
    "assert P == 19958400\n",
    "assert numbers == (6, 10, 12, 14, 15, 18, 20, 21, 22, 24, 28, 30, 33, \n",
    "                   36, 40, 42, 44, 45, 48, 50, 54, 55, 56, 60, 66)\n",
    "assert len(all_solutions) == 12781\n",
    "assert all(is_solution(s) for s in all_solutions)\n",
    "\n",
    "assert     is_solution({(6, 60), (10, 36), (12, 30), (15, 24), (18, 20)})\n",
    "assert not is_solution({(6, 60), (10, 60), (12, 30), (15, 24), (18, 20)}) #1\n",
    "assert not is_solution({(9, 40), (10, 36), (12, 30), (15, 24), (18, 20)}) #3\n",
    "assert not is_solution({(7, 60), (10, 36), (12, 30), (15, 24), (18, 20)}) #4"
   ]
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}