Matrici - Liste di liste 2 - Altri esercizi

Scarica zip esercizi

Naviga file online

ATTENZIONE

Gli esercizi che seguono contengono dei test con gli assert. Per capire come svolgerli, leggi prima Gestione errori e testing

Esercizio - diag

diag estrae la diagonale di una matrice. Per farlo, la funzione richiede una matrice n x n come input. Per essere sicuri di prendere effettivamente una matrice n x n, sarà meglio validare l’input, cioè controllare che il numero di righe sia uguale al numero di colonne (come al solito assumi che la matrice abbia almeno una riga e almeno una colonna). Se la matrice non è n x n, la funzione dovrebbe fermarsi e lanciare una eccezione. In particolare, possiamo lanciare un ValueError, che è il modo standard in Python di segnalare che l’input non è corretto (e non trovi errori più specifici).

Per scopi illustrativi, mostriamo qui i numeri indice i e j ed evitiamo di mettere gli apici intorno alle stringhe:

\ j  0,1,2,3
i
   [
0   [a,b,c,d],
1   [e,f,g,h],
2   [p,q,r,s],
3   [t,u,v,z]
   ]

Vediamo una esecuzione passo-passo:

                               \ j  0,1,2,3
                               i
                                  [
estrai dalla riga a  i=0 -->   0   [a,b,c,d],     'a' è estratto da mat[0][0]
                               1   [e,f,g,h],
                               2   [p,q,r,s],
                               3   [t,u,v,z]
                                  ]

                               \ j  0,1,2,3
                               i
                                  [
                               0   [a,b,c,d],
estrai dalla riga a i=1  -->   1   [e,f,g,h],    'f' è estratto da mat[1][1]
                               2   [p,q,r,s],
                               3   [t,u,v,z]
                                  ]

                               \ j  0,1,2,3
                               i
                                  [
                               0   [a,b,c,d],
                               1   [e,f,g,h],
estrai dalla riga a i=2  -->   2   [p,q,r,s],    'r' è estratto da mat[2][2]
                               3   [t,u,v,z]
                                  ]

                               \ j  0,1,2,3
                               i
                                  [
                               0   [a,b,c,d],
                               1   [e,f,g,h],
                               2   [p,q,r,s],
estrai dalla riga a i=3  -->   3   [t,u,v,z]     'z' è estratto da mat[3][3]
                                  ]

Da quanto sopra, notiamo che abbiamo bisogno di elementi da questi indici:

i, j
1, 1
2, 2
3, 3

Ci sono due modi di risolvere questo esercizio, uno è usare un doppio for (per essere precisi, un for annidato), mentre l’altro metodo usa solo un for. Prova a risolverlo in entrambi i modi.

Di quanti passi hai bisogno con un doppio for? E con uno solo?

✪✪ ESERCIZIO: Implementa la funzione diag, che data una matrice n x n come lista di liste, RITORNA una lista che contiene gli elementi della diagonale (da sinistra in alto fino all’angolo basso destro)

• se mat non è n x n solleva l’eccezione ValueError

Mostra soluzione

def diag(mat):

    if len(mat) != len(mat[0]):
        raise ValueError("mat dovrebbe essere n x n, trovato invece %s x %s" % (len(mat), len(mat[0])))
    ret = []
    for i in range(len(mat)):
        ret.append(mat[i][i])
    return ret


m = [ ['a','b','c'],
      ['d','e','f'],
      ['g','h','i'] ]

assert diag(m) == ['a','e','i']

try:
    diag([              # 1x2 dimension, non quadrata
           ['a','b']
         ])
    raise Exception("Dovrei aver fallito !") # se diag solleva un'eccezione che
                                             # è ValueError come ci aspettiamo
                                             # che faccia, il codice non dovrebbe
                                             # mai arrivare qui
except ValueError: # cattura solo ValueError, altri tipi di errori
                   # non sono catturati
    pass  # In una clausola except devi sempre mettere del codice
          # Qui mettiamo il comando pass che non fa niente

def diag(mat):
    raise Exception('TODO IMPLEMENT ME !')

m = [ ['a','b','c'],
      ['d','e','f'],
      ['g','h','i'] ]

assert diag(m) == ['a','e','i']

try:
    diag([              # 1x2 dimension, non quadrata
           ['a','b']
         ])
    raise Exception("Dovrei aver fallito !") # se diag solleva un'eccezione che
                                             # è ValueError come ci aspettiamo
                                             # che faccia, il codice non dovrebbe
                                             # mai arrivare qui
except ValueError: # cattura solo ValueError, altri tipi di errori
                   # non sono catturati
    pass  # In una clausola except devi sempre mettere del codice
          # Qui mettiamo il comando pass che non fa niente

Esercizio - anti_diag

✪✪ Data una matrice nxn come lista di liste, RITORNA una lista che contiene gli elementi della antidiagonale (dall’angolo destro fino all’angolo in basso a sinistra).

• Se mat non è nxn solleva ValueError.

Prima di implementarla, ricordati di scrivere gli indici richiesti come abbiamo fatto per l’esempio della funzione diag

Mostra soluzione

def anti_diag(mat):

    n = len(mat)
    ret = []
    for i in range(n):
        ret.append(mat[i][-1-i])
        #ret.append(mat[i][n-1-i])  # versione alternativa
    return ret


m = [ ['a','b','c'],
      ['d','e','f'],
      ['g','h','i'] ]

assert anti_diag(m) == ['c','e','g']

# Se hai dubbi sugli indici, ricordati di provare il codice in Python Tutor!
# jupman.pytut()

def anti_diag(mat):
    raise Exception('TODO IMPLEMENT ME !')

m = [ ['a','b','c'],
      ['d','e','f'],
      ['g','h','i'] ]

assert anti_diag(m) == ['c','e','g']

# Se hai dubbi sugli indici, ricordati di provare il codice in Python Tutor!
# jupman.pytut()

Esercizio - is_utriang

Chiediamoci cosa vuol dire iterare solo la parte triangolare inferiore di una matrice. Vediamo un esempio:

m = [
        [3,2,5,8],
        [0,6,2,3],
        [0,0,4,9],
        [0,0,0,5]
    ]

Solo per propositi illustrativi, mostriamo qui i numeri di indice i e j:

\ j  0,1,2,3
i
   [
0   [3,2,5,8],
1   [0,6,2,3],
2   [0,0,4,9],
3   [0,7,0,5]
   ]

Vediamo una esecuzione passo passo su una matrice triangolare non-superiore:

                                \ j  0,1,2,3
                                i
                                   [
                                0   [3,2,5,8],
inizia da riga a indice i=1 --> 1   [0,6,2,3],  Controlla fino a
                                2   [0,0,4,9],  colonna limite j=0 inclusa
                                3   [0,7,0,5]
                                   ]

Viene trovato uno zero, è ora di controllare la riga successiva.

                                \ j  0,1,2,3
                                i
                                   [
                                0   [3,2,5,8],
                                1   [0,6,2,3],
controlla riga a indice i=2 --> 2   [0,0,4,9],      Controlla fino a
                                3   [0,7,0,5]       colonna limite  j=1 inclusa
                                   ]

Due zeri sono trovati, è ora di controllare la riga successiva.

                                \ j  0,1,2,3
                                i
                                   [
                                0   [3,2,5,8],
                                1   [0,6,2,3],
                                2   [0,0,4,9],
controlla riga a indice i=3 --> 3   [0,7,0,5]       Controlla fino a colonna
                                   ]                limite  j=2 inclusa MA
                                                    può fermarsi prima a j=1
                                                    perchè il numero a j=1
                                                    è differente da zero.
                                                    Appena 7 è trovato, può
                                                    ritornare False
                                                    In questo caso la matrice
                                                    non è triangolare superiore

VII COMANDAMENTO: Scriverai anche su carta!

Quando sviluppi questi algoritmi, è fondamentale scrivere un esempio passo passo come quello sopra per avere un’idea chiara di cosa sta succedendo. Inoltre, se scrivi giù gli indici correttamente, sarai facilmente in grado di derivare una generalizzazione. Per trovarla, prova a scrivere ulteriormente gli indici trovati in una tabella.

Per esempio, da quanto sopra per ciascuna riga indice i possiamo facilmente trovare di quale indice limite j abbiamo bisogno per raggiungere nella nostra caccia agli zero:

i	limite j (incluso)	Note
1	0	cominciamo dalla riga a indice i=1
2	1
3	2

Dalla tabella, possiamo vedere che il limite per j può essere calcolato in termini dell’indice riga corrente i con una semplice formula i - 1

Il fatto che tu debba muoverti attraverso righe e colonne suggerisce che hai bisogno di due for, uno per le righe e uno per le colonne - cioè un for annidato

per svolgere l’esercizio:

• usa range di indici (quindi niente for riga in mat ..)

• usa i caratteri i come indice per le righe, j come indice per le colonne e in caso tu ne abbia bisogno la lettera n come dimensione della matrice

SUGGERIMENTO 1: ricorda che puoi consentire a range di partire da un indice specifico, come range(3,7) che partirà da 3 e finira a 6 incluso (l’ultimo 7 è escluso).

SUGGERIMENTO 2: Per implementare questo, è meglio guardare a numeri diversi da zero. Appena ne trovi uno, puoi fermare la funzione e ritornare False. Solo dopo che tutto il controllo dei numeri è fatto puoi ritornare True

Infine, ricordati di questo:

II COMANDAMENTO: Quando inserisci una variabile in un ciclo for, questa variabile deve essere nuova

✪✪✪ ESERCIZIO: Se hai letto tutto quanto sopra, comincia ad implementare la funzione is_utriang, che RITORNA True se la matrice nxn fornita è triangolare superiore, cioè, ha tutte le celle sotto la diagonale a zero. Altrimenti, ritorna False

Mostra soluzione

def is_utriang(mat):

    n = len(mat)
    m = len(mat[0])

    for i in range(1,n):
        for j in range(i): # nota che arriva fino alla i *esclusa*, cioè, arriva a i - 1 *inclusa*
            if mat[i][j] != 0:
                return False
    return True


assert is_utriang([ [1] ]) == True
assert is_utriang([ [3,2,5],
                    [0,6,2],
                    [0,0,4] ]) == True

assert is_utriang([ [3,2,5],
                    [0,6,2],
                    [1,0,4] ]) == False

assert is_utriang([ [3,2,5],
                    [0,6,2],
                    [1,1,4] ]) == False

assert is_utriang([ [3,2,5],
                    [0,6,2],
                    [0,1,4] ]) == False


assert is_utriang([ [3,2,5],
                    [1,6,2],
                    [1,0,4] ]) == False

def is_utriang(mat):
    raise Exception('TODO IMPLEMENT ME !')

assert is_utriang([ [1] ]) == True
assert is_utriang([ [3,2,5],
                    [0,6,2],
                    [0,0,4] ]) == True

assert is_utriang([ [3,2,5],
                    [0,6,2],
                    [1,0,4] ]) == False

assert is_utriang([ [3,2,5],
                    [0,6,2],
                    [1,1,4] ]) == False

assert is_utriang([ [3,2,5],
                    [0,6,2],
                    [0,1,4] ]) == False


assert is_utriang([ [3,2,5],
                    [1,6,2],
                    [1,0,4] ]) == False

Esercizio - attacca_sx_mod

Questa volta proviamo a modificare mat1 sul posto (in place), attaccando mat2 alla sinistra di mat1.

Perciò questa volta non mettere una istruzione return.

Avrai bisogno di eseguire una inserzione di lista, che può essere problematica. Ci sono molti modi di farlo in Python, uno potrebbe essere usare l’inserzione cosiddetta di ‘splice assignment’ (che può apparire un po’ strana):

mia_lista[0:0] = lista_da_inserire

Guarda qui per altre info (in inglese): https://stackoverflow.com/a/10623383

✪✪✪ ESERCIZIO: implementa attacca_sx_mod, che date le matrici mat1 e mat2 come lista di liste, con mat1 di dimensioni n x l e mat2 di dimensioni n x r, MODIFICA mat1 così che diventi di dimensioni n x (l + r), attaccando la mat2 alla sinistra di mat1

Mostra soluzione

def attacca_sx_mod(mat1,mat2):


    for i in range(len(mat1)):
        mat1[i][0:0] = mat2[i]



m1 = [ ['a','b','c'],
       ['d','b','a'] ]
m2 = [ ['f','b'],
       ['g','h'] ]

res = [ ['f','b','a','b','c'],
        ['g','h','d','b','a'] ]

attacca_sx_mod(m1, m2)
assert m1 == res

def attacca_sx_mod(mat1,mat2):
    raise Exception('TODO IMPLEMENT ME !')


m1 = [ ['a','b','c'],
       ['d','b','a'] ]
m2 = [ ['f','b'],
       ['g','h'] ]

res = [ ['f','b','a','b','c'],
        ['g','h','d','b','a'] ]

attacca_sx_mod(m1, m2)
assert m1 == res

Esercizio - trasposta_1

Vediamo come trasporre una una matrice sul posto (in-place). La trasposta \(M^T\) di una matrice \(M\) è definita come

\(M^T[i][j] = M[j][i]\)

La definizione è semplice eppure l’implementazione può essere insidiosa. Se non stai attento, potresti facilmente finire a scambiare valori due volte e riottenere la stessa matrice originale. Per evitare ciò, itera solo la parte triangolare superiore e ricordati che la funzione range può avere un indice di partenza:

list(range(3,7))

[3, 4, 5, 6]

Inoltre, assicurati di sapere come scambiare solo due valori risolvendo questo semplice esercizio - controlla inoltre il risultato in Python Tutor.

Mostra soluzione

x = 3
y = 7

# scrivi qui il codice per scambiare x,y - non usare direttamente le costanti 3 e 7

k = x
x = y
y = k

jupman.pytut()

Python Tutor visualization

x = 3
y = 7

# scrivi qui il codice per scambiare x,y - non usare direttamente le costanti 3 e 7

Python Tutor visualization

Tornando alla trasposta, per adesso consideriamo solo una matrice nxn. Per assicurarci che ci prendiamo in effetti una matrice nxn, valideremo l’input come fatto in precedenza

IV COMANDAMENTO(adattato per matrici): Non riassegnerai mai parametri di funzione

def myfun(M):

    # M è un parametro, perciò *non* commetterai mai malvagità come:

    M = [
            [6661,6662],
            [6663,6664 ]
        ]


    # Per il solo caso di parametri composti come liste (o liste di liste...),
    # puoi scrivere cose come questa SE E SOLO SE le specifiche della funzione
    # ti richiedono di modificare gli elementi interni del parametro
    # (es. trasopsta _in-place_)

    M[0][1] =  6663

✪✪✪ ESERCIZIO: Se hai letto tutto quanto sopra, adesso puoi procedere implementando la funzione trasposta_1, che MODIFICA la matrice nxn data mat, facendo la trasposta in-place

• Se la matrice non è nxn, lancia l’eccezione ValueError

Mostra soluzione

def trasposta_1(mat):

    if len(mat) != len(mat[0]):
        raise ValueError("La matrice dovrebbe essere nxn, trovato invece %s x %s" % (len(mat), len(mat[0])))
    for i in range(len(mat)):
        for j in range(i+1,len(mat[i])):
            el = m[i][j]
            mat[i][j] = m[j][i]
            mat[j][i] = el


# Controlliamo le dimensioni sbagliate della matrice:

try:
    trasposta_1([ [3,5] ])
    raise Exception("AVREI DOVUTO FALLIRE !")
except ValueError:
    pass

m = [ ['a'] ]

trasposta_1(m)
assert m == [ ['a'] ]

m = [ ['a','b'],
      ['c','d'] ]

trasposta_1(m)
assert m == [ ['a','c'],
              ['b','d'] ]

def trasposta_1(mat):
    raise Exception('TODO IMPLEMENT ME !')

# Controlliamo le dimensioni sbagliate della matrice:

try:
    trasposta_1([ [3,5] ])
    raise Exception("AVREI DOVUTO FALLIRE !")
except ValueError:
    pass

m = [ ['a'] ]

trasposta_1(m)
assert m == [ ['a'] ]

m = [ ['a','b'],
      ['c','d'] ]

trasposta_1(m)
assert m == [ ['a','c'],
              ['b','d'] ]

Esercizio - transposta_2

✪✪ Adesso proviamo a trasporre una matrice generica nxm. Questa volta per semplicità ritorneremo una intera nuova matrice.

Prende una matrice mat nxm come lista di liste e RITORNA una NUOVA matrice mxn che è la trasposta della matrice di input:

Mostra soluzione

def trasposta_2(mat):

    n = len(mat)
    m = len(mat[0])
    ret = [[0]*n for i in range(m)]
    for i in range(n):
        for j in range(m):
            ret[j][i] = mat[i][j]
    return ret


m1 = [ ['a'] ]

r1 = trasposta_2(m1)

assert  r1 == [ ['a'] ]
r1[0][0] = 'z'
assert m1[0][0] == 'a'

m2 = [ ['a','b','c'],
      ['d','e','f'] ]

assert trasposta_2(m2) == [ ['a','d'],
                            ['b','e'],
                            ['c','f'] ]

def trasposta_2(mat):
    raise Exception('TODO IMPLEMENT ME !')

m1 = [ ['a'] ]

r1 = trasposta_2(m1)

assert  r1 == [ ['a'] ]
r1[0][0] = 'z'
assert m1[0][0] == 'a'

m2 = [ ['a','b','c'],
      ['d','e','f'] ]

assert trasposta_2(m2) == [ ['a','d'],
                            ['b','e'],
                            ['c','f'] ]

Esercizio - matriverba

✪✪ Scrivi una funzione che data una matrice di caratteri, RITORNA una stringa con le parole estratte dalle colonne, mettendo in maiuscolo il primo carattere di ciascuna parola.

• per il maiuscolo usa .upper()

Esempio:

m  = [['p','c','z','g','b', 'd'],
      ['o','a','a','i','o', 'e'],
      ['r','l','n','a','r', 'n'],
      ['t','m','n','r','s', 't'],
      ['o','a','a','a','e', 'e']];

>>> matriverba(m)
'PortoCalmaZannaGiaraBorseDente'

• SUGGERIMENTO: evita di continuare a creare nuove stringhe dentro un ciclo perchè è inefficiente. Piuttosto usa una lista e convertila in stringa alla fine.

Mostra soluzione

def matriverba(mat):


    ret = []

    for j in range(len(mat[0])):
        ret.append(mat[0][j].upper())
        for i in range(1,len(mat)):
            ret.append(mat[i][j])
    return ''.join(ret)



# TEST
m1 = [['a']]
assert matriverba(m1) == 'A'

m2 = [['a','b']]
assert matriverba(m2) == 'AB'

m3 = [['c'],
      ['b']]
assert matriverba(m3) == 'Cb'

m4 = [['c','e'],
      ['b','q']]
assert matriverba(m4) == 'CbEq'

m5 = [['p','c','z','g','b', 'd'],
      ['o','a','a','i','o', 'e'],
      ['r','l','n','a','r', 'n'],
      ['t','m','n','r','s', 't'],
      ['o','a','a','a','e', 'e']];

assert matriverba(m5) == 'PortoCalmaZannaGiaraBorseDente'

def matriverba(mat):
    raise Exception('TODO IMPLEMENT ME !')


# TEST
m1 = [['a']]
assert matriverba(m1) == 'A'

m2 = [['a','b']]
assert matriverba(m2) == 'AB'

m3 = [['c'],
      ['b']]
assert matriverba(m3) == 'Cb'

m4 = [['c','e'],
      ['b','q']]
assert matriverba(m4) == 'CbEq'

m5 = [['p','c','z','g','b', 'd'],
      ['o','a','a','i','o', 'e'],
      ['r','l','n','a','r', 'n'],
      ['t','m','n','r','s', 't'],
      ['o','a','a','a','e', 'e']];

assert matriverba(m5) == 'PortoCalmaZannaGiaraBorseDente'

Esercizio - cirpillino

Data una stringa e un intero n, RITORNA una NUOVA matrice come lista di liste contenente tutte le lettere della stringa suddivise in righe da n elementi.

• se la lunghezza stringa non è esattamente divisibile per n, solleva ValueError

Esempio:

>>> cirpillino('cirpillinozimpirelloulalimpo', 4)
[['c', 'i', 'r', 'p'],
 ['i', 'l', 'l', 'i'],
 ['n', 'o', 'z', 'i'],
 ['m', 'p', 'i', 'r'],
 ['e', 'l', 'l', 'o'],
 ['u', 'l', 'a', 'l'],
 ['i', 'm', 'p', 'o']]

Mostra soluzione

def cirpillino(stringa, n):

    if len(stringa) % n != 0:
        raise ValueError('La stringa non è divisibile per %s' % n)
    ret = []

    for i in range(len(stringa) // n):
        ret.append(list(stringa[i*n:(i+1)*n]))
    return ret



# TEST
assert cirpillino('z', 1) == [['z']]

assert cirpillino('abc', 1) == [['a'],
                                ['b'],
                                ['c']]

assert cirpillino('abcdef', 2) == [['a','b'],
                                   ['c','d'],
                                   ['e','f']]

assert cirpillino('abcdef', 3) == [['a','b','c'],
                                   ['d','e','f']]

assert cirpillino('cirpillinozimpirelloulalimpo', 4) == [['c', 'i', 'r', 'p'],
                                                         ['i', 'l', 'l', 'i'],
                                                         ['n', 'o', 'z', 'i'],
                                                         ['m', 'p', 'i', 'r'],
                                                         ['e', 'l', 'l', 'o'],
                                                         ['u', 'l', 'a', 'l'],
                                                         ['i', 'm', 'p', 'o']]
try:
    cirpillino('abc', 5)
    raise Exception("Avrei dovuto fallire !")
except ValueError:
    pass

def cirpillino(stringa, n):
    raise Exception('TODO IMPLEMENT ME !')


# TEST
assert cirpillino('z', 1) == [['z']]

assert cirpillino('abc', 1) == [['a'],
                                ['b'],
                                ['c']]

assert cirpillino('abcdef', 2) == [['a','b'],
                                   ['c','d'],
                                   ['e','f']]

assert cirpillino('abcdef', 3) == [['a','b','c'],
                                   ['d','e','f']]

assert cirpillino('cirpillinozimpirelloulalimpo', 4) == [['c', 'i', 'r', 'p'],
                                                         ['i', 'l', 'l', 'i'],
                                                         ['n', 'o', 'z', 'i'],
                                                         ['m', 'p', 'i', 'r'],
                                                         ['e', 'l', 'l', 'o'],
                                                         ['u', 'l', 'a', 'l'],
                                                         ['i', 'm', 'p', 'o']]
try:
    cirpillino('abc', 5)
    raise Exception("Avrei dovuto fallire !")
except ValueError:
    pass

Esercizio - bandiera

Dati due numeri interi n e m, con m multiplo di 3, RITORNA una matrice n x m come lista di liste avente nelle celle i numeri da 0 a 2 ripartiti in 3 fasce verticali.

• se m non è un multiplo di 3, solleva ValueError

Esempio:

>>> bandiera(5,12)
[[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
 [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
 [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
 [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
 [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2]]

Mostra soluzione

def bandiera(n,m):


    if m % 3 != 0:
        raise ValueError('Il numero di colonne non è un multiplo di 3: %s' % m)

    ret = []

    for i in range(n):
        riga = []
        for j in range(m):
            num = j // (m // 3)
            riga.append(num)
        ret.append(riga)
    return ret



# TEST
assert bandiera(1,3) == [[0, 1, 2]]

assert bandiera(1,6) == [[0,0,1,1, 2,2]]

assert bandiera(4,6) == [[0, 0, 1, 1, 2, 2],
                         [0, 0, 1, 1, 2, 2],
                         [0, 0, 1, 1, 2, 2],
                         [0, 0, 1, 1, 2, 2]]

assert bandiera(2,9) == [[0, 0, 0, 1, 1, 1, 2, 2, 2],
                         [0, 0, 0, 1, 1, 1, 2, 2, 2]]

assert bandiera(5,12) == [[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
                          [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
                          [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
                          [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
                          [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2]]

try:
    bandiera(3,7)
    raise Exception("Avrei dovuto fallire!")
except ValueError:
    pass

def bandiera(n,m):
    raise Exception('TODO IMPLEMENT ME !')

# TEST
assert bandiera(1,3) == [[0, 1, 2]]

assert bandiera(1,6) == [[0,0,1,1, 2,2]]

assert bandiera(4,6) == [[0, 0, 1, 1, 2, 2],
                         [0, 0, 1, 1, 2, 2],
                         [0, 0, 1, 1, 2, 2],
                         [0, 0, 1, 1, 2, 2]]

assert bandiera(2,9) == [[0, 0, 0, 1, 1, 1, 2, 2, 2],
                         [0, 0, 0, 1, 1, 1, 2, 2, 2]]

assert bandiera(5,12) == [[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
                          [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
                          [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
                          [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2],
                          [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2]]

try:
    bandiera(3,7)
    raise Exception("Avrei dovuto fallire!")
except ValueError:
    pass

Esercizio - evita_diag

✪✪ Data una matrice quadrata \(n\) x \(n\) come liste di liste RITORNA una NUOVA lista con la somma di tutti i numeri di ogni riga TRANNE la diagonale.

• se la matrice non è quadrata, lancia ValueError

Esempio:

>>> evita_diag([ [5,6,2],
                 [4,7,9],
                 [1,9,8]])
[8, 13, 10]

perchè

 8 = 6 + 2
13 = 4 + 7
10 = 1 + 9

Mostra soluzione

def evita_diag(mat):

    if len(mat) != len(mat[0]):
        raise ValueError("Matrice non quadrata: %s x %s" % (len(mat), len(mat[0])))
    ret = []
    i = 0
    for riga in mat:
        ret.append(sum(riga) - riga[i])
        i += 1
    return ret


assert evita_diag([[5]]) == [0]

m2 = [[5,7],
      [9,1]]
assert evita_diag(m2) == [7,9]
assert m2 ==  [[5,7],
               [9,1]]

assert evita_diag([ [5,6,2],
                    [4,7,9],
                    [1,9,8]]) == [8, 13, 10]

try:
    evita_diag([[2,3,5],
                [1,5,2]])
    raise Exception("Avrei dovuto fallire!")
except ValueError:
    pass

def evita_diag(mat):
    raise Exception('TODO IMPLEMENT ME !')

assert evita_diag([[5]]) == [0]

m2 = [[5,7],
      [9,1]]
assert evita_diag(m2) == [7,9]
assert m2 ==  [[5,7],
               [9,1]]

assert evita_diag([ [5,6,2],
                    [4,7,9],
                    [1,9,8]]) == [8, 13, 10]

try:
    evita_diag([[2,3,5],
                [1,5,2]])
    raise Exception("Avrei dovuto fallire!")
except ValueError:
    pass

Esercizio - no_diag

✪✪ Data una matrice \(n\) x \(n\) come lista di liste, RITORNA una NUOVA matrice n x n-1 avente le stesse celle dell’originale ECCETTO le celle della diagonale.

• se la matrice non è quadrata, lancia ValueError

Esempio:

>>> m = [[8,5,3,4],
         [7,2,4,1],
         [9,8,3,5],
         [6,0,4,7]]
>>> no_diag(m)
[[5,3,4],
 [7,4,1],
 [9,8,5],
 [6,0,4]]

Mostra soluzione

def no_diag(mat):

    if len(mat) != len(mat[0]):
        raise ValueError("Matrice non quadrata: %s x %s" % (len(mat), len(mat[0])))

    ret = []
    i = 0
    for riga in mat:
        nuova_riga = riga[0:i] + riga[i+1:]
        ret.append(nuova_riga)
        i += 1

    return ret


# TEST
m1 = [[3,4],
      [8,7]]
assert no_diag(m1) == [[4],
                       [8]]
assert m1 == [[3,4],  # verifica che non abbia cambiato l'originale
              [8,7]]

m2 = [[9,4,3],
      [8,5,6],
      [0,2,7]]
assert no_diag(m2) == [[4,3],
                       [8,6],
                       [0,2]]
m3 = [[8,5,3,4],
      [7,2,4,1],
      [9,8,3,5],
      [6,0,4,7]]
assert no_diag(m3) == [[5,3,4],
                       [7,4,1],
                       [9,8,5],
                       [6,0,4]]
try:
    no_diag([[2,3,5],
             [1,5,2]])
    raise Exception("Avrei dovuto fallire!")
except ValueError:
    pass

def no_diag(mat):
    raise Exception('TODO IMPLEMENT ME !')

# TEST
m1 = [[3,4],
      [8,7]]
assert no_diag(m1) == [[4],
                       [8]]
assert m1 == [[3,4],  # verifica che non abbia cambiato l'originale
              [8,7]]

m2 = [[9,4,3],
      [8,5,6],
      [0,2,7]]
assert no_diag(m2) == [[4,3],
                       [8,6],
                       [0,2]]
m3 = [[8,5,3,4],
      [7,2,4,1],
      [9,8,3,5],
      [6,0,4,7]]
assert no_diag(m3) == [[5,3,4],
                       [7,4,1],
                       [9,8,5],
                       [6,0,4]]
try:
    no_diag([[2,3,5],
             [1,5,2]])
    raise Exception("Avrei dovuto fallire!")
except ValueError:
    pass

Esercizio - no_anti_diag

✪✪✪ Data una matrice quadrata \(n\) x \(n\) mat come lista di liste, RITORNA una NUOVA matrice n x n-1 avente le stesse celle dell’originale ECCETTO le celle della ANTI diagonale. Per esempi, vedere gli assert.

• se n non è quadrata, lancia ValueError

Mostra soluzione

def no_anti_diag(mat):

    if len(mat) != len(mat[0]):
        raise ValueError("Matrice non quadrata: %s x %s" % (len(mat), len(mat[0])))
    ret = []
    for i in range(len(mat)):
        k = len(mat) - i - 1
        nuova = mat[i][:k] + mat[i][k+1:]
        ret.append(nuova)
    return ret


m1 = [[3,4],
      [8,7]]
assert no_anti_diag(m1) == [[3],
                            [7]]

assert m1 == [[3,4],  # verifica che non abbia cambiato l'originale
              [8,7]]

m2 = [[9,4,3],
      [8,5,6],
      [0,2,7]]
assert no_anti_diag(m2) == [[9,4],
                            [8,6],
                            [2,7]]
m3 = [[8,5,3,4],
      [7,2,4,1],
      [9,8,3,5],
      [6,0,4,7]]
assert no_anti_diag(m3) == [[8,5,3],
                            [7,2,1],
                            [9,3,5],
                            [0,4,7]]
try:
    no_anti_diag([[2,3,5],
                  [1,5,2]])
    raise Exception("Avrei dovuto fallire!")
except ValueError:
    pass

def no_anti_diag(mat):
    raise Exception('TODO IMPLEMENT ME !')

m1 = [[3,4],
      [8,7]]
assert no_anti_diag(m1) == [[3],
                            [7]]

assert m1 == [[3,4],  # verifica che non abbia cambiato l'originale
              [8,7]]

m2 = [[9,4,3],
      [8,5,6],
      [0,2,7]]
assert no_anti_diag(m2) == [[9,4],
                            [8,6],
                            [2,7]]
m3 = [[8,5,3,4],
      [7,2,4,1],
      [9,8,3,5],
      [6,0,4,7]]
assert no_anti_diag(m3) == [[8,5,3],
                            [7,2,1],
                            [9,3,5],
                            [0,4,7]]
try:
    no_anti_diag([[2,3,5],
                  [1,5,2]])
    raise Exception("Avrei dovuto fallire!")
except ValueError:
    pass

Esercizio - repcol

✪✪ Data una matrice mat \(n\) x \(m\) e una lista di \(n\) elementi, MODIFICA mat scrivendo in ogni cella il valore corrispondente da lista.

• se lista ha lunghezza diversa da \(n\), lancia ValueError

• NON creare nuove liste

Esempio:

>>> m = [
            ['z','a','p','p','a'],
            ['c','a','r','t','a'],
            ['p','a','l','l','a']
        ]
>>> repcol( m, ['E','H','?'])   # non ritorna niente!
>>> m
[['E', 'E', 'E', 'E','E'],
 ['H', 'H', 'H', 'H','H'],
 ['?', '?', '?', '?','?']]

Mostra soluzione

def repcol(mat, lista):


    for i in range(len(mat)):
        for j in range(len(mat[0])):
            mat[i][j] = lista[i]



# INIZIO TEST
m1 = [ ['a'] ]
v1 = ['Q']
repcol(m1,v1)  # non ritorna niente!
assert m1 == [['Q']]

m2 = [
    ['a','b'],
    ['c','d'],
    ['e','f'],
    ['g','h'],
]

salvata = m2[0]   # salviamo puntatore alla prima riga originale
v2 = ['P','A','L','A']
repcol(m2,v2)  # non ritorna niente!
assert m2 == [['P', 'P'],
              ['A', 'A'],
              ['L', 'L'],
              ['A', 'A']]
assert id(salvata) == id(m2[0])  # non deve creare nuove liste

m3 = [
    ['z','a','p','p','a'],
    ['c','a','r','t','a'],
    ['p','a','l','l','a']
]

v3 = ['E','H','?']
repcol(m3,v3)  # non ritorna niente!
assert m3 == [['E', 'E', 'E', 'E','E'],
              ['H', 'H', 'H', 'H','H'],
              ['?', '?', '?', '?','?']]

def repcol(mat, lista):
    raise Exception('TODO IMPLEMENT ME !')

# INIZIO TEST
m1 = [ ['a'] ]
v1 = ['Q']
repcol(m1,v1)  # non ritorna niente!
assert m1 == [['Q']]

m2 = [
    ['a','b'],
    ['c','d'],
    ['e','f'],
    ['g','h'],
]

salvata = m2[0]   # salviamo puntatore alla prima riga originale
v2 = ['P','A','L','A']
repcol(m2,v2)  # non ritorna niente!
assert m2 == [['P', 'P'],
              ['A', 'A'],
              ['L', 'L'],
              ['A', 'A']]
assert id(salvata) == id(m2[0])  # non deve creare nuove liste

m3 = [
    ['z','a','p','p','a'],
    ['c','a','r','t','a'],
    ['p','a','l','l','a']
]

v3 = ['E','H','?']
repcol(m3,v3)  # non ritorna niente!
assert m3 == [['E', 'E', 'E', 'E','E'],
              ['H', 'H', 'H', 'H','H'],
              ['?', '?', '?', '?','?']]

Esercizio - matinc

✪✪ Data una matrice intera RITORNA True se tutte le righe sono strettamente crescenti da sinistra a destra, altrimenti ritorna False.

Esempio 1:

>>> m = [[1,4,6,7,9],
         [0,1,2,4,8],
         [2,6,8,9,10]]
>>> matinc(m)
True

Esempio 2:

>>> m = [[0,1,3,4],
         [4,6,9,10],
         [3,7,7,15]]
>>> matinc(m)
False

Mostra soluzione

def matinc(mat):

    for i in range(len(mat)):
        for j in range(1, len(mat[0])):
            if mat[i][j] <= mat[i][j-1]:
                return False
    return True


# TEST
m1 = [[5]]
assert matinc(m1) == True

m2 = [[7],
      [4]]
assert matinc(m2) == True

m3 = [[2,3],
      [3,5]]
assert matinc(m3) == True

m4 = [[9,4]]
assert matinc(m4) == False

m5 = [[5,5]]
assert matinc(m5) == False

m6 = [[1,4,6,7,9],
      [0,1,2,4,8],
      [2,6,8,9,10]]
assert matinc(m6) == True

m7 = [[0,1,3,4],
      [4,6,9,10],
      [3,7,7,15]]
assert matinc(m7) == False

m8 = [[1,4,8,7,9],
      [0,1,2,4,8]]
assert matinc(m8) == False

def matinc(mat):
    raise Exception('TODO IMPLEMENT ME !')

# TEST
m1 = [[5]]
assert matinc(m1) == True

m2 = [[7],
      [4]]
assert matinc(m2) == True

m3 = [[2,3],
      [3,5]]
assert matinc(m3) == True

m4 = [[9,4]]
assert matinc(m4) == False

m5 = [[5,5]]
assert matinc(m5) == False

m6 = [[1,4,6,7,9],
      [0,1,2,4,8],
      [2,6,8,9,10]]
assert matinc(m6) == True

m7 = [[0,1,3,4],
      [4,6,9,10],
      [3,7,7,15]]
assert matinc(m7) == False

m8 = [[1,4,8,7,9],
      [0,1,2,4,8]]
assert matinc(m8) == False

Esercizio - flip

✪✪ Prende una matrice come lista di liste in ingresso contenenti zeri e uni, e RITORNA una NUOVA matrice (sempre come lista di liste), costruita prima invertendo tutte le righe della matrice di input e poi rovesciando tutte le righe

Invertire una lista vuol dire trasformare gli 0 in 1 e gli 1 in 0. Per esempio:

• [0,1,1] diventa [1,0,0]

• [0,0,1] diventa [1,1,0]

Rovesciare una lista vuol dire che rovesciare l’ordine degli elementi. Per esempio:

• [0,1,1] diventa [1,1,0]

• [0,0,1] diventa [1,0,0]

Esempio: Combinando inversione e rovesciamento, per esempio se partiamo da

[
  [1,1,0,0],
  [0,1,1,0],
  [0,0,1,0]
]

Prima invertiamo ciascun elemento:

[
  [0,0,1,1],
  [1,0,0,1],
  [1,1,0,1]
]

e poi rovesciamo ciascuna riga:

[
  [1,1,0,0],
  [1,0,0,1],
  [1,0,1,1]

]

Suggerimenti:

• per rovesciare una lista usare il metodo .reverse() come in mia_lista.reverse() NOTA: mia_lista.reverse() modifica mia_lista, non ritorna una nuova lista !!

• ricordarsi ll return !!

Mostra soluzione

def flip(matrice):

    ret = []
    for riga in matrice:
        nuova_riga = []
        for elem in riga:
            nuova_riga.append(1 - elem)

        nuova_riga.reverse()
        ret.append(nuova_riga)
    return ret




assert flip([[]]) == [[]]
assert flip([[1]]) == [[0]]
assert flip([[1,0]]) == [[1,0]]

m1 = [ [1,0,0],
       [1,0,1] ]
r1 = [ [1,1,0],
       [0,1,0] ]
assert flip(m1) == r1


m2 = [ [1,1,0,0],
       [0,1,1,0],
       [0,0,1,0] ]

r2 = [ [1,1,0,0],
       [1,0,0,1],
       [1,0,1,1] ]

assert flip(m2) == r2

# verifica che l'm originale non sia cambiato !
assert m2 == [ [1,1,0,0],
               [0,1,1,0],
               [0,0,1,0] ]
# FINE TEST

def flip(matrice):
    raise Exception('TODO IMPLEMENT ME !')



assert flip([[]]) == [[]]
assert flip([[1]]) == [[0]]
assert flip([[1,0]]) == [[1,0]]

m1 = [ [1,0,0],
       [1,0,1] ]
r1 = [ [1,1,0],
       [0,1,0] ]
assert flip(m1) == r1


m2 = [ [1,1,0,0],
       [0,1,1,0],
       [0,0,1,0] ]

r2 = [ [1,1,0,0],
       [1,0,0,1],
       [1,0,1,1] ]

assert flip(m2) == r2

# verifica che l'm originale non sia cambiato !
assert m2 == [ [1,1,0,0],
               [0,1,1,0],
               [0,0,1,0] ]
# FINE TEST

Esercizio - muro

✪✪✪ Dato una lista ripe di ripetizioni e una matrice n x m mat come lista di liste, RITORNA una matrice completamente NUOVA prendendo le righe di mat e replicandole il numero di volte indicato nelle corrispondenti celle di ripe

• NON devono risultare puntatori dalla matrice nuova a quella vecchia!

Esempio:

>>> muro([3,4,1,2], [['i','a','a'],
                     ['q','r','f'],
                     ['y','e','v'],
                     ['e','g','h']])
[['i', 'a', 'a'],
 ['i', 'a', 'a'],
 ['i', 'a', 'a'],
 ['q', 'r', 'f'],
 ['q', 'r', 'f'],
 ['q', 'r', 'f'],
 ['q', 'r', 'f'],
 ['y', 'e', 'v'],
 ['e', 'g', 'h'],
 ['e', 'g', 'h']]

Mostra soluzione

def muro(ripe, mat):

    res = []

    i = 0
    for i in range(len(mat)):
        riga = mat[i]
        n = ripe[i]
        for i in range(n):
            res.append(riga[:])
    return res


m1 = [['a']]
assert muro([2], m1) == [['a'],
                         ['a']]

m2 = [['a','b','c','d'],
      ['e','q','v','r']]
r2 = muro([3,2], m2)
assert r2 == [['a','b','c','d'],
              ['a','b','c','d'],
              ['a','b','c','d'],
              ['e','q','v','r'],
              ['e','q','v','r']]
r2[0][0] = 'z'
assert m2 == [['a','b','c','d'],  # vogliamo una NUOVA matrice
              ['e','q','v','r']]

m3 = [['i','a','a'],
      ['q','r','f'],
      ['y','e','v'],
      ['e','g','h']]
r3 = muro([3,4,1,2], m3)
assert r3 == [['i', 'a', 'a'],
              ['i', 'a', 'a'],
              ['i', 'a', 'a'],
              ['q', 'r', 'f'],
              ['q', 'r', 'f'],
              ['q', 'r', 'f'],
              ['q', 'r', 'f'],
              ['y', 'e', 'v'],
              ['e', 'g', 'h'],
              ['e', 'g', 'h']]

def muro(ripe, mat):
    raise Exception('TODO IMPLEMENT ME !')

m1 = [['a']]
assert muro([2], m1) == [['a'],
                         ['a']]

m2 = [['a','b','c','d'],
      ['e','q','v','r']]
r2 = muro([3,2], m2)
assert r2 == [['a','b','c','d'],
              ['a','b','c','d'],
              ['a','b','c','d'],
              ['e','q','v','r'],
              ['e','q','v','r']]
r2[0][0] = 'z'
assert m2 == [['a','b','c','d'],  # vogliamo una NUOVA matrice
              ['e','q','v','r']]

m3 = [['i','a','a'],
      ['q','r','f'],
      ['y','e','v'],
      ['e','g','h']]
r3 = muro([3,4,1,2], m3)
assert r3 == [['i', 'a', 'a'],
              ['i', 'a', 'a'],
              ['i', 'a', 'a'],
              ['q', 'r', 'f'],
              ['q', 'r', 'f'],
              ['q', 'r', 'f'],
              ['q', 'r', 'f'],
              ['y', 'e', 'v'],
              ['e', 'g', 'h'],
              ['e', 'g', 'h']]

Esercizio - ordinul

✪✪✪ Data una matrice come lista di liste di numeri interi, MODIFICA la matrice ordinando SOLO i numeri nell’ultima colonna

• Tutte le altre celle NON devono cambiare

Esempio:

>>> m = [[8,5,3,2,4],
         [7,2,4,1,1],
         [9,8,3,3,7],
         [6,0,4,2,5]]
>>> ordinul(m)
>>> m
[[8, 5, 3, 2, 1],
 [7, 2, 4, 1, 4],
 [9, 8, 3, 3, 5],
 [6, 0, 4, 2, 7]]

Mostra soluzione

def ordinul(mat):


    ordinata = sorted([mat[i][-1] for i in range(len(mat))])
    for i in range(len(mat)):
        mat[i][-1] = ordinata[i]


# TEST
m1 = [[3]]
ordinul(m1)
assert m1 == [[3]]

m2 = [[9,3,7],
      [8,5,4]]
ordinul(m2)
assert m2 == [[9,3,4],
              [8,5,7]]

m3 = [[8,5,9],
      [7,2,3],
      [9,8,7]]
ordinul(m3)
assert m3 == [[8,5,3],
              [7,2,7],
              [9,8,9]]

m4 = [[8,5,3,2,4],
      [7,2,4,1,1],
      [9,8,3,3,7],
      [6,0,4,2,5]]
ordinul(m4)
assert m4 == [[8, 5, 3, 2, 1],
              [7, 2, 4, 1, 4],
              [9, 8, 3, 3, 5],
              [6, 0, 4, 2, 7]]

assert ordinul([[3]]) == None

def ordinul(mat):
    raise Exception('TODO IMPLEMENT ME !')

# TEST
m1 = [[3]]
ordinul(m1)
assert m1 == [[3]]

m2 = [[9,3,7],
      [8,5,4]]
ordinul(m2)
assert m2 == [[9,3,4],
              [8,5,7]]

m3 = [[8,5,9],
      [7,2,3],
      [9,8,7]]
ordinul(m3)
assert m3 == [[8,5,3],
              [7,2,7],
              [9,8,9]]

m4 = [[8,5,3,2,4],
      [7,2,4,1,1],
      [9,8,3,3,7],
      [6,0,4,2,5]]
ordinul(m4)
assert m4 == [[8, 5, 3, 2, 1],
              [7, 2, 4, 1, 4],
              [9, 8, 3, 3, 5],
              [6, 0, 4, 2, 7]]

assert ordinul([[3]]) == None

Esercizio - gratt

Il profilo di una città può essere rappresentato come una matrice 2D dove gli 1 rappredentano gli edifici. Nell’esempio sotto, l’altezza dell’edificio più alto è 4 (la seconda colonna da destra)

[[0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0],
 [0, 0, 1, 0, 1, 0],
 [0, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 1]]

Scrivi una funzione che prende un profilo come lista 2-D di 0 e 1 e RITORNA l’altezza del grattacielo più alto, per altri esempi vedere gli assert.

Mostra soluzione

def gratt(mat):

    n,m = len(mat), len(mat[0])
    for i in range(n):
        for j in range(m):
            if mat[i][j] == 1:
                return n-i
    return 0


assert gratt([[0, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 1, 0],
              [0, 0, 1, 0, 1, 0],
              [0, 1, 1, 1, 1, 0],
              [1, 1, 1, 1, 1, 1]])  == 4

assert gratt([ [0, 0, 0, 0],
               [0, 1, 0, 0],
               [0, 1, 1, 0],
               [1, 1, 1, 1] ]) == 3

assert gratt([ [0, 1, 0, 0],
               [0, 1, 0, 0],
               [0, 1, 1, 0],
               [1, 1, 1, 1] ]) == 4

assert gratt([ [0, 0, 0, 0],
               [0, 0, 0, 0],
               [1, 1, 1, 0],
               [1, 1, 1, 1] ]) == 2

def gratt(mat):
    raise Exception('TODO IMPLEMENT ME !')

assert gratt([[0, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 1, 0],
              [0, 0, 1, 0, 1, 0],
              [0, 1, 1, 1, 1, 0],
              [1, 1, 1, 1, 1, 1]])  == 4

assert gratt([ [0, 0, 0, 0],
               [0, 1, 0, 0],
               [0, 1, 1, 0],
               [1, 1, 1, 1] ]) == 3

assert gratt([ [0, 1, 0, 0],
               [0, 1, 0, 0],
               [0, 1, 1, 0],
               [1, 1, 1, 1] ]) == 4

assert gratt([ [0, 0, 0, 0],
               [0, 0, 0, 0],
               [1, 1, 1, 0],
               [1, 1, 1, 1] ]) == 2

Esercizio - discarica

✪✪✪ La multinazionale ToxiCorp vuole assumerti per sviluppare un camion a guida automatica che depositerà materiali altamente contaminati nelle discariche illegali che possiede in tutto il mondo. Lo trovi eticamente questionabile, ma pagano bene, e quindi accetti.

Una discarica è modellata come una regione rettangolare di dimensioni nrow e ncol, implementata come una matrice di liste. Ogni cella i,j contiene le tonnellate di materiali contaminati presenti, e può contenere al massimo 7 tonnellate di materiale.

Il camion dei rifiuti trasporterà q tonnellate di materiale, e proverà a riempire la discarica depositando i rifiuti nella prima riga, riempiendo ogni cella fino a 7 tonnellate. Quando la prima riga sarà riempita, procederà con la seconda riga a partire da sinistra, quindi la terza di nuovo da sinistra fino a che non ci sono più rifiuti da smaltire.

La funzione discarica(n,m) prende in input mat e il numero di tonnellate q da smaltire, e RITORNA una NUOVA lista rappresentante un piano con la sequenza di tonnellate da smaltire. Se i rifiuti da eliminare eccedono la dimensione della discarica, solleva ValueError.

NOTA: la funzione NON modifica la matrice

Esempio - data:

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

>>> discarica(m, 22)

[2, 3, 1, 3, 0, 6, 4, 3]

Per la prima riga smaltiamo 2,3,1 tonnellate in tre celle, nella seconda riga smaltiamo 3,0,6 tonnellate in tre celle, nella terza riga smaltiamo solo 4, 3 tonnellate in due celle perchè il limite q=22 è raggiunto

Mostra soluzione

def discarica(mat, q):

    rimanente = q
    ret = []

    for riga in mat:
        for j in range(len(riga)):
            da_riempire = 7 - riga[j]
            scarica = min(da_riempire, rimanente)
            rimanente -= scarica

            if rimanente > 0:
                ret.append(scarica)
            else:
                if scarica > 0:
                    ret.append(scarica)
                return ret

    if rimanente > 0:
        raise ValueError("Non posso riempire la discarica, rimangono %s tonnellate!" % rimanente)


# INIZIO TEST - NON TOCCARE !

m1 = [ [5] ]
assert discarica(m1,0) == []  # niente da scaricare

m2 = [ [4] ]
assert discarica(m2,2) == [2]

m3 = [ [5,4] ]
assert discarica(m3,3) == [2, 1]


m3 = [ [5,7,3] ]
assert discarica(m3,3) == [2, 0, 1]


m5 = [ [2,5],   # 5 2
       [4,3] ]  # 3 1
assert discarica(m5,11) == [5,2,3,1]


m6 = [ [5,4,6],   # 2 3 1  # tonnellate da scaricare in ciascuna cella
       [4,7,1],   # 3 0 6
       [3,2,6],   # 4 3 0
       [3,6,2] ]  # 0 0 0

assert discarica(m6, 22) == [2,3,1,3,0,6,4,3]

try:
    discarica ([[5]], 10)
    raise Exception("Dovrei aver fallito !")
except ValueError:
    pass
# TEST END

def discarica(mat, q):
    raise Exception('TODO IMPLEMENT ME !')

# INIZIO TEST - NON TOCCARE !

m1 = [ [5] ]
assert discarica(m1,0) == []  # niente da scaricare

m2 = [ [4] ]
assert discarica(m2,2) == [2]

m3 = [ [5,4] ]
assert discarica(m3,3) == [2, 1]


m3 = [ [5,7,3] ]
assert discarica(m3,3) == [2, 0, 1]


m5 = [ [2,5],   # 5 2
       [4,3] ]  # 3 1
assert discarica(m5,11) == [5,2,3,1]


m6 = [ [5,4,6],   # 2 3 1  # tonnellate da scaricare in ciascuna cella
       [4,7,1],   # 3 0 6
       [3,2,6],   # 4 3 0
       [3,6,2] ]  # 0 0 0

assert discarica(m6, 22) == [2,3,1,3,0,6,4,3]

try:
    discarica ([[5]], 10)
    raise Exception("Dovrei aver fallito !")
except ValueError:
    pass
# TEST END

Esercizio - school lab

✪✪✪ Se sei un insegnante che vede spesso nuovi studenti, hai questo problema: se due studenti amici si siedono fianco a fianco, c’è il rischio che parlino troppo. Per tenerli quieti, in qualche vuoi modo rendere casuale la posizione degli studenti seguendo questo procedimento:

1. prima ordina gli studenti alfabeticamente

2. gli studenti ordinati poi si siedono progressivamente alle sedie disponibili uno per uno, prima riempiendo la prima riga, poi la seconda, fino alla fine

Adesso implementa l’algoritmo.

INPUT:

• studenti: una lista di stringhe di lunghezza \(\leq n*m\)

• sedie: una matrice n x m come lista di liste riempite con valori None (sedie vuote)

OUTPUT: MODIFICA SIA gli studenti che le sedie, senza ritornare nulla

• Se gli studenti sono più delle sedie disponibili, solleva un ValueError

Esempio:

st =  ['b', 'd', 'e', 'g', 'c', 'a', 'h', 'f' ]

mat = [
            [None, None, None],
            [None, None, None],
            [None, None, None],
            [None, None, None]
         ]

lab(st,  mat)

dopo l’esecuzione, mat risulta cambiata così:

assert mat == [
                ['a',  'b', 'c'],
                ['d',  'e', 'f'],
                ['g',  'h',  None],
                [None, None, None],
              ]

dopo l’esecuzione, input st dovrebbe essere ordinato:

assert st == ['a','b','c','d','e','f','g','f']

Per altri esempi, vedere i test

Mostra soluzione

def lab(studenti, sedie):


    n = len(sedie)
    m = len(sedie[0])

    if len(studenti) > n*m:
        raise ValueError("Ci sono più studenti che sedie! Studenti = %s, sedie = %sx%s" % (len(studenti), n, m))

    i = 0
    j = 0
    studenti.sort()
    for s in studenti:
        sedie[i][j] = s

        if j == m - 1:
            j = 0
            i += 1
        else:
            j += 1


try:
    lab(['a','b'], [[None]])
    raise Exception("TEST FALLITO: Mi aspettavo un ValueError!")
except ValueError:
    "Test passato"

try:
    lab(['a','b','c'], [[None,None]])
    raise Exception("TEST FALLITO: Mi aspettavo un ValueError!")
except ValueError:
    "Test passato"

m0 = [ [None] ]

r0 = lab([],m0)
assert m0 == [ [None] ]
assert r0 == None  # si suppone la funzione non ritorni nulla
                   # (perciò ritorna None di default)

m1 = [ [None] ]
r1 = lab(['a'], m1)

assert m1 == [ ['a'] ]
assert r1 == None  # si suppone la funzione non ritorni nulla
                   # (perciò ritorna None di default)

m2 = [ [None, None] ]
lab(['a'], m2)  # 1 studente 2 sedie in una fila

assert m2 == [ ['a', None] ]

m3 = [ [None],
       [None] ]
lab(['a'], m3) # 1 studente 2 sedie in una colonna
assert m3 == [ ['a'],
               [None] ]

ss4 = ['b', 'a']
m4 = [ [None, None] ]
lab(ss4, m4)  # 2 studenti 2 sedie in una fila

assert m4 == [ ['a','b'] ]
assert ss4 == ['a', 'b']  # modificato anche lista di input
                          # come richiesto dal testo della funzione

m5 = [ [None, None],
       [None, None] ]
lab(['b', 'c', 'a'], m5)  # 3 studenti 2x2 sedie

assert m5 == [ ['a','b'],
               ['c', None] ]

m6 = [ [None, None],
       [None, None] ]
lab(['b', 'd', 'c', 'a'], m6)  # 4 studenti 2x2 sedie

assert m6 == [ ['a','b'],
               ['c','d'] ]

m7 = [ [None, None, None],
       [None, None, None] ]
lab(['b', 'd', 'e', 'c', 'a'], m7)  # 5 studenti 3x2 sedie

assert m7 == [ ['a','b','c'],
               ['d','e',None] ]

ss8 = ['b', 'd', 'e', 'g', 'c', 'a', 'h', 'f' ]
m8 = [ [None, None, None],
       [None, None, None],
       [None, None, None],
       [None, None, None] ]
lab(ss8, m8)  # 8 studenti 3x4 sedie

assert m8 == [ ['a',  'b',  'c'],
               ['d',  'e',  'f'],
               ['g',  'h',  None],
               [None, None, None] ]

assert ss8 == ['a','b','c','d','e','f','g','h']

def lab(studenti, sedie):
    raise Exception('TODO IMPLEMENT ME !')

try:
    lab(['a','b'], [[None]])
    raise Exception("TEST FALLITO: Mi aspettavo un ValueError!")
except ValueError:
    "Test passato"

try:
    lab(['a','b','c'], [[None,None]])
    raise Exception("TEST FALLITO: Mi aspettavo un ValueError!")
except ValueError:
    "Test passato"

m0 = [ [None] ]

r0 = lab([],m0)
assert m0 == [ [None] ]
assert r0 == None  # si suppone la funzione non ritorni nulla
                   # (perciò ritorna None di default)

m1 = [ [None] ]
r1 = lab(['a'], m1)

assert m1 == [ ['a'] ]
assert r1 == None  # si suppone la funzione non ritorni nulla
                   # (perciò ritorna None di default)

m2 = [ [None, None] ]
lab(['a'], m2)  # 1 studente 2 sedie in una fila

assert m2 == [ ['a', None] ]

m3 = [ [None],
       [None] ]
lab(['a'], m3) # 1 studente 2 sedie in una colonna
assert m3 == [ ['a'],
               [None] ]

ss4 = ['b', 'a']
m4 = [ [None, None] ]
lab(ss4, m4)  # 2 studenti 2 sedie in una fila

assert m4 == [ ['a','b'] ]
assert ss4 == ['a', 'b']  # modificato anche lista di input
                          # come richiesto dal testo della funzione

m5 = [ [None, None],
       [None, None] ]
lab(['b', 'c', 'a'], m5)  # 3 studenti 2x2 sedie

assert m5 == [ ['a','b'],
               ['c', None] ]

m6 = [ [None, None],
       [None, None] ]
lab(['b', 'd', 'c', 'a'], m6)  # 4 studenti 2x2 sedie

assert m6 == [ ['a','b'],
               ['c','d'] ]

m7 = [ [None, None, None],
       [None, None, None] ]
lab(['b', 'd', 'e', 'c', 'a'], m7)  # 5 studenti 3x2 sedie

assert m7 == [ ['a','b','c'],
               ['d','e',None] ]

ss8 = ['b', 'd', 'e', 'g', 'c', 'a', 'h', 'f' ]
m8 = [ [None, None, None],
       [None, None, None],
       [None, None, None],
       [None, None, None] ]
lab(ss8, m8)  # 8 studenti 3x4 sedie

assert m8 == [ ['a',  'b',  'c'],
               ['d',  'e',  'f'],
               ['g',  'h',  None],
               [None, None, None] ]

assert ss8 == ['a','b','c','d','e','f','g','h']

Esercizio - toepliz

✪✪✪ RITORNA True se la matrice come lista di liste in input è Toeplitz, mentre RITORNA False se non lo è.

• Una matrice è Toeplitz se e solo se ogni diagonale contiene gli stessi elementi.

• Assumiamo che la matrice contenga sempre almeno una riga di almeno un elemento

SUGGERIMENTO: usa due for, nel primo scorri la matrice per righe, nel secondo per colonne

Prova a chiederti:

• da che riga occorre partire per la scansione? La prima è utile?

• da che colonna occorre partire per la scansione? La prima è utile?

• se scorriamo le righe dalla prima verso l’ultima e stiamo esaminando un certo numero ad una certa riga, che condizione deve rispettare quel numero affinchè la matrice sia toepliz ?

Esempi:

>>> m1 = [
            [1,2,3,4],
            [5,1,2,3],
            [9,5,1,2]
        ]

>>> toepliz(m1)
True

Su ogni diagonale ci sono gli stessi numeri e quindi viene restituito True

>>> m2 = [
            [1, 2, 3, 4],
            [5, 1, 4, 3],
            [9, 3, 1, 2]
         ]

>>> toepliz(m2)
False

C’è almeno una diagonale con numeri diversi, in questo caso abbiamo le diagonali (5,3) e (2,4,2) e quindi viene restituito False

Mostra soluzione

def toepliz(matrix):

    for i in range(1,len(matrix)):
        for j in range(1,len(matrix[0])):
            if matrix[i][j] != matrix[i-1][j-1]:
                return False
    return True


# INIZIO TEST - NON TOCCARE !
assert toepliz([ [1] ]) == True
assert toepliz([ [3,7],
                 [5,3] ]) == True
assert toepliz([ [3,7],
                 [3,5] ]) == False
assert toepliz([ [3,7],
                 [3,5] ]) == False
assert toepliz([ [3,7,9],
                 [5,3,7] ]) == True
assert toepliz([ [3,7,9],
                 [5,3,8] ]) == False

assert toepliz([ [1,2,3,4],
                 [5,1,2,3],
                 [9,5,1,2] ]) == True

assert toepliz([ [1,2,3,4],
                 [5,9,2,3],
                 [9,5,1,2] ]) == False
# FINE TEST

def toepliz(matrix):
    raise Exception('TODO IMPLEMENT ME !')

# INIZIO TEST - NON TOCCARE !
assert toepliz([ [1] ]) == True
assert toepliz([ [3,7],
                 [5,3] ]) == True
assert toepliz([ [3,7],
                 [3,5] ]) == False
assert toepliz([ [3,7],
                 [3,5] ]) == False
assert toepliz([ [3,7,9],
                 [5,3,7] ]) == True
assert toepliz([ [3,7,9],
                 [5,3,8] ]) == False

assert toepliz([ [1,2,3,4],
                 [5,1,2,3],
                 [9,5,1,2] ]) == True

assert toepliz([ [1,2,3,4],
                 [5,9,2,3],
                 [9,5,1,2] ]) == False
# FINE TEST

Esercizio - Moltiplicazione di matrici

Guarda la definizione di moltiplicazione di matrici su Wikipedia e prova ad implementarla nella funzione seguente.

In sostanza, data una matrice nxm A e una matrice mxp B devi ritornare come output una matrice nxp C calcolando le celle \(c_{ij}\) con la formula

\(c_{ij} = a_{i1}b_{1j} +\cdots + a_{im}b_{mj}= \sum_{k=1}^m a_{ik}b_{kj}\)

Devi riempire tutte le nxp celle di C, perciò per assicurarti di riempire un rettangolo hai bisogno di due for. Hai forse bisogno di un’altro for? Aiutati con il diagramma seguente.

✪✪✪ ESERCIZIO: Implementa la funzione mul che date le matrici n x m mat1 e m x p mat2, RITORNA una NUOVA matrice n x p che è il risultato della moltiplicazione di mat1 per mat2.

• Se mat1 ha il numero di colonna diverso dal numero di righe di mat2, lancia un ValueError.

Mostra soluzione

def mul(mat1, mat2):

    n = len(mat1)
    m = len(mat1[0])
    p = len(mat2[0])
    if m != len(mat2):
        raise ValueError("il numero di colonne di mat1 %s deve essere uguale al numero di righe di mat2 %s !" % (m, len(mat2)))
    ret = [[0]*p for i in range(n)]
    for i in range(n):
        for j in range(p):
            ret[i][j] = 0
            for k in range(m):
                ret[i][j] += mat1[i][k] * mat2[k][j]
    return ret


# proviamo con dimensioni sbagliate per la matrice:
try:
    mul([[3,5]], [[7]])
    raise Exception("AVREI DOVUTO FALLIRE !")
except ValueError:
    pass

m11 = [ [3] ]
m12 = [ [5] ]
assert mul(m11,m12) == [ [15] ]

m21 = [ [3],
        [5] ]
m22 = [ [2,6] ]

assert mul(m21,m22) == [ [3*2, 3*6],
                         [5*2, 5*6] ]

m31 = [ [3,5] ]
m32 = [ [2],
        [6] ]
assert mul(m31,m32) == [ [3*2 + 5*6] ]

m41 = [ [3,5],
        [7,1],
        [9,4] ]
m42 = [ [4,1,5,7],
        [8,5,2,7] ]
assert mul(m41,m42) == [ [52, 28, 25, 56],
                         [36, 12, 37, 56],
                         [68, 29, 53, 91] ]

def mul(mat1, mat2):
    raise Exception('TODO IMPLEMENT ME !')

# proviamo con dimensioni sbagliate per la matrice:
try:
    mul([[3,5]], [[7]])
    raise Exception("AVREI DOVUTO FALLIRE !")
except ValueError:
    pass

m11 = [ [3] ]
m12 = [ [5] ]
assert mul(m11,m12) == [ [15] ]

m21 = [ [3],
        [5] ]
m22 = [ [2,6] ]

assert mul(m21,m22) == [ [3*2, 3*6],
                         [5*2, 5*6] ]

m31 = [ [3,5] ]
m32 = [ [2],
        [6] ]
assert mul(m31,m32) == [ [3*2 + 5*6] ]

m41 = [ [3,5],
        [7,1],
        [9,4] ]
m42 = [ [4,1,5,7],
        [8,5,2,7] ]
assert mul(m41,m42) == [ [52, 28, 25, 56],
                         [36, 12, 37, 56],
                         [68, 29, 53, 91] ]

Esercizio - check_nqueen

✪✪✪✪ E ora un problema difficile, per i più tenaci!

Hai una matrice nxn di booleani che rappresenta una scacchiera dove il valore True significa che c’è una regina nella cella, e False significa cella vuota.

Ai fini della visualizzazione, possiamo rappresentare una configurazione usando . per significare False e lettere come A e B per indicare che c’è una regina in una cella. Contrariamente a quanto abbiamo fatto sino ad adesso, per convenienza mostriamo la matrice con le j che vanno dal basso fino alla sommità.

Vediamo un esempio. In questo caso A e B non possono attaccare ciascun’altro, perciò l’algoritmo ritorna True:

    7  ......B.
    6  ........
    5  ........
    4  ........
    3  ....A...
    2  ........
    1  ........
    0  ........
    i
     j 01234567


Vediamo perchè evidenziando le linee di attacco di A ..

    7  \...|.B.
    6  .\..|../
    5  ..\.|./.
    4  ...\|/..
    3  ----A---
    2  .../|\..
    1  ../.|.\.
    0  ./..|..\
    i
     j 01234567


... e quelle di B :

    7  ------B-
    6  ...../|\
    5  ..../.|.
    4  .../..|.
    3  ../.A.|.
    2  ./....|.
    1  /.....|.
    0  ......|.
    i
     j 01234567

In quest’altro caso l’algoritmo ritornerebbe False perchè A e B possono attaccare ciascun altro:

7  \./.|...
6  -B--|--/
5  /|\.|./.
4  .|.\|/..
3  ----A---
2  .|./|\..
1  .|/.|.\.
0  ./..|..\
i
 j 01234567

Nel tuo algoritmo, prima devi cercare le regine. Quando ne trovi una (e per ciascuna di esse !), devi controllare se può essere colpita da un’altra regina. Vediamo come:

In questa tabella 7x7 abbiamo solo una regina A, alla posizione i=1 e j=4:

6  ....|..
5  \...|..
4  .\..|..
3  ..\.|./
2  ...\|/.
1  ----A--
0  .../|\.
i
 j 0123456

Per comprendere completamente il range della regina e come calcolare le diagonali, è conveniente estendere visualmente la tabella così da avere le diagonali che intersichino gli assi. Nota inoltre che abbiamo aggiunto le lettere y e x

NOTA: nell’algoritmo non hai bisogno di estendere la matrice !

 y
 6  ....|....
 5  \...|.../
 4  .\..|../.
 3  ..\.|./..
 2  ...\|/...
 1  ----A----
 0  .../|\...
-1  ../.|.\..
-2  ./..|..\.
-3  /...|...\
 i
  j 01234567 x

Vediamo che la diagonale da sinistra in alto a in basso a destra interseca l’asse verticale a y = 5 e che la diagonale da in basso a sinistra a in alto a destra interseca l’asse a y = -3. Dovresti usare queste informazioni per calcolare le equazioni di linea.

ESERCIZIO: Adessi dovresti avere tutti i suggerimenti necessari per procedere con l’implementazione. Implementa la funzione check_nqueen, che prende una matrice nxn di booleani che rappresentano una scacchiera dove True sinifica che c’è una regina nella cella, e False che non c’è niente. La funzione RITORNA True se nessuna regina può attaccare le altre, False altrimenti.

Mostra soluzione

def check_nqueen(mat):


    # equazione linea dal basso sinistra fino ad alto destra
    # y = x - 3
    # -3 = -j + i
    # y = x -j + i

    # equazione linea dall'alto sinistra al basso destra
    # y = x + 5
    # 5 = j + i
    # y = x + j + i

    n = len(mat)
    for i in range(n):
        for j in range(n):
            if mat[i][j]:  # queen is found at i,j
                for y in range(n):            # vertical scan
                    if y != i and mat[y][j]:
                        return False
                for x in range(n):            # horizontal scan
                    if x != j and mat[i][x]:
                        return False
                for x in range(n):
                    y = x + j + i       # top-left to bottom-right
                    if y >= 0 and y < n and y != i and x != j and mat[y][x]:
                        return False
                    y = x - j + i       # bottom-left to top-right
                    if y >= 0 and y < n and y != i and x != j and mat[y][x]:
                        return False

    return True


assert check_nqueen([ [True] ])
assert check_nqueen([ [True, True],
                      [False, False] ]) == False

assert check_nqueen([ [True, False],
                      [False, True] ]) == False

assert check_nqueen([ [True, False],
                      [True, False] ]) == False

assert check_nqueen([ [True,  False, False],
                      [False, False, True],
                      [False, False, False] ]) == True

assert check_nqueen([ [True,  False, False],
                      [False, False, False],
                      [False, False, True] ]) == False


assert check_nqueen([ [False, True,  False],
                      [False, False, False],
                      [False, False, True] ]) == True

assert check_nqueen([ [False, True,  False],
                      [False, True, False],
                      [False, False, True] ]) == False

def check_nqueen(mat):
    raise Exception('TODO IMPLEMENT ME !')

assert check_nqueen([ [True] ])
assert check_nqueen([ [True, True],
                      [False, False] ]) == False

assert check_nqueen([ [True, False],
                      [False, True] ]) == False

assert check_nqueen([ [True, False],
                      [True, False] ]) == False

assert check_nqueen([ [True,  False, False],
                      [False, False, True],
                      [False, False, False] ]) == True

assert check_nqueen([ [True,  False, False],
                      [False, False, False],
                      [False, False, True] ]) == False


assert check_nqueen([ [False, True,  False],
                      [False, False, False],
                      [False, False, True] ]) == True

assert check_nqueen([ [False, True,  False],
                      [False, True, False],
                      [False, False, True] ]) == False

Prosegui

Continua con le challenges