card_riddle.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from scipy.misc import comb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Thresholds for optimal strategy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def proba_highest(C, M):\n",
    "    # C is the number of cards that have been turned around\n",
    "    # M is the maximum value seen so far\n",
    "        \n",
    "    # probability of observing only lower cards (all remaining H-C cards happen to be among the M-C lower cards)\n",
    "    return comb(M-C,H-C) / comb(D-C,H-C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: 85, 2: 80, 3: 72, 4: 52, 5: 5}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = 100  # deck\n",
    "H = 5  # hand\n",
    "\n",
    "thresholds = dict()\n",
    "for C in range(1,H+1):\n",
    "    thresholds[C] = np.where(proba_highest(C,np.arange(1,D+1))>=.5)[0][0]+1\n",
    "thresholds_100_5 = thresholds\n",
    "thresholds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: 842, 2: 795, 3: 709, 4: 502, 5: 5}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = 1000  # deck\n",
    "H = 5  # hand\n",
    "\n",
    "thresholds = dict()\n",
    "for C in range(1,H+1):\n",
    "    thresholds[C] = np.where(proba_highest(C,np.arange(1,D+1))>=.5)[0][0]+1\n",
    "thresholds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: 93, 2: 93, 3: 92, 4: 90, 5: 88, 6: 86, 7: 82, 8: 74, 9: 55, 10: 10}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = 100  # deck\n",
    "H = 10  # hand\n",
    "\n",
    "thresholds = dict()\n",
    "for C in range(1,H+1):\n",
    "    thresholds[C] = np.where(proba_highest(C,np.arange(1,D+1))>=.5)[0][0]+1\n",
    "thresholds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Probability of winning"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def proba_of_winning(C, M):\n",
    "    # C is the number of cards that have been turned around\n",
    "    # M is the maximum value seen so far\n",
    "    \n",
    "    # shortcut if computed before\n",
    "    if (C,M) in proba_of_winning_lookup:\n",
    "        return proba_of_winning_lookup[(C,M)]\n",
    "    \n",
    "    total = 0\n",
    "    effective_threshold = max(M+1,thresholds[C])  # has to be larger than the current max and above threshold        \n",
    "    total += 1/(D-C+1) * proba_highest(C,np.arange(effective_threshold,D+1)).sum()  # end of game\n",
    "    if C < H:\n",
    "        # game continues\n",
    "        for X in range(M+1,effective_threshold):\n",
    "            total += 1/(D-C+1) * proba_of_winning(C+1, X)  # current max was improved\n",
    "        if M != 0:\n",
    "            total += (M-C+1)/(D-C+1) * proba_of_winning(C+1, M)  # current max was not improved\n",
    "            \n",
    "    proba_of_winning_lookup[(C,M)] = total\n",
    "    return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.64498053063774707"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = 100  # deck\n",
    "H = 5  # hand\n",
    "\n",
    "thresholds = dict()\n",
    "for C in range(1,H+1):\n",
    "    thresholds[C] = np.where(proba_highest(C,np.arange(1,D+1))>=.5)[0][0]+1\n",
    "        \n",
    "proba_of_winning_lookup = dict()\n",
    "proba_of_winning(1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.63873069354493894"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = 1000  # deck\n",
    "H = 5  # hand\n",
    "\n",
    "thresholds = dict()\n",
    "for C in range(1,H+1):\n",
    "    thresholds[C] = np.where(proba_highest(C,np.arange(1,D+1))>=.5)[0][0]+1\n",
    "    \n",
    "proba_of_winning_lookup = dict()\n",
    "proba_of_winning(1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.62034651955807552"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D = 100  # deck\n",
    "H = 10  # hand\n",
    "\n",
    "thresholds = dict()\n",
    "for C in range(1,H+1):\n",
    "    thresholds[C] = np.where(proba_highest(C,np.arange(1,D+1))>=.5)[0][0]+1\n",
    "    \n",
    "proba_of_winning_lookup = dict()\n",
    "proba_of_winning(1,0)"
   ]
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}