Newsgroup: it.hobby.enigmi
Titolo: [Pentamini] Farsi in tre

Vorrei trovare tutte le (o qualcuna delle :o)) figure di 20
quadretti che, triplicate, contengano esattamente tutti i
12 pentamini.
Esempio:
http://yfrog.com/gqpentaminox3g
Ciao
Livio

 12 pentamini...
Ciao Livio !
Dopo questa tua richiesta ho ritrovato, devo dire con un po' di 
emozione, un quadernino dove nei primi anni '80 avevo annotato 111 
soluzioni trovate a mano in non poche ore di lavoro.
spoiler...
...
Il solito Helmut Postl ha una lista di 339 soluzioni. Non e' detto che 
siano tutte.

 siano tutte.
E gia', eccoli qua:
http://pentomino.wirisonline.net/20poe.html
Beh, non pensavo fossero tante. La ricerca di Helmut
sembra sistematica, ma una controllata non ci starebbe
male.
Ciao!!!
Livio

 sembra sistematica, ma una controllata non ci starebbe
Eh, ma se gia' ci sono 339 soluzioni si sente un po'
meno la spinta ad investigare...
ciao a tutti e due!
giovanni resta

 Dopo questa tua richiesta ho ritrovato...
Sono completamente arrugginito e non ho piu'
alcuna documentazione al di fuori di internet.
Esistono sol di 4 shapes da 15?
Ciao
Livio

 Esistono sol di 4 shapes da 15?
No. Questo è il problema num.88 proposto dallo stesso Solomon Golomb sul 
suo "Polyominoes" del 1965.
Ho trovato una soluzione, come dire... patologica: Prendiamo 2 serie di 
Pentamini A e B, scambiamo un pezzo di A con un pezzo di B. Ora possiamo 
risolvere il problema 88 con entrambe le serie. Conosco 2 soluzioni 
distinte, ma presumo ne esistano altre. Ci proviamo ?
Ciao dario


Prometto di pensarci, ma mi sembra alquanto duretto.
Se ho una sol la metto qua sotto. Ma dammi tempo, neh :o)
Ciao!
Livio

 Ciao dario
Ecco la mia prima:
http://yfrog.com/1asoldario1g
Mica facile. Celo o manca?
Ciao
Livio

Chenickname ha scritto:

Ottimo ! con questa sono 3. Possiamo distinguerle utilizzando le lettere 
indicanti i due pezzi scambiati. La tua è IZ, le altre due sono YF e YN.
ciao

 ciao
Questo e' la FY:
http://yfrog.com/mtsoldariofyg
Per la NY sono in alto mare.
Ciao
http://yfrog.com/mtsoldariofyg

 
http://yfrog.com/mtsoldariofyg
E a questo punto la WX dovrebbe essere inedita:
http://yfrog.com/5ysoldariowxg
'Notte


Invece, Giovanni, il problema proposto da Dario?
Potresti esaminarlo come copertura dei 15-omini.
In fondo sono solo 3.426.576  :o))
Ciao
Livio

 
http://yfrog.com/5ysoldariowxg
Oh oh, oggi abbiamo la IX:
http://yfrog.com/mgsoldarioixg
Ciao
Livio

 ciao
Dario, io sulla YN mi arrendo, proprio non riesco a vederla.
Se vuoi dacci lo schema, anche solo il contorno in ascii-art,
che disegno la sol in bella. Con questa sarebbero 5.
Ciao
Livio
http://yfrog.com/1asoldario1g
http://yfrog.com/mtsoldariofyg
http://yfrog.com/5ysoldariowxg
http://yfrog.com/mgsoldarioixg

 
La tua efficacia riesce sempre a sorprendermi !!
complimenti davvero.
Eccola:
      y     y     f     x
   lyyyy vvvyy zzfff twxxx
   llll  ppvy  zufu  twwx
  iiiii pppvy zzuuu tttww
   nnn   ffl   nnn   xuu
  nnwt  ffvl  nnzz  xxxu
   wwt   fvl   ppz   xuu
  wwttt vvvll pppzz iiiii

   wwttt vvvll pppzz iiiii
Non sarei riuscito a trovarla tanto facilmente
perche' avevo erroneamente classificato lo
schema (2N-Y) da te usato come impossibile.
Non so, a questo punto, quanto sia esaustiva la
ricerca fatta.
http://yfrog.com/0fsoldarionyg


 wrote:
Come dice Livio ci sono solo alcuni milioni di 15-mini...
Gia' generarli non e' proprio immediato.
Il programma scaricato da Internet che ho usato anni fa per generare
fino ai dekamini
ci ha messo tipo un minuto per quelli da 11, circa un ora per quelli
ad 12,
adesso sta girando da una decina di ore senza essere arrivato a finire
quelli
da 13, quindi non ho tante speranze che mi generi quelli da 15 durante
la mia vita...
Adesso provo ad implementarne una versione mia sperando che
sia piu' veloce.
Se riesco ad ottenere in tempi ragionevoli l'elenco dei 15-omini
provo ad attaccare il problema esaustivamente (anche se magari voi
avrete
trovato tutte le soluzioni...)
In teoria potrei anche lasciar perdere i 15-omini e provare un metodo
piu' diretto come avevo fatto per i polipolimini
( 
http://www.iread.it/Poly/index_it.php
 )
ma era un programma abbastanza complicato (di cui non ricordo
niente!),
quidi propenderei per una soluzione che usi piu' tempo macchina e meno
tempo uomo.
Se arrivo a qualche risultato mi rifaccio vivo. E magari metto in
linea
una paginetta riassuntiva dei vostri sforzi.
ciao,
g.


Il problema e' intrigante per una macchina. :o)
Si', forse partire dai 15-omini e' eccessivo.
Si potrebbe considerare l'insieme di 3 pentamini
uniti per un minimo di N lati:
http://yfrog.com/f5semisoluzioneg
N potrebbe essere 5 se sono ad anello e 6 o forse 8
se sono uniti a catena aperta (A tocca B che tocca C
ma C non tocca A).
Il metodo piu' semplice dovrebbe essere quello di
catalogare le semi-soluzioni per poi vedere se ce
ne sono di complementari.
Se posso essere utile, fammi un fischio.
Ciao
Livio

Alla fine il mio programmino per generare i 15-omini ci ha messo
solo pochi minuti invece di mesi o anni.
Ci sono 79 semisoluzioni e 6 soluzioni.
(per me una semisoluzione e' determinata dalla coppia
di pentamini (doppio,mancante) e dal 15-omino.
Non ho considerato la possibilita' che lo stesso 15-omino si potesse
coprire
in piu' modi diversi con gli stessi pezzi).
Forza ragazzi vi manca solo una soluzione !
Riassumendo,
la   IZ si puo' fare in tre modi (uno dei due set si puo' disporre in
3 modi diversi)
la   IX  e la WX si possono fare in due modi.
la  NY e la FY in un modo.
Quella che manca si puo' fare in un modo.
ciao,
g.


Gia fatto?????
Io credevo che ci volessero dei giorno per fare un
programma cosi'!
Sei mitico!
Io ho 47 semisoluzioni contro le tue 79.
Forse un po' di fortuna ce ne ha fatto travare 5 su 6.
Sara' dura.
Tu, tra qualche giorno, magari con uno spoiler, se
vedi che non la troviamo, daccela lo stesso, va.  :o))
Complimentoni
Livio

 Quella che manca si puo' fare in un modo...
Che dire ?? veramente impressionante. Mi unisco ai complimenti di Livio.
Vado col piů facile, ho trovato una delle sol. alternative  della IZ:
uuu   vvv   lln   ppp
uzu   vww   lyn   tpp
fzzz  vxww  lynn  tttz
fffz  xxxw  lyyn  tzzz
  f     x     y     z
dario

Livio
Dopo giorni di tentativi ho trovato una manciata di semisoluzioni e 
finalmente una soluzione!
Peccato che sia la WX gia' abbondantemente trovata da Livio.
Ma sono contento lo stesso e continuo a scarabocchiare senza nessuna 
sistematicità, sperando nella botta di culo.
Ho anche pensato di scrivere un algoritmo, ma la difficolta', la pigrizia e 
non ultimo il fatto che anche li' sarei arrivato non proprio primo, mi fanno 
desistere.
Comunque almeno per me il thread non e' esaurito.
-- 
Ciao, Silv:o) 

 vedi che non la troviamo, daccela lo stesso, va.  :o))
Ho messo qui una pagina con il problema, le 79 semisoluzioni,
e le 6 (o 10) soluzioni (l'ultima e' quella che vi manca).
Se volete vi dico quale e' la coppia di pentamini da scambiare...
Una particolarita': e' l'unica soluzione in cui uno dei 2 pattern
comuni
contiene un "buco". L'altro pattern invece l'avete gia' visto...
http://www.iread.it/Poly/uri_problem_it.php
le soluzioni (a parte una)
e le semisoluzioni sono su pagine separate
per evitare spoiler.
ciao,
g.

L'avevo "sfiorato" piu' volte.
Mi consola il fatto che per una quindicina di giorni mi sono divertito a 
provare a mano senza alcuna sistematicità: stupido, ma molto divertente e 
rilassante.
Ancora complimenti per la tua ribadita' abilita'.
-- 
Silv:o) 


Io, di semisoluzioni col buco ne avevo travata soltanto una!
Quindi ero molto lontano.  :o(
Ancora complimenti per il lavoro. La cosa che mi ha
stupito di piu' e' la velocita' con cui ci sei arrivato.
Ciao
Livio

 stupito di piu' e' la velocita' con cui ci sei arrivato.
In realta', una volta superata l'inerzia mentale che mi
contraddistingue,
non era una cosa complicata.
La cosa che mi ha richiesto piu' sforzo e' stata
la generazione dei 15-omini, perche', come ho detto,
il codice altrui che avevo scaricato dalla rete era troppo lento.
Il metodo di generazione e' sostanzialmente quello
ovvio, con 2 accorgimenti per velocizzare  le cose.
Il metodo ovvio e' questo:
per generare i (n+1)-omini, prendi
ciascun n-omino, prova ad aggiungergli
un quadretto in ogni posizione possibile,
e per ciascun polimino cosi' ottenuto controlla
se lui o una delle sue altre 7 incarnazioni
figura gia' nella costituenda lista dei (n+1)-omini.
Chiaramente bisogna cercare di fare le cose
in modo efficiente, altrimenti il tempo (per tutte le
ricerche in una lista che supera presto il milione
di elementi) esplode.
Io ho fatto cosi'.
Ogni polimino di N caselle e' rappresentato
da una stringa di 2(N-1) caratteri alfanumerici.
In pratica: "butto" il polimino in una griglia di dimensione
opportuna. La scandisco riga per riga da sx a dx.
Il primo quadratino che trovo stabilisco che abbia coordinate (0,0),
e continuando la scansione stabilisco le coordinate degli
altri in relazione al primo (alcune coordinate possono
essere negative).
Date queste N coppie di coordinate, quindi 2*N numeri piccoli,
sommo ad essi una costante opportuna per ottenere 2*N
caratteri alfanumerici, scartando la coordinata (0,0) che per
costruzione appartiene ad ogni rappresentazione.
Perche' converto i polimini in stringhe di caratteri ?
Perche' sono facilmente e efficientemente ordinabili.
In particolare, date le 8 rotazioni di un potenziale nuovo polimino,
io considero solo la prima, lessicograficamente.
In questo modo riduco le ricerche nel listone di un fattore 8.
Poi, posso implementare il listone usando, in C++,
il tipo di dato set di stringhe, che sostanzialmente
e' gia' implementato nelle STL, quindi mi semplifica
grandemente la vita. Il set nelle STL e' fatto furbescamente
in modo che le operazioni principali
(test sulla presenza di un elemento ed eventuale inserzione)
ci mettono un tempo grosso modo logaritmico rispetto alla dimensione
della lista, al costo di consumare piu' memoria di un semplice array.
Passare da O(N) per la scansione naive della lista
a O(log(N))  fa una bella differenza. Infatti il programma
per calcolare tutti i polimini fino all'ordine 15 ci ha messo,
se ricordo bene, una decina di minuti.
Quindi come vedi niente di particolarmente furbo.
Una volta ottenuti tutti i 15-omini, ho solo riciclato un mio
vecchio programma generale per la ricopertura di un area
con un set di polimini. (Uno dei pochissimi programmi che
avendo usato un certo numero di volte continuo a
ricordarmi come usare...)
Gli ho dato in pasto ogni pattern di 15-omini
replicato 4 volte e provando per tutti i set di pentamini a cui
avevo aggiunto e tolto un elemento. Credo che ci abbia messo
qualche ora. Le 79 semisoluzioni le ho poi accoppiate con una
semplice batch sotto linux (perche' avevo nominato in modo opportuno
i files di soluzione).
ciao,
g.