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: 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 Precedente  1, 2, 3, 4, 5  Successivo
Pagina 3 di 5

 
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