Winner Yi Cao (Buy a ticket)

2007-05-16 12:00:00 UTC

# Messy-7

by DrSeuss

Status: Passed
Results: 39254.74 (cyc: 10)
CPU Time: 45.6614
Score: 3945.09
Submitted at: 2007-05-16 09:58:27 UTC
Scored at: 2007-05-16 10:02:53 UTC

Current Rank: 89th
Based on: Messy-4 (diff)
Basis for: Messy-8 (diff)
Basis for: Messy-9 (diff)

Code
```function [AA,AB] = solver(AD)
rand('state',0);
rand(7,1);
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);
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);
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)
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.4762];
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);
IT = nnz(IQ);
AA = zeros(IT,4);
IU = zeros(IT*4,1);
IV = IU;
IW = IU;
IX = IU;
IY = IU;
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( ...
ML, ...
MM, ...
EV,EZ,FB, ...
CK, ...
FX,GB,GD, ...
FJ,FK,FL)
MN = MM*rand(5000,1);
AA = zeros(CK-1,4);
MQ = zeros(CK-1,1);
MX = max(AD, 0);
MZ = (MV(EV) & MR(EZ) & MV(FB));
NA = find(MZ);
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(NE) = 0;
MX(NF) = 0;
MR(ND) = false;
MV(ND) = true;
MR(NE) = true;
MV(NE) = false;
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);
else
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);
end
AA(BN,:) = GD(HH,:);
ND = EZ(HH);
NE = EV(HH);
NF = FB(HH);
BN = BN+1;
MX(NE) = 0;
MX(NF) = 0;
MR(ND) = false;
MV(ND) = true;
MR(NE) = true;
MV(NE) = false;
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( ...
EV,EZ,FB, ...
CK, ...
FX,GB,GD,GH, ...
FJ,FK,FL)
AA = zeros(CK-1,4);
MQ = zeros(CK-1,1);
MX = max(AD, 0);
NX = (MV(EV) & MR(EZ) & MV(FB));
NA = find(NX);
[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);
MR(ND) = false;
MV(ND) = true;
MR(NE) = true;
MV(NE) = false;
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);
else
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;
BN=BN+1;
end
NF=FB(HH);
MR(ND) = false;
MV(ND) = true;
MR(NE) = true;
MV(NE) = false;
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```