#!/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:
            ...
            
        else :
            C[i][0] = ...
            for j in range(1,p):
                ...
    return C[n-1][p-1]
                
# tests

#avec M1
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:
            ...
            
        else :
            C[i][0] = ...
            for j in range(1,p):
                ...
                
                
                
            
    # 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 = ...
        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] =... 
            elif i==0:  # on traite les bords à part
                remplissage(i,j-1)
                C[i,j] = ...
            elif j == 0:
                ...
                
            else :  # cas général
                ...
                
                
            
    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):
        ...
        
        
        
        
        
        
        
                    
    remplissage(n-1,p-1)   
    
    # On reconstruit ensuite le chemin optimal
    ...
    
    
    return C[n-1][p-1][0], chemin


print(cheminOptimal(M1))

#En utilisant un dictionnaire
def cheminOptimalDico(M):
    ...
    
    
    
                
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')