Matrici e Ricorsione

Esercizio 1

Scrivere una funzione ricorsiva che calcoli la lunghezza massima di una "catena di numeri" in una lista. Una "catena" è una sequenza di numeri consecutivi nella lista in cui il numero successivo è uguale al precedente più 1.

def chain(lst):

    # Partiamo con l'indice 0, il conto degli elementi nella catena pari a 1 e il valore massimo della catena pari a 0

    return recursive_chain(lst, 0, 1, 0)

def recursive_chain(lst, i, current_count, max_value):

    # Caso base: terminiamo quando l'indice arriva al penultimo elemento

    if i >= len(lst)-1:

        return max_value

    # Verifica se l'elemento corrente (lst[i]) è immediatamente seguito (lst[i+1]) dal numero successivo.

    if lst[i] == lst[i+1]-1:

        # In caso affermativo, aumentiamo l'indice i, aggiorniamo il conto della catena e aggiorniamo il massimo (se necessario). 

        return recursive_chain(lst, i+1, current_count+1, max(max_value, current_count+1))

    # In caso negativo, aumentiamo l'indice i e lasciamo il conto pari a 1.

    return recursive_chain(lst, i+1, 1, max_value)

def iterative_chain(lst):

    current_count = 1

    max_value = 0

    for i in range(0, len(lst)-1):        

        if lst[i] == lst[i+1]-1:

            current_count += 1

            max_value = max(max_value, current_count)

        else:

            current_count = 1            

    return max_value

print(chain([1, 2, 3, 5, 6, 7, 8, 10, 11, 12]))

Esercizio 2

Scrivere una funzione ricorsiva chiamata anchestor che, dato una lista con l'elenco di coppie padre-figlio e due stringhe rappresentanti un potenziale antenato (person1) e un potenziale discendente (person2), determini se il primo è un antenato del secondo. Si può assumere che la lista in input rispetti le seguenti condizioni:

• Il nome identifica univocamente ciascuna persona presente nella lista.

• Ogni figlio ha al massimo un padre.

• Non sono presenti cicli nella relazione padre-figlio (ad esempio, non può verificarsi il caso in cui Mario è il padre di Antonio, che è il padre di Giovanni, che a sua volta è il padre di Mario).

def anchestor(father_son, person1, person2):

    for element in father_son:

        if element[0] == person1:

            if element[1] == person2 or anchestor(father_son, element[1], person2):

                return True            

    return False

def anchestor_iterative(father_son, person1, person2):

    to_visit = []

    for element in father_son: # Scorriamo la lista delle coppie

        if element[0] == person1: # Nota: viste le assunzioni della traccia, non è necessario controllare che l'elemento non sia presente in to_visit perché non si può creare un ciclo

            to_visit.append(element[1]) # Aggiungiamo alla lista tutti i figli di person1

    for person in to_visit: # Scorriamo la lista delle persone da visitare

        if person == person2: # Se è già la persona2, stop, vuol dire che person1 è un antenato

            return True

        # Aggiungiamo alla lista tutti i figli di person

        for element in father_son:

            if element[0] == person: # Nota: viste le assunzioni della traccia, non è necessario controllare che l'elemento non sia presente in to_visit perché non si può creare un ciclo

                to_visit.append(element[1])

    return False

father_son = [("antonio", "alberto"), ("francesco", "simone"), ("francesco", "mario"), ("angelo", "andrea"), ("antonio", "marco"), ("marco", "gabriele"), ("gabriele", "eugenio")]

print(anchestor(father_son, "antonio", "eugenio"))

print(anchestor_iterative(father_son, "antonio", "eugenio"))

Esercizio 3

Data una matrice n x m di numeri interi, una valle è una cella il cui valore è minore di quello di tutte le celle adiacenti (sopra, sotto, sinistra e destra, se esistono). La profondità di una valle si calcola come la somma di tutte le celle adiacenti (sopra, sotto, sinistra e destra, se esistono). Scrivere una funzione greatest_valley che restituisca gli indici della valle con la profondità più alta. Se non ci sono valli, restituisce None.

# Calcoliamo gli adiacenti

def get_adjacents(m, i, j):

    # Creiamo una lista con i 4 possibili adiacenti: gli elementi di sotto, sopra, destra, sinistra

    possible_adjacents = [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]

    # Restituiamo solo la lista degli adiacenti che sono validi

    valid_adjacents = []

    for element in possible_adjacents:

        # Per ogni coppia di elementi tra i possibili adiacenti, controlliamo che siano punti validi, cioè che non sforino la matrice

        if element[0] >= 0 and element[0] < len(m) and element[1] >= 0 and element[1] < len(m):

            valid_adjacents.append(m[element[0]][element[1]])

    return valid_adjacents

# Verifichiamo se è una valle

def is_valley(m, i, j):

    # Prendiamo gli adiacenti validi

    adjacents = get_adjacents(m, i, j)

    # Scorriamo gli adiacenti validi

    for adjacent in adjacents:

        # Se l'elemento in posizione i, j è superiore al valore dell'elemento adiacente, non è una valle

        if m[i][j] >= adjacent:

            return False

    # L'elemento è una valle.

    return True

# Calcoliamo la somma degli elementi adiacenti a un punto

def get_adjacents_sum(m, i, j):

    # Prendiamo tutti gli adiacenti validi e restituiamo la somma

    return sum(get_adjacents(m, i, j))

def greatest_valley(m):

    max_value = None

    max_element = None

    # Scorriamo la matrice

    for i in range(len(m)):

        for j in range(len(m)):

            # Se l'elemento nel punto i, j è una valle...

            if is_valley(m, i, j):

                # ...calcoliamo la somma degli elementi adiacenti

                current_sum = get_adjacents_sum(m, i, j)

                # Una stampa per capire meglio: stampiamo la valle e la sua somma

                print(f"La valle è: {(i, j)}, la somma è: {current_sum}")

                # Se è la prima valle, oppure se la somma è superiore al massimo precedente, aggiorniamo il massimo e la sua posizione

                if max_value is None or max_value < current_sum:

                    max_value = current_sum

                    max_element = (i, j)

    # Restituiamo la posizione

    return max_element

matrice = [

    [5, 3, 4, 7],

    [2, 1, 6, 8],

    [7, 3, 2, 5],

    [9, 3, 5, 1],

]

print(greatest_valley(matrice))

Esercizio 4

Data una matrice n x n contenente solo valori 0 e 1. Un'isola è definita come un gruppo di celle adiacenti contenenti 1 che possono essere collegate orizzontalmente o verticalmente (non diagonalmente). Scrivere una funzione find_largest_island che trova la dimensione dell’isola più grande presente nella matrice.

# Calcola gli elementi adiacenti a un punto

def get_adjacents(m, i, j):

    # I possibili adiacenti sono gli elementi di sotto, sopra, destra, sinistra.

    possible_adjacents = [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]

    valid_adjacents = []

    for element in possible_adjacents:

        # Per ogni coppia di elementi tra i possibili adiacenti, controlliamo che siano punti validi,

        # cioè che non sforino la matrice e che abbiano il valore 1.

        if element[0] >= 0 and element[0] < len(m) and element[1] >= 0 and element[1] < len(m) and m[element[0]][element[1]] == 1:

            valid_adjacents.append((element[0], element[1]))

    return valid_adjacents

# Cerchiamo un'isola a partire da un punto e restutiamo la lunghezza.

def find_island_length(m, i, j):

    to_visit = [(i, j)] # I punti da visitare, si parte dal punto stesso

    for element in to_visit:

        # Aggiungiamo agli elementi da visitare gli adiacenti che non sono già stati visitati

        for adjacent in get_adjacents(m, element[0], element[1]):

            if adjacent not in to_visit:

                 to_visit.append(adjacent)       

        # Versione compatta con list comprehension

        # to_visit.extend([adjacent for adjacent in get_adjacents(element[0], element[1]) if adjacent not in to_visit])

    return len(to_visit) # Restituiamo la lunghezza di to_visit

def find_largest_island(m):

    max_value = 0

    for i in range(len(m)):

        for j in range(len(m)):

            if m[i][j] == 1: # Per ogni elemento della matrice che fa parte di un'isola calcoliamo la grandezza dell'isola

                max_value = max(max_value, find_island_length(m, i, j)) # Se c'è un'isola più grande, aggiorniamo il massimo

    return max_value

m = [

    [1, 1, 0, 0],

    [1, 0, 0, 1],

    [0, 0, 1, 1],

    [0, 1, 1, 1]

]

print(find_largest_island(m))