Buy this book at Amazon.com

Chapter 9  Esercitazione: Giochi con le parole

Questo capitolo contiene la seconda esercitazione, in cui dovrete risolvere dei quesiti che consistono nel ricercare parole che hanno delle particolari proprietà. Ad esempio, cercherete i più lunghi palindromi della lingua inglese e le parole le cui lettere sono disposte in ordine alfabetico. Illustrerò anche un’altra tecnica di sviluppo: la riduzione ad un problema già risolto.

9.1  Leggere elenchi di parole

Per gli esercizi di questo capitolo ci serve un elenco di parole in inglese. Ci sono parecchi elenchi di parole disponibili sul Web, ma uno dei più adatti ai nostri scopi è quello raccolto da Grady Ward, di pubblico dominio, parte del progetto lessicale Moby (vedere http://wikipedia.org/wiki/Moby_Project). È un elenco di 113.809 parole ufficiali per cruciverba, cioè parole che sono considerate valide in un gioco di parole crociate o altri giochi con le parole. Nella raccolta Moby il nome del file è 113809of.fic; potete anche scaricare una copia chiamata più semplicemente words.txt, dal sito http://thinkpython2.com/code/words.txt.

Il file è in testo semplice, e potete aprirlo con qualsiasi editor di testo, ma anche leggerlo con Python: la funzione predefinita open richiede come parametro il nome di un file e restituisce un oggetto file che potete utilizzare per questo scopo.

>>> fin = open('words.txt')

fin è un nome comunemente usato per un oggetto file usato per operazioni di input.

L’oggetto file comprende alcuni metodi di lettura, come readline, che legge i caratteri da un file finché non giunge ad un ritorno a capo, e restituisce il risultato sotto forma di stringa:

>>> fin.readline()
'aa\r\n'

La prima parola di questa speciale lista è “aa”, che è un tipo di lava vulcanica. La sequenza \r\n rappresenta due caratteri spaziatori, un ritorno di carrello e un a capo, che separano questa parola dalla successiva.

L’oggetto file tiene traccia del punto in cui si trova all’interno del file, così quando chiamate nuovamente readline, ottenete la parola successiva:

>>> fin.readline()
'aah\r\n'

La parola successiva è “aah”, che è perfettamente valida per cui non fate quella faccia! Oppure, se gli spaziatori vi danno fastidio, potete sbarazzarvene con il metodo delle stringhe strip:

>>> riga = fin.readline()
>>> parola = riga.strip()
>>> parola
'aahed'

Potete anche usare un oggetto file all’interno di un ciclo for. Questo programma legge words.txt e stampa ogni parola, una per riga:

fin = open('words.txt')
for riga in fin:
    parola = riga.strip()
    print(parola)

9.2  Esercizi

Le soluzioni a questi esercizi sono discusse nel prossimo paragrafo. Tentate almeno di risolverli prima di continuare la lettura.

9.3  Ricerca

Tutti gli esercizi del paragrafo precedente hanno qualcosa in comune: possono essere risolti con lo schema di ricerca che abbiamo visto nel Paragrafo 8.6. L’esempio più semplice è:

def niente_e(parola):
    for lettera in parola:
        if lettera == 'e':
            return False
    return True

Il ciclo for attraversa i caratteri in parola. Se trova la lettera “e”, può immediatamente restituire False; altrimenti deve esaminare la lettera seguente. Se il ciclo termina normalmente, vuol dire che non è stata trovata alcuna “e”, per cui il risultato è True.

Si potrebbe scrivere questa funzione in modo più conciso usando l’operatore in, ma ho preferito iniziare con questa versione perché dimostra la logica dello schema di ricerca.

evita è una versione più generale di niente_e, ma la struttura è la stessa:

def evita(parola, vietate):
    for lettera in parola:
        if lettera in vietate:
            return False
    return True

Possiamo restituire False appena troviamo una delle lettere vietate; se arriviamo alla fine del ciclo, viene restituito True.

usa_solo è simile, solo che il senso della condizione è invertito:

def usa_solo(parola, valide):
    for lettera in parola: 
        if lettera not in valide:
            return False
    return True

Invece di un elenco di lettere vietate, ne abbiamo uno di lettere disponibili. Se in parola troviamo una lettera che non è una di quelle valide, possiamo restituire False.

usa_tutte è ancora simile, solo che rovesciamo il ruolo della parola e della stringa di lettere:

def usa_tutte(parola, richieste):
    for lettera in richieste: 
        if lettera not in parola:
            return False
    return True

Invece di attraversare le lettere in parola, il ciclo attraversa le lettere richieste. Se una qualsiasi delle lettere richieste non compare nella parola, restituiamo False.

Ma se avete pensato davvero da informatici, avrete riconosciuto che usa_tutte era un’istanza di un problema già risolto in precedenza, e avrete scritto:

def usa_tutte(parola, richieste):
    return usa_solo(richieste, parola)

Ecco un esempio di metodo di sviluppo di un programma chiamato riduzione ad un problema già risolto, che significa che avete riconosciuto che il problema su cui state lavorando è un’istanza di un problema già risolto in precedenza, al quale potete applicare una soluzione che avevate già sviluppato.

9.4  Cicli con gli indici

Ho scritto le funzioni del paragrafo precedente utilizzando dei cicli for perché avevo bisogno solo dei caratteri nelle stringhe e non dovevo fare nulla con gli indici.

Per alfabetica dobbiamo comparare delle lettere adiacenti, che è un po’ laborioso con un ciclo for:

def alfabetica(parola):
    precedente = parola[0]
    for c in parola:
        if c < precedente:
            return False
        precedente = c
    return True

Un’alternativa è usare la ricorsione:

def alfabetica(parola):
    if len(parola) <= 1:
        return True
    if parola[0] > parola[1]:
        return False
    return alfabetica(parola[1:])

E un’altra opzione è usare un ciclo while:

def alfabetica(parola):
    i = 0
    while i < len(parola)-1:
        if parola[i+1] < parola[i]:
            return False
        i = i+1
    return True

Il ciclo comincia da i=0 e finisce a i=len(parola)-1. Ogni volta che viene eseguito, il ciclo confronta l’ i-esimo carattere (consideratelo come il carattere attuale) con l’ i+1-esimo carattere (consideratelo come quello successivo).

Se il carattere successivo è minore di quello attuale (cioè viene alfabeticamente prima), allora abbiamo scoperto un’interruzione nella serie alfabetica e la funzione restituisce False.

Se arriviamo a fine ciclo senza trovare difetti, la parola ha superato il test. Per convincervi che il ciclo è terminato correttamente, prendete un esempio come 'flossy'. La lunghezza della parola è 6, quindi l’ultima ripetizione del ciclo si ha quando i è 4, che è l’indice del penultimo carattere. Nell’ultima iterazione, il penultimo carattere è comparato all’ultimo, che è quello che vogliamo.

Ecco una variante di palindromo (vedere l’Esercizio 3) che usa due indici; uno parte dall’inizio e aumenta, uno parte dalla fine e diminuisce.

def palindromo(parola):
    i = 0
    j = len(parola)-1

    while i<j:
        if parola[i] != parola[j]:
            return False
        i = i+1
        j = j-1

    return True

Oppure, possiamo ridurre ad un problema già risolto e scrivere:

def palindromo(parola):
    return al_contrario(parola, parola)

Usando al_contrario del Paragrafo 8.11.

9.5  Debug

Collaudare i programmi non è facile. Le funzioni di questo capitolo sono relativamente agevoli da provare, perché potete facilmente controllare il risultato da voi. Nonostante ciò, scegliere un insieme di parole che riescano a escludere ogni possibile errore è un qualcosa tra il difficile e l’impossibile.

Prendiamo ad esempio niente_e. Ci sono due evidenti casi da controllare: le parole che hanno una o più ’e’ devono dare come risultato False; quelle che invece non hanno ‘e’, True. E fin qui, in un caso o nell’altro, non c’è niente di particolarmente difficile.

Per ciascun caso ci sono alcuni sottocasi meno ovvi. Tra le parole che contengono “e”, dovreste provare parole che iniziano con “e”, finiscono con “e”, hanno “e” da qualche parte nel mezzo della parola. Dovreste poi provare parole lunghe, parole corte e parole cortissime. Nello specifico, la stringa vuota è un esempio di caso particolare, che è uno dei casi meno ovvi dove si nascondono spesso gli errori.

Oltre che con i casi da voi ideati, sarebbe anche bene fare un test del vostro programma con un elenco di parole come words.txt. Scansionando l’output potreste intercettare qualche errore, ma attenzione: può trattarsi di un certo tipo di errore (parole che non dovrebbero essere incluse ma invece ci sono) e non di un altro (parole che dovrebbero essere incluse ma non ci sono).

In linea generale, fare dei test può aiutarvi a trovare i bug, ma non è facile generare un buon insieme di casi di prova, e anche se ci riuscite non potete essere certi che il vostro programma sia corretto al 100 per cento.

Secondo un leggendario informatico:

Il test di un programma può essere usato per dimostrare la presenza di bug, ma mai per dimostrarne l’assenza!

— Edsger W. Dijkstra

9.6  Glossario

oggetto file:

Un valore che rappresenta un file aperto.

riduzione ad un problema già risolto:

Modo di risolvere un problema esprimendolo come un’istanza di un problema precedentemente risolto.

caso particolare:

un caso atipico o non ovvio (e con meno probabilità di essere gestito correttamente) che viene testato.

9.7  Esercizi

Buy this book at Amazon.com

Contribute

Pay what you want:

Small $1.00 USD Medium $5.00 USD Large $10.00 USD X-Large $20.00 USD XX-Large $50.00 USD

Are you using one of our books in a class?