# Ces import manquaient
from random import randint

import matplotlib.pyplot as plt


def verif(l, nb):
    # On peut descendre jusqu'au ca sde base len(l) == 0 qui est encore plus simple
    # On peut retourner un booléen ce qui est plus propre que 0 ou 1
    # On peut accèder à une liste par la fin avec des indices négatifs l[n-1] == l[-1]
    if not l:    # Une liste vide est "fausse" dans les tests booléens
        return nb == 0
    return verif(l[:-1], nb-l[-1]) or verif(l[:-1], nb+l[-1])


def suite(nb):
    # Simplification car maintenant verif accepte une liste vide et retourne un booléen
    l = []
    while not verif(l, nb):
        l.append(randint(1, 6))
    return l


def suite_2(nb):
    # Version optimisée de 'suite(nb)'
    # Au lieu de reparcourir tout l'arbre à chaque ajout à la liste, on met à jour seulement les feuilles
    # Il y a beaucoup de feuilles les mêmes (+5-3-5 == -5-3+5 par exemple), on ne garde qu'un exemplaire de chaque feuille (avec un set)
    # On peut encore réduire de moitié le nombre de feuille car si on peut atteindre n alors on peut atteindre -n en inversant les signes
    # Mes tests montre que ce suite_2 tourne 7.4 fois plus vite que suite pour nb==12, 593 fois plus vite pour nb==40
    nb = abs(nb)
    l = []
    numbers = {0}
    while nb not in numbers:
        number = randint(1, 6)
        l.append(number)
        numbers = {abs(n - number) for n in numbers} | {n + number for n in numbers}

    return l


def test(compt, nb):
    n = []
    d = []
    for i in range(compt):
        # l = suite(nb)
        l = suite_2(nb)
        n.append(len(l))
        d.append(l[-1])     # l[-1] est le dernier élément de l
    figure = plt.figure(figsize=(10, 10))
    plt.gcf().subplots_adjust(left=0.1, bottom=0.1, right=0.9, top=0.9, wspace=0, hspace=0.2)
    figure.add_subplot(2, 1, 1)  # On ne fait rien avec 'axes', pas besoin de cette variable
    plt.hist(n, bins=[k+0.5 for k in range(max(n)+1)])  # Centre les barres sur les nombres entiers et ne coupe pas le graphe
    # numerical_approx et mean semblent venir de SageMath qui est compliqué à installer comme une dépendance.
    # Le format .2f arrondi déjà à deux décimales et mean peut être calculé avec des fonctions builtin de python
    # Utiliser les f-strings est plus naturel que str.format
    plt.title(f"Histogramme du nombre d'essais nécessaires avec pour moyenne {sum(n)/len(n):.2f}")
    figure.add_subplot(2, 1, 2)
    plt.hist(d, bins=[k+0.5 for k in range(7)])     # Centre les barres sur les nombres entiers
    plt.title("Histogramme de la valeur du dernier essai")
    plt.show()
    return n, d


if __name__ == "__main__":  # Permet de réutiliser les fonctions de ce module dans un autre module sans lancer le test
    test(100000, 12)

def solve(target=12, depth=12):
    target = abs(target)
    unsolved_trows = {frozenset({0}): 1}
    nb_dices_to_target = []
    for _ in range(depth):
        nb_dices_to_target.append({dice: 0 for dice in range(1, 7)})
        unsolved_trows_ = {}
        for numbers, cases in unsolved_trows.items():
            for dice in range(1, 7):
                numbers_ = frozenset(n + dice for n in numbers) | frozenset(abs(n - dice) for n in numbers)
                if target in numbers_:
                    nb_dices_to_target[-1][dice] += cases
                else:
                    unsolved_trows_[numbers_] = unsolved_trows_.get(numbers_, 0) + cases

        unsolved_trows = unsolved_trows_

    return nb_dices_to_target, unsolved_trows


def main(depth=25):
    nb_dices_to_target, unsolved_trows = solve(depth=depth)
    print(' '.join((f'#lancers', *(f' dernier dé {dice}' for dice in range(1, 7)), f'         total', f'    ratio')))
    for nb_trows, cases in enumerate(nb_dices_to_target, 1):
        print(' '.join((f'{nb_trows: >8}', *(f'{cases[dice]: >13}' for dice in range(1, 7)), f'{sum(cases.values()): >14}', f'{sum(cases.values())/6**nb_trows: .6f}')))
    print(' '.join((f'   ratio', *(f'{sum(cases[dice]/6**nb_trows for nb_trows, cases in enumerate(nb_dices_to_target, 1)): >13.6f}' for dice in range(1, 7)), f'{sum(sum(cases.values())/6**nb_trows for nb_trows, cases in enumerate(nb_dices_to_target, 1)): >14.6f}')))

    print(f'Unsolved trows: {sum(unsolved_trows.values())} (ratio: {sum(unsolved_trows.values())/6**depth})')
print(f"Expected number of trows: {sum(sum(cases.values())/6**nb_trows*nb_trows for nb_trows, cases in enumerate(nb_dices_to_target, 1))}")

if __name__ == "__main__":
   main()

#lancers  dernier dé 1  dernier dé 2  dernier dé 3  dernier dé 4  dernier dé 5  dernier dé 6          total     ratio
       1             0             0             0             0             0             0              0  0.000000
       2             0             0             0             0             0             1              1  0.027778
       3             2             3             4             5             6             5             25  0.115741
       4            47            41            49            44            59            46            286  0.220679
       5           432           217           443           226           472           216           2006  0.257973
       6          2335           420          2338           433          2397           360           8283  0.177533
       7          8687           503          8586           497          8729           312          27314  0.097572
       8         27931           708         27585           685         27938           279          85126  0.050682
       9         86171          1135         85374          1101         86153           251         260185  0.025818
      10        262130          2039        260437          2001        262105           259         788971  0.013048
      11        792712          3848        789243          3805        792680           275        2382563  0.006567
      12       2389914          7468       2382868          7422       2389884           312        7177868  0.003297
      13       7192396         14659       7178199         14608       7192358           334       21592554  0.001653
      14      21621447         29034      21592921         28980      21621413           374       64894169  0.000828
      15      64951741         57727      64894560         57668      64951697           394      194913787  0.000415
      16     195028734        115112     194914216        115050     195028696           436      585202244  0.000207
      17     585431884        229819     585202695        229752     585431834           454     1756526438  0.000104
      18    1756985487        459238    1756526929        459168    1756985445           498     5271416765  0.000052
      19    5272334569        918007    5271417276        917932    5272334513           514    15817922811  0.000026
      20   15819758154       1835556   15817923364       1835478   15819758108           560    47461111220  0.000013
      21   47464781572       3670579   47461111791       3670496   47464781510           574   142398016522  0.000006
      22  142405356927       7340642  142398017137       7340556  142405356877           622   427223412761  0.000003
      23  427238093197      14680687  427223413392      14680596  427238093129           634  1281728961635  0.000002
      24 1281758322174      29360800 1281728962312      29360706 1281758322120           684  3845304328796  0.000001
      25 3845363049460      58720939 3845304329487      58720840 3845363049386           694 11536147870806  0.000000
   ratio      0.216061      0.084814      0.227654      0.097784      0.250463      0.123224       1.000000
Unsolved trows: 11536382753310 (ratio: 4.057779063358482e-07)
Expected number of trows: 5.250021664206247