# -*- coding: utf-8 -*-
"""
TP10 : Algorithmes gloutons - Corrigé

PCSI2 - Albert Schweitzer - Le Raincy
"""

euros = [50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1]

##Q2
def rendu_exh(L:list, s:int) -> list:
    '''
    Entrée : L liste d'entiers distincts contenant 1
    et s un entier positif
    Sortie : une liste contenant les pièces
    à utiliser pour obtenir la somme s avec
    un nombre minimal de pièces
    '''
    if s in euros:
        return 1
    if s == 0:
        return 0
    L = []
    for x in euros:
        if x <= s:
            L.append(1 + rendu_exh(s-x))
    return min(L)

##Q4
'''
Cet algorithme est très lent ! L'amélioration ci-dessous est un peu plus rapide, mais pour 1000 cents c'est déjà long.
'''

##Q5-Q6
def rendu_exh_opt(L:list, s:int) -> list:
    '''
    Entrée : L liste d'entiers distincts contenant 1
    et s un entier positif
    Sortie : une liste contenant les pièces
    à utiliser pour obtenir la somme s avec
    un nombre minimal de pièces
    '''
    resultat = [None]*(s+1)
    resultat[0] = []
    def aux(val):
        if resultat[val] != None:
            return resultat[val]
        else:
            min = s + 1
            for x in euros:
                if x <= val:
                    test = aux(val-x)
                    if len(test) < min:
                        min = len(test)
                        rendu = test[:]
                        rendu.append(x)
            resultat[val] = rendu
            return rendu
    return aux(s)

##Q7-Q8
def rendu_glouton(systeme:list, somme:int) -> list:
    '''
    Entrée : systeme liste d'entiers distincts
    contenant 1 triée par ordre décroissant
    et s un entier positif
    Sortie : une liste contenant les pièces
    à utiliser pour obtenir la somme s avec
    un nombre minimal de pièces
    Algorithme glouton.
    '''
    rendu = []
    for x in systeme:
        if x<=somme:
            nb = somme//x#nombre de pièces de type x à utiliser
            for i in range(nb):
                rendu.append(x)
            somme = somme%x#somme restante
            if somme == 0:
                return rendu
    raise ValueError("Echec de l'algorithme glouton")

##Q9
'''
La fonction rendu_glouton est bien plus rapide et simple à comprendre que rendu_exh.
'''

##Q10
autre = [4, 3, 1]
assert rendu_exh(autre, 6) == rendu_glouton(autre, 6), 'Problème glouton'
'''
L'algorithme glouton ne fonctionne pas pour tous les systèmes monétaires...
'''

##Q11
'''
1 : C2, C4, C3, C1
2 : C1, C3
3 : C1 -> pas bon !
'''

##Q12
'''
1 : C1, C2, C3, C4
2 : C2 -> pas bon !
3 : C2, C3
'''

##Q13
def takeThird(L:list):
    return L[2]

def cours_glouton(C:list) -> list:
    '''
    Entrée : liste de listes de la forme [str, int, int]
    Sortie : renvoie la liste des cours choisis
    en préférant ceux qui terminent en premier
    '''
    C.sort(key = takeThird)
    cours = [C[0]]
    i = 1
    while i < len(C):
        if C[i][1] >= cours[-1][2]:#on teste si le cours C[i] commence après la fin du dernier cours choisi
            cours.append(C[i])
        i = i + 1
    return cours

##Q14
E1 = [['C1', 3, 4], ['C2', 0, 1], ['C3', 2, 3], ['C4', 1, 2]]
E2 = [['C1', 0, 3], ['C2', 2, 4], ['C3', 3, 6]]
E3 = [['C1', 0, 3], ['C2', 1, 2], ['C3', 2, 3]]

##Q15
import random as rd
def cours_alea(debut:int, fin:int, n:int) -> list:
    '''
    Prend une heure de début et une heure de fin
    et renvoie une liste de n cours aléatoire qui
    commencent après début et avant fin
    Précondition : debut < fin
    '''
    C = []
    for i in range(n):
        nom = 'C' + str(i)
        d = rd.randint(debut, fin - 1)
        f = rd.randint(d + 1, fin)
        C.append([nom, d, f])
    return C

##Ex1
'''
1. Pour une somme s, l'algorithme glouton va donner s//x pièces x et s%x pièces 1.
Pour toutes les autres répartitions, le nombre de pièces x est inférieur : il faut donc compenser par x pièces 1. On utilise donc plus de pièces que le nombre donné par glouton.
'''

def rendu_glouton_d(systeme:list, somme:int) -> dict:
    '''
    Entrée : systeme liste d'entiers distincts
    contenant 1 triée par ordre décroissant
    et s un entier positif
    Sortie : un dictionnaire contenant les couples
    (pièces, nombre)
    à utiliser pour obtenir la somme s avec
    un nombre minimal de pièces
    Algorithme glouton.
    '''
    rendu = {}
    for x in systeme:
        if x<=somme:
            nb = somme//x#nombre de pièces de type x à utiliser
            rendu[x] = nb
            somme = somme%x#somme restante
            if somme == 0:
                return rendu
    raise ValueError("Echecs de l'algorithme glouton")

##Ex2
def sac_glouton(Objets:list, capacite:float) -> list:
    '''
    Renvoie la liste des objets répondant au pb
    du sac à dos en utilisant une heuristique
    gloutonne
    '''
    rapports = [(valeur/poids, valeur, poids) for (valeur, poids) in Objets]
    rapports.sort(reverse=True)#par ordre décroissant
    sac = []
    for i in range(len(rapports)):
        r, valeur, poids = rapports[i]
        if poids <= capacite:
            sac.append((valeur, poids))
            capacite = capacite - poids
    return sac

def sac_exh(Objets:list, capacite:float) -> list:
    '''
    Renvoie la liste des objets répondant au pb
    du sac à dos.
    Teste les 2**n possibilités
    '''
    def aux(i, c):
        if i >= len(Objets):
            return 0, []
        max, sac = aux(i+1, c) #on calcul l'optimum sans l'élément i
        if Objets[i][1] <= c:#on teste si on peut utiliser l'élément i
            val = Objets[i][0]
            for j in range(i+1, len(Objets)+1):
                t = aux(j, c-Objets[i][1])
                tmax = t[0] + val
                if max < tmax:
                    max = tmax
                    sac = t[1][:]
                    sac.append(Objets[i])
        return max, sac
    return aux(0, capacite)

objets = [(12, 9),(4, 3), (9, 6), (11, 5),  (11, 7)]
print(sac_exh(objets, 14))
print(sac_glouton(objets, 14))