Winner Yi Cao (Buy a ticket)

Finish 2007-05-16 12:00:00 UTC

Messy-8

by DrSeuss

Status: Passed
Results: 39250.19 (cyc: 10)
CPU Time: 45.826
Score: 3944.79
Submitted at: 2007-05-16 10:07:34 UTC
Scored at: 2007-05-16 10:09:39 UTC

Current Rank: 74th
Based on: Messy-7 (diff)

Comments
Please login or create a profile.
Code
function [AA,AB] = solver(AD)
rand('state',0);
rand(7,1);
[AL,n] = size(AD); 
CK = sum(AD(:)>0); 
rows = AL+4; 
CP = 5:rows; 
cols = n+4; 
cv = 5:cols; 
fill = (CK-nnz(AD<0)) / (AL*n);
i = repmat(CP',[n 1]); 
j = reshape(repmat(cv,[AL 1]),[AL*n 1]); 
DK = AL+8; 
DL = n+8;  
DM = -ones(DK, DL); 
DM(CP,cv) = AD; 
AK = [i;i;i;i];  
DW = [j;j;j;j]; 
DX = [i;i;i-2;i+2]; 
EA = [j-2;j+2;j;j]; 
EF = [i;i;i-4;i+4]; 
EG = [j-4;j+4;j;j]; 
EM = [i-2;i+2;i-2;i+2]; 
EP = [j-2;j+2;j+2;j-2];  
ES = [i+2;i-2;i-2;i+2]; 
ET = [j-2;j+2;j-2;j+2]; 
EV = AK+(DW-1)*DK; 
EZ = DX+(EA-1)*DK; 
FB = (EV+EZ)*0.5; 
FI = (DM(EV) < 0) | (DM(FB) < 0) | (DM(EZ) < 0);
AK(FI) = [];
DW(FI) = [];
DX(FI) = [];
EA(FI) = [];
EV(FI) = [];
EZ(FI) = [];
FB(FI) = [];
EF(FI) = [];
EM(FI) = [];
ES(FI) = [];
EG(FI) = [];
EP(FI) = [];
ET(FI) = [];
[FJ,FK,FL] = FM(FB,EV,EZ);
FU = EF+(EG-1)*DK; 
FV = EM+(EP-1)*DK; 
FW = ES+(ET-1)*DK; 
FX = [FU FV FW];
FY = (EZ+FU)*0.5; 
FZ = (EZ+FV)*0.5; 
GA = (EZ+FW)*0.5; 
GB = [FY FZ GA];
GD = [AK DW DX EA];
GE = [DX EA EF EG];
GF = [DX EA EM EP];
GG = [DX EA ES ET];
GH = {GE, GF, GG};
[AA,AB] = GJ( ...
DM, ...
EV,EZ,FB, ...
CK, ...
FX,GB,GD,GH, ...
FJ,FK,FL);
GK = sum(AD(AD>0));
GL = 0.81*GK;
for GQ = GR(CK)
if (size(AA,1) <= 3) || (AB > GL)
AA = AA - 4;
return
end
[HC,HD] = HE( ...
DM, ...
GQ,0, ...
EV,EZ,FB, ...
CK,  ...
FX,GB,GD, ...
FJ,FK,FL);
if (HD > AB)
AB = HD;
AA = HC;
end
end
HH = 1;
while HH <=(min((CK*0.0078125)+1,3)*(AB < GK*0.79))
[HC,HD] = HE( ...
DM, ...
1.0,1.16, ...
EV,EZ,FB, ...
CK, ...
FX,GB,GD, ...
FJ,FK,FL);
if (HD > AB)
AB = HD;
AA = HC;
end
HH = HH+1;
end
AA = AA - 4;
if (CK < 272) && (fill < .96)*(AB < GK*0.775)
[HC,HD] = HJ(AD,rows,cols);
if (HD > AB)
AB = HD;
AA = HC;
end
end
end   
function HK = GR(CK)
HM = 2*(rand(4,1)-0.5);
switch ceil(CK/102.5)
case 1
HK = [1+0.1*HM(1) 0.05];
case 2
HK = [6.8 5 2.1 1+0.1*HM(2) 0.6+0.1*HM(2) 0.45];
rand(750,1);
case 3
HK = [0.05 2.1 1+0.1*HM(3) 0.6+0.1*HM(3) 0.4+0.1*HM(3) 0.254];
case 5
HK = [0.05 2.1 0.6+0.1*HM(4) 0.18];
otherwise
HK = [0.05 2.1 1+0.1*HM(4) 0.592];
end
end
function [FJ,FK,FL] = FM(FB,EV,EZ)
HR = max([max(FB) max(EV) max(EZ)]); 
HZ = zeros(HR,1);
IA = HZ;
IB = HZ;
FJ = zeros(HR,4);
FK = FJ;
FL = FJ;
for HH = 1:numel(EV) 
HZ(EV(HH)) = HZ(EV(HH))+1; 
FJ(EV(HH),HZ(EV(HH))) = HH; 
IA(FB(HH)) = IA(FB(HH))+1;
FK(FB(HH),IA(FB(HH))) = HH;
IB(EZ(HH)) = IB(EZ(HH))+1;
FL(EZ(HH),IB(EZ(HH))) = HH;
end
end
function [AA,IP] = HJ(AD,rows,cols)
IQ = -ones(rows,cols);
IQ(3:end-2,3:end-2) = AD;
IT = nnz(IQ);
AA = zeros(IT,4);
IU = zeros(IT*4,1);
IV = IU;
IW = IU;
IX = IU;
IY = IU;
JB = 0.1 * mean(AD(AD>0));
JC = 0;
JD = 0;
AB = 0;
JE = 0;
IP = 0;
depth = 10;
JF = 0;
JG = 0;
[JH,JI,JJ] = JK(IQ);
while true
if isempty(JH)
break
end
JQ(IQ,JH,JJ,JI);
if (JF ~= 0) && (JG > 2)
for JS = 1:JG-1
JH = [JH;IY(JS)]; 
JJ = [JJ;IY(JS+1)];  
JI = [JI;JF]; 
DoMove(numel(JH)); 
end
else
[JW,JX] = sort(JI,'descend'); 
JI = JW; 
JH = JH(JX); 
JJ = JJ(JX); 
for JS = 1:min(depth,numel(JH))
[KD,newC,KE,KF] = ...
KG(IQ,JS,JH,JJ,JI);
JQ(KD,newC,KE,KF); 
JW(JS) = JW(JS) + JF; 
end
[KH,JX] = max(JW); 
DoMove(JX) 
end
end
AA(JE+1:end,:) = [];
function DoMove(JX)
KK = JH(JX); 
KM = JJ(JX); 
JC = JC+1; 
AA(JC,:) = [mod(KK-2,rows),ceil(KK/rows)-2,mod(KM-2,rows),ceil(KM/rows)-2]; 
KO = (KK+KM)/2; 
AB = AB + IQ(KO); 
if (KK ~= JD) 
AB = AB - IQ(KK); 
end
if (AB > IP) 
JE = JC; 
IP = AB; 
end;
[IQ,JH,JJ,JI] = KG(IQ,JX,JH,JJ,JI); 
JD = KM; 
end
function JQ(IQ,JH,JJ,JI)
JF = 0;
if ~isempty(JH)
KV=JJ(1:numel(JH));
KW=(~IQ(KV+2)&IQ(KV+1));
KW=(~IQ(KV-2)&IQ(KV-1))|KW;
KW=(~IQ(KV-2*rows)&IQ(KV-rows))|KW;
KW=(~IQ(KV+2*rows)&IQ(KV+rows))|KW;
KX=find(~KW);
if ~isempty(KX)
KY=JI(KX); [JF,KY]=max(KY); KY=KX(KY);
JG=2; IY(1)=JH(KY); IY(2)=JJ(KY);
end;
KX=find(KW)';
for KZ=KX
IX(1)=JH(KZ);
LA(IQ,JH(KZ),JJ(KZ),JI(KZ),2);
end;
end;
end
function LA(IQ,LB,KV,LC,JC)
IQ(KV) = IQ(LB);
IQ((LB+KV)/2) = 0;
IQ(LB) = 0;
IX(JC) = KV;
if ~IQ(KV+2) && IQ(KV+1)>0
LA(IQ,KV,KV+2,LC+IQ(KV+1),JC+1);
end
if ~IQ(KV-2) && IQ(KV-1)>0
LA(IQ,KV,KV-2,LC+IQ(KV-1),JC+1);
end
if ~IQ(KV+2*rows) && IQ(KV+rows)>0
LA(IQ,KV,KV+2*rows,LC+IQ(KV+rows),JC+1);
end
if ~IQ(KV-2*rows) && IQ(KV-rows)>0
LA(IQ,KV,KV-2*rows,LC+IQ(KV-rows),JC+1);
end
if LC > JF
JF = LC;
JG = JC;
IY(1:JC) = IX(1:JC);
end
end
function n = LE(IQ,LB,KV,n)
LF = IQ((LB+KV)*0.5); 
if LF>0 && ~IQ(KV) && IQ(LB)>0 
n = n+1; 
if sum(IQ([KV+1 KV-1 KV+rows KV-rows])>0) == 1 
IV(n) = LF-IQ(LB)-JB; 
else
IV(n) = LF-IQ(LB); 
end
IU(n) = LB; 
IW(n) = KV;
end
end
function n = LL(IQ,KV,LB,n)
LM = (LB+KV)/2; 
if IQ(LM)>0 && IQ(LB)>0 
n = n+1; 
if sum(IQ([KV+1 KV-1 KV+rows KV-rows])>0) == 1 
IV(n) = IQ(LM)-IQ(LB)-JB; 
else
IV(n) = IQ(LM)-IQ(LB); 
end
IU(n) = LB; 
IW(n) = KV;
end
end
function [LO,LP,LQ] = JK(IQ)
LR = find(IQ>0); 
LS = find(~IQ); 
n = 0;
if numel(LS)<numel(LR) 
for LU = 1:numel(LS) 
i = LS(LU);
n = LL(IQ,i,i-2,n);
n = LL(IQ,i,i+2,n);
n = LL(IQ,i,i-rows*2,n);
n = LL(IQ,i,i+rows*2,n);
end
else
for LU = 1:numel(LR) 
i = LR(LU);
n = LE(IQ,i,i-2,n);
n = LE(IQ,i,i+2,n);
n = LE(IQ,i,i-rows*2,n);
n = LE(IQ,i,i+rows*2,n);
end
end
LO = IU(1:n);
LP = IV(1:n);
LQ = IW(1:n);
end
function [IQ,JH,JJ,JI] = KG(IQ,JX,JH,JJ,JI)
LB = JH(JX); 
KV = JJ(JX); 
LM = (LB+KV)/2; 
IQ(KV) = IQ(LB); 
IQ(LM) = 0; 
IQ(LB) = 0; 
MA = LB-LM;
if (abs(MA) == 1)
MB = rows;
else
MB = 1;
end
JJ(logical(JJ == KV)) = 0;
JJ(logical(JH == LB)) = 0;
JJ(logical(JH == LM)) = 0;
MD = find(JH == LB-MB);
JJ(MD(JJ(MD) == LB+MB)) = 0;
MD = find(JH == LB+MB);
JJ(MD(JJ(MD) == LB-MB)) = 0;
MD = find(JH == LB-MB-MA);
JJ(MD(JJ(MD) == LB+MB-MA)) = 0;
MD = find(JH == LB+MB-MA);
JJ(MD(JJ(MD) == LB-MB-MA)) = 0;
[JJ,MF] = sort(JJ,'descend');
JH = JH(MF);
JI = JI(MF);
MG = find(~JJ,1,'first');
JH = JH(1:MG-1);
JI = JI(1:MG-1);
JJ = JJ(1:MG-1);
n = 0;
n = LE(IQ,LB-3*MA,LB-MA,n);
n = LE(IQ,LB+2*MB-MA,LB-MA,n);
n = LE(IQ,LB+2*MB,LB,n);
n = LE(IQ,LB+2*MA,LB,n);
n = LE(IQ,LB-2*MB,LB,n);
n = LE(IQ,LB-2*MB-MA,LB-MA,n);
n = LE(IQ,KV,KV-2*MA,n);
n = LE(IQ,KV,KV-2*MB,n);
n = LE(IQ,KV,KV+2*MB,n);
clf = LB-MB-2*MA;
MK = LB+MB-2*MA;
if ~IQ(clf)
n = LE(IQ,MK,clf,n);
end
if ~IQ(MK)
n = LE(IQ,clf,MK,n);
end
if (n > 0)
if (MG > 1)
JH = [JH; IU(1:n)];
JJ = [JJ; IW(1:n)];
JI = [JI; IV(1:n)];
else
JH = IU(1:n);
JI = IV(1:n);
JJ = IW(1:n);
end
end
end
end
function [AA,MB] = HE( ...
AD, ...
ML, ...
MM, ...
EV,EZ,FB, ...
CK, ...
FX,GB,GD, ...
FJ,FK,FL)
MN = MM*rand(5000,1); 
AA = zeros(CK-1,4); 
MQ = 0*[1:CK-1]'; 
MR = ~AD;  
MV = AD>0; 
MX = max(AD, 0); 
MZ = (MV(EV) & MR(EZ) & MV(FB));
NA = find(MZ);
NB = AD(FB(NA))-AD(EV(NA)); 
if ML
CV = max(MX(GB(NA,:)).*MR(FX(NA,:)),[],2); 
else
CV = 0;
end
[MB,HH] = max( (1+MN(1:length(NB))).*(NB+CV*ML) );
MQ(1) = NB(HH); 
HH = NA(HH);  
AA(1,:) = GD(HH,:); 
ND = EZ(HH); 
NE = EV(HH); 
NF = FB(HH); 
BN = 2; 
MX(ND) = AD(NE); 
MX(NE) = 0; 
MX(NF) = 0; 
AD(ND) = AD(NE); 
MR(ND) = false; 
MV(ND) = true; 
AD(NE) = 0; 
MR(NE) = true; 
MV(NE) = false; 
AD(NF)=0; 
MV(NF) = false;  
MR(NF) = true; 
NI=[NE NF ND];
NJ = FJ(NI,:);
NJ = NJ(NJ > 0);
NK = FK(NI,:);
NK = NK(NK > 0);
NL = FL(NI,:);
NL = NL(NL > 0);
NM = [NJ; NK; NL];
MZ(NM) = MV(EV(NM)) & MR(EZ(NM)) & MV(FB(NM));
NA = find(MZ);
while ~isempty(NA)
if (numel(NA) > 1)
NO = find(EV(NA) == ND); 
if ~isempty(NO) 
NA = NA(NO); 
NB = AD(FB(NA)); 
else
NB = AD(FB(NA))-AD(EV(NA)); 
end
if ML
CV = max(MX(GB(NA,:)).*MR(FX(NA,:)),[],2); 
else
CV = 0;
end
[MB,HH] = max( (1+MN(1:length(NB))).*(NB+CV*ML) );
MQ(BN) = NB(HH); 
HH = NA(HH);  
else
HH = NA(1); 
MQ(BN) = AD(FB(HH))-AD(EV(HH)); 
end
AA(BN,:) = GD(HH,:); 
ND = EZ(HH); 
NE = EV(HH); 
NF = FB(HH); 
BN = BN+1; 
MX(ND) = AD(NE); 
MX(NE) = 0; 
MX(NF) = 0; 
AD(ND) = AD(NE); 
MR(ND) = false; 
MV(ND) = true; 
AD(NE) = 0; 
MR(NE) = true; 
MV(NE) = false; 
AD(NF)=0; 
MV(NF) = false;  
MR(NF) = true; 
NI=[NE NF ND];
NJ = FJ(NI,:);
NJ = NJ(NJ > 0);
NK = FK(NI,:);
NK = NK(NK > 0);
NL = FL(NI,:);
NL = NL(NL > 0);
NM = [NJ; NK; NL];
MZ(NM) = MV(EV(NM)) & MR(EZ(NM)) & MV(FB(NM));
NA = find(MZ);
end
MQ = cumsum(MQ); 
[MB,BN] = max(MQ); 
AA = AA(1:BN,:); 
end
function [AA,MB] = GJ( ...
AD, ...
EV,EZ,FB, ...
CK, ...
FX,GB,GD,GH, ...
FJ,FK,FL)
AA = zeros(CK-1,4); 
MQ = zeros(CK-1,1); 
MR = ~AD;  
MV = AD>0; 
MX = max(AD, 0); 
NX = (MV(EV) & MR(EZ) & MV(FB)); 
NA = find(NX); 
NB = AD(FB(NA))-AD(EV(NA)); 
[CV,NY] = max(MX(GB(NA,:)).*MR(FX(NA,:)),[],2); 
[MB,HH] = max(NB+CV); 
MQ(1) = NB(HH); 
HH = NA(HH);  
AA(1,:) = GD(HH,:); 
NE = EV(HH); 
BN = 2; 
ND=EZ(HH); 
NI=[NE FB(HH) ND];
NF=FB(HH);
MX(ND)=AD(NE);MX(NE)=0;MX(NF)=0;
AD(ND) = AD(NE); 
MR(ND) = false; 
MV(ND) = true; 
AD(NE) = 0; 
MR(NE) = true; 
MV(NE) = false; 
AD(NF) = 0; 
MV(NF) = false; 
MR(NF) = true; 
NJ = FJ(NI,:);
NJ = NJ(NJ>0);  
NK = FK(NI,:);
NK = NK(NK>0);  
NL = FL(NI,:);
NL = NL(NL>0);  
NM = [NJ; NK; NL]; 
NX(NM) = MV(EV(NM)) & MR(EZ(NM)) & MV(FB(NM)); 
NA = find(NX);
while ~isempty(NA)
NO = find(EV(NA) == ND); 
if ~isempty(NO) 
NA = NA(NO); 
NB = AD(FB(NA)); 
else
NB = AD(FB(NA))-AD(EV(NA)); 
end
[CV,NY] = max(MX(GB(NA,:)).*MR(FX(NA,:)),[],2); 
[MB,HH] = max(NB+CV); 
MQ(BN) = NB(HH); 
cv=CV(HH);NY=NY(HH);
HH = NA(HH);  
AA(BN,:) = GD(HH,:); 
NE = EV(HH); 
BN = BN+1; 
if ~cv
ND=EZ(HH); 
NI=[NE FB(HH) ND];
else
ND=FX(HH,NY);
NF=GB(HH,NY);
AA(BN,:)=GH{NY}(HH,:);
NI=[NE FB(HH) NF ND];
MQ(BN)=cv;
AD(NF)=0;MR(NF)=true;MV(NF)=false;MX(NF)=0;
BN=BN+1;
end
NF=FB(HH);
MX(ND)=AD(NE);MX(NE)=0;MX(NF)=0;
AD(ND) = AD(NE); 
MR(ND) = false; 
MV(ND) = true; 
AD(NE) = 0; 
MR(NE) = true; 
MV(NE) = false; 
AD(NF) = 0; 
MV(NF) = false; 
MR(NF) = true; 
NJ = FJ(NI,:);
NJ = NJ(NJ>0);  
NK = FK(NI,:);
NK = NK(NK>0);  
NL = FL(NI,:);
NL = NL(NL>0);  
NM = [NJ; NK; NL]; 
NX(NM) = MV(EV(NM)) & MR(EZ(NM)) & MV(FB(NM)); 
NA = find(NX);
end
MQ = cumsum(MQ); 
[MB,BN] = max(MQ); 
AA = AA(1:BN,:); 
end