Problem 2072. Packing Santa's Sleigh: First Layer

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is inspired by the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.kaggle.com/c/packing-santas-sleigh\"><w:r><w:t>Packing Santa's Sleigh</w:t></w:r></w:hyperlink><w:r><w:t> contest at kaggle that runs until January 26, 2014.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Bag has a 1000 x 1000 base with the contest having 1,000,000 packages.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is to place as many of the first N Santa Presents onto the 1000 x 1000 grid. The packages have been presorted to have Z as max, not provided, thus minimizing the X*Y cross section. Only the first 240 packages are provided as package 241 busts the bag bottom making an area greater than 1,000,000. Packages out of sequence cause a severe penalty thus all packages less than the highest package used must fit on the board.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input</w:t></w:r><w:r><w:t>: Presents ; Presents(240,2)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output</w:t></w:r><w:r><w:t>: L, xyTL; L(1000,1000) of values 0:n&lt;=240, 0 is unused space</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Scoring</w:t></w:r><w:r><w:t>: Unused Area</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example</w:t></w:r><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>[2 2;3 3;1 2] is Presents</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>L</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[1 1 2 2 2 0 thru column 1000\n1 1 2 2 2\n3 3 2 2 2\n0 0 0 0 0 0 rows 4 thru 1000 are zeros]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>xyTL [1 1;1 3;3 1]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Scores 1,000,000 - 15= 999985</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Boxes 1:236 are possible, 97.5719% efficient pack in &lt; 1sec.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>TestSuite Sample Code:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>In the TestSuite at the end is wrapper code for entering the kaggle contest. Update your SantaPack routine and execute the wrapper to see your contest score. The official presents.mat file needs to be downloaded. The wrapper has further discussion on efficient methods and current scores.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This Challenge is inspired by the <a href = "http://www.kaggle.com/c/packing-santas-sleigh">Packing Santa's Sleigh</a> contest at kaggle that runs until January 26, 2014.The Bag has a 1000 x 1000 base with the contest having 1,000,000 packages.This Challenge is to place as many of the first N Santa Presents onto the 1000 x 1000 grid. The packages have been presorted to have Z as max, not provided, thus minimizing the X*Y cross section. Only the first 240 packages are provided as package 241 busts the bag bottom making an area greater than 1,000,000. Packages out of sequence cause a severe penalty thus all packages less than the highest package used must fit on the board.Input: Presents ; Presents(240,2)Output: L, xyTL; L(1000,1000) of values 0:n&lt;=240, 0 is unused spaceScoring: Unused AreaExample:[2 2;3 3;1 2] is PresentsL<pre class="language-matlab">1 1 2 2 2 0 thru column 1000
1 1 2 2 2
3 3 2 2 2
0 0 0 0 0 0 rows 4 thru 1000 are zeros
</pre>xyTL
[1 1;1 3;3 1]Scores 1,000,000 - 15= 999985Boxes 1:236 are possible, 97.5719% efficient pack in &lt; 1sec.TestSuite Sample Code:In the TestSuite at the end is wrapper code for entering the kaggle contest.
Update your SantaPack routine and execute the wrapper to see your contest score. The official presents.mat file needs to be downloaded. The wrapper has further discussion on efficient methods and current scores.

Solve

Solution Stats

7 Solutions
4 Solvers

Last Solution submitted on Oct 01, 2020

Last 200 Solutions

Solution Comments

Solution 403281

1 Comment

1 Comment

Alfonso Nieto-Castanon on 13 Feb 2014

this solution packs all 240 boxes (99.1% efficiency); Rather than entering as many boxes as possible in each level, in the actual contest I used a somewhat more convoluted strategy that attempted to condition the box heights so that they would also pack nicely vertically across sequential levels, but the 2d-packing solver works just as well for these simpler "unconstrained" cases. Here (http://www.kaggle.com/c/packing-santas-sleigh/forums/t/6934/how-d-you-do-it/38414#post38414) is a more detailed description of the method I used in that contest, and you may find a link to the solution code there (as well as in this solution) in case you are interested.

Problem Recent Solvers4

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 2072. Packing Santa's Sleigh: First Layer

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Problem 2072. Packing Santa's Sleigh: First Layer

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Players