Untitled.ipynb

{
 "cells": [
  {
   "metadata": {
    "trusted": true,
    "collapsed": true
   },
   "cell_type": "code",
   "source": "from copy import copy\nfrom pprint import pprint",
   "execution_count": 105,
   "outputs": []
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "# Riddle of Three Logicians\n\nSee http://fivethirtyeight.com/features/can-you-solve-the-impossible-puzzle/\n\n**TL;DR** *Question 1*: `2` and `8`. *Question 2*: No.\n\nWe will reproduce the thought process of the skilled logicians using the following Python code.\n\nFirst let us create a set of all possible combinations of 2 numbers between 1 and 10"
  },
  {
   "metadata": {
    "trusted": true,
    "collapsed": false
   },
   "cell_type": "code",
   "source": "combs = {(a, b) for a in range(1, 10) for b in range(a, 10)}\nlen(combs)  # total of 45",
   "execution_count": 135,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "45"
     },
     "metadata": {},
     "execution_count": 135
    }
   ]
  },
  {
   "metadata": {
    "trusted": true,
    "collapsed": false
   },
   "cell_type": "code",
   "source": "# associative array which map a turn number to an arithmetic function \n# (multiplication for Pete and addition for Susan) and the respective names\n\naggrs = {0: lambda a, b: a * b,  # first step\n        1: lambda a, b: a + b  # second step\n        }\nnames = {0: 'Pete',\n        1: 'Susan'}",
   "execution_count": 108,
   "outputs": []
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## Basic Concept\n\nBefore a logician gives an answer they check if the number on their sheet is uniquelly defined by two number between 1 and 9 and their respective mathematical operation (multiplication for Pete, addition for Susan). I.e. if Susan has a 17 on her sheet, she know that the numbers Barack though of have to be 8 and 9, since no other combination is possible.\n\nThe following function takes a set of combinations and a function aggr (i.e. `*` or `+`) and returns only the combinations which produce a unique answer with the function `aggr`."
  },
  {
   "metadata": {
    "trusted": true,
    "collapsed": true
   },
   "cell_type": "code",
   "source": "def do_step(combs, aggr):\n    groups = {}\n    for a, b in combs:\n        # group the combinations by the result of aggr(*combs)\n        groups.setdefault(aggr(a, b), []).append((a, b))\n    # return a set of combinations which produce a unique result\n    return {comb for combs in groups.values() for comb in combs if len(combs) == 1}",
   "execution_count": 130,
   "outputs": []
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## Solution of the Riddle\n\nWe simulate the search for the solution by generating the thought process of the logicians under the consideration of the previous answers. Since the initial combinations are known, both sides can eliminate the same posibilities when a negative answer is given."
  },
  {
   "metadata": {
    "trusted": true,
    "collapsed": false
   },
   "cell_type": "code",
   "source": "def sequence(combs):\n    # start with the complete set of combinations\n    possible_combs = copy(combs)\n    for step in range(0, 12):  # even steps are Pete's, odd are Susan's\n        aggr = aggrs[step % 2]  # the aggregation function, i.e. * or +\n        eliminated_combs = do_step(possible_combs, aggr)  # generate a list of combination which produce a unique answer\n        # print the thought process\n        print(\"%s's answer number %d:\" % (names[step % 2], step // 2 + 1))\n        print(\"Give answer 'yes' if the number on the paper is one of the following:\")\n        for a, b in sorted(list(eliminated_combs), key=lambda _: aggr(_[0], _[1])):\n            print(\"\\tif it's %d: answer is %d and %d\" % (aggr(a, b), a, b))\n        print(\"%d combinations were excluded in this step\" % len(eliminated_combs))\n        # exclude the combinations with a unique answer from the next iteration\n        possible_combs -= eliminated_combs\n        print(\"The logician has one of the following numbers on their sheet: %s\" % \", \".join(\n                map(str, sorted(list({aggr(a, b) for a, b in possible_combs})))))  \n        print(\"Following combinations are still possible (total of %d): %s\" % (len(possible_combs), \", \".join(map(str, possible_combs))))\n        print('-' * 80)\n        print('')",
   "execution_count": 160,
   "outputs": []
  },
  {
   "metadata": {
    "trusted": true,
    "collapsed": false,
    "scrolled": false
   },
   "cell_type": "code",
   "source": "sequence(combs)",
   "execution_count": 161,
   "outputs": [
    {
     "output_type": "stream",
     "text": "Pete's answer number 1:\nGive answer 'yes' if the number on the paper is one of the following:\n\tif it's 1: answer is 1 and 1\n\tif it's 2: answer is 1 and 2\n\tif it's 3: answer is 1 and 3\n\tif it's 5: answer is 1 and 5\n\tif it's 7: answer is 1 and 7\n\tif it's 10: answer is 2 and 5\n\tif it's 14: answer is 2 and 7\n\tif it's 15: answer is 3 and 5\n\tif it's 20: answer is 4 and 5\n\tif it's 21: answer is 3 and 7\n\tif it's 25: answer is 5 and 5\n\tif it's 27: answer is 3 and 9\n\tif it's 28: answer is 4 and 7\n\tif it's 30: answer is 5 and 6\n\tif it's 32: answer is 4 and 8\n\tif it's 35: answer is 5 and 7\n\tif it's 40: answer is 5 and 8\n\tif it's 42: answer is 6 and 7\n\tif it's 45: answer is 5 and 9\n\tif it's 48: answer is 6 and 8\n\tif it's 49: answer is 7 and 7\n\tif it's 54: answer is 6 and 9\n\tif it's 56: answer is 7 and 8\n\tif it's 63: answer is 7 and 9\n\tif it's 64: answer is 8 and 8\n\tif it's 72: answer is 8 and 9\n\tif it's 81: answer is 9 and 9\n27 combinations were excluded in this step\nThe logician has one of the following numbers on their sheet: 4, 6, 8, 9, 12, 16, 18, 24, 36\nFollowing combinations are still possible (total of 18): (6, 6), (2, 8), (1, 6), (4, 9), (3, 3), (2, 9), (4, 4), (3, 6), (2, 2), (2, 6), (1, 4), (2, 3), (1, 9), (4, 6), (3, 8), (1, 8), (3, 4), (2, 4)\n--------------------------------------------------------------------------------\n\nSusan's answer number 1:\nGive answer 'yes' if the number on the paper is one of the following:\n\tif it's 4: answer is 2 and 2\n\tif it's 12: answer is 6 and 6\n\tif it's 13: answer is 4 and 9\n3 combinations were excluded in this step\nThe logician has one of the following numbers on their sheet: 5, 6, 7, 8, 9, 10, 11\nFollowing combinations are still possible (total of 15): (2, 8), (1, 6), (3, 3), (2, 9), (4, 4), (3, 6), (2, 6), (1, 4), (2, 3), (1, 9), (4, 6), (3, 8), (1, 8), (3, 4), (2, 4)\n--------------------------------------------------------------------------------\n\nPete's answer number 2:\nGive answer 'yes' if the number on the paper is one of the following:\n\tif it's 4: answer is 1 and 4\n1 combinations were excluded in this step\nThe logician has one of the following numbers on their sheet: 6, 8, 9, 12, 16, 18, 24\nFollowing combinations are still possible (total of 14): (2, 8), (1, 6), (3, 3), (2, 9), (4, 4), (3, 6), (2, 6), (2, 3), (1, 9), (4, 6), (3, 8), (1, 8), (3, 4), (2, 4)\n--------------------------------------------------------------------------------\n\nSusan's answer number 2:\nGive answer 'yes' if the number on the paper is one of the following:\n\tif it's 5: answer is 2 and 3\n1 combinations were excluded in this step\nThe logician has one of the following numbers on their sheet: 6, 7, 8, 9, 10, 11\nFollowing combinations are still possible (total of 13): (2, 8), (1, 6), (3, 3), (2, 9), (4, 4), (3, 6), (2, 6), (1, 9), (4, 6), (3, 8), (1, 8), (3, 4), (2, 4)\n--------------------------------------------------------------------------------\n\nPete's answer number 3:\nGive answer 'yes' if the number on the paper is one of the following:\n\tif it's 6: answer is 1 and 6\n1 combinations were excluded in this step\nThe logician has one of the following numbers on their sheet: 8, 9, 12, 16, 18, 24\nFollowing combinations are still possible (total of 12): (2, 8), (3, 3), (2, 9), (4, 4), (3, 6), (2, 6), (1, 9), (4, 6), (3, 8), (1, 8), (3, 4), (2, 4)\n--------------------------------------------------------------------------------\n\nSusan's answer number 3:\nGive answer 'yes' if the number on the paper is one of the following:\n\tif it's 7: answer is 3 and 4\n1 combinations were excluded in this step\nThe logician has one of the following numbers on their sheet: 6, 8, 9, 10, 11\nFollowing combinations are still possible (total of 11): (2, 8), (3, 3), (2, 9), (4, 4), (3, 6), (2, 6), (1, 9), (4, 6), (3, 8), (1, 8), (2, 4)\n--------------------------------------------------------------------------------\n\nPete's answer number 4:\nGive answer 'yes' if the number on the paper is one of the following:\n\tif it's 12: answer is 2 and 6\n1 combinations were excluded in this step\nThe logician has one of the following numbers on their sheet: 8, 9, 16, 18, 24\nFollowing combinations are still possible (total of 10): (2, 8), (3, 3), (2, 9), (4, 4), (3, 6), (1, 9), (4, 6), (3, 8), (1, 8), (2, 4)\n--------------------------------------------------------------------------------\n\nSusan's answer number 4:\nGive answer 'yes' if the number on the paper is one of the following:\n\tif it's 8: answer is 4 and 4\n1 combinations were excluded in this step\nThe logician has one of the following numbers on their sheet: 6, 9, 10, 11\nFollowing combinations are still possible (total of 9): (2, 8), (3, 3), (2, 9), (3, 6), (1, 9), (4, 6), (3, 8), (1, 8), (2, 4)\n--------------------------------------------------------------------------------\n\nPete's answer number 5:\nGive answer 'yes' if the number on the paper is one of the following:\n\tif it's 16: answer is 2 and 8\n1 combinations were excluded in this step\nThe logician has one of the following numbers on their sheet: 8, 9, 18, 24\nFollowing combinations are still possible (total of 8): (3, 3), (2, 9), (3, 6), (1, 9), (4, 6), (3, 8), (1, 8), (2, 4)\n--------------------------------------------------------------------------------\n\nSusan's answer number 5:\nGive answer 'yes' if the number on the paper is one of the following:\n0 combinations were excluded in this step\nThe logician has one of the following numbers on their sheet: 6, 9, 10, 11\nFollowing combinations are still possible (total of 8): (3, 3), (2, 9), (3, 6), (1, 9), (4, 6), (3, 8), (1, 8), (2, 4)\n--------------------------------------------------------------------------------\n\nPete's answer number 6:\nGive answer 'yes' if the number on the paper is one of the following:\n0 combinations were excluded in this step\nThe logician has one of the following numbers on their sheet: 8, 9, 18, 24\nFollowing combinations are still possible (total of 8): (3, 3), (2, 9), (3, 6), (1, 9), (4, 6), (3, 8), (1, 8), (2, 4)\n--------------------------------------------------------------------------------\n\nSusan's answer number 6:\nGive answer 'yes' if the number on the paper is one of the following:\n0 combinations were excluded in this step\nThe logician has one of the following numbers on their sheet: 6, 9, 10, 11\nFollowing combinations are still possible (total of 8): (3, 3), (2, 9), (3, 6), (1, 9), (4, 6), (3, 8), (1, 8), (2, 4)\n--------------------------------------------------------------------------------\n\n",
     "name": "stdout"
    }
   ]
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "#### Answer to subquestion 1\n\nIf Pete gives a positive answer 5th time he is asked then he has a **16** on his sheet, i.e. the numbers Barack thought of are **2** and **8**.\n\n#### Answer to the subquestion 2\n\nIf Pete's answer to the 5th question, then Susan can't eliminate any additional combinations, and neither can Steve in the following turn.\n\nThis means that if the numbers Barack thought of are ones of the following: `(3, 3), (2, 9), (3, 6), (1, 9), (4, 6), (3, 8), (1, 8), (2, 4)` then Susan and Pete can not find them out using the described process."
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "mimetype": "text/x-python",
   "version": "3.4.4",
   "file_extension": ".py",
   "pygments_lexer": "ipython3",
   "name": "python",
   "nbconvert_exporter": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   }
  },
  "gist_id": "abb9b65631a1c94a275b59c5503905d7"
 },
 "nbformat": 4,
 "nbformat_minor": 0
}