{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Ce billet a été écrit à l'aide d'un notebook Jupyter. Son contenu est sous licence BSD. Une vue statique de ce notebook peut être consultée et téléchargée ici : [20170731_batonnetsFortBoyard.ipynb](http://nbviewer.ipython.org/urls/raw.github.com/flothesof/posts/master/20170731_batonnetsFortBoyard.ipynb).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans ce billet, nous allons nous intéresser au jeu desbâtonnets de Fort Boyard.\n",
    "\n",
    "Voici l'énoncé du jeu (adapté d'après <http://www.fan-fortboyard.fr/pages/emission/conseil/batonnets.html>) :\n",
    "\n",
    "> Dans ce duel, le candidat et le Maître se retrouvent à jouer avec un alignement de dix-huit bâtonnets (20 jusqu’en 2008).\n",
    "\n",
    "> Chacun leur tour, ils peuvent en retirer soit un, soit deux, soit trois. Celui qui retirera le dernier bâtonnet de la pile perd le duel."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Raisonnement à l'aide de quelques exemples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "D'après l'énoncé, on sait que la configuration avec un seul bâtonnet est perdante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "losing = [1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que se passe-t-il pour deux bâtonnets ? En en enlevant un, on met l'adversaire dans la position perdante. Donc 2 est gagnante."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "winning = [2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour 3, c'est pareil, car en retirant deux bâtonnets, l'adversaire est en position perdante. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "winning.append(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et idem pour 4 : en enlevant 3 bâtonnets, on fait perdre l'adversaire."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "winning.append(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que se passe-t-il pour 5 ? Les possibilités que nous avons peuvent se calculer avec la fonction suivante :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def possible_outcomes(number_of_sticks):\n",
    "    return number_of_sticks - 1, number_of_sticks - 2, number_of_sticks - 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, 3, 2)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "possible_outcomes(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il s'avère que toutes les configurations atteignables depuis 5 sont gagnantes. Donc la position 5 est perdante ! On peut écrire une fonction qui teste ceci :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "all_winning = lambda candidates: all(candidate in winning for candidate in candidates)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On vérifie que la fonctionne donne le résultat attendu :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_winning(possible_outcomes(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On ajoute 5 aux positions perdantes :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "losing.append(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Généralisons cette démarche d'induction à l'aide d'une boucle sur les configurations possibles."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Généralisation de la démarche"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On définit d'abord le nombre maximal de bâtonnets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "max_sticks = 18"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'algorithme est le même que celui que nous venons d'appliquer plus haut :\n",
    "\n",
    "- soit une configuration permet d'aboutir à une configuration qui fait perdre l'autre (c'est le cas de 2->1, 3->1 ou 4->1 par exemple) et donc elle est gagnante\n",
    "- soit une configuration ne permet d'aboutir qu'à des positions qui font gagner l'autre et donc elle est perdante\n",
    "\n",
    "A priori, il peut y avoir d'autre positions (qui font accéder à des positions gagnantes et perdantes), mais nous constaterons expérimentalement que ce cas n'est pas possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "losing = [1]\n",
    "winning = [2, 3, 4]\n",
    "\n",
    "for sticks in range(5, max_sticks + 1):\n",
    "    candidates = possible_outcomes(sticks)\n",
    "    # configuration gagnante car elle permet d'accéder \n",
    "    # à une config qui fait perdre l'autre joueur\n",
    "    for candidate in candidates:\n",
    "        if candidate in losing:\n",
    "            winning.append(sticks)\n",
    "            break\n",
    "    # configuration perdante car l'autre joueur gagne \n",
    "    # à tous les coups\n",
    "    if all_winning(candidates):\n",
    "        losing.append(sticks)        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vérifions les résultats :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 6, 7, 8, 10, 11, 12, 14, 15, 16, 18]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "winning"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 5, 9, 13, 17]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "losing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vérifions que nous avons couvert tous les nombres de bâtonnets entre 1 et `max_sticks` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "set()"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set(losing + winning) - set(range(1, max_sticks + 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les résultats de l'algorithme ci-dessus montrent que si l'on arrive à placer l'adversaire dans la position où le nombre de bâtonnet qu'il voit est de la forme $n = 4 k + 1, k \\in \\mathbb{N}$, alors on gagne à coup sûr. Donc, si l'on commence à 18 et que l'on connaît le jeu, on peut facilement remporter la partie (en commençant par retirer un bâtonnet puis en s'assurant d'enlever 4 bâtonnets entre son propre tour et le tour de l'adversaire). Idem pour la variante à 20 bâtonnets."
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}