# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# + hide_input=false pycharm={"name": "#%%\n"}
from IPython.core.display import display, HTML, Markdown
from ipywidgets import Button, HBox, VBox, widgets, Layout
from tabulate import tabulate
import copy

# + hide_input=false pycharm={"name": "#%%\n"}
campo_minato = [
         [ 0 , 2 , 3 , 1 , 1 , 3 , 4 , 7 ,-1 ],
         [ 2 , 1 ,-1 , 2 ,-1 ,-1 , 7 , 1 , 2 ],
         [ 4 ,-1 , 2 , 3 , 7 , 1 , 1 , 5 , 4 ],
         [ 5 , 1 ,-1 , 4 , 5 ,-1 , 9 , 3 , 6 ],
         [ 1 , 3 , 3 ,-1 , 3 , 1 , 1 ,10 , 8 ],
         [ 1 , 4 ,-1 , 5 ,-1 , 3 , 1 , 8 , 9 ],
         [ 7 , 5 , 2 ,-1 , 2 , 2 , 3 , 4 , 0 ],
        ]

m = len(campo_minato)
n = len(campo_minato[0])
#mappa = [ [-1]*(n+1) ] + [ ([-1] + r) for r in campo_minatomappa = [ [-1]*(n+1) ] + [ ([-1] + r) for r in campo_minato#]
mappa = [["*"]*(n+1)]
for r in campo_minato:
    aux=["*"]
    for elem in r:
        aux.append("*") if elem==-1 else aux.append(elem)
    mappa.append(aux)


# + hide_input=true
def visualizza(env):
    if len(env)==m+1 and len(env[0])==n+1:
        index=[chr(65+i) for i in range(m)]
        aux=[r[1:] for r in env[1:]]
        

    if len(env)==m+2 and len(env[0])==n+2:
        index=[chr(65+i) for i in range(m)]
        aux=[r[1:-1] for r in env[1:-1]]
        
    for i in range(len(aux)):
        for j in range(len(aux[0])):
            if aux[i][j] is None:
                aux[i][j]="x"

    columns=[str(i) for i in range(1,n+1)]
    print(tabulate(aux, headers=columns, tablefmt='fancy_grid', showindex=index))
        
def evaluation_format(answ, pt_green,pt_red):
    pt_blue=0
    if pt_green!=0:
        pt_blue=pt_red-pt_green
        pt_red=0
    return f"{answ}. Totalizzeresti <span style='color:green'>[{pt_green} safe pt]</span>, \
                                    <span style='color:blue'>[{pt_blue} possible pt]</span>, \
                                    <span style='color:red'>[{pt_red} out of reach pt]</span>.<br>"

def check_num_gems_to(mappa, num_gems_to, return_only_boolan=False):
    """
    verifica che la matrice num_gems_to sia conforme alla consegna (perdonando solamente eventuale anomalia su cella (1,1) ).
    """
    if len(num_gems_to) != m+1:
        if return_only_boolan:
                return False
        return evaluation_format("No", 0, 10)+f"Le righe della matrice $num\_gems\_to$ devono essere $m+1=${m+1}, non {len(num_gems_to)}."
    if len(num_gems_to[0]) != n+1:
        if return_only_boolan:
                return False
        return evaluation_format("No", 0, 10)+f"Le colonne della matrice $num\_gems\_to$ devono essere $n+1=${n+1}, non {len(num_gems_to[0])}."
        
    for i in range (0,m):
        if num_gems_to[i][0]!=0:
            if return_only_boolan:
                return False
            return evaluation_format("No", 0, 10)+f"Attenzione, la raccolta delle gemme deve partire dalla cella $(1,1)$ e pertanto $num\_gems\_to[${i}$][0] = 0$"
    for j in range (0,n):
        if num_gems_to[0][j]!=0:
            if return_only_boolan:
                return False
            return evaluation_format("No", 0, 10)+f"Attenzione, la raccolta delle gemme deve partire dalla cella $(1,1)$ e pertanto $num\_gemss\_to[0][${j}$] = 0$"
    num_gems_to_forgiving = copy.deepcopy(num_gems_to)
    num_gems_to_forgiving[1][1] = 0
    for i in range(m,0,-1):
        for j in range (n,0,-1):
            if i==1 and j==1:
                if return_only_boolan:
                    return True
                return  evaluation_format("Si", 10, 10)+"Non riscontro particolari problemi della tua versione della matrice $num\_gems\_to$."
            if mappa[i][j]=="*" or (num_gems_to_forgiving[i][j-1] is None and num_gems_to_forgiving[i-1][j] is None):
                if num_gems_to_forgiving[i][j] is not None:
                    if return_only_boolan:
                        return False
                    return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $num\_gems\_to$."
            else:
                if num_gems_to_forgiving[i][j]!=max((num_gems_to_forgiving[i-1][j] if num_gems_to_forgiving[i-1][j] is not None else 0),(num_gems_to_forgiving[i][j-1] if num_gems_to_forgiving[i][j-1] is not None else 0)) + mappa[i][j]:
                    if return_only_boolan:
                        return False
                    return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $num\_gems\_to$."
                
def check_max_gems_to(mappa, max_gems_to, return_only_boolan=False):
    """
    verifica che la matrice max_gems_to_with_opt sia conforme alla consegna.
    """
    if len(max_gems_to) != m+1:
        if return_only_boolan:
                return False
        return evaluation_format("No", 0, 10)+f"Le righe della matrice $max\_gems\_to$ devono essere $m+1=${m+1}, non {len(max_gems_to)}."
    if len(max_gems_to[0]) != n+1:
        if return_only_boolan:
                return False
        return evaluation_format("No", 0, 10)+f"Le colonne della matrice $max\_gems\_to$ devono essere $n+1=${n+1}, non {len(max_gems_to[0])}."
        
    for i in range (0,m):
        if max_gems_to[i][0][0]!=0:
            if return_only_boolan:
                return False
            return evaluation_format("No", 0, 10)+f"Attenzione, la raccolta delle gemme deve partire dalla cella $(1,1)$ e pertanto $max\_gems\_to\_with\_opt[${i}$][0] = 0$"
    for j in range (0,n):
        if max_gems_to[0][j][0]!=0:
            if return_only_boolan:
                return False
            return evaluation_format("No", 0, 10)+f"Attenzione, la raccolta delle gemme deve partire dalla cella $(1,1)$ e pertanto $max\_gems\_to[0][${j}$] = 0$"
    max_gems_to_forgiving = copy.deepcopy(max_gems_to)
    max_gems_to_forgiving[1][1] = (0,1)
    for i in range(m,0,-1):
        for j in range (n,0,-1):
            if i==1 and j==1:
                if return_only_boolan:
                    return True
                return  evaluation_format("Si", 10, 10)+"Non riscontro particolari problemi della tua versione della matrice $max\_gems\_to$."
            if mappa[i][j]=="*" or (max_gems_to_forgiving[i][j-1] is None and max_gems_to_forgiving[i-1][j] is None):
                if max_gems_to_forgiving[i][j] is not None:
                    if return_only_boolan:
                        return False
                    return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_to$."
            else:
                if max_gems_to_forgiving[i][j][0]!=max((max_gems_to_forgiving[i-1][j][0] if max_gems_to_forgiving[i-1][j] is not None else 0),(max_gems_to_forgiving[i][j-1][0] if max_gems_to_forgiving[i][j-1] is not None else 0)) + mappa[i][j]:
                        if return_only_boolan:
                            return False
                        return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_to$."
                
                if max_gems_to_forgiving[i-1][j] is None:
                    if max_gems_to_forgiving[i][j][1]!=max_gems_to_forgiving[i][j-1][1]:
                        if return_only_boolan:
                            return False
                        return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_to$."
                elif max_gems_to_forgiving[i][j-1] is None:
                    if max_gems_to_forgiving[i][j][1]!=max_gems_to_forgiving[i-1][j][1]:
                        if return_only_boolan:
                            return False
                        return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_to$."
                else:
                    if max_gems_to_forgiving[i-1][j][0]==max_gems_to_forgiving[i][j-1][0]:
                        if max_gems_to_forgiving[i][j][1]!=max_gems_to_forgiving[i-1][j][1]+max_gems_to_forgiving[i][j-1][1]:
                            if return_only_boolan:
                                return False
                            return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_to$."
                    elif max_gems_to_forgiving[i-1][j][0]>max_gems_to_forgiving[i][j-1][0]:
                        if max_gems_to_forgiving[i][j][1]!=max_gems_to_forgiving[i-1][j][1]:
                            if return_only_boolan:
                                return False
                            return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_to$."
                    else:
                        if max_gems_to_forgiving[i][j][1]!=max_gems_to_forgiving[i][j-1][1]:
                            if return_only_boolan:
                                return False
                            return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_to$."
                                         
def check_num_gems_from(mappa, num_gems_from, return_only_boolan=False):
    """
    verifica che la matrice num_gems_from sia conforme alla consegna.
    """
    if len(num_gems_from) != m+2:
        if return_only_boolan:
                return False
        return evaluation_format("No", 0, 10)+f"Le righe della matrice $num\_gems\_from$ devono essere $m+2=${m+2}, non {len(num_gems_from)}."
    if len(num_gems_from[0]) != n+2:
        if return_only_boolan:
                return False
        return evaluation_format("No", 0, 10)+f"Le colonne della matrice $num\_gems\_from$ devono essere $n+2=${n+2}, non {len(num_gems_from[0])}."
        
    for i in range (0,m+1):
        if num_gems_from[i][n+1]!=0:
            if return_only_boolan:
                return False
            return evaluation_format("No", 0, 10)+f"Attenzione, la raccolta delle gemme deve partire dalla cella $({m},{n})$ e pertanto $num\_gems\_from[${i}$][${n}$] = 0$"
    for j in range (0,n+1):
        if num_gems_from[m+1][j]!=0:
            if return_only_boolan:
                return False
            return evaluation_format("No", 0, 10)+f"Attenzione, la raccolta delle gemme deve partire dalla cella $({m},{n})$ e pertanto $num\_gems\_from[${m}$][${j}$] = 0$"
    num_gems_from_forgiving = copy.deepcopy(num_gems_from)
    num_gems_from_forgiving[m][n] = 0
    for i in range(1,m):
        for j in range (1,n):
            if mappa[i][j]=="*" or (num_gems_from_forgiving[i][j+1] is None and num_gems_from_forgiving[i+1][j] is None):
                if num_gems_from_forgiving[i][j] is not None:
                    if return_only_boolan:
                        return False
                    return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $num\_gems\_from$."
            else:
                if num_gems_from_forgiving[i][j]!=max((num_gems_from_forgiving[i+1][j] if num_gems_from_forgiving[i+1][j] is not None else 0),(num_gems_from_forgiving[i][j+1] if num_gems_from_forgiving[i][j+1] is not None else 0)) + mappa[i][j]:
                    if return_only_boolan:
                        return False
                    return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $num\_gems\_from$." 
    if return_only_boolan:
        return True
    return  evaluation_format("Si", 10, 10)+"Non riscontro particolari problemi della tua versione della matrice $num\_gems\_from$."


def check_max_gems_from(mappa, max_gems_from, return_only_boolan=False):
    """
    verifica che la matrice max_gems_from_with_opt sia conforme alla consegna.
    """
    if len(max_gems_from) != m+2:
        if return_only_boolan:
                return False
        return evaluation_format("No", 0, 10)+f"Le righe della matrice $max\_gems\_from$ devono essere $m+2=${m+2}, non {len(max_gems_from)}."
    if len(max_gems_from[0]) != n+2:
        if return_only_boolan:
                return False
        return evaluation_format("No", 0, 10)+f"Le righe della matrice $max\_gems\_from$ devono essere $m+2=${m+2}, non {len(max_gems_from)}."
    
    for i in range (0,m+1):
        if max_gems_from[i][n+1]!=(0,0):
            if return_only_boolan:
                return False
            return evaluation_format("No", 0, 10)+f"Attenzione, la raccolta delle gemme deve partire dalla cella $({m},{n})$ e pertanto $max\_gems\_from[${i}$][${n}$] = 0$"
    for j in range (0,n+1):
        if max_gems_from[m+1][j]!=(0,0):
            if return_only_boolan:
                return False
            return evaluation_format("No", 0, 10)+f"Attenzione, la raccolta delle gemme deve partire dalla cella $({m},{n})$ e pertanto $max\_gems\_from[${m}$][${j}$] = 0$"
    
    max_gems_from_forgiving = copy.deepcopy(max_gems_from)
    max_gems_from_forgiving[m][n] = (0,1)
    for i in range(1,m):
        for j in range (1,n):         
            if mappa[i][j]=="*" or (max_gems_from_forgiving[i][j+1] is None and max_gems_from_forgiving[i+1][j] is None):
                if max_gems_from_forgiving[i][j] is not None:
                    if return_only_boolan:
                        return False
                    return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_from$."
            else:
                if max_gems_from_forgiving[i][j][0]!=max((max_gems_from_forgiving[i+1][j][0] if max_gems_from_forgiving[i+1][j] is not None else 0),(max_gems_from_forgiving[i][j+1][0] if max_gems_from_forgiving[i][j+1] is not None else 0)) + mappa[i][j]:
                        if return_only_boolan:
                            return False
                        return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_from$."
                
                if max_gems_from_forgiving[i+1][j] is None:
                    if max_gems_from_forgiving[i][j][1]!=max_gems_from_forgiving[i][j+1][1]:
                        if return_only_boolan:
                            return False
                        return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_from$."
                elif max_gems_from_forgiving[i][j+1] is None:
                    if max_gems_from_forgiving[i][j][1]!=max_gems_from_forgiving[i+1][j][1]:
                        if return_only_boolan:
                            return False
                        return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_from$."
                else:
                    if max_gems_from_forgiving[i+1][j][0]==max_gems_from_forgiving[i][j+1][0]:
                        if max_gems_from_forgiving[i][j][1]!=max_gems_from_forgiving[i+1][j][1]+max_gems_from_forgiving[i][j+1][1]:
                            if return_only_boolan:
                                return False
                            return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_from$."
                    elif max_gems_from_forgiving[i+1][j][0]>max_gems_from_forgiving[i][j+1][0]:
                        if max_gems_from_forgiving[i][j][1]!=max_gems_from_forgiving[i+1][j][1]:
                            if return_only_boolan:
                                return False
                            return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_from$."
                    else:
                        if max_gems_from_forgiving[i][j][1]!=max_gems_from_forgiving[i][j+1][1]:
                            if return_only_boolan:
                                return False
                            return  evaluation_format("No", 0, 10)+"Ti avviso: riscontro dei problemi nella tua versione della matrice $max\_gems\_from$."                
    if return_only_boolan:
                return True
    return  evaluation_format("Si", 10, 10)+"Non riscontro particolari problemi della tua versione della matrice $max\_gems\_from$."     

def Latex_type(string):
    return string.replace("_", "\_")

def visualizza_e_valuta(nome_matrice, matrice):
    display(Markdown(f"La tua versione attuale della matrice ${Latex_type(nome_matrice)}$ è la seguente:"))
    visualizza(matrice)
    display(Markdown(f"<b>Validazione della tua matrice ${Latex_type(nome_matrice)}$:</b>"))
    display(Markdown(eval(f"check_{nome_matrice}(mappa,matrice)"))) 


# +
#unit test
num_gems_to=[
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
                [0, 0, 2, 5, 6, 7, 10, 14, 21, None], 
                [0, 2, 3, None, 8, None, None, 21, 22, 24], 
                [0, 6, None, None, 11, 18, 19, 22, 27, 31], 
                [0, 11, 12, None, 15, 23, None, 31, 34, 40], 
                [0, 12, 15, 18, None, 26, 27, 32, 44, 52], 
                [0, 13, 19, None, None, None, 30, 33, 52, 61], 
                [0, 20, 25, 27, None, None, 32, 36, 56, 61]
            ]

num_gems_from=[
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
                [0, 61, 61, 59, 56, 55, 54, 51, 43, None, 0], 
                [0, 27, None, None, 53, None, None, 47, 36, 29, 0], 
                [0, 25, None, 53, 51, 48, 41, 40, 35, 27, 0], 
                [0, 21, 15, None, 41, 37, None, 39, 30, 23, 0], 
                [0, 16, 14, None, None, 32, 29, 28, 27, 17, 0], 
                [0, 15, 11, None, None, None, 21, 18, 17, 9, 0], 
                [0, 14, 7, 2, None, 11, 9, 7, 4, 0, 0], 
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
               ]

max_gems_to=[
                [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)], 
                [(0, 0), (0, 0), (2, 1), (5, 1), (6, 1), (7, 1), (10, 1), (14, 1), (21, 1), None], 
                [(0, 0), (2, 1), (3, 2), None, (8, 1), None, None, (21, 1), (22, 2), (24, 2)], 
                [(0, 0), (6, 1), None, None, (11, 1), (18, 1), (19, 1), (22, 1), (27, 3), (31, 3)], 
                [(0, 0), (11, 1), (12, 1), None, (15, 1), (23, 1), None, (31, 1), (34, 1), (40, 1)], 
                [(0, 0), (12, 1), (15, 2), (18, 2), None, (26, 1), (27, 1), (32, 1), (44, 1), (52, 1)], 
                [(0, 0), (13, 1), (19, 2), None, None, None, (30, 1), (33, 1), (52, 1), (61, 2)], 
                [(0, 0), (20, 1), (25, 1), (27, 1), None, None, (32, 1), (36, 1), (56, 1), (61, 2)]
            ]

max_gems_from=[
                [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)], 
                [(0, 0), (61, 2), (61, 2), (59, 2), (56, 2), (55, 2), (54, 2), (51, 2), (43, 2), None, (0, 0)], 
                [(0, 0), (27, 1), None, None, (53, 2), None, None, (47, 2), (36, 2), (29, 1), (0, 0)], 
                [(0, 0), (25, 1), None, (53, 2), (51, 2), (48, 2), (41, 2), (40, 2), (35, 2), (27, 1), (0, 0)], 
                [(0, 0), (21, 1), (15, 1), None, (41, 2), (37, 2), None, (39, 2), (30, 2), (23, 1), (0, 0)], 
                [(0, 0), (16, 1), (14, 1), None, None, (32, 2), (29, 2), (28, 2), (27, 2), (17, 1), (0, 0)], 
                [(0, 0), (15, 1), (11, 1), None, None, None, (21, 1), (18, 1), (17, 1), (9, 1), (0, 0)], 
                [(0, 0), (14, 1), (7, 1), (2, 1), None, (11, 1), (9, 1), (7, 1), (4, 1), (0, 0), (0, 0)], 
                [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)]
               ]

assert (check_num_gems_to(mappa, num_gems_to, return_only_boolan=True) == True)
assert (check_num_gems_from(mappa, num_gems_from, return_only_boolan=True) == True)
assert (check_max_gems_to(mappa, max_gems_to, return_only_boolan=True) == True)
assert (check_max_gems_from(mappa, max_gems_from, return_only_boolan=True) == True)
# -

# ## Esercizio \[60 pts\]
# (campo minato con gemme) Ricerca di cammini in una griglia rettangolare con celle proibite e gemme da raccogliere.

# Bimo cammina sulle celle di un campo minato dalla forma di una griglia rettangolare $m\times n$.\
# Le mine sono indicate da un -1 mentre le altre celle che contengono un numero intero >0 
# sono tutte transitabili (il numero indica il numero di monete in quella cella).\
# Le mosse consentite portano Bimo dalla cella $(i,j)$ alla cella $(i+1,j)$ oppure $(i,j+1)$, sempre ove queste siano transitabili.\
# Organizzati per calcolare quante monete riesce a raccogliere Bimo tra due celle date e per rispondere ad altre domande di questo tipo.

# <b>Notice:</b> Anche se ne hai quì ogni opportunità, non ti è però richiesto in alcun modo di scrivere del codice per condurre a termine il tuo esercizio. Puoi fare tutto a mano e vogliamo essere chiari che noi non facciamo alcuna differenza tra i punti conquistati in un modo piuttosto che in un altro (noi guardiamo ai risultati e ci piace che voi vi ingegniate a modo vostro per portarli a casa, in tutta libertà). Sei incoraggiato piuttosto a ricercare l'approccio per tè più pratico, sicuro, e conveniente. E magari quello che puoi trovare più piacevole e stimolante quando svolgi l'esercizio da casa, dove ti suggerisco sperimentare, potrebbe anche essere diverso .
# Ciò nononostante, per facilitare chi di voi volesse scrivere del codice a proprio supporto, abbiamo aggiunto alla mappa di $m$ righe ed $n$ colonne una riga e colonna iniziale (di indice zero), fatte interamente di mine, perchè non si crei confusione col fatto che gli indici di liste ed array in programmazione partono da zero.

# Un robot, inizialmente situato nella cella $A1=(1,1)$, deve portarsi nella cella $G9=(7,9)$.
# Le celle che riportano un numero negativo contengono una mina od altre trapole mortali, ed il robot deve evitarle. Ogni altra cella contiene il numero di monete rappresentato nella tabella.\
# I movimenti base possibili sono il passo verso destra (ad esempio il primo passo potrebbe avvenire dalla cella $A1$ alla cella $A2$) ed il passo verso il basso (ad esempio, come unica altra alternativa per il primo passo il robot potrebbe posrtarsi quindi nella cella $B1$).\
# Quante monete può raccogliere al massimo il robot in un percorso che vada dalla cella $A1$ alla cella $G9$?\
# E quanti sono i percorsi che gli consentono di raccogliere un tale numero di monete?

# + hide_input=true
visualizza(mappa)
# -

# __Richieste__:

# \[10 pts\]__ A mano o tramite un programma componi la matrice $num\_gems\_to$ di dimensione $(m+1)\times(n+1)$, nella cui cella $num\_gems\_to[i][j]$, per ogni $i = 0,..., m+1$ e $j = 0,..., n+1$, sia riposto il massimo numero di gemme incontrate da un cammino dalla cella $A1=(1,1)$ alla generica cella $(i,j)$. Se non vi è alcun cammino dalla cella $A1=(1,1)$ alla generica cella $(i,j)$ poni allora $num\_gems\_to[i][j]$ a $None$.

num_gems_to=[
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
                [0, 0, 2, 5, 6, 7, 10, 14, 21, None], 
                [0, 2, 3, None, 8, None, None, 21, 22, 24], 
                [0, 6, None, None, 11, 18, 19, 22, 27, 31], 
                [0, 11, 12, None, 15, 23, None, 31, 34, 40], 
                [0, 12, 15, 18, None, 26, 27, 32, 44, 52], 
                [0, 13, 19, None, None, None, 30, 33, 52, 61], 
                [0, 20, 25, 27, None, None, 32, 36, 56, 61]
            ]
#num_gems_to=conta_gemme(mappa)

# + hide_input=false
visualizza_e_valuta("num_gems_to",num_gems_to)

# + [markdown] hide_input=true
# __\[10 pts\]__ Componi ora una matrice $num\_gems\_from$, di dimensione $(m+2)times(n+2)$, nella cui cella $num\_gems\_from[i][j]$, per ogni $i = 1,..., m+1$ e $j = 1,..., n+1$, sia riposto il numero di gemme raccolte dalla generica cella $(i,j)$ alla cella $G9=(7,9)$.
# -

num_gems_from=[
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
                [0, 61, 61, 59, 56, 55, 54, 51, 43, None, 0], 
                [0, 27, None, None, 53, None, None, 47, 36, 29, 0], 
                [0, 25, None, 53, 51, 48, 41, 40, 35, 27, 0], 
                [0, 21, 15, None, 41, 37, None, 39, 30, 23, 0], 
                [0, 16, 14, None, None, 32, 29, 28, 27, 17, 0], 
                [0, 15, 11, None, None, None, 21, 18, 17, 9, 0], 
                [0, 14, 7, 2, None, 11, 9, 7, 4, 0, 0], 
                [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
               ]
#num_gems_from=conta_gemme_rev(mappa)

# + hide_input=true
visualizza_e_valuta("num_gems_from",num_gems_from)
# -

# __\[10 pts\]__ A mano o tramite un programma componi la matrice $max\_gems\_to$ di dimensione $(m+1)\times(n+1)$, nella cui cella $max\_gems\_to[i][j]$, per ogni $i = 0,..., m+1$ e $j = 0,..., n+1$, sia riposto il numero di gemme raccolte dalla cella $A1=(1,1)$ e il numero di percorsi che assicurano di raccogliere quel numero di gemme alla generica cella $(i,j)$.

max_gems_to=[
                [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)], 
                [(0, 0), (0, 0), (2, 1), (5, 1), (6, 1), (7, 1), (10, 1), (14, 1), (21, 1), None], 
                [(0, 0), (2, 1), (3, 2), None, (8, 1), None, None, (21, 1), (22, 2), (24, 2)], 
                [(0, 0), (6, 1), None, None, (11, 1), (18, 1), (19, 1), (22, 1), (27, 3), (31, 3)], 
                [(0, 0), (11, 1), (12, 1), None, (15, 1), (23, 1), None, (31, 1), (34, 1), (40, 1)], 
                [(0, 0), (12, 1), (15, 2), (18, 2), None, (26, 1), (27, 1), (32, 1), (44, 1), (52, 1)], 
                [(0, 0), (13, 1), (19, 2), None, None, None, (30, 1), (33, 1), (52, 1), (61, 2)], 
                [(0, 0), (20, 1), (25, 1), (27, 1), None, None, (32, 1), (36, 1), (56, 1), (61, 2)]
            ]
#max_gems_to=conta_gemme_with_opt(mappa)

# + hide_input=false
visualizza_e_valuta("max_gems_to",max_gems_to)
# -

# __\[10 pts\]__ Componi ora una matrice $max\_gems\_from$, di dimensione $(m+2)times(n+2)$, nella cui cella $max\_gems\_from[i][j]$, per ogni $i = 1,..., m+1$ e $j = 1,..., n+1$, sia riposto il numero di gemme raccolte dalla generica cella $(i,j)$ alla cella $G9=(7,9)$ e il numero di percorsi che assicurano di raccogliere quel numero di gemme.

# +
#max_gems_from=conta_gemme_rev_with_opt(mappa)

max_gems_from=[
                [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)], 
                [(0, 0), (61, 2), (61, 2), (59, 2), (56, 2), (55, 2), (54, 2), (51, 2), (43, 2), None, (0, 0)], 
                [(0, 0), (27, 1), None, None, (53, 2), None, None, (47, 2), (36, 2), (29, 1), (0, 0)], 
                [(0, 0), (25, 1), None, (53, 2), (51, 2), (48, 2), (41, 2), (40, 2), (35, 2), (27, 1), (0, 0)], 
                [(0, 0), (21, 1), (15, 1), None, (41, 2), (37, 2), None, (39, 2), (30, 2), (23, 1), (0, 0)], 
                [(0, 0), (16, 1), (14, 1), None, None, (32, 2), (29, 2), (28, 2), (27, 2), (17, 1), (0, 0)], 
                [(0, 0), (15, 1), (11, 1), None, None, None, (21, 1), (18, 1), (17, 1), (9, 1), (0, 0)], 
                [(0, 0), (14, 1), (7, 1), (2, 1), None, (11, 1), (9, 1), (7, 1), (4, 1), (0, 0), (0, 0)], 
                [(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0)]
               ]

# + hide_input=true
visualizza_e_valuta("max_gems_from",max_gems_from)
# -



StarcoderdataJupyterScriptsDedupFiltered