#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 10 22:32:20 2024

@author: phjo
"""

# Projets 18 et 67 du projet Euler

T1 = [[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]
T2 = [[5], [3, 2], [5, 4, 6], [1, 3, 5, 4]]
T3 = [[75], [95, 64], [17, 47, 82], [18, 35, 87, 10], [20, 4, 82, 47, 65],\
      [19, 1, 23, 75, 3, 34], [88, 2, 77, 73, 7, 63, 67],\
      [99, 65, 4, 28, 6, 16, 70, 92], 
      [41, 41, 26, 56, 83, 40, 80, 70, 33],
      [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
      [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
      [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
      [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
      [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
      [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]]
T4 = T3+[[0]*16,[0]*17,[0]*18,[0]*19,[0]*20,[0]*21,[0]*22,[0]*23,[0]*24, [0]*25]

def euler18glouton(T):
    """ Renvoie la somme obtenue pour le triangle T avec l'algorithme glouton """
    # votre code
    return
    
def euler18rec(T, i, j):
    """ Renvoie la plus grande somme depuis T[i][j] (sommet compris) 
    
    >>> euler18rec([[4]], 0, 0)
    4
    
    >>> euler18rec([[2], [3, 1]], 0, 0)
    5
    
    >>> euler18rec([[1], [2, 3], [1, 3, 2]], 1, 1)
    6
    """
    # votre code
    return
    
# Sélection d'activités

Act = [[1, 4], [3, 5], [0, 6], [3, 7], [5, 7], [5, 9], [7, 10], [9, 12], [11, 14]]

def selectionActivités(Act):
    """ En entrée, une liste des activités [h_debut, h_fin]
    supposée triée selon l'heure de fin
    En sortie, la liste des indices des activités sélectionnées
    """
    # votre code
    return

# Allocation de salles

Cours = [[0, 3], [0, 3], [0, 7], [4, 7], [4, 10], [8, 11], [8, 11], [10, 15], [12, 15], [12, 15]]

def allocationSalles(Cours):
    """ en entrée : une liste des cours [h_debut, h_fin]
    en sortie : un tuple (p, L) où p est le nombre de salles nécessaire,
    et L une liste telle que pour tout j, L[j] est la salle attribuée au cours j
    """
    nbSalles, L = 0, [] # initialement aucune salle n'est nécessaire
    n = len(Cours)
    # votre code
    return (nbSalles, L)
            
# retour aux problèmes 18 et 67 du projet Euler

# avec la memoïzation :
def euler18(T):
    memo = {}
    def euler18rec2(i, j):
        # ne pas oublier la condition d'arrêt : nul besoin d'appel récursif pour la dernière ligne
        if (i, j) not in memo:
            # le même traitement que pour euler18rec
            memo[(i, j)] = "à compléter"    
        return memo[(i, j)]
    return euler18rec2(0, 0)

def euler18dynamique(T):
    """ renvoie la plus grande somme depuis le sommet de T.
    Le triangle T sera modifié ici (de sorte que T[i][j] prenne pour valeur
    la plus grande somme depuis T[i][j])"""
    n = len(T)
    # votre code ici
    return T[0][0]