#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Feb 18 11:35:31 2021

@author: pjoulaud
"""
import matplotlib.pyplot as plt
import timeit

def nb_rendus(n:int, pieces:list)->int:
    """
    Fonction qui  retourne le nombre de possibilités pour un rendu de monnaie
    @params :
    - n : montant à rendre de type int
    - pieces : liste de pièces que l' on peut utiliser de type list
    @returns :
    - Nombre de possibilités de type int
    """
    if n<0 or len(pieces)==0:
        return 0
    if n>0:
        return nb_rendus(n, pieces[:-1]) + nb_rendus(n-pieces[-1], pieces)
    return 1

def count_change(n:int, k:int, pieces:list)->int:
    """
    Fonction qui  retourne le nombre de possibilités pour un rendu de monnaie
    VERSION MEMOISE - Les calculs déjà effectués sont mémorisée dans un dictionnaire
    @params :
    - n : montant à rendre de type int
    - k : dans la liste des pièces, on n' utilise que les k premières pièces
    - pieces : liste complète de pièces que l' on peut utiliser de type list
    @returns :
    - Nombre de possibilités de type int
    """
    if n<0  or len(pieces)==0:
        return 0
    if (n, k) in mon_dico :
        return mon_dico[n, k]
    if k==0:
        v = 1
    else :
        v = count_change(n, k-1, pieces) + count_change(n-pieces[k], k, pieces)
        #print(f"n: {n} - k : {k} - pieces  : {pieces}")
        mon_dico[n, k] = v
        #print(mon_dico)
    return v

#PROGRAMME PRINCIPAL
print("### DEBUT PROGRAMME NB FACONS DONT ON PEUT RENDRE LA MONNAIE ###")
print("EXERCICE 6")
pieces =  (2,3,7,23,47)
x, rendu, rendu_mem = [], [], []
for un_x in range(0,300,50) :
    mon_dico = {}
    x.append(un_x)
    rendu.append(timeit.timeit('nb_rendus(un_x, pieces)', number=100, globals=globals()))
    rendu_mem.append(timeit.timeit('count_change(un_x, len(pieces)-1, pieces)', number=100, globals=globals()))
    
    
# Créer un graphique
plt.plot(x, rendu, marker='o', linestyle='-', color='b', label="rendu")
plt.plot(x, rendu_mem, marker='x', linestyle='-.', color='r', label="rendu_mem")


# Ajouter des étiquettes et un titre
plt.xlabel("Nombres")
plt.ylabel("Fonctions")
plt.title("Différentes fonctions rendu de monnaie")

# Afficher la légende
plt.legend()

# Afficher la grille
plt.grid(True)

# Afficher le graphique
plt.show()