# importation de quelques fonctions que je vais utiliser
from math import ceil, floor, log, sqrt, log2

# illustration des deux fonction d'arrondi présentées dans le sujet: ceil (arrondi supérieur) et floor (arrondi inférieur)
# arrondi sup.
print(ceil(1.24)) 
print(ceil(2.0))
print(ceil(2))

# arrondi inf.
print(floor(1.24))
print(floor(1.0))
print(floor(1))

# définition d'une fonction simple reprenant strictement la relation énoncée précédemment
def L_n(n):
    """ Calcul le nombre de Lucas L(n) """
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        # petit calcul récursif pour les éléments n ≥ 2
        return L_n(n - 1) + L_n(n - 2)

# Les éléments demandés
[L_n(i) for i in range(2, 8)]

def lucas1(n):
    if n == 0:
        return 2
    phi = (1 + sqrt(5)) / 2
    phi2 = (1 - sqrt(5)) / 2
    return phi**n + phi2**n

# calcul des 8 premières valeurs, comme précédemment
[lucas1(n) for n in range(8)]

def lucas2(n):
    if n == 0:
        return 2
    phi = (1+ sqrt(5)) / 2
    if n % 2 == 0:
        return ceil(phi**n)
    else:
        return floor(phi**n)

# calcul des 8 premières valeurs
[lucas2(n) for n in range(8)]

lucas2(36)

def lucas3(n):
    if n == 0:
        return 2
    if n == 1:
        return 1
    a, b = (2, 1)
    for i in range(n):
        a, b = (b, a + b)
    return a

# calcul des 8 premiers nombrer de Lucas avec cette nouvelle fonction
[lucas3(n) for n in range(8)]

# petit rappel sur l'opérateur  %
print(7 % 3, 8 % 3, 9 % 3)

# k % 2 est à valeur dans {0, 1}, donc 1-2*(k%2) vaudra 1 si k est pair, 1-2=-1 si k est impair
[1 - 2*(k % 2) for k in range(10)]

# l'expression précédente est équivalente à classique (-1)**k
[(-1)**k for k in range(10)]

def lucas4(n):
    if n == 0:
        return (2, 1)
    if n == 1:
        return (1, 3)
    k = n // 2
    u = 1 - 2*(k % 2)
    a, b = lucas4(k)
    if n % 2 == 0:
        return (a**2 - 2*u, a*b - u)
    else:
        return (a*b - u , b*b + 2*u)

# calcul sur les 10 premières valeur entières
[lucas4(k) for k in range(10)]

# n = 3
print(floor(log2(3)))  # il y a un appel récursif

# n = 4
print(floor(log2(4)))  # il y a 2 appels récursifs

def prodMat(M1, M2):
    """ Renvoie le produit de 2 matrice 2x2  """
    return [
        [M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0],
         M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]],
        [M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0],
         M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]]
    ]

# un petit test de la fonction
prodMat([[1, 2], [3, 4]], [[5, 6],[7, 8]])

def puissanceMat(M, p):
    R = [[1, 0], [0, 1]]
    for i in range (p):
        R = prodMat(R, M)
    return R

def puissanceMatRapide(M, n):
    R = [[1, 0], [0, 1]]
    P = M
    while n > 0:
        if n % 2 == 1:
            R = prodMat(R, P)
        P = prodMat(P, P)
        n = n // 2
    return R

def lucas5(n):
    """ calcul le nombre de Lucas en utilisant la représentation matricielle.
        V_n = (L_n, L_n+1) = A^n x V_0
    """
    # initialisation des variables
    V0 = [2, 1]  # (L_0, L_1)
    A = [[0, 1], [1, 1]]
    
    # on calcul V_{n-1} = A^{n-1} x V_0
    A_n = puissanceMatRapide(A, n - 1)  # on s'arrête un grand avant, c'est suffisant
    V_n = [A_n[0][0] * V0[0] + A_n[0][1]*V0[1], A_n[1][0]*V0[0] + A_n[1][1]*V0[1]]
    
    # comme en fait on a calculé V_{n-1}, on prend le deuxième coefficient
    return V_n[1]

lucas5(36)

# importatior de quelques modules pour cette partie, pour les graphiques
%pylab inline

def affiche(liste_intervalles):
    """ fonction qui affiche les graphes d'intervalles.  """
    figure()
    rc('text', usetex=True)
    ylim((-0.25, len(liste_intervalles) - 0.25))
    t_min = min(map(lambda x: x[0], liste_intervalles))
    t_max = max(map(lambda x: x[1], liste_intervalles))
    for i, intervalle in enumerate(liste_intervalles):
        plot(intervalle, [i]*2, "k")
        text(intervalle[0], i + 0.10, "$C_" + str(i) + "$", {'fontsize': 20})

# on défini deux exemples de liste de cours
# exemple 1
intervalles_1 = [[0, 7], [2, 13], [8, 10]]
affiche(intervalles_1)

# exemple 2
intervalles_2 = [[0, 2], [1, 7], [4, 11], [5, 6], [8, 11], [9, 13]]
affiche(intervalles_2)

# version qui utilise peu certains raccoucis du langage python
def insere(l, elt):
    """ Insere elt dans une copie de la liste l et la retourne """
    # l est supposée triée croissante
    idx = 0
    nouvelle_liste = []
    while idx < len(l):
        e = l[idx]
        if e < elt:
            # on ajoute les éléments plus petits
            nouvelle_liste.append(e)
        else:
            break
        idx = idx + 1
    nouvelle_liste.append(elt)  # on ajoute l'élément elt
    nouvelle_liste.extend(l[idx:])  # on complète avec le reste des éléments
    return nouvelle_liste        

# quelques tests pour vérifier que cela fonctionne
insere([], 2)

insere([1, 2, 4, 5], 3)

insere([1, 2, 3, 4, 5], 3) 

insere([1, 2, 3], 0)

# Il n'est pas précisé dans le texte le comportement à adopter si deux listes possèdent le même premier élément

def insereBis(LL, li):
    """ Insere la liste li dans une copie de la liste de liste LL, par rapport au premier élément des listes. """
    # le code est très similaire à celui de la fonction insere précédente.
    idx = 0
    nouvelle_liste = []
    while idx < len(LL):
        e = LL[idx]
        # on compare le premier élément de la liste li et d'une des listes de LL
        if e[0] < li[0]:
            nouvelle_liste.append(e)
        else:
            break
        idx = idx + 1
    nouvelle_liste.append(li)
    nouvelle_liste.extend(LL[idx:])
    return nouvelle_liste
    

# quelques tests
insereBis([], [1, 2])

insereBis([[2, 3, 4], [5, 6, 7]], [3, 4])

insereBis([[4, 5], [5, 6], [6, 7]], [1, 2, 3])

insereBis([[1, 2], [2, 3], [3, 4]], [2, 4])

# par rapport à la description d'un événement, le codage suivant est utilisé :
# la valeur 0 du tuple indique un début de cours, la valeur 1 une fin de cours.

def traduit(liste_intervalles):
    """ Traduit une liste d'intervalles en liste d'événements. """
    liste_evt = []
    for i, intervalle in enumerate(liste_intervalles):
        liste_evt.append([intervalle[0], i, 0])
        liste_evt.append([intervalle[1], i, 1])
    return liste_evt

traduit(intervalles_1)

traduit(intervalles_2)

# pour accélérer un peu, on peut obtenir les événements triés ainsi
sorted(traduit(intervalles_1), key=lambda x: x[0])

sorted(traduit(intervalles_2), key=lambda x: x[0])

# Soit on fait comme juste au dessus avec sorted, soit on le fait à la main
# je pense qu'il est attendu de le faire à la main, surtout avec l'indication d'utiliser insereBis
def agenda(liste_evt):
    result = []
    # on insere les éléments un par un à partir d'une liste vide au départ
    for elt in liste_evt:
        result = insereBis(result, elt)
    return result

# exemple 1
A = traduit(intervalles_1)
print(A)
agenda(A)

# exemple 2
B = traduit(intervalles_2)
agenda(B)

# je prend la version valideD comme fonction de départ
def valideD(agenda):
    c = 0
    for e in agenda:
        c += 1 - 2*e[2]
        if c < 0:
            return False
    return c == 0

# je la modifie pour prendre en compte l'information du nombre d'intersection maximal
def intersection_max(agd):
    c = 0
    m = 0  # le max
    for e in agd:
        c += 1 - 2*e[2]
        m = max(m, c)
        if c < 0:
            return None
    return m

# exemple 1
intersection_max(agenda(A))

# exemple 2
intersection_max(agenda(B))

def nbr_optimal(liste_intervalles):
    evt = traduit(liste_intervalles)
    agd = agenda(evt)
    if valideD(agd):
        return(intersection_max(agd))
    return None

# pour l'exemple 1
nbr_optimal(intervalles_1)

# pour l'exemple 2
nbr_optimal(intervalles_2)

# Premier bémol: conformité pep8, mais bon
# (1): pas d'initialisation de la variable "i"
# (2): la boucle va faire une erreur pour l'après dernier élément. En effet, le test liste[i] est effectué en premier
#      et donc si on a débordé, il y aura une erreur immédiatemente, sans même faire le deuxiène test. En inversant les
#      deux tests c'est bon
# (3): le test liste[i] est inversé: il faut boucler tant que le contenu est False
# (4): erreur de confusion "=" (affectation) et "==" (test)
#
# on obtient au final:
def plus_petit_vrai(liste):
    n = len(liste)
    i = 0
    while (i < n) and not liste[i]:
        i += 1
    if i == n:
        return -1
    else:
        return i

# Quelques tests
plus_petit_vrai([True, True])

plus_petit_vrai([False, False])

plus_petit_vrai([])

plus_petit_vrai([False, True])

plus_petit_vrai([True, False])

def allocation(liste_intervalles):
    """ retourne le numéro de la salle allouée au cours i. """
    nb_cours = len(liste_intervalles)
    liste = agenda(traduit(liste_intervalles))
    nb_salles = nbr_optimal(liste_intervalles)  # nb salle max
    salles_dispos = [True] * nb_salles
    alloc = [-1] * nb_cours
    for l in liste:
        if l[2] == 0:
            alloc[l[1]] = plus_petit_vrai(salles_dispos)  # on cherche la première salle dispo
            salles_dispos[plus_petit_vrai(salles_dispos)] = False  # on l'occupe (plus disponible)
        else:
            salles_dispos[alloc[l[1]]] = True  # le cours est fini, on rend disponible la salle 
    return alloc

# pour l'exemple 1
allocation(intervalles_1)

# pour l'exemple 2
allocation(intervalles_2)

def affiche_allocation(liste_intervalles):
    """ fonction qui va afficher l'allocation de salle, chaque salle a une couleur dédiée. """
    # attention, pas plus de 8 salles, sinon il faudrait des couleurs supplémentaires
    rc('text', usetex=True)
    nbr_o = nbr_optimal(liste_intervalles)
    ylim((-0.25, len(liste_intervalles) - 0.25))
    allocations = allocation(liste_intervalles)
    couleurs = list(zip(range(nbr_o), ['b', 'g', 'r', 'c', 'm', 'y', 'k', 'w']))
    t_min = min(map(lambda x: x[0], liste_intervalles))
    t_max = max(map(lambda x: x[1], liste_intervalles))
    for i, intervalle in enumerate(liste_intervalles):
        plot(intervalle, [i]*2, couleurs[allocations[i]][1])
        text(intervalle[0], i+0.10, "$C_" + str(i)+"$", {'fontsize': 20})

# Pour l'exemple 1
affiche_allocation(intervalles_1)

# pour l'exemple 2
affiche_allocation(intervalles_2)