<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Esistono molti modi diversi di approcciarsi alla risoluzione di un problema. In base alla propria astuzia, alle proprie conoscenze algoritmiche, matematiche, statistiche, al proprio buonsenso, è possibile elaborare strategie sempre più raffinate. 
Oggi invece siamo pigri. Supponiamo di essere in assoluto il più pigro studente che sia mai esistito. E supponiamo che il problema che dobbiamo risolvere sia imparare un frammento dell’Amleto di Shakespeare. Il frammento in questione è una semplice frase di Amleto
Step1:  E poi proporre la nostra frase all’insegnante il quale si limita a
Step2:  Ben presto ci accorgiamo di quanta pazienza devono avere le scimmie, dopo 100000 tentativi (saremo pur pigri ma anche molto tenaci) abbiamo azzeccato appena 8 lettere su 28
Step3:  Con questa semplice modifica siamo in grado di imparare la frase corretta in appena qualche migliaio di tentativi.
Circa tremila tentativi è decisamente un risultato molto migliore di prima! Certo che però provarle una alla volta è un po’ noioso, perché non proviamo invece a proporne di più allo stesso tempo? Proviamo a proporne 100 in un colpo solo
Step4:  Wow ora sono riuscito a scendere attorno al migliaio, ma ho davvero guadagnato qualcosa in termini di numero di tentativi necessari? Alla fine ora faccio 100 tentativi alla volta, perchè non ci metto 100 volte meno? In effetti è sleale contare il numero di volte che passo i miei tentativi all’insegnante, dovrei contare invece quante volte l’insegnante valuta i miei tentativi!
Vediamo un po’
Step5:  Diamine! Sì, è vero che ci metto circa un terzo delle iterazioni adesso ma quel poveretto del mio insegnante deve valutare uno sproposito di tentativi in più! circa 130000! Mentre prima quando gli proponevo una frase alla volta ne bastavano circa 3000. E dal momento che devo aspettare che lui abbia finito prima di  poter provare nuove frasi mi sto tirando la zappa sui piedi!
Inoltre cos’è questo macello nei miei tentativi inziali?
Come possono cambiare così tanto l’uno dall’altro? Io modifico solo una lettera per volta! Aspetta… ah già, dal momento che ho molte frasi contemporaneamente può essere che alcune di loro abbiano trovato alcune lettere corrette ma che siano state battute in velocità da altre alcune iterazioni dopo. Alla fine mi curo solo di chi è il miglior candidato, se per caso qualche suo rivale riesce a trovare anche solo una lettera in più il mio povero campione viene gettato nel dimenticatoio. Ma perchè sul finale le cose sembrano molto più “uniformi” come me le aspettavo?
Mmmm… potrebbe essere che all’inizio fosse facile migliorare il proprio risultato dato che la maggior parte delle lettere erano sbagliate. Sul finale invece solo una o due lettere sono sbagliate quindi è difficile progredire, bisogna sia avere la fortuna di azzeccare la posizione giusta che la lettera mancante!
Forse è meglio se do un occhio a cosa succede alle mie frasi oltre che al campione
Step6:  Proviamo a vedere cosa succede ai nostri candidati quando ne considero 10 alla volta
Step7:  Eh sì è come pensavo, quello che era il mio campione ha fallito a trovare un miglioramento e quindi un suo rivale è passato in vantaggio!
Ma perchè devono competere tra di loro! Io voglio solo trovare la frase che vuole l’insegnante, se collaborassero sarebbe molto più semplice...
Posso far si che condividano le parti corrette che ognuno di loro ha trovato? Diamine se solo sapessi quali sono! Maledetto insegnante che mi dici solo quante lettere azzecco.
Mmmm e se facessi mescolare tra di loro le varie frasi sperando che mettano insieme le parti corrette che hanno trovato? Potrei prendere due frasi a caso e costruirne una nuova prendendo lettere da una o l’altra. Sì, sembra una buona idea, alla fine se entrambe le frasi hanno trovato una lettera giusta non importa da chi pesco, la nuova frase avrà senz’altro quella lettera, almeno posso star tranquillo che non rovinerò le soluzioni che trovano!
Step8:  Ok, ma chi mescolo tra loro? Argh…
Uff,riflettiamo, senz’altro voglio la frase migliore, alla fine è quella con più lettere giuste, ma con chi potrei mescolarla? La seconda migliore? E se frasi meno “buone” avessero comunque trovato parti che alla migliore mancano? Facciamo così le scelgo a caso, ma do priorità a quelle con valori più alti. Si, mi sembra sensato, ma come faccio a farlo? T_T
Mmmm.... è come se volessi girare una roulette, dove chi ha un fitness più elevato ha più “spicchi” proviamo a fare uno schizzo
<ASSISTANT_TASK:>
Python Code:
import random
import string
def random_char():
    return random.choice(string.ascii_lowercase + ' ')
def genera_frase():
    return [random_char() for n in range(0,len(amleto))]
amleto = list('parmi somigli ad una donnola')
print("target= '"+''.join(amleto)+"'")
frase = genera_frase()
print(str(frase)+" = '"+''.join(frase)+"'")
Explanation: Esistono molti modi diversi di approcciarsi alla risoluzione di un problema. In base alla propria astuzia, alle proprie conoscenze algoritmiche, matematiche, statistiche, al proprio buonsenso, è possibile elaborare strategie sempre più raffinate. 
Oggi invece siamo pigri. Supponiamo di essere in assoluto il più pigro studente che sia mai esistito. E supponiamo che il problema che dobbiamo risolvere sia imparare un frammento dell’Amleto di Shakespeare. Il frammento in questione è una semplice frase di Amleto:
Parmi somigli ad una donnola
Dato che siamo mostruosamente pigri siamo stati affiancati ad un insegnante, profumatamente pagato per aiutarci a svolgere il nostro compito ma purtroppo altrettanto pigro.
Sforzarsi di imparare la frase che ci è stata assegnata è fuori questione. Perché non cominciare provando a buttare là frasi a caso e vedere come va? Alla fine se delle scimmie che premono tasti a caso su una macchina da scrivere possono riscrivere tutte le opere di Shakespeare perché non possiamo farcela noi con una sola frase?
Una normale persona probabilmente metterebbe insieme delle parole che l’autore potrebbe aver usato ma non vogliamo dare alle scimmie nostre rivali alcun handicap e quindi cominciamo a dire lettere a caso.
Nello specifico selezioniamo un numero di lettere casuali, pari alla lunghezza della frase che vogliamo imparare e lo proponiamo al nostro insegnante, il quale, pigro quanto noi, si limita a dirci quante lettere abbiamo azzeccato.
Quello che facciamo in pratica è:
End of explanation
def valuta( candidato ):
        azzeccate = 0
        for (lettera1, lettera2) in zip(candidato, amleto):
            if lettera1 == lettera2:
                azzeccate = azzeccate + 1
        return azzeccate
risposta = valuta(frase)
print(risposta)
Explanation: E poi proporre la nostra frase all’insegnante il quale si limita a:
End of explanation
def altera(vecchia_frase):
    posizione_da_cambiare = random.choice(range(0,len(vecchia_frase)))
    lettera_da_cambiare = vecchia_frase[posizione_da_cambiare]
    alternative = (string.ascii_lowercase + ' ').replace(lettera_da_cambiare,'')
    nuova_frase = list(vecchia_frase)
    nuova_frase[posizione_da_cambiare] = random.choice(alternative)
    return nuova_frase
i=0
miglior_frase = [random_char() for n in range(0,len(amleto))]
miglior_risultato = valuta(miglior_frase)
while(miglior_risultato < len(amleto)):
    frase = altera(miglior_frase)
    risposta = valuta(frase)
    i = i+1
    if risposta > miglior_risultato:
        miglior_risultato = risposta
        miglior_frase = frase
        print(str(i)+':\t"'+''.join(miglior_frase)+'"\t'+str(miglior_risultato))
Explanation: Ben presto ci accorgiamo di quanta pazienza devono avere le scimmie, dopo 100000 tentativi (saremo pur pigri ma anche molto tenaci) abbiamo azzeccato appena 8 lettere su 28:
“vfgoyflcmorpiisd untmsonqcji”
“parmi somigli ad una donnola”
Un risultato non proprio stellare.
Abbiamo 28 lettere da azzeccare, per ognuna abbiamo 27 scelte ('abcdefghijklmnopqrstuvwxyz '), il che vuol dire che la nostra probabilità di azzeccare tirando a caso è una su $27^{28}$ cioè circa:
0.00000000000000000000000000000000000000008<br>
Mentre proponiamo la 1000001-esima frase pensiamo tra noi che sarebbe bello non dover ricominciare da capo ogni volta, che magari ora che abbiamo una frase con 8 lettere corrette sarebbe bello poter migliorarla invece di buttarla via e ricominciare. Se solo il nostro insegnante fosse così gentile da dirci quali sono le lettere che abbiamo azzeccato oltre che quante, finiremmo in un attimo.
Vabbè, cerchiamo comunque di provarci, invece di buttare via la nostra frase ogni volta proviamo a tenerla e cambiare una lettera cercando di ottenere risultati sempre migliori:
End of explanation
def migliore(candidati):
    ordinati = sorted(candidati,key=lambda tup: tup[1], reverse=True)
    return ordinati[0]
def genera_candidati(num_candidati):
    candidati = []
    for i in range(0,num_candidati):
        tmp_frase = genera_frase()
        tmp_risposta = valuta(tmp_frase)
        candidati.append((tmp_frase,tmp_risposta))
    return candidati
candidati = genera_candidati(100)
i=0
miglior_frase, miglior_risultato = migliore(candidati)
while(miglior_risultato < len(amleto)):
    i = i+1
    for n in range(0,len(candidati)):
        frase,risposta = candidati[n]
        nuova_frase = altera(frase)
        nuova_risposta = valuta(nuova_frase)
        if nuova_risposta > risposta:
            candidati[n] = (nuova_frase,nuova_risposta)
        if nuova_risposta > miglior_risultato:
            miglior_risultato = nuova_risposta
            miglior_frase = nuova_frase
            print(str(i)+':\t"'+''.join(miglior_frase)+'"\t'+str(miglior_risultato))
Explanation: Con questa semplice modifica siamo in grado di imparare la frase corretta in appena qualche migliaio di tentativi.
Circa tremila tentativi è decisamente un risultato molto migliore di prima! Certo che però provarle una alla volta è un po’ noioso, perché non proviamo invece a proporne di più allo stesso tempo? Proviamo a proporne 100 in un colpo solo:
End of explanation
def valuta( candidato ):
        global valutazioni
        valutazioni = valutazioni + 1
        azzeccate = 0
        for (lettera1, lettera2) in zip(candidato, amleto):
            if lettera1 == lettera2:
                azzeccate = azzeccate + 1
        return azzeccate
def prova_piu_frasi_insieme(num_frasi):
    global valutazioni
    valutazioni = 0
    i=0
    candidati = genera_candidati(num_frasi)
    miglior_frase, miglior_risultato = migliore(candidati)
    while(miglior_risultato < len(amleto)):
        i = i+1
        for n in range(0,len(candidati)):
            frase,risposta = candidati[n]
            nuova_frase = altera(frase)
            nuova_risposta = valuta(nuova_frase)
            if nuova_risposta > risposta:
                candidati[n] = (nuova_frase,nuova_risposta)
            if nuova_risposta > miglior_risultato:
                miglior_risultato = nuova_risposta
                miglior_frase = nuova_frase
                print(str(i)+':\t"'+''.join(miglior_frase)+'"\t'+str(miglior_risultato))
    print('Valutazioni totali: '+str(valutazioni))
    
prova_piu_frasi_insieme(100)
Explanation: Wow ora sono riuscito a scendere attorno al migliaio, ma ho davvero guadagnato qualcosa in termini di numero di tentativi necessari? Alla fine ora faccio 100 tentativi alla volta, perchè non ci metto 100 volte meno? In effetti è sleale contare il numero di volte che passo i miei tentativi all’insegnante, dovrei contare invece quante volte l’insegnante valuta i miei tentativi!
Vediamo un po’:
End of explanation
import pprint
pp = pprint.PrettyPrinter()
def stampa_candidati(candidati):
    # candidati -> array di char, li trasformo in stringhe con ''.join(...)
    # [' ', 'x', 'p', 'l', 'f', … ,'d', 'z', 'h', 'f'] -> ' xplfrvvjjvnmzkovohltroudzhf'
    stringhe_e_valori = list(map(lambda x : (''.join(x[0]),x[1]), candidati))
    # per comodità ordino le stringhe in base al numero di lettere corrette, decrescente
    stringhe_ordinate = sorted(stringhe_e_valori,key=lambda tup: tup[1], reverse=True)
    pp.pprint(stringhe_ordinate)
stampa_candidati(genera_candidati(10))
Explanation: Diamine! Sì, è vero che ci metto circa un terzo delle iterazioni adesso ma quel poveretto del mio insegnante deve valutare uno sproposito di tentativi in più! circa 130000! Mentre prima quando gli proponevo una frase alla volta ne bastavano circa 3000. E dal momento che devo aspettare che lui abbia finito prima di  poter provare nuove frasi mi sto tirando la zappa sui piedi!
Inoltre cos’è questo macello nei miei tentativi inziali?
Come possono cambiare così tanto l’uno dall’altro? Io modifico solo una lettera per volta! Aspetta… ah già, dal momento che ho molte frasi contemporaneamente può essere che alcune di loro abbiano trovato alcune lettere corrette ma che siano state battute in velocità da altre alcune iterazioni dopo. Alla fine mi curo solo di chi è il miglior candidato, se per caso qualche suo rivale riesce a trovare anche solo una lettera in più il mio povero campione viene gettato nel dimenticatoio. Ma perchè sul finale le cose sembrano molto più “uniformi” come me le aspettavo?
Mmmm… potrebbe essere che all’inizio fosse facile migliorare il proprio risultato dato che la maggior parte delle lettere erano sbagliate. Sul finale invece solo una o due lettere sono sbagliate quindi è difficile progredire, bisogna sia avere la fortuna di azzeccare la posizione giusta che la lettera mancante!
Forse è meglio se do un occhio a cosa succede alle mie frasi oltre che al campione:
End of explanation
def prova_piu_frasi_insieme(num_frasi):
    global valutazioni
    valutazioni = 0
    i=0
    candidati = genera_candidati(num_frasi)
    miglior_frase, miglior_risultato = migliore(candidati)
    while(miglior_risultato < len(amleto)):
        i = i+1
        for n in range(0,len(candidati)):
            frase,risposta = candidati[n]
            nuova_frase = altera(frase)
            nuova_risposta = valuta(nuova_frase)
            if nuova_risposta > risposta:
                candidati[n] = (nuova_frase,nuova_risposta)
            if nuova_risposta > miglior_risultato:
                miglior_risultato = nuova_risposta
                miglior_frase = nuova_frase
                print(str(i)+':\t"'+''.join(miglior_frase)+'"\t'+str(miglior_risultato))
                stampa_candidati(candidati)
    print('Valutazioni totali: '+str(valutazioni))
    
prova_piu_frasi_insieme(10)
Explanation: Proviamo a vedere cosa succede ai nostri candidati quando ne considero 10 alla volta:
End of explanation
def mescola(frase1, frase2):
    nuova_frase = []
    for i in range(0,len(frase1[0])):
        if random.random() > 0.5:
            nuova_frase.append(frase1[0][i])
        else:
            nuova_frase.append(frase2[0][i])
    return (nuova_frase,valuta(nuova_frase))
test_frase1 , test_frase2 = genera_frase(), genera_frase()
print('frase1: "'+''.join(test_frase1)+'"')
print('frase2: "'+''.join(test_frase2)+'"')
print('mix:    "'+''.join(mescola((test_frase1,1),(test_frase2,1))[0])+'"')
Explanation: Eh sì è come pensavo, quello che era il mio campione ha fallito a trovare un miglioramento e quindi un suo rivale è passato in vantaggio!
Ma perchè devono competere tra di loro! Io voglio solo trovare la frase che vuole l’insegnante, se collaborassero sarebbe molto più semplice...
Posso far si che condividano le parti corrette che ognuno di loro ha trovato? Diamine se solo sapessi quali sono! Maledetto insegnante che mi dici solo quante lettere azzecco.
Mmmm e se facessi mescolare tra di loro le varie frasi sperando che mettano insieme le parti corrette che hanno trovato? Potrei prendere due frasi a caso e costruirne una nuova prendendo lettere da una o l’altra. Sì, sembra una buona idea, alla fine se entrambe le frasi hanno trovato una lettera giusta non importa da chi pesco, la nuova frase avrà senz’altro quella lettera, almeno posso star tranquillo che non rovinerò le soluzioni che trovano!
End of explanation
def genera_ruota(candidati):
    totale = 0
    ruota = []
    for frase,valore in candidati:
        totale = totale + valore
        ruota.append((totale,frase,valore))
    return ruota
def gira_ruota(wheel):
    totale = wheel[-1][0]
    pick = totale * random.random()
    for (parziale,candidato,valore) in wheel:
        if parziale >= pick:
            return (candidato,valore)
    return wheel[-1][1:]
candidati = genera_candidati(10)
wheel = genera_ruota(candidati)
pretty_wheel = list(map(lambda x:(x[0],''.join(x[1]),x[2]),wheel))
pp.pprint(pretty_wheel)
print("migliore='"+''.join(migliore(candidati)[0])+"'")
def prova_piu_frasi_e_mescola(num_frasi):
    global valutazioni
    valutazioni = 0
    i=0
    candidati = genera_candidati(num_frasi)
    miglior_frase, miglior_risultato = migliore(candidati)
    while(miglior_risultato < len(amleto)):
        i = i+1
        ruota = genera_ruota(candidati)
        nuovi_candidati = []
        for n in range(0,len(candidati)):
            minitorneo = [gira_ruota(ruota),gira_ruota(ruota)]
            nuova_frase = altera(mescola(minitorneo[0],minitorneo[1])[0])
            nuova_risposta = valuta(nuova_frase)
            minitorneo.append((nuova_frase,nuova_risposta))
            vincitore,valore_vincitore = migliore(minitorneo)
            nuovi_candidati.append((vincitore,valore_vincitore))
            if valore_vincitore > miglior_risultato:
                miglior_risultato = valore_vincitore
                miglior_frase = vincitore
                print(str(i)+':\t"'+''.join(miglior_frase)+'"\t'+str(miglior_risultato))
                stampa_candidati(candidati)
        candidati = nuovi_candidati
    print('valutazioni: '+str(valutazioni))
    
prova_piu_frasi_e_mescola(10)
Explanation: Ok, ma chi mescolo tra loro? Argh…
Uff,riflettiamo, senz’altro voglio la frase migliore, alla fine è quella con più lettere giuste, ma con chi potrei mescolarla? La seconda migliore? E se frasi meno “buone” avessero comunque trovato parti che alla migliore mancano? Facciamo così le scelgo a caso, ma do priorità a quelle con valori più alti. Si, mi sembra sensato, ma come faccio a farlo? T_T
Mmmm.... è come se volessi girare una roulette, dove chi ha un fitness più elevato ha più “spicchi” proviamo a fare uno schizzo:
<img src="roulette.png">
Mmm una frase che ha 24 di valore, merita 24 spicchi, mentre una che ha 20 ne riceverà solo 20, quindi il totale degli spicchi è la somma di tutti i valori.
End of explanation
<END_TASK>