Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
* QUIZ: Le TRE taniche (forse anche di più)
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici
Precedente :: Successivo  
Autore Messaggio
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 09 Gen 2007 23:52    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 17 Gen 2007 17:03    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 17 Gen 2007 21:48    Oggetto: Rispondi citando

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... Smile

Ciao.
Marco.
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 18 Gen 2007 09:13    Oggetto: Rispondi citando

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... Smile


Ehm, ehm... Embarassed Embarassed Embarassed Embarassed Embarassed

E' che io conosco a malapena il Baasic... Toilet


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? Jump
Prova a sottoporre al tuo programma il secondo problema con tre taniche e dimmi che succede...
Top
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 18 Gen 2007 10:34    Oggetto: Rispondi citando

ulisse ha scritto:

Tempi macchina che si allungano? Jump
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! Smile

Ciao.
Marco.
Top
Profilo Invia messaggio privato
Salmastro
Dio minore
Dio minore


Registrato: 13/12/06 19:36
Messaggi: 883
Residenza: Casalmico

MessaggioInviato: 18 Gen 2007 10:54    Oggetto: mi fido di taifu Rispondi citando

...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
Profilo Invia messaggio privato AIM Yahoo MSN
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 18 Gen 2007 15:52    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 18 Gen 2007 15:58    Oggetto: Rispondi citando

Siamo a 42 mosse.

Sono curioso di vedere fino a dove scende...
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 18 Gen 2007 16:20    Oggetto: Rispondi citando

41...

E mi sa che oltre non scende.
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 18 Gen 2007 16:34    Oggetto: Rispondi citando

E mi "sapeva" male.

39
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 18 Gen 2007 18:47    Oggetto: Rispondi citando

36
Top
Profilo Invia messaggio privato
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 18 Gen 2007 18:56    Oggetto: Rispondi citando

35

Ora però devo andare a casa.
Domattina troverò la risposta finale.
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 19 Gen 2007 00:21    Oggetto: Re: mi fido di taifu Rispondi citando

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
Profilo Invia messaggio privato HomePage
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 19 Gen 2007 10:34    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
_L_
Semidio
Semidio


Registrato: 27/12/06 23:47
Messaggi: 215
Residenza: Brugherio (MI)

MessaggioInviato: 19 Gen 2007 19:45    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato HomePage MSN
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 19 Gen 2007 21:17    Oggetto: Rispondi citando

_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
Profilo Invia messaggio privato HomePage
_L_
Semidio
Semidio


Registrato: 27/12/06 23:47
Messaggi: 215
Residenza: Brugherio (MI)

MessaggioInviato: 19 Gen 2007 22:55    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato HomePage MSN
Taifu
Semidio
Semidio


Registrato: 24/10/06 10:13
Messaggi: 203

MessaggioInviato: 20 Gen 2007 02:10    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 21 Gen 2007 13:49    Oggetto: Rispondi citando

_L_ ha scritto:
va bene qst?


Si, questa va bene!
Bel colpo! Applause

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
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 21 Gen 2007 14:02    Oggetto: Rispondi

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

Applause Applause Applause Applause Applause Applause Applause Applause Applause

Perfetto!
Ora mi leggo il programma vecchio e poi attacco con quello nuovo.
Sono proprio curioso di vedere come lo hai impostato!
Top
Profilo Invia messaggio privato HomePage
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici Tutti i fusi orari sono GMT + 1 ora
Vai a 1, 2, 3  Successivo
Pagina 1 di 3

 
Vai a:  
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