[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] Packing (#62

James Gray

1/13/2006 1:41:00 PM

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rub...

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Ilmari Heikkinen

You're moving. And that means a whole bunch of boxes need to be moved from the
old place to the new one. You've got a pickup truck to do the moving, but it can
only hold one vertical level of boxes. The boxes need to be padded with one unit
worth of foam on each side that's facing another box.

The goal is to minimize the amount of trips you have to do to move all the
boxes.

The solver program should take two lines of input, first one containing the
trunk dimensions (e.g. 10x20), and the second one containing all the box
dimensions, separated by spaces (e.g. 1x3 4x8 3x7 9x4 10x14.)

The output of the solver should be ascii art of the trunk packings, with each
trunkful separated by an empty line.

Example:
$ ruby solver.rb
10x20
1x3 4x8 3x7 9x4 10x14

**************.***..
**************......
**************.****.
**************.****.
**************.****.
**************.****.
**************.****.
**************.****.
**************.****.
**************.****.

*********...........
*********...........
*********...........
*********...........
....................
*******.............
*******.............
*******.............
....................
....................
17 Answers

Ilmari Heikkinen

1/13/2006 3:22:00 PM

0

On 1/13/06, Ruby Quiz <james@grayproductions.net> wrote:> The three rules of Ruby Quiz:>> 1. Please do not post any solutions or spoiler discussion for this quiz until> 48 hours have passed from the time on this message.>> 2. Support Ruby Quiz by submitting ideas as often as you can:>> http://www.rubyquiz.co... 3. Enjoy!>> Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone> on Ruby Talk follow the discussion.>> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=>> by Ilmari Heikkinen>> You're moving. And that means a whole bunch of boxes need to be moved from the> old place to the new one. You've got a pickup truck to do the moving, but it can> only hold one vertical level of boxes. The boxes need to be padded with one unit> worth of foam on each side that's facing another box.>> The goal is to minimize the amount of trips you have to do to move all the> boxes.>> The solver program should take two lines of input, first one containing the> trunk dimensions (e.g. 10x20), and the second one containing all the box> dimensions, separated by spaces (e.g. 1x3 4x8 3x7 9x4 10x14.)>> The output of the solver should be ascii art of the trunk packings, with each> trunkful separated by an empty line.>> Example:> $ ruby solver.rb> 10x20> 1x3 4x8 3x7 9x4 10x14Good luck, everyone!Finding an optimal solution is going to be quite computationally intensive,so unoptimal solvers are also welcome.Checking that the solution you get really is optimal might be a wee bit hard,so here's a little program that generates problems with known optimalsolutions (these are without the 1 unit padding though):$ ruby troublemaker.rb 6x6 2 # 2 6x6 trunks6x64x3 4x3 2x6 4x3 4x3 2x6$ cat troublemaker.rbdef randomly_cut_up(box) if box.min > 3 cut = 3+rand(box.max-3) if box.max == box[0] randomly_cut_up([cut, box[1]]) + randomly_cut_up([box[0]-cut, box[1]]) else randomly_cut_up([box[0], cut]) + randomly_cut_up([box[0], box[1]-cut]) end else [box] endendif __FILE__ == $0 trunk_size = ARGV[0].split("x").map{|i| i.to_i} trunk_count = ARGV[1].to_i boxes = [] (1..trunk_count).each{|i| boxes += randomly_cut_up trunk_size } #puts "requested volume: #{trunk_size[0]*trunk_size[1]*trunk_count}" #puts "cut up volume: #{boxes.inject(0){|s,b| s+b[0]*b[1]}}" box_str = boxes.map{|box| box.join("x")}.join(" ") puts trunk_size.join("x") puts box_strend

Robert Retzbach

1/13/2006 3:27:00 PM

0

Ruby Quiz schrieb:

>The three rules of Ruby Quiz:
>
>1. Please do not post any solutions or spoiler discussion for this quiz until
>48 hours have passed from the time on this message.
>
>2. Support Ruby Quiz by submitting ideas as often as you can:
>
>http://www.rub...
>
>3. Enjoy!
>
>Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
>on Ruby Talk follow the discussion.
>
>-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>
>by Ilmari Heikkinen
>
>You're moving. And that means a whole bunch of boxes need to be moved from the
>old place to the new one. You've got a pickup truck to do the moving, but it can
>only hold one vertical level of boxes. The boxes need to be padded with one unit
>worth of foam on each side that's facing another box.
>
>The goal is to minimize the amount of trips you have to do to move all the
>boxes.
>
>The solver program should take two lines of input, first one containing the
>trunk dimensions (e.g. 10x20), and the second one containing all the box
>dimensions, separated by spaces (e.g. 1x3 4x8 3x7 9x4 10x14.)
>
>The output of the solver should be ascii art of the trunk packings, with each
>trunkful separated by an empty line.
>
> Example:
> $ ruby solver.rb
> 10x20
> 1x3 4x8 3x7 9x4 10x14
>
> **************.***..
> **************......
> **************.****.
> **************.****.
> **************.****.
> **************.****.
> **************.****.
> **************.****.
> **************.****.
> **************.****.
>
> *********...........
> *********...........
> *********...........
> *********...........
> ....................
> *******.............
> *******.............
> *******.............
> ....................
> ....................
>
>
>
>
Hello,
this is a interesting quiz, but I am still in the middle to understand
the last! :D

However... I can't access ruby62.html. It's always rewritten to ruby26.html.
Maybe I stand alone with this problem.

MfG
Retze

James Gray

1/13/2006 3:33:00 PM

0

On Jan 13, 2006, at 9:26 AM, Robert Retzbach wrote:

> However... I can't access ruby62.html. It's always rewritten to
> ruby26.html.
> Maybe I stand alone with this problem.

Are you talking about:

http://www.rubyquiz.com/q...

It loads fine for me. Is anyone else seeing this?

The page contains exactly the same information as the email you
quoted though, so you're not missing anything.

James Edward Gray II

Robert Retzbach

1/13/2006 3:39:00 PM

0

Robert Retzbach schrieb:

> Ruby Quiz schrieb:
>
>> The three rules of Ruby Quiz:
>>
>> 1. Please do not post any solutions or spoiler discussion for this
>> quiz until
>> 48 hours have passed from the time on this message.
>>
>> 2. Support Ruby Quiz by submitting ideas as often as you can:
>>
>> http://www.rub...
>>
>> 3. Enjoy!
>>
>> Suggestion: A [QUIZ] in the subject of emails about the problem
>> helps everyone
>> on Ruby Talk follow the discussion.
>>
>> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
>>
>>
>> by Ilmari Heikkinen
>>
>> You're moving. And that means a whole bunch of boxes need to be moved
>> from the
>> old place to the new one. You've got a pickup truck to do the moving,
>> but it can
>> only hold one vertical level of boxes. The boxes need to be padded
>> with one unit
>> worth of foam on each side that's facing another box.
>>
>> The goal is to minimize the amount of trips you have to do to move
>> all the
>> boxes.
>>
>> The solver program should take two lines of input, first one
>> containing the
>> trunk dimensions (e.g. 10x20), and the second one containing all the box
>> dimensions, separated by spaces (e.g. 1x3 4x8 3x7 9x4 10x14.)
>>
>> The output of the solver should be ascii art of the trunk packings,
>> with each
>> trunkful separated by an empty line.
>>
>> Example:
>> $ ruby solver.rb
>> 10x20
>> 1x3 4x8 3x7 9x4 10x14
>>
>> **************.***.. **************......
>> **************.****.
>> **************.****.
>> **************.****.
>> **************.****.
>> **************.****.
>> **************.****.
>> **************.****.
>> **************.****.
>>
>> *********...........
>> *********...........
>> *********...........
>> *********...........
>> ....................
>> *******.............
>> *******.............
>> *******.............
>> ....................
>> ....................
>>
>>
>>
>>
> Hello,
> this is a interesting quiz, but I am still in the middle to understand
> the last! :D
>
> However... I can't access ruby62.html. It's always rewritten to
> ruby26.html.
> Maybe I stand alone with this problem.
>
> MfG
> Retze
>
>
Hmmm,
with Ie it works, maybe I have something in my ff cache.
Nvm then, happy quizzing.

MenTaLguY

1/13/2006 4:25:00 PM

0

Are we allowed to rotate boxes?

-mental

James Gray

1/13/2006 4:30:00 PM

0

On Jan 13, 2006, at 10:24 AM, mental@rydia.net wrote:

> Are we allowed to rotate boxes?

You bet.

James Edward Gray II

Ilmari Heikkinen

1/13/2006 4:31:00 PM

0

On 1/13/06, mental@rydia.net <mental@rydia.net> wrote:> Are we allowed to rotate boxes?>> -mental>>Yes.

hampton c

1/13/2006 5:07:00 PM

0

Is the primary goal to have the fastest algorithm or the best-answer
generating algorithm?

MenTaLguY

1/13/2006 8:15:00 PM

0

Quoting Ruby Quiz <james@grayproductions.net>:

> Example:
> $ ruby solver.rb
> 10x20
> 1x3 4x8 3x7 9x4 10x14
>
> **************.***..
> **************......
> **************.****.
> **************.****.
> **************.****.
> **************.****.
> **************.****.
> **************.****.
> **************.****.
> **************.****.
>
> *********...........
> *********...........
> *********...........
> *********...........
> ....................
> *******.............
> *******.............
> *******.............
> ....................
> ....................

Whoops, this example shows an 8x4 box, not a 9x4 one.

-mental

Ilmari Heikkinen

1/13/2006 9:13:00 PM

0

On 1/13/06, mental@rydia.net <mental@rydia.net> wrote:> Quoting Ruby Quiz <james@grayproductions.net>:>> > Example:> > $ ruby solver.rb> > 10x20> > 1x3 4x8 3x7 9x4 10x14> >> > **************.***..> > **************......> > **************.8x4*.> > **************.****.> > **************.****.> > **************.****.> > **************.****.> > **************.****.> > **************.****.> > **************.****.> >> > 9x4******...........> > *********...........> > *********...........> > *********...........> > ....................> > *******.............> > *******.............> > *******.............> > ....................> > ....................>> Whoops, this example shows an 8x4 box, not a 9x4 one.Actually, there's an 8x4 box and a 9x4 box.The small width of the characters really is quite confusing,long lines of asterisks merging into each otherwhile rows are well separated,making counting difficult -a Gestalt law in effect.</bad poetry>(=