#### TP n°11: Algorithmes gloutons ####
#################



### RENDU DE MONNAIE ###

## Question 1 : Système de pièces européen
pieces1=[50000,20000,10000,5000,2000,1000,500,200,100,50,20,10,5,2,1]
def monnaie(pieces:list,somme:int) -> list:
    a_payer=[]
    r=somme
    for i in range(len(pieces)):
        while pieces[i]<=r:
            a_payer.append(pieces[i])
            r=r-pieces[i]
    return a_payer

print(monnaie(pieces1,3423))
## Question 2 
pieces2=[30000,10000,3000,1000,300,100,30,10,3,1]
print(len(monnaie(pieces1,2214)))
print(len(monnaie(pieces2,2214)))
## Question 3 
pieces3=[40000,30000,10000,4000,3000,1000,400,300,100,40,30,10,4,3,1]
print(monnaie(pieces3,1600))
# meilleur: [1000,300,300]

### PROBLÈME DU SAC À DOS ###


## Question 4 
for key in dico_objets:
    volume=dico_objets[key][0]
    utilite=dico_objets[key][1]
    print(key+", de volume "+str(volume)+", d'utilité "+str(utilite))
## Question 5 
somme=0
for key in dico_objets:
    somme=somme+dico_objets[key][0]
print(somme)
## Question 6 
def cle_de_valeur_max(dico:dict) -> str:
    """ renvoie la clé correspondant à la valeur maximale """
    clemax=""
    valmax=float("-inf")
    for k in dico:
        if dico[k]>valmax:
            valmax=dico[k]
            clemax=k
    return clemax

print(cle_de_valeur_max({"a":3,"b":2,"c":5,"d":8,"e":4})) # doit afficher "d"
## Question 7 
def ordre_ratios(dico:dict) -> list:
    dico_ratios={}
    # remplissage du dictionnaire avec les clés de dico, et comme valeur les ratios utilité/volume
    for cle in dico:
        dico_ratios[cle]=dico[key][1]/dico[key][0]
    # sélection des clés par ordre décroissant des ratios
    ordre=[]
    # tant qu'il y a des clés dans dico_ratio, on récupère la clé de ratio max, on la stocke dans ordre, et on efface la case
    while dico_ratios!={}:
        clemax=cle_de_valeur_max(dico_ratios)
        ordre.append(clemax)
        del(dico_ratios[clemax])
    return ordre
print(ordre_ratios(dico_objets)) # doit renvoyer ['Carte','Lampe','Couteau','Téléphone',...]
## Question 8 
def sac_a_dos(dico:dict,Vmax:int) -> list:
    """ remplit un sac à dos par algorithme glouton 
    dico_objets: dictionnaire contenant les objets, leur volume et leur utilité
    Vmax: volume maximal
    """
    Vlibre=Vmax
    ordre=ordre_ratios(dico)
    objets_pris=[]
    for i in range(len(ordre)):
        objet=ordre[i]
        volume=dico[objet][0]
        if volume<=Vlibre:
            objets_pris.append(objet)
            Vlibre=Vlibre-volume
    return objets_pris
bagages=sac_a_dos(dico_objets,45)
print(bagages)
print(set(dico_objets.keys())-set(bagages))
volume_total=0
utilite_totale=0
for i in range(len(bagages)):
    volume_total=volume_total+dico_objets[bagages[i]][0]
    utilite_totale=utilite_totale+dico_objets[bagages[i]][1]
print(volume_total)
print(utilite_totale)

### VOYAGEUR DE COMMERCE ###



## Question 9 
import math
def distance(dico:dict,ville1:str,ville2:str) -> int:
    coord1=dico[ville1]
    coord2=dico[ville2]
    return math.sqrt((coord1[0]-coord2[0])**2+(coord1[1]-coord2[1])**2)
## Question 10 
def voyageur_commerce(dico:dict,depart:str) -> [list,float]:
    dico2=dico.copy()
    voyage=[depart] # liste des villes visitées
    ville=depart # ville actuelle
    dtot=0 # distance parcourue
    del(dico2[depart])
    while dico2!={}:
        dmin=10000
        vmin=""
        for v in dico2:
            d=distance(dico,ville,v)
            if d<dmin:
                dmin=d
                vmin=v
        voyage.append(vmin)
        dtot=dtot+dmin
        ville=vmin
        del(dico2[vmin])
    voyage.append(depart)
    dtot=dtot+distance(dico,ville,depart)
    return voyage,dtot


### OCCUPATION DE SALLES ###


## Question 11 
def planning(debuts:list,fins:list,ordre:list) -> list:
    ordrec=ordre.copy()
    planning=[]
    while max(ordrec)>=0:
        occupation=[]
        horaire=8
        for i in range(len(ordrec)):
            if ordrec[i]>=0 and debuts[ordrec[i]]>=horaire:
                occupation.append(ordrec[i])
                horaire=fins[ordrec[i]]
                ordrec[i]=-1
        planning.append(occupation)
    return planning

## Question 12 
ordre_fin=list(numpy.argsort(horaires_fin))
salles=planning(horaires_debut,horaires_fin,ordre_fin)
print(salles)
print("Le planning utilise "+str(len(salles))+" salles")
for i in range(len(salles)):
    message="La salle "+str(i)+" accueille des cours "
    for j in range(len(salles[i])):
        debut=horaires_debut[salles[i][j]]
        fin=horaires_fin[salles[i][j]]
        message=message+" de "+str(debut)+"h à "+str(fin)+"h, "
    print(message)
### ADMISSION POSTBAC ###


## Question 13 
places=3
def apb(voeux,classements):
    liste_affectations=[[],[],[],[]]
    liste_eleves=list(range(len(liste_voeux)))
    while len(liste_eleves)>0:
        eleve=liste_eleves[0]
        voeux_eleve=voeux[eleve]
        ivoeu=0
        classe=False
        while classe==False:
            voeu=voeux_eleve[ivoeu]
            if len(liste_affectations[voeu])<places:
                liste_affectations[voeu].append(eleve)
                del(liste_eleves[0])
                classe=True
            else:
                imauvais=0
                for i in range(len(liste_affectations[voeu])):
                    if classements[voeu].index(liste_affectations[voeu][i])>classements[voeu].index(liste_affectations[voeu][imauvais]):
                        imauvais=i
                if classements[voeu].index(liste_affectations[voeu][i])>classements[voeu].index(eleve):
                    liste_eleves.append(liste_affectations[voeu][i])
                    liste_affectations[voeu][i]=eleve
                    del(liste_eleves[0])
                    classe=True
                else:
                    ivoeu=ivoeu+1
    return liste_affectations
## Question 14 
affectations=apb(liste_voeux,liste_classements)
print(affectations)
for i in range(len(liste_voeux)):
    for j in range(len(affectations)):
        for k in range(len(affectations[j])):
            if affectations[j][k]==i:
                print("L'élève n°"+str(i)+" a obtenu son vœu numéro "+str(1+liste_voeux[i].index(j)))
for i in range(len(affectations)):
    message="L'établissement n°"+str(i)+" a reçu les élèves qu'il avait classé en positions " 
    for j in range(len(affectations[i])):
        message=message+str(liste_classements[i].index(affectations[i][j]))+", "
    print(message)