#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Dec 10 22:40:13 2025

@author: vincentleprince
"""

Lgrille = [[5,3,7,3,2],[4,1,6,2,3],[3,2,3,4,5]]





def scoreParcours(Lgrille,lparcours):
    p = len(lparcours) # on peut aussi utiliser p = len(Lgrille[0])
    s = 0
    for i in range(p):
        s += Lgrille[lparcours[i]][i]
    return s


lparcours = [2,1,1,0,1]
print(scoreParcours(Lgrille,lparcours))



        
        

def scoreMaxGlouton(L):
    n , p = len(L) , len(L[0])
    score , lparcours = 0 , []
    # On détermine la ligne contenant le poids max dans la première colonne
    iMax , poidsMax = 0 , L[0][0]
    for i in range(1,n):
        if L[i][0] > poidsMax:
            iMax , poidsMax = i , L[i][0]
            
    score += poidsMax
    lparcours.append(iMax)
    # On parcourt ensuite la grille de gauche à droite
    # Si à l'étape j-1 on se trouve au niveau i,
    # à l'étape j on pourra se trouver au niveau i, i-1 ou i+1
    # (si ces niveaux sont valables)
    for j in range(1,p):
        iMaxSuivant , poidsMax = iMax , L[iMax][j]
        if iMax - 1 >= 0 and L[iMax - 1][j] > poidsMax:
            iMaxSuivant , poidsMax = iMax-1 , L[iMax-1][j]
        if iMax + 1 < n and L[iMax + 1][j] > poidsMax:
            iMaxSuivant , poidsMax = iMax+1 , L[iMax+1][j]
        iMax = iMaxSuivant
        score += poidsMax
        lparcours.append(iMax)
    return score , lparcours

print(scoreMaxGlouton(Lgrille))
            
    

        

def scoreMaxRecPart(L,i,j):
    n , p = len(L) , len(L[0])
    if j == p-1:
        return  L[i][j]
    else:
        # on recherche le score max parmi les trois (ou 2) successeurs de (i,j)
        # en effectuant un appel récursif à cette fonction pour chaque successeur
        scoreMax = scoreMaxRecPart(L,i,j+1)
        if i-1 >= 0: 
            score = scoreMaxRecPart(L,i-1,j+1)
            if score > scoreMax:
                scoreMax = score
        if i+1 < n:
            score = scoreMaxRecPart(L,i+1,j+1)
            if score > scoreMax:
                scoreMax = score
        return scoreMax + L[i][j]
    
print(scoreMaxRecPart(Lgrille,0,4))
print(scoreMaxRecPart(Lgrille,0,3))

print(scoreMaxRecPart(Lgrille,0,0))
print(scoreMaxRecPart(Lgrille,1,0))
print(scoreMaxRecPart(Lgrille,2,0))

def scoreMaxRec(L):
    n , p = len(L) , len(L[0])
    sMax = scoreMaxRecPart(L,0,0)
    for i in range(1,n):
        score = scoreMaxRecPart(L,i,0)
        if score > sMax:
            sMax = score
    return sMax

print(scoreMaxRec(Lgrille))



def grilleZeros(Lgrille):
    n , p = len(Lgrille) , len(Lgrille[0])
    return [[0 for j in range(p)] for i in range(n)]

    
def remplitLscore(L,Lscore,i,j):
    n , p = len(L) , len(L[0])
    if Lscore[i][j] == 0:
        if j == p-1:
            Lscore[i][j] = L[i][j]
        else : 
            remplitLscore(L,Lscore,i,j+1)
            scoreMax = Lscore[i][j+1] 
            if i-1 >= 0:
                remplitLscore(L,Lscore,i-1,j+1)
                if Lscore[i-1][j+1] > scoreMax:
                    scoreMax = Lscore[i-1][j+1]
            if i+1 < n :
                remplitLscore(L,Lscore,i+1,j+1)
                if Lscore[i+1][j+1] > scoreMax:
                    scoreMax = Lscore[i+1][j+1]
            Lscore[i][j] = scoreMax + L[i][j]
                    
# test

n , p = len(Lgrille) , len(Lgrille[0])
Lscore = [[0 for j in range(p)] for i in range(n)]
remplitLscore(Lgrille,Lscore,1,2)    
print(Lscore[1][2])         
                
def scoreMaxMemo(L):
    n , p = len(L) , len(L[0])
    Lscore = grilleZeros(L)
    remplitLscore(Lgrille,Lscore,0,0)  
    scoreMax = Lscore[0][0]
    for i in range(1,n):
        remplitLscore(Lgrille,Lscore,i,0)  
        if Lscore[i][0] > scoreMax:
            scoreMax = Lscore[i][0]
    return scoreMax 

#test
print(scoreMaxMemo(Lgrille))


"""Programmation dynamique"""

def indMaxDisqueSuivant(Lscore,i,j):
    n , p = len(Lscore) , len(Lscore[0]) 
    if i == 0:
        if Lscore[1][j+1] > Lscore[0][j+1] :
            return 1
        else :
            return 0
    elif i == n-1:
        if Lscore[n-2][j+1] > Lscore[n-1][j+1] :
            return  n-2 
        else :
            return  n-1 
    else:
        scoreMax , indMax = Lscore[i][j+1] , i
        for d in [-1,1] :
            if Lscore[i+d][j+1] > scoreMax:
                scoreMax  , indMax  = Lscore[i+d][j+1] , i+d
        return indMax
        
        
    
 
 
def LscoreProgDyn(L):
    n , p = len(L) , len(L[0])
    Lscore = grilleZeros(L)
    for i in range(n):
        Lscore[i][p-1] =  L[i][p-1]
    j = p-2
    while j >= 0:
        for i in range(0,n):
            indMax = indMaxDisqueSuivant(Lscore,i,j)
            Lscore[i][j] = Lscore[indMax][j+1] + L[i][j]
        j -= 1
    return Lscore
            
print(LscoreProgDyn(Lgrille))        
                
         
     
 
def scoreMaxProgDyn(L):
    n , p = len(L) , len(L[0])
    Lscore = LscoreProgDyn(L)
    scoreMax = Lscore[0][0]
    for i in range(1,n):
        if Lscore[i][0] > scoreMax:
            scoreMax = Lscore[i][0]
    return scoreMax
    
        
print(scoreMaxProgDyn(Lgrille)) 

 


def LscoreLsuivProgDyn(L):
    n , p = len(L) , len(L[0])
    Lsuiv = grilleZeros(L)
    Lscore = grilleZeros(L)
    for i in range(n):
        Lscore[i][p-1] = L[i][p-1]
        Lsuiv[i][p-1] =   None  
    j = p-2
    while j >= 0:
        for i in range(0,n) :
            indMax = indMaxDisqueSuivant(Lscore,i,j) 
            Lscore[i][j] = Lscore[indMax][j+1] + L[i][j]
            Lsuiv[i][j] =   indMax
        j -= 1
    return Lscore , Lsuiv
            
print(LscoreLsuivProgDyn(Lgrille))  


def ParcoursMaxiProgDyn(L):
    n , p = len(L) , len(L[0])
    Lscore , Lsuiv = LscoreLsuivProgDyn(L) 
    # On recherche tout d'abord le niveau du disque de la colonne 0
    # où le score est maximal : 
    #ce sera le point de départ de notre parcours
    scoreMax , indMax = Lscore[0][0]  , 0
    for i in range(1,n):
        if Lscore[i][0]  > scoreMax :
            scoreMax , indMax = Lscore[i][0]  , i
    # On reconstruit ensuite le parcours
    indParcours = indMax
    lParcours = [indParcours]
    for j in range(0,p-1):
        indParcours = Lsuiv[indParcours][j] 
        lParcours.append(indParcours)
    return lParcours

print(ParcoursMaxiProgDyn(Lgrille))