assignin('caller','score',100000);

%% 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));

%% %{ 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 %}