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)