Precedente :: Successivo |
Autore |
Messaggio |
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 09 Gen 2007 23:52 Oggetto: |
|
|
Se vi puo` essere di aiuto questi sono i numeri minimi di mosse con cui si possono raggiungere le configurazioni possibili:
Codice: |
0
5 6
4 . 3
1 . . 2
7 . . 7
2 . . 1
3 . 4
6 5
2
|
|
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 17 Gen 2007 17:03 Oggetto: |
|
|
Avevo lasciato una domanda in sospeso:
Ulisse ha scritto: | E' tutto qui e le sequenze di mosse vanno costruite per tentativi o ci sono ulteriori regole che ci garantiscono di determinare con certezza se il problema ammette o no soluzione e, nel caso esista, di costruirla? |
Quindi rispondo prima di passare alla fase successiva.
Non pensavate mica di cavarvela col semplice problema delle 3 taniche, vero? In fondo al post trovate il nuovo problema!
Ci sono ulteriori regole che garantiscono di determinare se il problema ammetta o meno soluzione.
Il metodo è costruttivo quindi, oltre a garantire l'esistenza, consente anche di individuare la soluzione.
Innanzi tutto avevo trascurato di specificare che i possibili cammini devono essere reversibili.
I vincoli dichiarati nel problema si traducono pari pari nella richiesta di reversibilità delle mosse.
Si parte da una configurazione "terminale" ovvero in cui ogni tanica è o completamente piena o completamente vuota e si arriva ad un'altra configurazione terminale.
Ciò definisce completamente una mossa reversibile.
A che serve specificare la reversibilità delle mosse?
Serve perché uno dei metodi per individuare le soluzioni richiede di procedere a ritroso dalla configurazione finale, fino a raggiungere quella iniziale.
Ciò è possibile solo in presenza di mosse reversibili.
Come si sceglie la nuova mossa dopo averne effettuata una?
Basta osservare che nel movimento sul reticolo vale la "regola del rimbalzo" nota ai giocatori di biliardo: quando arriviamo ad un punto sul perimetro, la nuova mossa è quella che fa procedere in direzione simmetrica rispetto all'asse della "sponda".
Muoversi in direzioni diverse è vietato dalla regola di reversibilità.
Se anche tale regola non sussistesse (formalmente nessuno vieta di spostarsi da un punto interno ad un lato ad un suo vertice) otterremmo solo una inutile perdita di mosse.
Fanno eccezione i vertici dai quali si può uscire seguendo la regola del rimbalzo oppure costeggiando il perimetro.
Nel problema in esame (3 taniche da 3, 5 e 8 galloni) l'unica ragione per non seguire la regola del rimbalzo è per raggiungere in due sole mosse il vertice 350.
Detto questo, rimangono solo due possibili cammini risolutivi:
Quello in blu rappresenta la soluzione in 8 mosse fornita da MK66.
Quella in giallo rappresenta la soluzione in 7 mosse fornita da _L_
Un altro modo di procedere consiste nel partire dalla configurazione iniziale ed etichettare con un 1 tutti i punti raggiungibili da 008 in una sola mossa e poi procedere etichettando con 2 tutti i punti raggiungibili con una sola mossa a partire da tutti i punti etichettati 1 e così via sino a esaurimento delle mosse possibili. Se con una mossa raggiungiamo un punto già etichettato con un numero più basso, abbandoniamo il cammino e ci concentriamo sui rimanenti.
Con questo metodo otteniamo, nel nostro problema, il seguente grafico che è pari pari il grafico formato testo postato da Taifu:
Oltre ad individuare tutti i punti raggiungibili a partire dalla configurazione iniziale (e quindi a determinare l'esistenza o meno di una soluzione) possiamo in questo modo individuare il percorso più breve (se esistente) che conduce alla soluzione e quantificare il numero di mosse necessarie.
Per concludere c'è ancora una cosa da dire: il problema delle tre taniche è stato proposto per la prima volta da Tartaglia nel XVI secolo.
Ricordo che quanto ho scritto è tratto (traducendolo con un bagno di sudore da un inglese probabilmente ineccepibile ma decisamente contorto e arzigogolato) dal testo citato nel post di apertura.
Unico contributo personale è la parte iniziale per spiegare da dove piova il triangolo che nel testo, come al solito, viene presentato direttamente senza spiegare se l'idea sia grazia dello spirito santo o chissà che.
Chi volesse divertirsi può cimentarsi ancora con tre taniche, questa volta da 5, 7 e 9 galloni tentando di suddividere 9 galloni in due parti da 3 e 6 galloni ognuna.
Ora che la trattazione del problema delle tre taniche è completata, passiamo a qualcosa di più impegnativo cioè al problema delle quattro taniche ecco il problema che l'autore immerge in un contesto di spionaggio:
In un centro militare di ricerche hanno sviluppato la formula per un nuovo propellente. Ne hanno anche prodotto una piccola quantità (26 galloni) che custodiscono in tre taniche da 5, 8 e 13 galloni.
Tre agenti segreti di una potenza nemica rubano le taniche prendendone ognuno una.
Quando, ancora in territorio nemico, si radunano si accorgono che la tanica più piccola ha perso il tappo e, durante il trasporto, si è svuotata.
Essi hanno a disposizione una quarta tanica da 26 galloni in grado, quindi, di contenere tutto il propellente residuo.
Per non rischiare il danno totale durante il rientro in patria (ovvero di perdere in un botto tutto il propellente rimasto) decidono, però, di dividere i 21 galloni residui in tre parti uguali.
Siete in grado di individuare una soluzione ottimale?
Uscendo dalla metafora il problema è: date quattro taniche da 5, 8, 13 e 26 galloni, vuote quelle da 5 e da 26 galloni e piene le altre due, suddividere 21 galloni in tre parti uguali.
Chi arrivasse ad una soluzione tramite forza bruta (uno a caso) può farlo ma dovrà fornirmi una copia del codice (in Pythoon per caso?) che sono curioso di vedere come avete impostato la risoluzione. |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 17 Gen 2007 21:48 Oggetto: |
|
|
ulisse ha scritto: | Uscendo dalla metafora il problema è: date quattro taniche da 5, 8, 13 e 26 galloni, vuote quelle da 5 e da 26 galloni e piene le altre due, suddividere 21 galloni in tre parti uguali.
Chi arrivasse ad una soluzione tramite forza bruta (uno a caso) può farlo ma dovrà fornirmi una copia del codice (in Pythoon per caso?) che sono curioso di vedere come avete impostato la risoluzione. |
Ulisse,
una domanda: va bene solo la configurazione 0/7/7/7 oppure basta anche una in cui uno dei 7 e` diviso in due taniche? Per esempio 1/7/7/6 ?
Te lo chiedo perche` posso gia` affermare che non esistono soluzioni con 7 o meno mosse anche nell'ipotesi in cui un 7 e` diviso tra due taniche. Aumentare a 8 o piu` mosse vuol dire allungare di parecchio i tempi di esecuzione per cui vorrei capire se posso tagliare qualche ramo.
Con 5 mosse siamo a 15 secondi di esecuzione.
Con 6 mosse siamo a 1 minuto e 8 secondi di esecuzione.
Con 7 mosse siamo a 5 minuti e 8 secondi di esecuzione.
E cosi` via...
Ah, dimenticavo: si chiama Python. Ancora non lo sapete, ma in futuro chiamarlo Pythoon sara` come aver accennato al teorema di Piiitagora...
Ciao.
Marco. |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 18 Gen 2007 09:13 Oggetto: |
|
|
Taifu ha scritto: | Ah, dimenticavo: si chiama Python. Ancora non lo sapete, ma in futuro chiamarlo Pythoon sara` come aver accennato al teorema di Piiitagora... |
Ehm, ehm...
E' che io conosco a malapena il Baasic...
La configurazione 1/7/7/6 non può essere considerata finale (ad esempio perché le tre spie, per potersene andare ognuno con una tanica, devono fare ancora una mossa e concludere con 0/7/7/7).
Tempi macchina che si allungano?
Prova a sottoporre al tuo programma il secondo problema con tre taniche e dimmi che succede... |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 18 Gen 2007 10:34 Oggetto: |
|
|
ulisse ha scritto: |
Tempi macchina che si allungano?
Prova a sottoporre al tuo programma il secondo problema con tre taniche e dimmi che succede... |
Il secondo problema con tre taniche non ha soluzione (do per scontato che una soluzione abbia meno di 99 mosse).
E il tuo sorrisino beffardo riguardo ai tempi macchina mi pensare che anche la versione a quattro taniche non ce l'abbia.
Mi toccherà leggere a fondo la tua spiegazione per dimostrare che non c'è soluzione...
Ma il tempo latita!
Ciao.
Marco. |
|
Top |
|
|
Salmastro Dio minore
Registrato: 13/12/06 19:36 Messaggi: 883 Residenza: Casalmico
|
Inviato: 18 Gen 2007 10:54 Oggetto: mi fido di taifu |
|
|
...per cui abbandono i rimbalzi nel "trapezio" (?) legato alle configurazioni delle tre taniche, anche se a prima vista il fatto che i punti di arrivo siano ben 4 (036, 063, 306, 360) e siano tutti sul perimetro dovrebbe invitarmi a perseverare.
Per le 4 taniche sono curioso di vedere come si gioca a biliardo all'interno di una piramide tronca.
Salmastro |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 18 Gen 2007 15:52 Oggetto: |
|
|
Dunque, dunque, limitandoci alla soluzione con 7/7/7 il programmino è molto più spedito.
La soluzione più breve trovata sinora è in 45 mosse (in circa 5 secondi di tempo macchina).
Sta ancora girando, vediamo.
Ciao.
Marco.
P.S. Il tempo di scrivere questo messaggio e ne ha trovata una da 44 mosse.
Citazione: |
In 44 mosse
['<Tanica da 5 con 5>', '<Tanica da 8 con 3>', '<Tanica da 13 con 13>', '<Tanica da 26 con 0>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 8>', '<Tanica da 13 con 13>', '<Tanica da 26 con 0>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 13>', '<Tanica da 26 con 8>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 0>', '<Tanica da 13 con 8>', '<Tanica da 26 con 8>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 5>', '<Tanica da 13 con 8>', '<Tanica da 26 con 8>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 8>', '<Tanica da 26 con 13>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 0>', '<Tanica da 13 con 3>', '<Tanica da 26 con 13>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 5>', '<Tanica da 13 con 3>', '<Tanica da 26 con 13>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 3>', '<Tanica da 26 con 18>']
['<Tanica da 5 con 3>', '<Tanica da 8 con 0>', '<Tanica da 13 con 0>', '<Tanica da 26 con 18>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 3>', '<Tanica da 13 con 0>', '<Tanica da 26 con 18>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 0>', '<Tanica da 26 con 21>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 0>', '<Tanica da 13 con 0>', '<Tanica da 26 con 16>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 5>', '<Tanica da 13 con 0>', '<Tanica da 26 con 16>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 5>', '<Tanica da 26 con 16>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 0>', '<Tanica da 13 con 5>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 5>', '<Tanica da 13 con 5>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 10>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 8>', '<Tanica da 13 con 2>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 3>', '<Tanica da 13 con 2>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 3>', '<Tanica da 13 con 7>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 3>', '<Tanica da 8 con 0>', '<Tanica da 13 con 7>', '<Tanica da 26 con 11>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 7>', '<Tanica da 26 con 14>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 0>', '<Tanica da 13 con 2>', '<Tanica da 26 con 14>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 5>', '<Tanica da 13 con 2>', '<Tanica da 26 con 14>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 0>', '<Tanica da 13 con 2>', '<Tanica da 26 con 19>']
['<Tanica da 5 con 2>', '<Tanica da 8 con 0>', '<Tanica da 13 con 0>', '<Tanica da 26 con 19>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 2>', '<Tanica da 13 con 0>', '<Tanica da 26 con 19>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 2>', '<Tanica da 13 con 0>', '<Tanica da 26 con 14>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 7>', '<Tanica da 13 con 0>', '<Tanica da 26 con 14>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 7>', '<Tanica da 13 con 0>', '<Tanica da 26 con 9>']
['<Tanica da 5 con 4>', '<Tanica da 8 con 8>', '<Tanica da 13 con 0>', '<Tanica da 26 con 9>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 8>', '<Tanica da 13 con 4>', '<Tanica da 26 con 9>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 3>', '<Tanica da 13 con 4>', '<Tanica da 26 con 9>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 3>', '<Tanica da 13 con 9>', '<Tanica da 26 con 9>']
['<Tanica da 5 con 3>', '<Tanica da 8 con 0>', '<Tanica da 13 con 9>', '<Tanica da 26 con 9>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 0>', '<Tanica da 13 con 9>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 5>', '<Tanica da 13 con 9>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 5>', '<Tanica da 13 con 4>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 2>', '<Tanica da 8 con 8>', '<Tanica da 13 con 4>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 2>', '<Tanica da 8 con 0>', '<Tanica da 13 con 12>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 2>', '<Tanica da 13 con 12>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 5>', '<Tanica da 8 con 2>', '<Tanica da 13 con 7>', '<Tanica da 26 con 7>']
['<Tanica da 5 con 0>', '<Tanica da 8 con 7>', '<Tanica da 13 con 7>', '<Tanica da 26 con 7>']
|
Il codice del programma Python è questo:
Codice: |
class Tanica(object):
def __init__(self, capacita, litri=0):
self.capacita = capacita
self.litri = litri
def capacita_residua(self):
return self.capacita - self.litri
def __eq__(self, tanica):
return self.capacita == tanica.capacita and self.litri == tanica.litri
def versa_in(self, tanica, litri=None):
if litri == None:
litri = min(tanica.capacita_residua(), self.litri)
self.litri -= litri
tanica.litri += litri
return litri
def __repr__(self):
return "<Tanica da %d con %d>" % (self.capacita, self.litri)
def esplora(situazione, risultato, massimo, mosse = []):
if len(mosse) > massimo:
return massimo
if situazione == risultato:
print "*" * 40
print "In %d mosse" % len(mosse)
for mossa in mosse:
print mossa
return len(mosse)
else:
for prima in range(len(situazione)):
for seconda in range(len(situazione)):
if prima != seconda and situazione[prima].litri > 0 and situazione[seconda].capacita_residua > 0:
litri = situazione[prima].versa_in(situazione[seconda])
mossa = str([str(tanica) for tanica in situazione])
if not mossa in mosse:
mosse.append(str([str(tanica) for tanica in situazione]))
massimo = esplora(situazione, risultato, massimo, mosse)
mosse.pop()
litri = situazione[seconda].versa_in(situazione[prima], litri)
return massimo
max_mosse = 50
taniche = [Tanica(5), Tanica(8, 8), Tanica(13, 13), Tanica(26)]
risultato = [Tanica(5, 0), Tanica(8, 7), Tanica(13, 7), Tanica(26, 7)]
print "=" * 20
print "Da\t%s\nA\t%s" % (taniche, risultato)
print "In massimo %d mosse" % max_mosse
esplora (taniche, risultato, max_mosse)
|
|
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 18 Gen 2007 15:58 Oggetto: |
|
|
Siamo a 42 mosse.
Sono curioso di vedere fino a dove scende... |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 18 Gen 2007 16:20 Oggetto: |
|
|
41...
E mi sa che oltre non scende. |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 18 Gen 2007 16:34 Oggetto: |
|
|
E mi "sapeva" male.
39 |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 18 Gen 2007 18:47 Oggetto: |
|
|
36 |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 18 Gen 2007 18:56 Oggetto: |
|
|
35
Ora però devo andare a casa.
Domattina troverò la risposta finale. |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 19 Gen 2007 00:21 Oggetto: Re: mi fido di taifu |
|
|
salmastro ha scritto: | ...per cui abbandono i rimbalzi nel "trapezio" (?) legato alle configurazioni delle tre taniche, anche se a prima vista il fatto che i punti di arrivo siano ben 4 (036, 063, 306, 360) e siano tutti sul perimetro dovrebbe invitarmi a perseverare.
Per le 4 taniche sono curioso di vedere come si gioca a biliardo all'interno di una piramide tronca.
Salmastro |
Per dimostrare graficamente che il problema 5/7/9 non ha soluzioni bisogna disegnare il cammino (chiuso) che parte e finisce nello stato iniziale 009 e verificare che nessuno degli stati risolutivi vi appartiene o, viceversa, bisogna disegnare il cammino (anch'esso inesorabilmente chiuso) che parte e finisce in uno degli stati risolutivi e verificare che a tale cammino appartengono anche tutti gli altri stati risolutivi ma non lo stato iniziale 009.
Ecco il secondo grafico:
Il movimento nel tetraedro "pluritronco" è un po' più complesso.
Per capire quali sono le linee del reticolo tridimensionale che possono essere assunte come cammino lecito bisogna considerare due cose.
Da un lato (quello delle taniche) c'è da notare che una mossa tira in ballo due taniche e lascia il contenuto delle altre due inalterato.
Dall'altro (quello del grafico) che una mossa che lascia inalterato il contenuto di una tanica giace su un piano parallelo ad una delle quattro facce del tetraedro.
Quindi, dovendo lasciare inalterato il contenuto di due taniche simultaneamente, la mossa lecita deve giacere sulla retta interesezione di due piani paralleli a due distinte facce del tetraedro.
Per evitare il problema del nonhalting ai programmi basati su algoritmi brute force bisogna fare la seguente considerazione.
Gli n punti del reticolo non possono essere tutti collegati tra loro da un cammino inferiore a n-1 passi.
D'altro canto, ogni altro cammino che li tocchi tutti o è lungo anch'esso n-1 o qualche punto lo tocca più volte.
Quindi, nella peggiore delle ipotesi, il miglior cammino che raggiunge la configurazione desiderata è quello di lunghezza n-1 passante per tutti gli n punti perimetrali del reticolo.
Considerare cammini di lunghezza superiore è ridondante.
Nel caso 3/5/8 i punti perimetrali sono 16 ( 16=3+5+8 ) e il cammino più lungo che ha senso considerare ha, pertanto, lunghezza 15.
Nel caso 5/7/9 i punti perimetrali sono 21 ( 21=5+7+9 ) e quindi, Taifu, non ha senso far esplorare al programma cammini più lunghi di 20 passi.
Secondo voi quale può essere la massima lunghezza da considerare nel problema 5/8/13/26 ?
Sarà 52=5+8+13+26 o il giochetto della somma funziona solo sul piano? |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 19 Gen 2007 10:34 Oggetto: |
|
|
Sono stato troppo ottimista.
Il programmillo ha trovato una soluzione in 28 mosse e da tutta la notte sta girato alla ricerca di una soluzione con 27 mosse.
Evidentemente questo spazio di ricerca o non ha soluzioni o ne ha poche per cui lo esplorando tutto.
Non ho idea di quanto tempo sia necessario.
Io lo lascio girare, tanto non mi da fastidio.
Ciao.
Marco. |
|
Top |
|
|
_L_ Semidio
Registrato: 27/12/06 23:47 Messaggi: 215 Residenza: Brugherio (MI)
|
Inviato: 19 Gen 2007 19:45 Oggetto: |
|
|
per quanto riguarda il problema 5/7/9:
Citazione: |
0 0 0 (configurazione iniziale)
0 7 0
5 2 0
0 2 0
2 0 0
2 0 9
5 0 6
0 5 6
5 5 6
3 7 6
3 0 6
in 10 mosse
|
mentre quello da 4 taniche 5/8/13/26
Citazione: |
0 0 0 21 (conf. iniziale)
5 0 0 16
0 0 5 16
5 0 5 11
0 0 10 11
0 8 2 11
5 3 2 11
0 3 7 11
0 8 7 6
5 8 7 1
5 0 7 9
0 5 7 9
5 5 7 4
2 8 7 4
2 0 7 12
0 2 7 12
5 2 7 7
0 7 7 7
in 18 mosse
|
|
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 19 Gen 2007 21:17 Oggetto: |
|
|
_L_ ha scritto: | per quanto riguarda il problema 5/7/9:
0 0 0 (configurazione iniziale)
0 7 0
5 2 0
0 2 0
2 0 0
2 0 9
5 0 6
0 5 6
5 5 6
3 7 6
3 0 6
in 10 mosse |
C'è qualcosa che non quadra!
Stai usando di nascosto una quarta tanica sufficientemente capiente da contenere almeno 16 galloni (tanti quanti ne ritroviamo nelle tre taniche alla ottava mossa: 5 5 6).
La tua sequenza con una tanica da 16 galloni piena può essere accorciata di due mosse:
0 0 0 16 (configurazione iniziale)
0 7 0 9
5 2 0 9
0 2 0 14
2 0 0 14
2 0 9 5
5 0 6 5
0 5 6 5 (mossa superflua)
5 5 6 0
3 7 6 0
3 0 6 7 (mossa superflua)
Credo che l'errore sia frutto di un fraintendimento: il liquido da travasare è già presente nelle tre taniche (la configurazione iniziale, infatti, non è 0 0 0 ma 0 0 9) e non abbiamo una fontana di fianco nella quale versare il liquido in eccesso e dalla quale attingere infinitamente il liquido necessario.
La quarta tanica "sufficientemente capiente" gioca il ruolo della fontana.
In un mio post precedente ho riportato la dimostrazione grafica dell'impossibilità del problema...
La verifica della soluzione al problema delle quattro taniche richiede un'attenzione che ora non ho.
Mi balza subito all'occhio, però, che la configurazione iniziale non è 0 0 0 21 ma 0 8 13 0 e quindi, a meno che ciò non risulti essere una facilitazione, la tua soluzione si allunga di un passo.
In ogni caso, leggo dalla fonte che ci sono soluzioni più brevi... |
|
Top |
|
|
_L_ Semidio
Registrato: 27/12/06 23:47 Messaggi: 215 Residenza: Brugherio (MI)
|
Inviato: 19 Gen 2007 22:55 Oggetto: |
|
|
in effetti avevo fatto i conti con la fontana....
ci riprovo con quello da 4 taniche
Citazione: | 0 8 13 0 (conf. iniziale)
5 3 13 0
0 3 13 5
5 3 8 5
5 0 11 5
0 0 11 10
5 0 6 10
5 8 6 2
5 1 13 2
0 1 13 7
1 0 13 7
1 8 5 7
5 4 5 7
0 4 10 7
4 0 10 7
4 8 2 7
5 7 2 7
0 7 7 7
17 mosse
|
va bene qst? |
|
Top |
|
|
Taifu Semidio
Registrato: 24/10/06 10:13 Messaggi: 203
|
Inviato: 20 Gen 2007 02:10 Oggetto: |
|
|
Siccome non credo che tutti leggeranno sino in fondo, aggiungo subito alcuni nuovi sotto-indovinelli per il problema delle quattro taniche:
1) quante sono le differenti configurazioni raggiungibili dalla partenza 0/8/13/0 ?
2) quanto è distante la configurazione più lontana dal punto di partenza ?
3) e quante sono?
4) e quali sono? (ne basta una)
Essendomi stufato di aspettare, ho interrotto il programma ancora fermo ad esplorare l'albero delle 27 mosse e ho ripensato completamente l'algoritmo passando da una versione a forza "brutta" ad una realmente a forza bruta.
Adesso, con un leggerissimo fattore di miglioramento, in 87 centesimi di secondo ho trovato una soluzione in 16 mosse.
Mi sono dato per metà dell'asino per non averci pensato prima e per metà mi sono beato del programmino...
Citazione: |
In 16 mosse
<5 con 0> <8 con 8> <13 con 13> <26 con 0>
<5 con 5> <8 con 3> <13 con 13> <26 con 0>
<5 con 0> <8 con 3> <13 con 13> <26 con 5>
<5 con 3> <8 con 0> <13 con 13> <26 con 5>
<5 con 3> <8 con 8> <13 con 5> <26 con 5>
<5 con 5> <8 con 6> <13 con 5> <26 con 5>
<5 con 0> <8 con 6> <13 con 10> <26 con 5>
<5 con 5> <8 con 1> <13 con 10> <26 con 5>
<5 con 0> <8 con 1> <13 con 10> <26 con 10>
<5 con 1> <8 con 0> <13 con 10> <26 con 10>
<5 con 1> <8 con 8> <13 con 2> <26 con 10>
<5 con 5> <8 con 4> <13 con 2> <26 con 10>
<5 con 0> <8 con 4> <13 con 7> <26 con 10>
<5 con 4> <8 con 0> <13 con 7> <26 con 10>
<5 con 4> <8 con 8> <13 con 7> <26 con 2>
<5 con 5> <8 con 7> <13 con 7> <26 con 2>
<5 con 0> <8 con 7> <13 con 7> <26 con 7>
|
Per gli uomini di buona volontà questa è la nuova versione:
Codice: |
class Tanica(object):
def __init__(self, capacita, litri=0):
self.capacita = capacita
self.litri = litri
def capacita_residua(self):
return self.capacita - self.litri
def __eq__(self, tanica):
return self.capacita == tanica.capacita and self.litri == tanica.litri
def versa_in(self, tanica, litri=None):
if litri == None:
litri = min(tanica.capacita_residua(), self.litri)
self.litri -= litri
tanica.litri += litri
return litri
def __repr__(self):
return "<%d con %d>" % (self.capacita, self.litri)
class Stato(object):
def __init__(self, taniche):
self.stato = []
for tanica in taniche:
self.stato.append((tanica.capacita, tanica.litri))
def __eq__(self, stato):
return self.stato == stato.stato
def __iter__(self):
for coppia in self.stato:
yield Tanica(*coppia)
def __repr__(self):
return " ".join(["<%d con %d>" % s for s in self.stato])
class Nodo(object):
def __init__(self, stato, mosse):
self.stato = stato
self.mosse = mosse
def esplora(partenza):
grafo = [Nodo(partenza, [])]
history = [partenza]
nextLast = 0
while True:
aggiunto = False
last = nextLast
nextLast = len(grafo)
if last == nextLast:
break
for nodo in grafo[last:]:
taniche = [tanica for tanica in nodo.stato]
for prima in taniche:
for seconda in taniche:
if prima != seconda and prima.litri > 0 and seconda.capacita_residua > 0:
litri = prima.versa_in(seconda)
if Stato(taniche) not in history:
history.append(Stato(taniche))
grafo.append(Nodo(Stato(taniche), nodo.mosse[:] + history[-1:]))
seconda.versa_in(prima, litri)
return grafo
grafo = esplora(Stato([Tanica(5), Tanica(8, 8), Tanica(13, 13), Tanica(26)]))
obiettivo = Stato([Tanica(5), Tanica(8, 7), Tanica(13, 7), Tanica(26, 7)])
for nodo in grafo:
if obiettivo == nodo.stato:
print "*" * 20
print "In %d mosse" % len(nodo.mosse)
print grafo[0].stato
for mossa in nodo.mosse:
print mossa
|
Cambiando le seguenti due righe si può risolvere qualunque problema trovando la soluzione ottimale (anche se non il numero di soluzioni univoche):
Codice: |
grafo = esplora(Stato([Tanica(5), Tanica(8, 8), Tanica(13, 13), Tanica(26)]))
obiettivo = Stato([Tanica(5), Tanica(8, 7), Tanica(13, 7), Tanica(26, 7)])
|
Ciao.
Marco.
P.S. Il codice non è commentato ma sono assolutamente disponibile a spiegarlo riga per riga a chi me lo chiedesse. |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 21 Gen 2007 13:49 Oggetto: |
|
|
_L_ ha scritto: | va bene qst? |
Si, questa va bene!
Bel colpo!
Leggo dal libro che hai trovato una delle circa 800 soluzioni in 17 mosse.
Ma ci sono 7 soluzioni in sole 16 mosse.
Penso che tu non sia molto lontano.
Una delle 7 soluzioni, infatti, percorre il segmento centrale della tua soluzione, da 0 3 13 5 a 1 8 5 7, con una mossa in meno. Il resto del cammino è identico al tuo. |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 21 Gen 2007 14:02 Oggetto: |
|
|
Taifu ha scritto: | Siccome non credo che tutti leggeranno sino in fondo, aggiungo subito alcuni nuovi sotto-indovinelli per il problema delle quattro taniche:
1) quante sono le differenti configurazioni raggiungibili dalla partenza 0/8/13/0 ?
2) quanto è distante la configurazione più lontana dal punto di partenza ?
3) e quante sono?
4) e quali sono? (ne basta una)
Essendomi stufato di aspettare, ho interrotto il programma ancora fermo ad esplorare l'albero delle 27 mosse e ho ripensato completamente l'algoritmo passando da una versione a forza "brutta" ad una realmente a forza bruta.
Adesso, con un leggerissimo fattore di miglioramento, in 87 centesimi di secondo ho trovato una soluzione in 16 mosse.
Mi sono dato per metà dell'asino per non averci pensato prima e per metà mi sono beato del programmino...
|
Mi sono permesso di riscrivere la tua soluzione indicando solo le quantità e non le taniche (forse è l'età ma non riuscivo a tenere gli occhi solo sulle quantità senza confonderle con le taniche)
Citazione: |
0 8 13 0
5 3 13 0
0 3 13 5
3 0 13 5
3 8 5 5
5 6 5 5
0 6 10 5
5 1 10 5
0 1 10 10
1 0 10 10
1 8 2 10
5 4 2 10
0 4 7 10
4 0 7 10
4 8 7 2
5 7 7 2
0 7 7 7
|
Perfetto!
Ora mi leggo il programma vecchio e poi attacco con quello nuovo.
Sono proprio curioso di vedere come lo hai impostato! |
|
Top |
|
|
|
|
Non puoi inserire nuovi argomenti Non puoi rispondere a nessun argomento Non puoi modificare i tuoi messaggi Non puoi cancellare i tuoi messaggi Non puoi votare nei sondaggi
|
|