# -*- coding: utf-8 -*-
"""
Created on Mon Jul  5 17:10:02 2021

Corrigé du TP Algo gloutons
"""

# =============================================================================
# Imports nécessaires
# =============================================================================

# =============================================================================
# Définition des variables globales
# =============================================================================
#Graph étudié
#A compléter
G = [[0,0,7,-1,1],[5,4,10,3,1],[1,-1,5,5,8],[0,-1,2,7,0],[0,-1,3,9,6]]

# =============================================================================
# Cases voisines accessibles
# =============================================================================
def voisins_possibles(c,grille):
    """
    Cette fonction renvoie la liste des cases voisines de la case c
    dans la grille graph contenant de la nourriture
    (donc tout entier strictement positif). Si aucun voisin n’est possible,
    la fonction renvoie None.
    """
    
    i,j=c[0],c[1]
    if 0<i<len(grille)-1 and 0<j<len(grille)-1: #En dehors des bords
        Lcand=[[i+1,j], [i-1,j], [i,j+1], [i,j-1]]  #Liste des cases voisines
    elif i==0 and 0<j<len(grille)-1: #Première ligne sans les bords
        Lcand=[[i+1,j], [i,j+1], [i,j-1]]
    elif 0<i<len(grille)-1 and j==0 : #Première colonne sans les bords
        #A compléter
        Lcand=[[i+1,j], [i-1,j], [i,j+1]] 
    elif i==len(grille)-1 and 0<j<len(grille)-1: #Dernière ligne sans les bords
        #A compléter
        Lcand=[[i-1,j], [i,j+1], [i,j-1]]
    elif 0<i<len(grille)-1 and j==len(grille)-1: #Dernière colonne sans les bords
        #A compléter
        Lcand=[[i+1,j], [i-1,j], [i,j-1]]
    elif i==0 and j==0: 
        Lcand=[[i+1,j], [i,j+1]]
    elif i==0 and j==len(grille)-1: 
        Lcand=[[i+1,j], [i,j-1]]
    elif i==len(grille)-1 and j==0: 
        Lcand=[[i-1,j], [i,j+1]]
    elif i==len(grille)-1 and j==len(grille)-1: 
        Lcand=[[i-1,j], [i,j-1]]
    Lok=[] #Liste des positions contenant de la nourriture
    #A compléter
    for (i,j) in Lcand:
        if grille[i][j]>0:
            Lok.append([i,j])
    if len(Lok)>0:
        return Lok
    else:
        return None
#Test
print(voisins_possibles([0,0],G))
print(voisins_possibles([0,1],G))
print(voisins_possibles([3,2],G))
print(voisins_possibles([4,0],G))
# =============================================================================
# Sélection de la case voisine
# =============================================================================
def choix_voisin(c,grille):
    """
    voisin(c,G) qui renvoie les coordonnées de la case voisine de c orantl ep lus
    de nourriture, ou l’une de ces cases au hasard au cas ou plusieurs conviennent (on utilisera obligatoirement la
    fonction rd.choice du module random) pour choisir une case dans ce cas). Si jamais le monstre est dans la situation
    ou les cases voisines n’orentd ed en ourriture( doncu niquementd es0 o ud esm urs),l af onctionr enverral av aleur
    None.
    """
    #A compléter
    voisins = voisins_possibles(c,grille) 
    if voisins is None:
        return None
    cmax = voisins[0]
    i,j = cmax
    vmax = grille[i][j]
    for i,j in voisins :
        if grille[i][j] > vmax:
            cmax = [i,j]
            vmax = grille[i][j]            
    return cmax       
   
#Test
print(choix_voisin([0,0],G))
print(choix_voisin([0,1],G))
print(choix_voisin([3,2],G))
print(choix_voisin([4,0],G))
# =============================================================================
# Gavage du monstre
# =============================================================================
def gavage(grille):
    """
    Cette fonction simule le repas du monstre, jusqu'à ce qu'il se retrouve sans nourriture ou bloqué.
    Elle renvoie la quantité de nourriture totale ingérée au cours de l'évolution ainsi que
    le parcours suivi sous forme d'une liste de cases.
    """
    #A compléter
    c = [0,0] #point de départ
    q = 0 #quantité de nouriture
    Lparcours = []
    while True: #structure faire....jusqu'à condition
        Lparcours.append(c) #on ajoute la case au parcours
        q +=grille[c[0]][c[1]] #on ajoute la nourriture
        grille[c[0]][c[1]] = 0 #on actualise le graph
        c = choix_voisin(c,grille) #on cherche le voisin suivant
        if c is None: #si pas de voisin on stop la boucle
            return Lparcours,q
        
#Test        
print(gavage(G))        
        

# =============================================================================
# Allocation salles
# =============================================================================
def allocation(L_cours,Ns):
    L_fin_cours=[-1]*Ns #au départ, les salles ne sont pas occuppées
    L_edt=[[] for _ in range(Ns)] #pas de cours ! pas [[]]*Ns car sinon listes non indépendantes
    icours=0
    while icours<len(L_cours): #icours est l'indice du cours
        cours=L_cours[icours]
        isalle=0 #on commence par regarder la première salle
        while isalle<Ns and L_fin_cours[isalle]>cours[0]: #tant que la salle n'est pas dispo pour ce cours
            isalle+=1 #on va voir la salle suivante
        if isalle==Ns: #si on scanné toutes les salles sans résultat:
            break #Fin boucle et échec de l'algo
        else: #sinon, on affecte le cours à la salle et on met à jour l'horaire de fin de ce cours dans la salle
            L_edt[isalle].append(icours)
            L_fin_cours[isalle]=cours[1]
        icours+=1
    if isalle==Ns:
        return None #on n'a pas pu placer un cours: l'aglo échoue
    else:
        return L_edt

# =============================================================================
# Test          
# =============================================================================
Lcours=[[2,10],[5,7],[7,12],[8,14],[11,15],[15,16]]
Ns=3

print(allocation(Lcours,Ns))