Bé, quando non esiste altra strada, non conta molto il giudizio estetico. Ma se il programma è un bel programma, tanto meglio. E, in ogni caso, il programma è stato scritto da un umano, basta leggerlo e controllare che funzioni bene. Per dire: come faccio a fidarmi del fatto che l'ultimo teorema di Fermat è stato dimostrato? Quante persone al mondo sono in grado di leggere la dimostrazione e giudicarla? Perché non devo avere problemi su quella dimostrazione e devo farmene invece su un programma che potrei leggere, o scrivere, io stesso?
Il programma di BL è bellissimo, ma è scritto in perl, linguaggio che io non conosco. E allora come faccio a dire che è bellissimo?
Bé, si vede. Anche se non conosco i dettagli del linguaggio, comunque capisco il senso del programma. E vedo anche l'eleganza con cui è scritto. Lo lancio, e mi mostra la sequenza di 22 mosse (una sequenza di 22 mosse) che risolve il problema. E, per come mi è stato descritto il funzionamento, capisco anche che quello è il minimo. Ma voglio andare più a fondo, e decido di riscrivere il programma utilizzando un linguaggio che conosco un po' e che mi piace molto: python.
(Disclaimer: programmatori seri che state per leggere il seguito, abbiate pietà. Sono un autodidatta di questo linguaggio, non conosco tutte le sue potenzialità, sto sperimentando. Se avete suggerimenti per migliorarlo, e migliorare la mia comprensione, fateli pure)
Il programma ha una filosofia molto semplice: analizza l'albero di tutte le mosse fino a che non arriva alla soluzione. Quindi non ci si può sbagliare: la prima soluzione che salta fuori è quella che si ottiene con il numero minimo di mosse.
Entrando più nel dettaglio, il programma parte dalla posizione iniziale e genera tutte le possibili mosse ottenibili facendo un movimento. Queste vengono memorizzate assieme al numero di mosse necessarie per arrivare in quella posizione, e (qui sta il bello) assieme anche alla posizione da cui provengono, per poi recuperare il percorso una volta giunti alla fine. Poi ricomincia, partendo dalle nuove posizioni ottenute e generando tutte le nuove possibili mosse, e così via.
Arrivati alla soluzione, basta percorrere il cammino all'indietro per ottenere l'elenco di tutti i passaggi.
La griglia delle varie posizioni viene numerata in questo modo
___ ___
| | | |
| 2 | | 6 |
___ ___|___|___|___|___
| | | | | | |
| 0 | 1 | 3 | 5 | 7 | 9 |
|___|_ _|___|___|___|___|
| | | |
| 4 | | 8 |
|___| |___|
e memorizzata in una lista (all'inizio una stringa, in realtà, poi trasformata in una lista per lavorarci sopra). Dunque la posizione iniziale sarà memorizzata così: "AI.L.A.T.I". In realtà nel programma al posto dei puntini ci metto degli zeri, per poter fare dei controlli più comodamente, ma non ha importanza.
Ecco la parte di programma che si occupa di definire la griglia: nella lista c è contenuto, per ogni casella, l'elenco delle caselle confinanti.
La variabile w contiene la posizione iniziale, finale naturalmente contiene quella finale, Nmax contiene il livello massimo al quale il programma arriverà: se non è stata trovata una soluzione fino a quel momento, si ferma.
mosse è un dizionario: è la struttura che associa, ad ogni posizione, il livello al quale la posizione è stata incontrata la prima volta, assieme alla posizione precedente, dalla quale questa proviene. All'inizio contiene solo la posizione di partenza w, che si trova a livello 0 e non proviene da nessun'altra posizione (in realtà qui la definiamo come proveniente da sé stessa).
Proseguiamo. Questa è la funzione che si occupa di calcolare la lista di tutte le possibili posizioni ottenibili con una mossa, a partire da una posizione m data.
Contiene un ciclo che esplora ogni casella, e se ne trova una vuota (cioè contenente 0) per ogni casella confinante fa uno scambio: la lettera che si trova nella casella confinante va in quella vuota. Tutte le nuove posizioni vengono inserite nella lista ris, inizialmente vuota, che alla fine viene restituita al programma chiamante.
Ora il programma principale:
È un ciclo che ripete sempre la stessa procedura, fino a che non arriva a trovare una soluzione (o non arriviamo al livello Nmax). Dal dizionario di tutte le mosse estrae quelle del livello precedente; per ogni mossa crea la lista delle mosse successive; se queste sono nuove (cioè non stanno già nel dizionario), allora vengono inserite, assieme al loro livello e alla mossa precedente. Se trova la posizione finale, ferma tutta la baracca.
Ora si tratta di stampare per bene il risultato. La funzione bellastampa()
stampa in maniera comprensibile le varie posizioni. Non c'è molto da dire, se non che ho provato a utilizzare un sistema per contare il numero di mosse utilizzando una variabile statica locale (invece di una variabile globale). Probabilmente non è il modo migliore, ma tant'è.
E ora la parte finale:
la funzione scrivisoluzione() è ricorsiva, e permette di scrivere l'elenco delle mosse dalla prima all'ultima (e non dall'ultima alla prima). Noi la chiamiamo passandole, come parametro, l'ultima posizione trovata (quella finale, insomma), e lei ripercorre l'albero delle mosse all'indietro, fino a tornare al livello zero. Da lì comincia a stampare, in discesa, tutte le mosse.
Ed ecco il risultato:
. .
0: AILATI
. .
. T
1: AILA.I
. .
. T
2: AILAI.
. .
L T
3: AI.AI.
. .
L T
4: AI.A..
. I
L T
5: AI..A.
. I
L T
6: A.I.A.
. I
L T
7: A..IA.
. I
L T
8: A..I.A
. I
L T
9: .A.I.A
. I
L .
10: .A.ITA
. I
L .
11: ..AITA
. I
L .
12: ...ITA
A I
L .
13: ..I.TA
A I
L .
14: ..IT.A
A I
L .
15: .I.T.A
A I
L .
16: .IT..A
A I
L .
17: I.T..A
A I
L .
18: IT...A
A I
. .
19: ITL..A
A I
. .
20: IT.L.A
A I
. .
21: ITAL.A
. I
. .
22: ITALIA
. .
Appendice: ho scritto questo post prima di pubblicare il precedente, nei cui commenti si discute sulla validità di una dimostrazione fatta col computer. In questo caso credo che sia abbastanza semplice da poter essere considerata valida anche dai puristi. Comunque sia, il programma, prima di terminare, ha analizzato e memorizzato 24824 posizioni diverse. Per la precisione:
Posizioni di livello 0 = 1 Posizioni di livello 1 = 4 Posizioni di livello 2 = 12 Posizioni di livello 3 = 30 Posizioni di livello 4 = 58 Posizioni di livello 5 = 130 Posizioni di livello 6 = 200 Posizioni di livello 7 = 358 Posizioni di livello 8 = 442 Posizioni di livello 9 = 660 Posizioni di livello 10 = 766 Posizioni di livello 11 = 1106 Posizioni di livello 12 = 1243 Posizioni di livello 13 = 1642 Posizioni di livello 14 = 1692 Posizioni di livello 15 = 2188 Posizioni di livello 16 = 2119 Posizioni di livello 17 = 2427 Posizioni di livello 18 = 2029 Posizioni di livello 19 = 2289 Posizioni di livello 20 = 2046 Posizioni di livello 21 = 2461 Posizioni di livello 22 = 921
13 commenti:
detto papale papale: un programma che fa una ricerca esaustiva è una schifezza (dal punto di vista matematico, non informatico) ma la soluzione che trova è una soluzione corretta.
E a quelli che dicono che il programma può essere errato, rispondo che anche le dimostrazioni "umane" possono essere errate. Chiedere al signor Kempe quando nel 1879 "dimostrò" il teorema dei quattro colori.
Sì, non è gran matematica, ma temo che ci si possa fare poco con questo quesito.
Come spesso mi accade, tendo ad "allargarmi" e nel precedente post ho voluto credere che si volesse parlare in generale della possibilità di accettare o meno dimostrazioni al computer. Questo tuo nuovo articolo invece conferma (perché l'avevi già dichiarato nel precedente e probabilmente io sono stato poco attento) la tua intenzione di dimostrare che per casi specifici come l'esempio proposto fosse possibile e giusto accettare dimostrazioni derivanti da algoritmi costruiti in modo mirato. Se questa era la tua intenzione, ci sei perfettamente riuscito. Quindi alla domanda precisa: "si può accettare una dimostrazione al computer per casi specifici che non hanno bisogno di essere generalizzati e/o astratti?" rispondo assolutamente SI.
Altra cosa è invece affrontare un discorso più generale sulle dimostrazioni "umane" (come le chiama .mau) e quelle digitali (che poi alla fine sono sempre e comunque "umane" con l'aggiunta della velocità di calcolo e lo spazio di archiviazione). Ma probabilmente non è questa la sede adatta e ancor meno sono adatto io per una discussione che potrebbe presentare non pochi spigoli su cui farsi male (io sicuramente).
Un saluto
Marco
Sì, sì, parlavo di questo particolare problema. Qui direi che la soluzione sia accettabile senza problemi.
Tra l'altro, 22 è il numero minimo nel caso della specifica sequenza di lettere "AILATI". Se invece avessimo scelto, ad esempio, ABCDEF, dopo i 22 passi qui riportati ci ritroveremmo con la sequenza BEACFD.
Già. Pensa che se si facesse lo stesso giochino ai cugini francesi (i giochi Bocconi sono fatti assieme a loro), con ECNARF-FRANCE, ci vorrebbero 38 mosse, e il programma dovrebbe analizzare 150337 possibili posizioni.
Quindi è 38 il numero minimo di mosse nel caso in cui le 6 lettere sono tutte diverse tra loro, oppure se nel caso di lettere uguali si tiene conto anche della loro posizione relativa.
Curiosità, se hai voglia di controllare, quante sarebbero le mosse minime nel caso di AÑAPSE-ESPAÑA, tanto per rimanere in tema di Paesi europei? ;-)
Dice 32 mosse...
è ovvio anche a una profana come me che dipende dal fatto che ci siano delle lettere che si ripetono,e quindi lo stesso carattere può essere usato con due valenze.
In Italia ci sono due coppie di lettere uguali, in Espana una sola, in France, nessuna.
Se questo è vero, Latvia e Hellas dovrebbero dare 32 come Espana, Polska 38 come France.
Mi incuriosisce Suisse (3 lettere ambivalenti), potrebbe essere una via di mezzo tra 32 e 22 (28?).
Suisse: 30
Hellas: 34 (dipende anche da dove si trovano le lettere uguali, a questo punto)
Latvia: 30
Espana: 32
Polska: 38
vedi quante cose si scoprono?
A proposito, come sono tristi i matematici, vedono solo quello che hanno davanti al naso (vedi pecora nera).
Personalmente preferisco l'ingegnere, sarebbe l'unico a potermi mai dire ti amerò per sempre
mi sento chiamato in causa quasi unicamente sull'amore, nonostante sia a tutti gli effetti un matematico.
se proprio vogliamo seguire la barzelletta, se un ingegnere ti dice "ti amerò per sempre" probabilmente sta mentendo. se te lo dice un matematico puoi essere assolutamente certa che sia vero :)
comunque zar sei meraviglioso
Posta un commento