ipynb/RiddlerLottery.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<div style=\"text-align:right\">Peter Norvig<br>Nov 2019</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 with a lot in common are playing the [Riddler Lottery](https://fivethirtyeight.com/features/can-you-decode-the-riddler-lottery/), in which each must choose exactly five numbers from 1 to 70. After they all picked their numbers,\n",
    "- The first friend notices that no number was selected by two or more friends. \n",
    "- The second friend observes that all 25 selected numbers are composite (i.e., not prime). \n",
    "- The third friend points out that each selected number has at least two distinct prime factors. \n",
    "- The fourth friend excitedly remarks that the product of selected numbers on each ticket is exactly the same. \n",
    "- The fifth friend is left speechless. (You can tell why all these people are friends.)\n",
    "\n",
    "> 1. What is the product of the selected numbers on each ticket?\n",
    "2. How many _different_ ways could the friends have selected five numbers each so that all their statements are true?\n",
    "\n",
    "# Preliminary Analysis\n",
    "\n",
    "The fourth friend's statement was a bit unclear, but I take it to mean that each friend multiplied together their own five numbers, and they all got the same product.  To be concrete, here's an example of a solution in a simplified version of the problem where each friend only selects two tickets, not five:\n",
    "\n",
    "     Friend   Selection  Product  Factors\n",
    "     1        ( 6, 60)   360      [2, 3] + [2, 2, 3, 5]\n",
    "     2        (10, 36)   360      [2, 5] + [2, 2, 3, 3]\n",
    "     3        (12, 30)   360      [2, 2, 3] + [2, 3, 5]\n",
    "     4        (15, 24)   360      [3, 5] + [2, 2, 2, 3]\n",
    "     5        (18, 20)   360      [2, 3, 3] + [2, 2, 5]\n",
    "\n",
    "And here's a list of the key concepts:\n",
    "\n",
    "- **number**: An integer from 1 to 70, e.g. the int `42`.\n",
    "- **factors**: Every positive integer has a unique prime factorization, e.g. `factors(12) == [2, 2, 3]`:  two distinct primes factors. But `factors(8) == [2, 2, 2]`: one distinct prime factor.\n",
    "- **selection**: A collection of 5 numbers, e.g. the sorted tuple `(12, 15, 20, 28, 30)`.\n",
    "- **product**: The result of multiplying together the 5 numbers in a selection, e.g. the int `3024000`.\n",
    "- **candidate**: A candidate solution is a set of 5 selections e.g.  `{( 6, 60), (10, 36), (12, 30), (15, 24), (18, 20)}` in my simplified version where each selection has only two numbers.\n",
    "- **solution**: A solution is a candidate that satisifes each of the four friends' statements.\n",
    "\n",
    "Can I use brute force and enumerate all the possible candidates? \n",
    "\n",
    "There are (70 choose 5) × (65 choose 5) × (60 choose 5) × (55 choose 5) × (50 choose 5) / 5! or [about](https://www.wolframalpha.com/input/?i=%2870+choose+5%29+*+%2865+choose+5%29+*+%2860+choose+5%29+*+%2855+choose+5%29+*+%2850+choose+5%29+%2F+5%21) $10^{31}$ candidates, so no. We'll have to be more clever."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Valid Numbers\n",
    "\n",
    "There will be fewer candidates to consider if we can reduce the number of valid numbers to select from. The __third__ friend stated that the numbers all have at least two distinct prime factors. So let's find the numbers that have that property. (The numbers we are dealing with are small, so don't worry about the inefficiency of my function `factors`.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "from collections import Counter, defaultdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "41 {6, 10, 12, 14, 15, 18, 20, 21, 22, 24, 26, 28, 30, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 65, 66, 68, 69, 70}\n"
     ]
    }
   ],
   "source": [
    "def factors(n) -> list:\n",
    "    \"List of prime factors that multiply together to give n.\"\n",
    "    return ([]   if n == 1\n",
    "            else next([p] + factors(n // p) \n",
    "                      for p in range(2, n + 1) if n % p == 0))\n",
    "\n",
    "distinct = set\n",
    "\n",
    "numbers = {n for n in range(1, 71) if len(distinct(factors(n))) >= 2}\n",
    "\n",
    "print(len(numbers), numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great; we got it down from 70 to 41 possible numbers.\n",
    "\n",
    "Now the __fourth__ friend's statement says that each friend picks five numbers that have the same product. \n",
    "In my simplified version where the friends pick two numbers each, they all picked a selection with the product 360.  The prime factorization of 360 is `[2, 2, 2, 3, 3, 5]`; that means that all five friends had to find a different way of allocating these factors to their numbers. \n",
    "\n",
    "For each number that is selected by any friend, and for each prime factor $p$ of that number, it must be the case that there are at least four other valid numbers that also have $p$ as a factor; otherwise the product couldn't be the same for all the friends. So let's count in how many numbers each prime appears:"
   ]
  },
  {
   "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": [
    "prime_counts = Counter(p for n in numbers for p in distinct(factors(n)))\n",
    "\n",
    "prime_counts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This says that the prime factor 2 appears in 29 valid numbers and the prime factor 31 appears in only 1 valid number. Only factors that appear in at least 5 valid numbers can be part of a solution, so that's `{2, 3, 5, 7, 11}`.\n",
    "\n",
    "Let's update the set of valid numbers to contain only numbers $n$ such that every prime factor $p$ of $n$ appears in at least 5 valid numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "28 {6, 10, 12, 14, 15, 18, 20, 21, 22, 24, 28, 30, 33, 35, 36, 40, 42, 44, 45, 48, 50, 54, 55, 56, 60, 63, 66, 70}\n"
     ]
    }
   ],
   "source": [
    "numbers = {n for n in numbers if all(prime_counts[p] >= 5 for p in distinct(factors(n)))}\n",
    "\n",
    "print(len(numbers), numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are now only 28 valid numbers; a nice reduction from 70 to 41 to 28.\n",
    "\n",
    "# Valid Selections\n",
    "\n",
    "Now let's switch attention from individual numbers to selections of five numbers. There are (28 choose 5) = 98,280 possible selections; a manageable number. But that means there are (98,280 choose 5) = $\\approx 10^{23}$ candidate solutions; an unmanageable number.\n",
    "\n",
    "My first thought to reduce the number of candidates is to say that we should only consider candidates where all five selections in the candidate have the same product. To do that, we can group selections by product.\n",
    "\n",
    "We'll make `products` be a `dict` where each key is the product of the five numbers in a selection, and the corresponding value is a list of all the selections of five numbers with that product:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def multimap(items, key) -> dict:\n",
    "    \"A dict of {key(item): [item, ...]}\"\n",
    "    result = defaultdict(list)\n",
    "    for x in items:\n",
    "        result[key(x)].append(x)\n",
    "    return result\n",
    "\n",
    "def product(nums) -> int: \n",
    "    \"Multiply nums together (similar to sum(nums)).\"\n",
    "    result = 1\n",
    "    for num in nums:\n",
    "        result *= num\n",
    "    return result\n",
    "\n",
    "products = multimap(combinations(numbers, 5), key=product)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is an entry in the `products` dict:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(6, 10, 12, 14, 30),\n",
       " (6, 10, 12, 15, 28),\n",
       " (6, 10, 12, 20, 21),\n",
       " (6, 10, 14, 15, 24),\n",
       " (6, 10, 14, 18, 20),\n",
       " (6, 12, 14, 15, 20)]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "products[6 * 12 * 14 * 15 * 20]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This says there are 6 selections whose product is 6 * 12 * 14 * 15 * 20 = 302,400; if there were a way to choose 5 of these 6 with all distinct numbers, that would be a solution. Sadly, there is no such way. Since every one of the selections contains a 6; we can't even choose two disjoint selections, let alone five.\n",
    "\n",
    "Let's see how many different products there are, and how many have at least five selections:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4042, 2407)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(products), len([n for n in products if len(products[n]) >= 5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It seems reasonable to go through all the products and see if one of the 29,506 with 5 or more selections can come up with 5 disjoint selections. The function `k_disjoint(k, selections)` finds all ways to choose `k` different elements of `selections` such that there is no shared number among any selection. The function keeps track of a `partial_solution`&mdash;a set of previously-found selections&mdash;as it recursively searches for a complete solution. Any new selection must be disjoint from all the selections in `partial_solution`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def k_disjoint(k, selections, start=0, partial_solution=set()) -> list:\n",
    "    \"All ways of picking k elements of selections that have all disjoint members.\"\n",
    "    if len(partial_solution) == k:\n",
    "        yield partial_solution\n",
    "    elif len(partial_solution) + (len(selections) - start) >= k:\n",
    "        for i in range(start, len(selections)):\n",
    "            selection = selections[i]\n",
    "            if all(is_disjoint(selection, s) for s in partial_solution):\n",
    "                yield from k_disjoint(k, selections, i + 1, partial_solution | {selection})\n",
    "    \n",
    "def is_disjoint(A, B) -> bool: return not any(a in B for a in A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's an example of how `k_disjoint` works. Out of the following six selections (which in this simplified example have only two numbers each, not five), there are two ways to pick five selections without having a duplicate number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{(6, 60), (10, 36), (12, 30), (15, 24), (18, 20)},\n",
       " {(6, 60), (10, 35), (12, 30), (15, 24), (18, 20)}]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "selections = [(6, 60), (10, 36), (12, 30), (15, 24), (18, 20), (10, 35)]\n",
    "list(k_disjoint(5, selections))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But for the six selections whose product is 302,400, there are no disjoint solutions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "selections = [(6, 10, 12, 14, 30),\n",
    " (6, 10, 12, 15, 28),\n",
    " (6, 10, 12, 20, 21),\n",
    " (6, 10, 14, 15, 24),\n",
    " (6, 10, 14, 18, 20),\n",
    " (6, 12, 14, 15, 20)]\n",
    "list(k_disjoint(5, selections))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we're ready to solve the problem.\n",
    "\n",
    "# 1. What is the product of the selected numbers on each ticket?\n",
    "\n",
    "That is, find the  number `N` in `products` that can form 5 disjoint selections."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The product is 19,958,400; factors are [2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 7, 11]\n"
     ]
    }
   ],
   "source": [
    "N = next(n for n in products if any(k_disjoint(5, products[n])))\n",
    "\n",
    "print(f'The product is {N:,d}; factors are {factors(N)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. How many different ways could the friends have selected five numbers?\n",
    "\n",
    "I'll compute all of the results for `k_disjoint`, and see how many there are:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "There are 12,781 different ways.\n"
     ]
    }
   ],
   "source": [
    "different_ways = list(k_disjoint(5, products[N]))\n",
    "print(f'There are {len(different_ways):,d} different ways.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's too many to look at all of them, but I can peek at every thousandth one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "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)},\n",
       " {(6, 18, 55, 56, 60),\n",
       "  (10, 21, 30, 48, 66),\n",
       "  (12, 22, 28, 50, 54),\n",
       "  (14, 20, 36, 44, 45),\n",
       "  (15, 24, 33, 40, 42)},\n",
       " {(6, 20, 54, 55, 56),\n",
       "  (10, 21, 36, 44, 60),\n",
       "  (12, 28, 33, 40, 45),\n",
       "  (14, 18, 24, 50, 66),\n",
       "  (15, 22, 30, 42, 48)},\n",
       " {(6, 21, 48, 50, 66),\n",
       "  (10, 24, 33, 45, 56),\n",
       "  (12, 18, 28, 55, 60),\n",
       "  (14, 20, 30, 44, 54),\n",
       "  (15, 22, 36, 40, 42)},\n",
       " {(6, 22, 50, 54, 56),\n",
       "  (10, 14, 36, 60, 66),\n",
       "  (12, 18, 40, 42, 55),\n",
       "  (15, 21, 30, 44, 48),\n",
       "  (20, 24, 28, 33, 45)},\n",
       " {(6, 24, 42, 50, 66),\n",
       "  (10, 18, 33, 56, 60),\n",
       "  (12, 28, 30, 36, 55),\n",
       "  (14, 15, 40, 44, 54),\n",
       "  (20, 21, 22, 45, 48)},\n",
       " {(6, 28, 30, 60, 66),\n",
       "  (10, 15, 44, 54, 56),\n",
       "  (12, 22, 36, 42, 50),\n",
       "  (14, 24, 33, 40, 45),\n",
       "  (18, 20, 21, 48, 55)},\n",
       " {(6, 28, 40, 45, 66),\n",
       "  (10, 30, 33, 42, 48),\n",
       "  (12, 21, 24, 55, 60),\n",
       "  (14, 18, 36, 44, 50),\n",
       "  (15, 20, 22, 54, 56)},\n",
       " {(6, 28, 44, 50, 54),\n",
       "  (10, 21, 33, 48, 60),\n",
       "  (12, 14, 40, 45, 66),\n",
       "  (15, 22, 30, 36, 56),\n",
       "  (18, 20, 24, 42, 55)},\n",
       " {(6, 30, 36, 55, 56),\n",
       "  (10, 15, 42, 48, 66),\n",
       "  (12, 28, 33, 40, 45),\n",
       "  (14, 20, 22, 54, 60),\n",
       "  (18, 21, 24, 44, 50)},\n",
       " {(6, 30, 44, 45, 56),\n",
       "  (10, 15, 42, 48, 66),\n",
       "  (12, 14, 40, 54, 55),\n",
       "  (18, 24, 28, 33, 50),\n",
       "  (20, 21, 22, 36, 60)},\n",
       " {(6, 33, 40, 45, 56),\n",
       "  (10, 12, 42, 60, 66),\n",
       "  (14, 22, 24, 50, 54),\n",
       "  (15, 28, 30, 36, 44),\n",
       "  (18, 20, 21, 48, 55)},\n",
       " {(6, 36, 40, 42, 55),\n",
       "  (10, 20, 33, 54, 56),\n",
       "  (12, 18, 28, 50, 66),\n",
       "  (14, 15, 44, 45, 48),\n",
       "  (21, 22, 24, 30, 60)}]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "different_ways[::1000]"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}