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.
Test | Status | Code Input and Output |
---|---|---|
1 | Pass |
assignin('caller','score',100000);
|
2 | Pass |
%%
Santa_L1=[3 2;207 73;160 78;8 3;
9 9;
170 120;116 91;
206 142;28 8;
3 2;41 22;
31 11;28 20;
29 13;98 96;
26 4;34 9;
4 3;84 78;
219 114;28 22;
195 185;3 2;
31 9;104 101;
32 31;188 142;
45 18;8 2;
13 10;49 22;
172 72;28 17;
90 87;33 5;
32 23;16 14;
42 18;32 8;
7 5;6 6;
201 69;20 11;
30 18;211 120;
206 97;3 2;
124 92;48 43;
2 2;173 103;
26 12;8 7;
8 8;57 33;
21 20;24 15;
26 12;44 24;
30 8;
43 26;
23 23;
9 4;
16 13;
58 29;
133 125;
5 2;
197 117;
39 10;
31 11;
41 18;
6 3;
31 8;
40 32;
41 39;
36 30;
2 2;
25 24;
6 2;
3 2;
2 2;
85 70;
37 25;
24 20;
60 26;
29 14;
49 30;
153 75;
6 3;
7 3;
185 162;
4 2;
6 5;
176 99;
4 2;
219 154;
24 22;
148 87;
32 7;
143 98;
23 13;
150 65;
5 2;
53 41;
25 12;
36 6;
21 10;
211 79;
183 130;
6 3;
36 28;
32 16;
21 15;
27 26;
39 14;
36 7;
57 17;
214 90;
36 5;
27 16;
52 15;
8 6;
5 4;
52 37;
7 2;
92 79;
37 35;
33 5;
5 2;
52 10;
29 5;
44 18;
8 5;
16 8;
137 105;
78 74;
9 5;
39 29;
43 31;
6 3;
8 4;
26 19;
22 7;
30 15;
199 195;
7 7;
7 5;
134 81;
206 108;
54 29;
16 7;
116 99;
35 23;
31 17;
56 11;
7 3;
52 5;
102 99;
5 5;
35 17;
8 6;
51 7;
28 16;
107 83;
26 8;
8 6;
149 83;
45 29;
55 52;
27 6;
82 81;
9 5;
27 21;
19 10;
56 26;
19 14;
11 8;
47 7;
26 13;
36 19;
87 73;
14 10;223 100;2 2;33 5;198 135;38 15;19 8;211 95;9 6;21 7;175 145;22 16;7 5;7 4;9 8;42 5;3 3;2 2;3 2;5 2;30 24;29 29;27 9;168 72;6 4;22 7;9 6;10 6;19 16;7 2;43 14;138 115;138 130;39 20;9 4;27 7;26 22;169 144;8 8;41 9;50 26;62 10;33 19;7 2;121 112;102 93;109 88;9 8;40 40;25 19;31 8;55 23;41 11;6 2;8 3;128 114;40 16;7 6;5 2];
[L,xyTL]=SantaPack(Santa_L1);
ptrxy=find(xyTL(:,1)>0,1,'last');
presents=Santa_L1;
for k=1:ptrxy
ptrxmin=xyTL(k,1);
ptrymin=xyTL(k,2);
assert(isequal(L(ptrxmin,ptrymin),k)) % Verify TL corner
if ptrxmin+presents(k,1)-1>1000 || ptrymin+presents(k,2)-1>1000
% BR Corner verify for rotated only fit case
assert(isequal(L(ptrxmin+presents(k,2)-1,ptrymin+presents(k,1)-1),k))
elseif ptrxmin+presents(k,2)-1>1000 || ptrymin+presents(k,1)-1>1000
% BR corner verify for non-rotated only fit case
assert(isequal(L(ptrxmin+presents(k,1)-1,ptrymin+presents(k,2)-1),k))
else % rot or non-rot case
v1=L(ptrxmin+presents(k,2)-1,ptrymin+presents(k,1)-1)==k;
v2=L(ptrxmin+presents(k,1)-1,ptrymin+presents(k,2)-1)==k;
assert(v1 || v2); % simple corner check
end
% More robust checks may be implemented if needed
end
A=Santa_L1(:,1).*Santa_L1(:,2);
As=sum(A(1:ptrxy))
assignin('caller','score',min(100000,1000000-As));
As =
991003
|
3 | Pass |
%%
%{
function SantaPack_Cody
% www.kaggle.com Santa Packing Contest
% 11/2013 thru January 2014
% Given 1 Million Rectangularoid packages
% Fit Packages into a Minimum Heigth Box with a base of 1000 x 1000
% Rules allow presents out of order but this is virtually non-optimiziable
% Presents out of order incur a penalty
% Packing Construction Here:
% All boxes dimension sorted [Mid, Min, Max]
% Boxes 1:236 all have their tops on the same plane (97.5719% efficient pack)
% Boxes 237:423 have their tops 250 lower in Z. Max Z of 1:236 is 250.
% The very bottom layer, with box 1000000 has bottom box at Z=1
% Note: Max dimension after box 700,000 is 70
% This construction has min cross area per present, max dimension is placed on Z
% Input is presents that have cumulative area <= 1000000
% The optimal score with perfect layer packing is
% Layers 4098 zsum 996483 Score 1,992,966
% Layers 4210, Score of 2,047,696 is possible with sequence layer packing
% Kaggle Lead as of 12/21/2013 is 1,999,256. Unknown method.
% Pack routine returns a 1000x1000 array with values 1:n, n<=N
% N is the Nth box that fits in the 1,000,000 area limit
% Next call uses n+1:N
load presents % available at kaggle site as a Mat file
numPresents = size(presents,1);
presents(:,2:4)=sort(presents(:,2:4),2);
presents(:,2:3)=fliplr(sort(presents(:,2:3),2)); % x>y, z>x
presents=[presents presents(:,2).*presents(:,3)]; % Area of box tops
presents=[presents cumsum(presents(:,end))]; % [presID x y z A Asum]
pe=0;
Layer=0;
zsum=0;
z=-1;
presentCoords=zeros(1000000,25);
tic
while pe<1000000
ps=pe+1;
Asum=presents(ps:min(ps+5000,1000000),end); % valid for layer 1
if pe>0, Asum=Asum-presents(pe,end); end% remove prior layers sum
ptr1M=find(Asum<=1000000,1,'last');
pe=ps+ptr1M-1;
[L,xyTL]=SantaPack(presents(ps:pe,2:3)); % L has values 1 thru n, being ps thru ps+n-1
% xyTL is Top Left position of pieces 1:n
%figure(3);imagesc(L);
pe=ps-1+find(xyTL(:,1)>0,1,'last'); % find number of boxes placed
zmax=max(presents(ps:pe,4));
% Convert Layers to coordinates
% Locate pieces in Layer and assign coordinate values
% z axis values fixed in post processing to positives
% Valid placement and sizes assumed
for k=1:pe-ps+1
idx=k+ps-1;
ptrxmin=xyTL(k,1);
ptrymin=xyTL(k,2);
if ptrxmin+presents(idx,2)-1<=1000 && ptrymin+presents(idx,3)-1<=1000
if L(ptrxmin+presents(idx,2)-1,ptrymin+presents(idx,3)-1)==k
ptrxmax=ptrxmin+presents(idx,2)-1;
ptrymax=ptrymin+presents(idx,3)-1;
else
ptrxmax=ptrxmin+presents(idx,3)-1;
ptrymax=ptrymin+presents(idx,2)-1;
end
else % assumed placement if xmax(1)>1000
ptrxmax=ptrxmin+presents(idx,3)-1;
ptrymax=ptrymin+presents(idx,2)-1;
end % if
% place this section inside SantaPack and output presentCoords vs L
presentCoords(idx,1) = idx;
presentCoords(idx,[2 8 14 20]) = ptrxmin;
presentCoords(idx,[5 11 17 23]) = ptrxmax;
presentCoords(idx,[3 6 15 18]) = ptrymin;
presentCoords(idx,[9 12 21 24]) = ptrymax;
presentCoords(idx,[4 7 10 13]) = z;
presentCoords(idx,[16 19 22 25]) = z - presents(idx,4) + 1;
end % k
z=z-zmax;
Layer=Layer+1;
zsum=zsum+zmax;
fprintf('Layer %i Start %i Final %i Zsum %i Time %.2f\n',Layer,ps,pe,zsum,toc) % Processing Status
% Deep routine to 2M takes 30 minutes
% Fast Placement takes 187 sec
end % pe
% Offset Z coordinates
% Bottom is 1 and very top is Positive
zCoords = presentCoords(:,4:3:end);
minZ = min(zCoords(:));
presentCoords(:,4:3:end) = zCoords - minZ + 1;
% Scoring function
% Ideal order is the original order
presentIDs = presents(:,1); %z
idealOrder = presentIDs;
% Determine the max z-coordinate; this is the max height of the box
maxZ = max(max(presentCoords(:,4:3:end)));
% Go down the layers from top to bottom, reorder presents in numeric order
% for each layer
maxZCoord = zeros(numPresents,2);
for i = 1:numPresents
maxZCoord(i,1) = presentCoords(i);
maxZCoord(i,2) = max(presentCoords(i,4:3:end));
end
maxzCoordSorted = sortrows(maxZCoord,[-2 1]); %sort max z-coord for each present
reOrder = maxzCoordSorted(:,1);
% Compare the new order to the ideal order
order = sum(abs(idealOrder - reOrder));
% Compute metric
fprintf('Metric %i MaxZ %i Order Penalty %i\n',2*maxZ + order,maxZ,order);
% Creating a Submission File
subfile = 'submissionfile_SantaPack_Cody.csv';
fileID = fopen(subfile, 'w');
headers = {'PresentId','x1','y1','z1','x2','y2','z2','x3','y3','z3','x4','y4','z4','x5','y5','z5','x6','y6','z6','x7','y7','z7','x8','y8','z8'};
fprintf(fileID,'%s,',headers{1,1:end-1});
fprintf(fileID,'%s\n',headers{1,end});
fprintf(fileID,'%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n',presentCoords');
fclose(fileID);
end % SantaPack_Cody
function [L,xyTL]=SantaPack(p)
% p is an Nx2
% xyTL is Top Left position of pieces 1:n
% Place 1:n of p onto L, a 1000x1000 array
% Put p row onto L array. [2 3] may be placed [1 1 1;1 1 1] or [1 1; 1 1;1 1] for box 1
% Note: big boxes typically pack to 95% and small boxes to >98%
L=zeros(1000);
xyTL=p*0;
% L(1:p(1,1),1:p(1,2))=1; % putting one piece per layer
% return
% Placing first 16 pieces
% No piece exceeds 250x250
pxy=[1 251 501 751];
piece=1;
for i=1:4
for j=1:4
L(pxy(i):pxy(i)+p(piece,1)-1,pxy(j):pxy(j)+p(piece,2)-1)=piece; % putting piece on layer
xyTL(piece,:)=[pxy(i) pxy(j)]; % Location of piece
piece=piece+1;
end
end
%figure(3);imagesc(L)
end % SantaPack
%}
|
Find state names that start with the letter N
465 Solvers
50 Solvers
77 Solvers
77 Solvers
Determine Whether an array is empty
561 Solvers