Esercizio: funzioni ricorsive.

Un piccolo esercizio sulla ricorsione, proposto su forumpython.it:
Si consideri il seguente solitario: abbiamo una sequenza iniziale di N interi; una mossa consiste nel selezionare due numeri consecutivi la cui somma sia pari, e sostituirli con la loro media aritmetica. Data una configurazione iniziale noi siamo interessati a trovare la lista di tutte le possibili configurazioni finali (quelle per cui non c’è possibilità di continuare il gioco per mancanza di possibili mosse).
Ad esempio dalla configurazione
"10 20 30 40 5 1"
le possibili configurazioni finali sono 5:
["8", "14", "17", "15 20 1", "10 25 40 3"]
L’esercizio prescrive poi di usare una funzione ricorsiva, che deve accettare in input una stringa di numeri separati da spazio e restituire una lista di stringhe, come nell’esempio.
Azzardiamo una soluzione in cinque minuti. Per prima cosa separiamo la parte interessante da quella noiosa: la faccenda dell’input come stringa e output come lista di stringhe è del tutto secondaria e ce ne occuperemo più in là. Cominciamo invece a scrivere una funzione che accetta, com’è naturale, una lista di interi:
def game_engine(lst):
    founds = set()
    # ... tutto il resto
    return founds
Le nostre soluzioni saranno raccolte in founds che è un set perché, così a occhio, troveremo un sacco di doppioni e non vogliamo portarceli dietro. Per prima cosa, liberiamoci del caso degenere in cui la nostra lista sia più corta di due elementi: quando è così, questa è già sicuramente una configurazione “finale” che non può essere accorciata, e merita di essere aggiunta alle soluzioni:
def game_engine(lst):
    founds = set()
    if len(lst) < 2:
        founds.add(tuple(lst))
    else:
        # ... tutto il resto
    return founds
Al momento di aggiungere una soluzione a founds dobbiamo trasformarla in tupla, perché un set non può contenere liste. Questo è un po’ scomodo, ma l’alternativa è tenere le soluzioni in una lista e dover cercare ogni volta se la soluzione non è già presente: if lst not in founds: founds.append(lst).
Il nostro compito a questo punto sarebbe di scansionare la lista alla ricerca di coppie “eliminabili” (ossia la cui somma è pari). Qualunque sia il nostro metodo di scansione, va detto che se non troviamo nessuna coppia eliminabile vuol dire che la lista è “finale” e deve essere aggiunta alle soluzioni. Gestiamo prima di tutto questo caso, aggiungendo un semplice flag:
def game_engine(lst):
    founds = set()
    if len(lst) < 2:
        founds.add(tuple(lst))
    else:
        no_change = True
        # ... scansioniamo la lista
        if no_change:
            founds.add(tuple(lst))
    return founds
Adesso affrontiamo il problema principale, ovvero scansionare la lista alla ricerca di coppie “eliminabili”:
def game_engine(lst):
    founds = set()
    if len(lst) < 2:
        founds.add(tuple(lst))
    else:
        no_change = True
        for i in range(len(lst)-1):
            s = lst[i] + lst[i+1]
            if s % 2 == 0:
                no_change = False
                lst_copy = lst[:]
                lst_copy[i] = s // 2
                lst_copy.pop(i+1)
                founds.update(game_engine(lst_copy))
        if no_change:
            founds.add(tuple(lst))
    return founds
Ecco quel che succede: prendendo un elemento alla volta, lo sommiamo con il suo successore. Se la somma è pari, allora dobbiamo prima di tutto segnalare che la lista sta per essere modificata (no_change = False) e quindi non deve essere considerata “finale”. Poi dobbiamo fare una copia della lista: questo perché dobbiamo comunque tenere la lista originale intatta per proseguire successivamente nella scansione (potrebbero esserci altre coppie “eliminabili” più in là). Dalla lista copiata eliminiamo la coppia che ci interessa sostituendo l’elemento con la media, e rimuovendo il successore.
A questo punto entra in gioco la ricorsione: la nuova lista così ottenuta viene passata di nuovo alla nostra funzione, per cercare ulteriori soluzioni. Questa ricerca “annidata” produrrà un suo set founds di soluzioni, che aggiungeremo semplicemente a quello che abbiamo già (founds.update(...)). Alla fine, ogni funzione annidata non potrà che arrivare a una configurazione finale e restituire le sue soluzioni senza più ulteriori chiamate ricorsive.
Se provate questa funzione con qualche semplice lista di numeri, vedrete che… funziona appunto (per comodità metto i test alla fine: inutile dire che invece dovreste scriverli man mano che procedete…). Abbiamo un problema, però: non appena la lista di partenza diventa un po’ lunga, dieci elementi o giù di lì, il tempo di esecuzione si fa noiosamente lungo. Per fortuna c’è un modo facile per ottimizzare: se provate a fare a mano qualche esempio, vi accorgerete ben presto che molti rami dell’albero delle soluzioni si ripetono identici. Basterà quindi tener conto di tutte le sotto-liste man mano che finiamo di scansionarle, per evitare di perdere tempo a ripeterle:
def faster_game_engine(lst, already_done=None):
    founds = set()
    if already_done is None:
        already_done = set()
    lst_as_tuple = tuple(lst)
    if len(lst) < 2:
        already_done.add(lst_as_tuple)
        founds.add(lst_as_tuple)
    else:
        if lst_as_tuple not in already_done:
            no_change = True
            for i in range(len(lst)-1):
                s = lst[i] + lst[i+1]
                if s % 2 == 0:
                    no_change = False
                    lst_copy = lst[:]
                    lst_copy[i] = s // 2
                    lst_copy.pop(i+1)
                    founds.update(faster_game_engine(lst_copy, already_done))
            already_done.add(lst_as_tuple)
            if no_change:
                founds.add(lst_as_tuple)
    return founds
already_done è un set dove raccogliamo tutte le sotto-liste man mano che diventano “finali”, cioè che abbiamo finito di scansionarle. Il consueto pattern if already_done is None:... serve a proteggerci dalla vecchia trappola degli argomenti di default mutabili (ricordiamo che i set, come le liste, sono mutabili!). Prima di imbarcarci nella scansione vera e propria, controlliamo di non aver già incontrato in passato quella lista (if lst_as_tuple not in already_done). Infine passiamo a ogni chiamata ricorsiva successiva anche un riferimento a already_done (e quindi a tutte le sotto-liste scansionate fino a quel momento).
Se provate questa versione della nostra funzione con una lista più lunga, scoprirete di aver guadagnato tutta la velocità che vi serve.
Non resta che occuparci degli aspetti noiosi del problema: scriviamo una funzione separata che ha il compito di formattare gli input e gli output come vuole l’esercizio:
def game(s, engine=faster_game_engine):
    lst = list(map(int, s.split()))
    res = list(engine(lst))
    res.sort()
    res.sort(key=len)
    res = [' '.join(map(str, i)) for i in res]
    return res
La funzione game è il nostro entry-point per l’esercizio: accetta una stringa di numeri separati da spazi, la trasforma in una lista, chiama il “motore” del gioco vero e proprio, e poi ritrasforma l’output in una lista di stringhe. La lista è ordinata per lunghezza delle soluzioni e poi lessicograficamente, in modo da ottenere output più leggibili e soprattutto ripetibili.
Scriviamo infine alcuni test per essere sicuri che tutto funzioni davvero:
def test():
    tests = (
        ('', ['']),
        ('1', ['1']),
        ('3 2', ['3 2']),
        ('2 4', ['3']), 
        ('2 3 5', ['3']),
        ('2 4 6', ['2 5', '3 6']),
        ('2 5 5', ['2 5']),
        # l'esempio dell'esercizio:
        ('10 20 30 40 5 1', ['8', '14', '17', '15 20 1', '10 25 40 3']),
             )
    for test, res in tests:
        g1 = game(test, engine=game_engine)
        g2 = game(test, engine=faster_game_engine)
        assert g1 == g2 == res
Ecco fatto. Non troppo difficile, dopo tutto. Probabilmente con un po' di lavoro in più si può ottimizzare ulteriormente: per esempio ci può venire in mente che, una volta che abbiamo imparato a tener conto delle sotto-liste già scansionate, non corriamo più il rischio di ottenere doppioni delle soluzioni. Di conseguenza possiamo usare una semplice lista per raccoglierle, invece di un set. Se avete voglia di indagare ulteriormente, fatemi sapere che cosa ne pensate... e buono studio delle funzioni ricorsive!

Commenti

Post più popolari