Code source de jouets.verger
# Copyright 2020 Louis Paternault
#
# This file is part of Jouets.
#
# Jouets is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# Jouets is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Jouets. If not, see <http://www.gnu.org/licenses/>.
"""Calcul des probabilités de victoire au jeu du verger"""
import functools
import os
import random
VERSION = "0.1.0"
[docs]
def panier_max(arbres):
"""Choisir l'arbre le moins vide (contenant le plus de fruits)."""
if len(arbres) == 1:
return [arbres[0] - 2]
if arbres[-1] == 1 or arbres[-1] == arbres[-2]:
return sorted(
(
fruits
for fruits in (list(arbres[:-2]) + [arbres[-2] - 1] + [arbres[-1] - 1])
if fruits
)
)
return sorted(
(fruits for fruits in (list(arbres[:-1]) + [arbres[-1] - 2]) if fruits)
)
[docs]
def panier_min(arbres):
"""Choisir l'arbre le plus vide (contenant le moins de fruits)."""
if len(arbres) == 1:
return [arbres[0] - 2]
if arbres[0] == 1:
return sorted(
(fruits for fruits in ([arbres[1] - 1] + list(arbres[2:])) if fruits)
)
return sorted((fruits for fruits in ([arbres[0] - 2] + list(arbres[1:])) if fruits))
[docs]
def panier_random(arbres):
"""Choisir l'arbre au hasard."""
copie = list(arbres)
for _ in range(2):
indice = random.randint(0, len(copie) - 1)
copie[indice] -= 1
if not copie[indice]:
del copie[indice]
return sorted(copie)
#: Stratégies disponibles lorsqu'un « panier » est obtenu au dé.
STRATEGIES = {"max": panier_max, "min": panier_min, "random": panier_random}
CACHESIZE_ENV = "VERGER_CACHE_SIZE"
def cache_size():
"""Renvoit la taille du cache.
Celle-ci est lue depuis la variable d'environnement `CACHESIZE_ENV`:
- si elle est définie à une chaîne vide, elle est infinie (valeur `None`) ;
- sinon, si elle est définie à une chaîne pouvant être
interprétée comme un nombre entier, ce nombre désigne la
taille du cache ;
- sinon, si la variable d'environnement n'est pas définie, ou
si elle est définie à une chaîne non vide non reconnue comme
un nombre, la taille est :math:`2^{20}`.
"""
cachesize_str = os.getenv(CACHESIZE_ENV)
if cachesize_str == "":
return None
try:
return int(cachesize_str)
except (ValueError, TypeError):
return 2**20
[docs]
@functools.lru_cache(cache_size())
def probabilite(corbeau, panier, *arbres):
"""Renvoit la probabilité de victoire pour une partie.
:param int corbeau: Nombre de pièces du puzzle restant au corbeau.
:param function panier: Stratégie à utiliser, comme une valeur de :data:`STRATEGIES`.
:param list arbres: Nombre de fruits sur chacun des arbres,
comme une liste décroissante d'entiers strictement
positifs. Les arbres vides ne sont pas représentés
(puisque la probabilité de gagner dans un jeu à quatre
arbres dont deux vides est égale à celle de gagner dans un
jeu à deux arbres).
"""
# Conditions de victoire et de défaite
if sum(arbres) == 0:
return 1
if corbeau == 0:
return 0
# Appel récursif
proba = 0
# Corbeau
proba += probabilite(corbeau - 1, panier, *arbres)
# Fruit
for i in range(len(arbres)):
copie = list(arbres)
copie[i] -= 1
if not copie[i]:
del copie[i]
proba += probabilite(corbeau, panier, *sorted(copie))
# Panier
if sum(arbres) <= 2:
proba += 1
else:
proba += probabilite(corbeau, panier, *panier(arbres))
return proba / (len(arbres) + 2)