# -*- coding: utf-8 -*-

##### -------2023-ITC-DS3 PCSI-----------------######
### GESTION CONCERT
concert = {'Jimi Hendrix' : [12, 13.5], 'Blood, Sweat and Tears' : [13, 14],
'Joan Baez' : [15, 16.5], 'Creedence Clearwater Revival' : [15, 16],
'The Band' : [17, 18.5], 'Janis Joplin' : [18, 20],
'Jefferson Airplane' : [15, 17]}

#1- artistes par horaire
def heure_list(concert:dict) -> dict:
    dico = {12+i: [] for i in range(12)}
    for artiste,horaires in concert.items():
        dico[horaires[0]] += [artiste]  # l'artiste est présent dès le début de son concert
        if horaires[1] - horaires[0] > 1:
            dico[horaires[0]+1] += [artiste]
    return dico


#2- Liste d'artiste par heure
def  heure_nb(concert:dict) -> dict:
    dico_nbParHeure = {}
    for heure, l_artistes in heure_list(concert).items():
        dico_nbParHeure[heure] = len(l_artistes)
    return dico_nbParHeure

def  heure_nb1(concert:dict) -> dict: #Modèle réduit!
    return {heure:len(liste_groupes) for (heure, liste_groupes) in heure_list(concert).items()}


#3- Horaires d'affluence
def maxi_heure(concert:dict) -> list:
    l_max = []
    max_artistes = 0
    for heure, nb_artistes in heure_nb(concert).items():
        if nb_artistes >= max_artistes:
            max_artistes = nb_artistes
    for heure, nb_artistes in (heure_nb(concert)).items():
        if nb_artistes == max_artistes:
            l_max.append(heure)
    return l_max

### POSITION DU PB D'OPTIMISATION

##Questions péliminaires
# 4-Fonction valeur
def valeur(concerts:list)->int:
    valeur_tot = 0
    for i in range(len(concerts)):
        valeur_tot += concerts[i][2]
    return valeur_tot

def valeur_rec(concerts:list)->int:
    if len(concerts) == 0:
        return 0
    return concerts[0][2] + valeur_rec(concerts[1:])
#Complexité: O(n)

#5- Tri_selection
#(a)
def tri_selection(liste_nb):
    for i in range (len(liste_nb)):
        # SELECTION
        i_min = i
        for j in range(i+1, len(liste_nb)):
            if liste_nb[j] < liste_nb[i_min]:
                i_min = j
        # ECHANGE
        liste_nb[i_min], liste_nb[i] = liste_nb[i], liste_nb[i_min]

#(b) complexité quadratique
#(c)
def tri_selection_rec(liste_nb):
    #condition d'arrêt
    if len(liste_nb) == 1:
        return liste_nb
    #SELECTION
    i_mini = 0
    for j in range(i_mini+1,len(liste_nb)):
        if liste_nb[j] < liste_nb[i_mini] :
            i_mini = j
    #echange
    liste_nb[i_mini], liste_nb[0] = liste_nb[0], liste_nb[i_mini]
    return  [liste_nb[0]] + tri_selection_rec(liste_nb[1:])



# 7- Compatibilité des concerts
def compatible(concerts:list)->bool:
    # tri dans l'ordre croissant des heures de fin de concerts
    concerts_tries = tri(concerts)
    # test de compatibilité
    for i in range(len(concerts)):
        if concerts_tries[i][1] > concerts_tries[i+1][0]:
            return False
    return True


## GLOUTONS
#8- a- Fonction gloutonne
def glouton(concerts):
    concerts_tries = tri(concerts)[::-1]  #pour ranger par ordre décroissant d'heure de fin de concert
    dernier_concert = concerts_tries[0]
    choix = [dernier_concert]
    for element in concerts_tries:
        if element[1] <= dernier_concert[0]:
            choix.append(element)
            dernier_concert = element[:]
    return choix

#8-b - Complexité
#Cn = C(tri_fusion) + 3n = n.logn + 3n  soit O(n.logn)

#8-c - Critique méthode: solution rapide mais pas forcément orptimale


## FORCE BRUTE
# 9 -a- fonction génération de sous-listes
def tousous(concerts:list)->list:
    if len(concerts) == 0:
        return [[]]
    liste_ss_listes = []
    for element in tousous(concerts[1:]):
        liste_ss_listes.append(element)
        liste_ss_listes.append(element + [concerts[0]])
    return liste_ss_listes

# 9- b- dénombrement de combinaisons:
#nb_Combi = somme(de 1 à n)des combinaisons de p concerts parmi n = 2^n

# 10-
#a- fonction naive générant des sous-listes de concerts compatibles
def toucompatible(concerts:list)->list:
    l_combi_concerts_compatibles = []
    for element in tousous(concerts):
        if compatible(element):
            l_combi_concerts_compatibles.append(element)
    return l_combi_concerts_compatibles

# 10-b- complexité
#Cn = 1 + 2^n . [C(compatible)] = 1 + 2^n . [C(tri)+n] < K.(2^n.(nlogn))

#11- a- choix naif
def maxichoix(concerts:list)->(float, list):
    valeur_max = 0
    for element in toucompatible(concerts):
        if valeur(element) > valeur_max:
            valeur_max = valeur(element)
            liste_choisie = element
    return valeur_max, liste_choisie

#11-b- Complexité
#dans le pire des cas on Cn = C(toucompatible).C(valeur) = 2^n.n^2.logn

#11-c-
#trop grande complexité mais assure la réponse correcte par l'étude exhaustive des possibilités.