MICHEL ET SES AMIS

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

################# AFFICHAGE DES RESULTATS ####################

import matplotlib.pyplot as plt
plt.rcdefaults()
import matplotlib.patches as mpatches

def minutesVersHeures(minutes):
    return minutes // 60, minutes % 60

def ajouterOral(Oral, OrauxType, Color, patches):
    import copy
    temp = copy.deepcopy([o.Matiere for o in OrauxType])
    temp.sort()
    NumeroOral = temp.index(Oral.OralType_.Matiere)
    rect = mpatches.Rectangle((Oral.Heure, NumeroOral), Oral.OralType_.Duree, 1, color = Color, ec = "black")
    patches.append(rect)


def afficher(patches, margin = 8):
    fig, ax = plt.subplots()
    for p in patches:
        ax.add_patch(p)
    maxMachines = max(rect.get_y() for rect in patches) + 1
    maxJobs = max(rect.get_x() + margin for rect in patches)
    plt.axis([0, maxJobs, 0, maxMachines])
    plt.show()

################### PARCOURS D'ARBRE EN PROFONDEUR #############################

# On part d'une situation initiale vide
# On pose un oral à une heure (minimale)
# On appelle la fonction avec cette nouvelle configuration et un oral en moins à placer.

# Cette fonction ne doit pas être appelée par le programme, seulement par solutionOptimale() !
# Un oral est un élément de N * N : Prof * Eleve

def dureeSolutionOptimale(Solution):
    #Oral[2] : Heure de début
    #Oral[1] : Durée de l'oral
    return max([oral[2] + oral[1] for oral in Solution])

def trouverPremiereHeure(solution, Jury, Eleve, Pause, Duree):
    heure = 0
    orauxDuJury = [oral for oral in solution if oral[0] == Jury]
    orauxDuCandidat = [oral for oral in solution if oral[2] == Eleve]
    while True:
        incompatible = False
        for oral in orauxDuCandidat:
            if oral[2] <= heure and oral[2] + oral[1] + Pause > heure:
                incompatible = True
            elif oral[2] >= heure and heure + Duree + Pause > oral[2]:
                incompatible = True
        for oral in orauxDuJury:
            if oral[2] <= heure and oral[2] + oral[1] > heure:
                incompatible = True
            elif oral[2] >= heure and heure + Duree > oral[2]:
                incompatible = True
        if incompatible:
            heure += 1
        else:
            break
    return heure

def solutionOptimaleAux(Oraux, Solution, MakespanHeuristique, Pause):
    solutionModifiable = copy.deepcopy(Solution)
    for Oral in Oraux:
        solutionModifiable.append((Oral[0], Oral[1], trouverPremiereHeure(solutionModifiable, Oral[0][0], Oral[0][1], Pause, Oral[1])))
        if dureeSolutionOptimale(solutionModifiable) >= MakespanHeuristique:
            return None
        else:
            resultat = solutionOptimaleAux([OralAGarder for OralAGarder in Oraux if OralAGarder != Oral], solutionModifiable, MakespanHeuristique, Pause)
            if resultat == None:
                solutionModifiable = solutionModifiable[:-1]
            else:
                return resultat

def solutionOptimale(Eleves, Jurys):
    Eleves.sort(key = lambda Eleve: Eleve.Nom)
    Jurys.sort(key = lambda Jury: Jury.Nom)

    Pause = Eleves[0].Pause
    DictEleves = {}
    DictJurys = {}

    Oraux = []

    for i in range(len(Eleves)):
        DictEleves[i] = Eleves[i]
    for p in range(len(Jurys)):
        DictJurys[p] = Jurys[p]

    for i in DictJurys.keys():
        Duree = DictJurys[i].OralType_.Duree
        for e in DictEleves.keys():
            # Le nouvel oral est sous le format ((n° prof, n° élève), durée) : on évite de se trimballer des objets
            Oraux.append(((i, e), Duree))

    resultatHeuristique = creerMeilleurEmploiDuTempsAvecPermutations(Jurys, Eleves)
    meilleurMakespanHeuristique = resultatHeuristique[2]
    resultatAux = solutionOptimaleAux(Oraux, [], meilleurMakespanHeuristique, Pause)
    if resultatAux == None:
        print("L'heuristique donne la meilleure solution.")
        return resultatHeuristique
    else:
        return resultatAux

################### CLASSES ELEVES / JURYS / ORAUX #############################

import copy

class Eleve:
    Pause = 1
    def __init__(self, Nom, Oraux):
        self.Nom = Nom
        self.Oraux = Oraux

    def estDisponible(self, Heure, OralType_, overrideAssocie = False):
        if self.associe(OralType_) and not overrideAssocie:
            return False
        for Oral in self.Oraux:
            if Oral.Heure <= Heure and Oral.HeureFin + self.Pause > Heure:
                return False
            elif Oral.Heure >= Heure and Heure + OralType_.Duree + self.Pause > Oral.Heure:
                return False
        return True

    def copieVide(self):
        newEleve = Eleve(self.Nom, [])
        return newEleve
    def deplacerOral(self, oralADeplacer, nouvelleHeure):
        for o in self.Oraux:
            if o == oralADeplacer:
                o.changerHeure(nouvelleHeure)

    def associe(self, OralType_):
        return OralType_ in [o.OralType_ for o in self.Oraux]

    def Associer(self, Oral):
        self.Oraux.append(Oral)

    def __str__(self):
        renvoye = self.Nom + "\n"
        for o in self.Oraux:
            renvoye += "\t"
            renvoye += o.OralType_.Matiere + " de " + str(o.Heure) + " à " + str(o.HeureFin) + " pour " + o.Eleve.Nom + " avec " + o.Jury.Nom
            renvoye += "\n"
        return renvoye

class Jury:
    def __init__(self, Nom, OT, Oraux):
        self.Nom = Nom
        self.OralType_ = OT
        self.Oraux = Oraux

    def copieVide(self):
        newJury = Jury(copy.copy(self.Nom), self.OralType_, [])
        return newJury

    def __str__(self):
        return self.Nom

    def Associer(self, Oral):
        self.Oraux.append(Oral)

    def estDisponible(self, Heure):
        for Oral in self.Oraux:
            if Oral.Heure <= Heure and Oral.HeureFin > Heure:
                return False
            elif Oral.Heure >= Heure and Heure + self.OralType_.Duree > Oral.Heure:
                return False
        return True

class OralType:
    def __init__(self, Matiere, Duree):
        self.Matiere = Matiere
        self.Duree = Duree

class Oral:
    def __init__(self, OT, Jury, Eleve, Heure):
        self.OralType_ = OT
        self.Jury = Jury
        self.Eleve = Eleve
        self.Heure = Heure
        self.HeureFin = Heure + OT.Duree
        self.Duree = OT.Duree

    def __str__(self):
        return self.OralType_.Matiere + " de " + str(self.Heure) + " à " + str(self.HeureFin) + " pour " + self.Eleve.Nom + " avec " + self.Jury.Nom

    def changerHeure(self, nouvelleHeure):
        self.Heure = nouvelleHeure
        self.HeureFin = nouvelleHeure + self.OralType_.Duree

################# FONCTION DE GENERATION / VERIFICATION / ... #####################

def creerEmploiDuTemps(Jurys, Eleves):
    for j in range(len(Jurys)):
        heure = 0
        while not Associes(Eleves, Jurys[j].OralType_):
            AssociesDansCetteBoucle = 0
            for e in range(len(Eleves)):
                if Eleves[e].estDisponible(heure, Jurys[j].OralType_):
                    if Jurys[j].estDisponible(heure):
                        #Création du nouvel objet oral
                        newOral = Oral(Jurys[j].OralType_, Jurys[j], Eleves[e], heure)
                        #Ajout de l'oral à l'élève en cours
                        Eleves[e].Associer(newOral)
                        #Ajout de l'oral au jury en cours
                        Jurys[j].Associer(newOral)

                        #Modification des paramètres de recherche
                        AssociesDansCetteBoucle += 1
                        heure += Jurys[j].OralType_.Duree
                        break #Sortie du for (élèves)
            if AssociesDansCetteBoucle == 0:
                heure += 1

def trouverPermutations(Liste):
    renvoye = []
    ListeTravail = [elt.copieVide() for elt in Liste]
    longueurListe = len(ListeTravail)
    if longueurListe == 0:
        return []
    elif longueurListe == 1:
        return [[ListeTravail[0].copieVide()]]
    for elt in Liste:
        temp = [copy.copy(autre) for autre in Liste if autre is not elt]
        for perm in trouverPermutations(temp):
            renvoye.append([elt.copieVide()] + perm)
    return renvoye

def dureeEmploiDuTemps(Jurys):
    maximum = 0
    for Jury in Jurys:
        for Oral in Jury.Oraux:
            if Oral.HeureFin > maximum:
                maximum = Oral.HeureFin
    return maximum

def Gerard(Jurys):
    '''
    Gerard trouve le dernier oral.
    '''
    maxi = 0
    oralMaxi = None
    juryMaxi = None
    for Jury in Jurys:
        for Oral in Jury.Oraux:
            if Oral.Heure + Jury.OralType_.Duree > maxi:
                maxi = Oral.Heure + Jury.OralType_.Duree
                oralMaxi = Oral
                juryMaxi = Jury
    return maxi, oralMaxi, juryMaxi

def Michel(Eleve, OralADeplacer, Heure, maxHeure):
    '''
    Michel trouve où il peut déplacer l'oral fautif.
    '''
    #A la recherche de l'oral fautif
    fautif = None

    for Oral in Eleve.Oraux:
        if Oral.Heure <= Heure and Oral.HeureFin + Eleve.Pause > Heure:
            fautif = Oral
            break
        elif Oral.Heure >= Heure and Heure + OralADeplacer.OralType_.Duree + Eleve.Pause > Oral.Heure:
            fautif = Oral
            break
    # On a trouvé l'oral fautif !
    #Où peut-on le mettre ?
    nouvelleHeureFautif = 0
    trouve = False
    assert fautif != None, "fautif = none"
    while nouvelleHeureFautif + Oral.Duree < maxHeure and not trouve:
        if Pascal(Eleve, OralADeplacer, Heure, fautif, nouvelleHeureFautif):
            trouve = True
            break
        nouvelleHeureFautif += 1
    Eleve.deplacerOral(OralADeplacer, Heure)
    Eleve.deplacerOral(fautif, nouvelleHeureFautif)

def Pascal(Eleve, OralADeplacer, Heure, OralTrouve, nouvelleHeure):
    '''
    Pascal fait un test : il déplace l'oral qu'on souhaite déplacer à sa nouvelle heure
    puis déplace l'oral qui pose problème à la nouvelleHeure
    Si c'est bon, il renvoie True ; sinon False
    '''
    sauvegarde = OralADeplacer.Heure
    OralADeplacer.changerHeure(Heure)

    if Eleve.estDisponible(nouvelleHeure, OralTrouve.OralType_, True):
        if OralTrouve.Jury.estDisponible(nouvelleHeure):
            aRenvoyer = True
        else:
#           print("Prof pas disponible à " + str(nouvelleHeure))
#           print(OralTrouve.Prof)
            aRenvoyer = False
    else:
#       print("Eleve pas disonible à " + str(nouvelleHeure))
#       print(Eleve)
        aRenvoyer = False
    OralADeplacer.changerHeure(sauvegarde)
    return aRenvoyer


def Thierry(Jury, Oral):
    '''
    Thierry trouve les trous où on peut mettre l'oral par rapport au prof
    '''
    disponible = []
    for i in range(Oral.Heure):
        if Jury.estDisponible(i):
            disponible.append(i)
    return disponible

def Bernard(Jurys):
    '''
    Bernard appelle ses potos pour faire le travail à sa place.
    '''
    maxi, oralMaxi, juryMaxi = Gerard(Jurys)
    HeuresPossiblesProf = Thierry(juryMaxi, oralMaxi)
    for Heure in HeuresPossiblesProf:
        if oralMaxi.Eleve.estDisponible(Heure, oralMaxi.OralType_):
            #bouger l'oral
            oralMaxi.Eleve.deplacerOral(oralMaxi, Heure)
        else:
            #trouver une place libre et mettre l'oral
            Michel(oralMaxi.Eleve, oralMaxi, Heure, maxi)
            return


def creerMeilleurEmploiDuTempsAvecPermutations(Jurys, Eleves):
    meilleurMakespan = -1
    meilleureSerie = ([], [])
    permutations = copy.deepcopy(trouverPermutations(Jurys))
    for permutation in permutations:
        tempEleves = [Eleve.copieVide() for Eleve in Eleves]
        creerEmploiDuTemps(permutation, tempEleves)
        duree = dureeEmploiDuTemps(permutation)
        if duree < meilleurMakespan or meilleurMakespan == -1:
            meilleurMakespan = duree
            meilleureSerie = (permutation, tempEleves, meilleurMakespan)
    return meilleureSerie

def creerEmploiDuTempsSansPermutations(Jurys, Eleves):
    creerEmploiDuTemps(Jurys, Eleves)
    return Jurys, Eleves, dureeEmploiDuTemps(Jurys)

def Associes(Eleves, OralType_):
    for E in Eleves:
        if E.associe(OralType_) == False:
            return False
    return True

############## TESTS ###################


Epreuves = {"Français" : OralType("Français", 4), "Anglais" : OralType("Anglais", 6), "Maths" : OralType("Maths", 4), "Physique" : OralType("Physique", 6)}
Jurys = [Jury("Gugger", Epreuves["Maths"], []), Jury("Demange", Epreuves["Anglais"], []), Jury("Dervieux", Epreuves["Physique"], []), Jury("Astier", Epreuves["Français"], [])]
#Eleves = [Eleve("Thomas", []), Eleve("Benjamin", []), Eleve("Matthis", []), Eleve("Esprit", []), Eleve("Eldred", []), Eleve("Louis-Matis", [])]
Eleves = [Eleve("Thomas", []), Eleve("Benjamin", []), Eleve("Esprit", [])]

#Couleurs jolies pour l'affichage
Couleurs = ['darksalmon', 'mediumaquamarine', 'pink', 'springgreen', 'peru', 'dimgrey', 'brown']




#Génération d'un emploi du temps avec les données du dessus ^
EDT = creerMeilleurEmploiDuTempsAvecPermutations(Jurys, Eleves)
print("Génération d'un emploi du temps pour {} élèves et {} jurys (avec une pause minimale de {} minutes entre chaque épreuve pour les élèves).".format(len(Eleves), len(Jurys), Eleves[0].Pause * 10))
print("Makespan : {} heures, {} minutes".format(minutesVersHeures(EDT[2] * 10)[0], minutesVersHeures(EDT[2] * 10)[1]))
if EDT[2] == max([Oral.Duree for Oral in Epreuves.values()]) * len(Eleves):
    optimal = True
    print("Solution optimale. (Makespan = Makespan_min = t_max * n)")
else:
    optimal = False

if not optimal:
    print("Application de Bernard.")
    compteur = 1
    duree = dureeEmploiDuTemps(EDT[0])
    Bernard(EDT[0])
    dureeBernard = EDT[0]
    while duree != dureeBernard:
        compteur += 1
        Bernard(EDT[0])
        duree = dureeBernard
        dureeBernard = dureeEmploiDuTemps(EDT[0])
    print("Bernard est venu aider " + str(compteur) + " fois !")

print("Affichage de la solution en cours.")

#Génération de la solution optimale en utilisant le parcours d'arbre

#print("Génération de la solution optimale (ça peut prendre du temps...)")
#EDT = solutionOptimale(Eleves, Jurys)
#print("Génération terminée, affichage des résultats.")


#Préparation de l'affichage
#Liste qui contient les rectangles
patches = []
#Pour chaque prof
for Prof in EDT[0]:
    #On utilise cette liste pour obtenir les couleurs associées aux élèves
    temp = copy.deepcopy([e.Eleve.Nom for e in Prof.Oraux])
    temp.sort()
    for oral in Prof.Oraux:
        #On ajoute un rectangle correspondant à la combinaison oral / élève dans patches
        ajouterOral(oral, [Epreuves[k] for k in Epreuves.keys()], Couleurs[temp.index(oral.Eleve.Nom)], patches)
#Affiche la fenêtre graphique
afficher(patches)