Newsgroup: it.hobby.enigmi
Titolo: Problema di packing

[per vedere l'ascii-art, usare caratteri fissi]
ATTO I
Ho sistemato, ordinatamente e con simmetria, 20 pentamini
tipo "X" in una scatola 12x12, pero' ho sciupato un sacco
di spazio:
 _ _ _ _ _ _ _ _ _ _ _ _
|_| |_|_| |_|_| |_|_| |_|
|_   _|_   _|_   _|_   _|
|_|_|_| |_|_|_|_| |_|_|_|
|_| |_   _| |_|_   _| |_|
|_   _|_|_   _| |_|_   _|
|_|_|_|_| |_|_   _|_|_|_|
|_| |_|_   _| |_|_|_| |_|
|_   _| |_|_   _| |_   _|
|_|_|_   _|_|_|_   _|_|_|
|_| |_|_| |_|_| |_|_| |_|
|_   _|_   _|_   _|_   _|
|_|_|_|_|_|_|_|_|_|_|_|_|
Chissa' quanti riuscirete a farne entrare, con la liberta'
di disporli come volete, anche inclinati...
(Questo e' il primo quesito).
ATTO II
Dopo tutta 'sta fatica di disporne quanti piu' possibile
in una scatola da 12x12, il mio rappresentante da Buenos
Aires mi scrive dicendomi che in Argentina vanno solo
confezioni da 20. Il Mercato Globale, si sa, la fa da
padrone. Quindi ho chiesto a due scatolifici di farmi il
preventivo per la piu' piccola scatola quadrata che ne
contenga 20. Lo scatolaio De Cubis mi dice che mantenendo
i pezzi ortogonali tra loro, e' possibile minimizzare le
dimensioni della scatola quadrata.
Lo sfizzero Impacket Tell, invece, dice che De Cubis non
capisce niente e che lui disponendo 16 "X" cosi':
         _
       _| |_ _
      |_   _| |_ _
     _| |_|_   _| |_ _
    |_   _| |_|_   _| |_
   _| |_|_   _| |_|_   _|
  |_   _| |_|_   _| |_|
 _| |_|_   _| |_|_   _|
|_   _| |_|_   _| |_|
  |_|_   _| |_|_   _|
      |_|_   _| |_|
          |_|_   _|
              |_|
e altri 4, uno per lato, opportunamente inclinati, riesce a
fare una scatola quadrata piu' piccola.
I preventivi sono identici, dovro' scegliere lo scatolaio
che fara' la scatola piu' piccola.
Voi quale mi consigliate?
Ciao!!!  ((^__^))'
Livio

 Voi quale mi consigliate?
Livio: tu per caso hai gia qualche soluzione? Mi piacerebbe sapere a cosa
sei approdato, io non sono arrivato a niente di interessante.
Fammi sapere qualche cosa,
Gabriele

 ha scritto:

Si', mi sembra giunta l'ora...  :o)
Il primo quesito mi pare interessante proprio perche' sembra
che il packing ortogonale sia molto ridondante, mentre non c'e'
verso di farcene stare uno in piu'. Basterebbe che la scatola
quadrata fosse 0.075 piu' larga e ce ne starebbero addirittura 25.
(Non fucilatemi!  :o))
L'atto II e' piu' serio. Ci sono almeno due packing che permettono
di fare la scatola *leggermente* piu' piccola. Qual e' il piu'
conveniente, this is the question.
A presto!!!  ((^__^))'
Livio

 conveniente, this is the question.
Non riesco a vedere quella con la disposizione ortogonale dei pezzi, ma ci
proverò meglio.
Gabriele

 conveniente, this is the question.
Se lo svizzero sistema i 4 pentamini spaiati "uno per lato" (come viene
detto nel post originale) non mi pare che possa migliorare. Dimmi se
sbaglio: i 16 pentamini nell'impacchettamento stretto stanno in una
scatola quadrata di lato 4,4*sqrt(5); la distanza massima di un
pentamino dal bordo del quadrato è 0,4*sqrt(5), mentre la larghezza
minima di un pentamino è 2*sqrt(2); quindi l'aggiunta di un pentamino
per lato rende necessario come minimo un quadrato di
4,4*sqrt(5) + 2*[2*sqrt(2) - 0,4*sqrt(5)] = 13,706.... 
quando sappiamo che ne basta uno di 12.
Forse lo svizzero mette due pentamini su due lati consecutivi? In questo
caso, mi pare che la penetrazione massima dei pentamini laterali sia di
sqrt(2)/3, quindi ottengo un quadrato di lato:
4,4*sqrt(5) + [2*sqrt(2) - sqrt(2)/3] = 12,195...
sempre troppo!
Dove sbaglio?
Maurizio

 detto nel post originale) non mi pare che possa migliorare.
Questo, per quanto mi riguarda, e' vero ma il ragionamento che segue no,
questo perche dai per scontata un inclinazione fissata mentre, se si
aggiunge un altro pentamino, potrei voler cambiare la pendenza del lato.
Aggiungendo un pentamino per lato, infatti, riesco ad impacchettarli
*obliquamente* in un quadrato di lato 12, con i lati con una pendenza di 4/3
(rispetto al lati delle X): si ancora il fatidico 12 che non ci lascia in
pace (prima di fare i conti pensavo di aver trovato una soluzione migliore).
Livio aiuto!
Gabriele
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

 Livio aiuto!
Partiamo da questa situazione in cui 16 "X" stanno dentro
ad un quadrato di 12x12:
 _ _ _ _ _ _ _ _ _ _ _ _
|      _| |_ _          |
|     |_   _| |_ _      |
|    _| |_|_   _| |_ _  |
|   |_   _| |_|_   _| |_|
|  _| |_|_   _| |_|_   _|
| |_   _| |_|_   _| |_| |
|_| |_|_   _| |_|_   _| |
|_   _| |_|_   _| |_|   |
| |_|_   _| |_|_   _|   |
|     |_|_   _| |_|     |
|         |_|_   _|     |
|_ _ _ _ _ _ _|_|_ _ _ _|
Ai quattro vertici ci stanno comodamente ancora 4 "X".
Ora, prima di inserire i 4 "X", ruotiamo il quadrato in
senso orario di *qualche grado*: il quadrato puo' diventare
un po' piu' piccolo e si possono ancora cacciare dentro
gli ultimi 4 "X", ruotandoli anch'essi, ma di un altro angolo.
Non e' banale.
Ciao!!!  ((^__^))'
Livio


A me viene un lato di circa 11.914 (poi mi sono stufato... perche'
andavo a tentativi)
La configurazione finale e' alla quale mi sono fermato e' questa:
http://www.imc.pi.cnr.it/resta/fittt.pdf
   (sono circa 2k).
il blocco grande e' inclinato di circa 2.208 gradi (0.038537513981976 
radianti).
ciao,
g.

 radianti).
Proprio cosi'!
Restano aperti due problemi:
- Affinare un metodo che permetta di trovare il valore ottimale, che
comunque non e' lontano dal tuo risultato.
- Trovare la configurazione che De Cubis dice essere migliore, e
io comincio a dargli ragione.
Ciao!!!  ((^__^))'
Livio

 [per vedere l'ascii-art, usare caratteri fissi]
... il problema era impacchettare 20 pentamini "X" nel piu'
piccolo quadrato possibile.
Mentre mi accingevo a scrivere questa soluzione, mi sono
reso conto di aver perduto gli scarabocchi che avevo fatto.
Oh beh, che ci vuole? Mi son detto. La ricostruisco in un
amen. Gia' mi ricordo che avevo semplicemente fatto 20/4=5
e avevo costruito con 5 "X" una specie di quadrato con cui
comporre poi quello finale:
         _
   _   _| |_
 _| |_|_   _|
|_   _| |_|_
  |_|_   _| |_
   _| |_|_   _|
  |_   _| |_|
    |_|
E che ci vuole! ecco qua:
                 _
           _   _| |_
         _| |_|_   _|
        |_   _| |_|_
   _   _| |_|_   _| |_ _
 _| |_|_   _| |_|_   _| |_
|_   _| |_|_   _| |_|_   _|
  |_|_   _| |_|_   _| |_|_
   _| |_|_   _| |_|_   _| |_
  |_   _| |_|_   _| |_|_   _|
    |_|_   _| |_|_   _| |_|
        |_|_   _| |_|
         _| |_|_   _|
        |_   _| |_|
          |_|
Ora, fatte le opportune triangolazioni, il lato del
quadrato che li contiene e'... ma porc@#@@*@#*@#!!!
e'... 12!!!!
E gia' avevo cominciato a scrivere un post di scuse
al ng, del tono "Scusate, ho preso un granchio, che
figura di m... ". Quando, lampadina!, c'erano dei buchi!
Mi ricordono benissimo, c'erano dei buchi e in questa
figura non ci sono. Impreca qui, impreca la', eccolo qua:
                   _
             _   _| |_
         _ _| |_|_   _|
   _   _| |_   _| |_|_
 _| |_|_   _|_|_   _| |_
|_   _| |_|_ _| |_|_   _|
  |_|_   _| |_   _| |_| |_
   _| |_|_   _|_| |_|_   _|
  |_   _| |_| |_   _| |_|_
    |_| |_|_   _|_|_   _| |_
    |_   _| |_|_ _| |_|_   _|
      |_|_   _| |_   _| |_|
       _| |_|_   _|_|
      |_   _| |_|
        |_|
Lato = 11.8845  Alleluia!
Ho capito perche' non e' stato facile.  :o)
Ciao a tutti!!!  ((^__^))'
Livio