#!/usr/bin/env python
# coding: utf-8

# *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).*

# Dans ce billet, nous allons nous intéresser au jeu desbâtonnets de Fort Boyard.
# 
# Voici l'énoncé du jeu (adapté d'après <http://www.fan-fortboyard.fr/pages/emission/conseil/batonnets.html>) :
# 
# > Dans ce duel, le candidat et le Maître se retrouvent à jouer avec un alignement de dix-huit bâtonnets (20 jusqu’en 2008).
# 
# > 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.

# # Raisonnement à l'aide de quelques exemples

# D'après l'énoncé, on sait que la configuration avec un seul bâtonnet est perdante :

# In[1]:


losing = [1]


# 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.

# In[2]:


winning = [2]


# Pour 3, c'est pareil, car en retirant deux bâtonnets, l'adversaire est en position perdante. 

# In[3]:


winning.append(3)


# Et idem pour 4 : en enlevant 3 bâtonnets, on fait perdre l'adversaire.

# In[4]:


winning.append(4)


# Que se passe-t-il pour 5 ? Les possibilités que nous avons peuvent se calculer avec la fonction suivante :

# In[5]:


def possible_outcomes(number_of_sticks):
    return number_of_sticks - 1, number_of_sticks - 2, number_of_sticks - 3


# In[6]:


possible_outcomes(5)


# 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 :

# In[7]:


all_winning = lambda candidates: all(candidate in winning for candidate in candidates)


# On vérifie que la fonctionne donne le résultat attendu :

# In[8]:


all_winning(possible_outcomes(5))


# On ajoute 5 aux positions perdantes :

# In[9]:


losing.append(5)


# Généralisons cette démarche d'induction à l'aide d'une boucle sur les configurations possibles.

# # Généralisation de la démarche

# On définit d'abord le nombre maximal de bâtonnets.

# In[10]:


max_sticks = 18


# L'algorithme est le même que celui que nous venons d'appliquer plus haut :
# 
# - 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
# - soit une configuration ne permet d'aboutir qu'à des positions qui font gagner l'autre et donc elle est perdante
# 
# 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.

# In[11]:


losing = [1]
winning = [2, 3, 4]

for sticks in range(5, max_sticks + 1):
    candidates = possible_outcomes(sticks)
    # configuration gagnante car elle permet d'accéder 
    # à une config qui fait perdre l'autre joueur
    for candidate in candidates:
        if candidate in losing:
            winning.append(sticks)
            break
    # configuration perdante car l'autre joueur gagne 
    # à tous les coups
    if all_winning(candidates):
        losing.append(sticks)        


# Vérifions les résultats :

# In[12]:


winning


# In[13]:


losing


# Vérifions que nous avons couvert tous les nombres de bâtonnets entre 1 et `max_sticks` :

# In[14]:


set(losing + winning) - set(range(1, max_sticks + 1))


# # Conclusions

# 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.