#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Nov 16 16:54:52 2022

@author: vincentleprince
"""

import matplotlib.pyplot as plt
import numpy as np 
import random as rd


#Création d'un tableau aléatoire et affichage de l'image le représentant
n , p = 10, 10

M = np.zeros((n,p),dtype = np.uint8)
for i in range(n):
    for j in range(p):
        M[i,j] = rd.randint(0,255)
        
        
plt.imshow(M,cmap='gray')    

#pour tester les programmes sur un exemple simple :
M1 = np.array([[1,2,3,3],
               [1,1,4,4],
               [1,1,1,4],
               [3,2,1,2]])

plt.imshow(M1,cmap='gray')   

# stratégie de bas en haut (fonction basée sur un algorithme itératif)
# On définit une liste de listes destinée à contenir, pour chaque  case i,j ,  
#le  cout min et le  couple précédent i,j sur le chemin de cout min

def coutOptimalIter(M):
    """version sans le chemin"""
    n , p = np.shape(M)
    C = [[0 for j in range(p)] for i in range(n)]
    C[0][0] = M[0,0] 

    for i in range(0,n):
        if i == 0:
            for j in range(1,p):
                C[i][j] = C[i][j-1] + M[i,j]  
            
        else :
            C[i][0] = C[i-1][0] + M[i,0] 
            for j in range(1,p):
                C[i][j] = min( C[i-1][j],C[i][j-1] )+ M[i,j]
    return C[n-1][p-1]
                
print(coutOptimalIter(M1))



def cheminOptimalIter(M):
    n , p = np.shape(M)
    C = [[0 for j in range(p)] for i in range(n)]
    C[0][0] = [M[0,0] , None] # pas de prédécesseur ici

    for i in range(0,n):
        if i == 0:
            for j in range(1,p):
                C[i][j] = [ C[i][j-1][0] + M[i,j] , (i,j-1)]
        else :
            C[i][0] = [ C[i-1][0][0] + M[i,0] , (i-1,0)]
            for j in range(1,p):
                if C[i-1][j][0] < C[i][j-1][0]:
                    C[i][j] = [ C[i-1][j][0] + M[i,j] , (i-1,j)]
                else:
                    C[i][j] = [ C[i][j-1][0] + M[i,j] , (i,j-1)]
            
    # On reconstruit ensuite le chemin optimal
    i , j = n-1 , p-1 # on part de la case d'arrivée
    chemin = [(i,j)]
    while not ( (i,j) == (0,0) ):
        i , j = C[i][j][1]
        chemin.append((i,j)) 
    chemin.reverse()
    return C[n-1][p-1][0], chemin



    
# tests

#avec M1
print(cheminOptimalIter(M1))

#tracé avec un tableau aléatoire
n , p = 100 , 100
M2 = np.zeros((n,p),np.uint8)
for i in range(n):
    for j in range(p):
        M2[i,j] = rd.randint(0,255)

M2_avec_chemin = M2.copy()
chemin = cheminOptimalIter(M2)[1]
for case in chemin:
    i , j = case
    M2_avec_chemin[i,j] = 0
    
plt.imshow(M2_avec_chemin,cmap='gray')     

#résolution par mémo¨isation

def coutOptimal(M):
    n , p = np.shape(M)
    C = np.zeros((n,p))
    for i in range(n):
        for j in range(p):
            C[i,j] = -1   # -1 signale une case non visitée 
        
    def remplissage(i,j):
        if C[i,j] == -1:
            if i==0 and j==0:
                C[i,j] = M[i,j]
            elif i==0:  # on traite les bords à part
                remplissage(i,j-1)
                C[i,j] = C[i,j-1] + M[i,j]
            elif j == 0:
                remplissage(i-1,j)
                C[i,j] = C[i-1,j] + M[i,j]
            else :  # cas général
                remplissage(i-1,j)
                remplissage(i,j-1)
                C[i,j] = min(C[i-1,j],C[i,j-1]) + M[i,j]
            
    remplissage(n-1,p-1)   
    
    return C[n-1,p-1]

print(coutOptimal(M1))

def cheminOptimal(M):
    n , p = np.shape(M)
    C = [[[-1,None] for j in range(p)] for i in range(n)]
    
    def remplissage(i,j):
        if C[i][j][0] == -1:
            if i==0 and j==0:
                C[i][j][0] = M[i,j] # on laisse C[i][j][1] à None
            elif i == 0:
                remplissage(i,j-1)
                C[i][j] = [ C[i][j-1][0] + M[i,j] , [i,j-1]]
            elif j == 0:
                remplissage(i-1,j)
                C[i][j] = [ C[i-1][j][0] + M[i,j] , [i-1,j] ]
                
            else :
                remplissage(i-1,j)
                remplissage(i,j-1)
                
                if C[i-1][j][0]<C[i][j-1][0] :
                    C[i][j] =  [ C[i-1][j][0] + M[i,j] , [i-1,j] ]
                    
                else:
                    C[i][j] = [ C[i][j-1][0] + M[i,j] , [i,j-1]]
                    
    remplissage(n-1,p-1)   
    
    # On reconstruit ensuite le chemin optimal
    i , j = n-1 , p-1 # on part de la case d'arrivée
    chemin = [[i,j]]
    while not ( [i,j] == [0,0] ):
        i , j = C[i][j][1]
        chemin.append([i,j]) 
    chemin.reverse()
    return C[n-1][p-1][0], chemin


print(cheminOptimal(M1))

#En utilisant un dictionnaire
def cheminOptimalDico(M):
    n , p = np.shape(M)
    dico = {}
    
    def remplissage(i,j):
        if not (i,j) in dico:
            if (i,j) == (0,0):
                dico[(i,j)] = [M[i,j] , None]
            elif i == 0:
                remplissage(i,j-1)
                dico[(i,j)] = [dico[(i,j-1)][0] + M[i,j] , (i,j-1)]
                
            elif j == 0:
                remplissage(i-1,j)
                dico[(i,j)] = [dico[(i-1,j)][0] + M[i,j] , (i-1,j)]
                
            else :
                remplissage(i-1,j)
                remplissage(i,j-1)
                
                if dico[(i-1,j)][0]<dico[(i,j-1)][0] :
                    dico[(i,j)] =  [ dico[(i-1,j)][0] + M[i,j] , (i-1,j) ]
                    
                else:
                    dico[(i,j)] = [ dico[(i,j-1)][0]+ M[i,j] , (i,j-1)]
                    
    remplissage(n-1,p-1)   
    
    # On reconstruit ensuite le chemin optimal
    i , j = n-1 , p-1 # on part de la case d'arrivée
    chemin = [(i,j)]
    while not ( (i,j) == (0,0) ):
        i , j = dico[(i,j)][1]
        chemin.append((i,j)) 
    chemin.reverse()
    return dico[(n-1,p-1)][0], chemin
                
print(cheminOptimalDico(M1))

# tracé

#avec M1
M1_avec_chemin = M1.copy()
chemin = cheminOptimal(M1)[1]
for case in chemin:
    i , j = case
    M1_avec_chemin[i,j] = 0
    
plt.imshow(M1_avec_chemin,cmap='gray')    

#avec un tableau aléatoire
n , p = 100 , 100
M2 = np.zeros((n,p),np.uint8)
for i in range(n):
    for j in range(p):
        M2[i,j] = rd.randint(0,255)

M2_avec_chemin = M2.copy()
chemin = cheminOptimal(M2)[1]
for case in chemin:
    i , j = case
    M2_avec_chemin[i,j] = 0
    
plt.imshow(M2_avec_chemin,cmap='gray')