Winner the cyclist (typ2)

Finish 2006-04-12 09:00:00 UTC

take no prisoners

by David

Status: Passed
Results: 84358
CPU Time: 67.771
Score: 848.356
Submitted at: 2006-04-12 15:46:42 UTC
Scored at: 2006-04-12 17:49:56 UTC

Current Rank: 89th
Based on: take a chance #5 (diff)
Basis for: final try 1 (diff)

Comments
Please login or create a profile.
Code
function mv=solver(b,nmv)
[R, C]=size(b);
mv=ones(nmv,3);
count=0;
r=rand(4,1);
if (R*C) > 10.5*nmv
X=40;
choke_factor=.847;
depth_factor=2.93;
rot         =1.566;
elseif (R*C) > 8.5*nmv
X=29;
choke_factor=.847;
depth_factor=2.93;
rot         =1.566;
elseif R*C >= 256
X=26;
choke_factor=.951;
depth_factor=2.8;
rot=1.4; 
else
X=26;
choke_factor=0.945;
depth_factor=2.97;
rot         =1.46;
end
b=nthroot(b,rot);
depth=ceil(depth_factor*nmv/10);
flip=floor((0.66+(rand-0.5)*0.1)*nmv);
while 1
if count==flip, b=nthroot(b,2/(1+rot)); end
[Z,value_list,mask]=Calculatemv(R,C,b);
if isempty(Z),
[swapmv,b]=CheckForSwap(R,C,b);
if swapmv(1)
count=count+1;
mv(count,:)=swapmv;
if (count==nmv)
break;
end
continue
end
break
end
if count<nmv-1
[value_list,pos]=sort(value_list,2,'descend');
Z=Z(pos);
for k=1:min(numel(Z),X)
new_b=ProcessMove(b,mask,Z(k),R);
[new_Z,Q]=Calculatemv(R,C,new_b);

if (~isempty(new_Z))
depth_=max(min(depth,nmv-count-3),1);
if numel(Q)<=depth_
value_list(k)=value_list(k)+sum(Q);
else
Q=sort(Q,2,'descend');
value_list(k)=value_list(k)+sum(Q(1:depth_));
end
end
if (value_list(k) < choke_factor * value_list(1))
break;
end
end
end
[max_val,pos]=max(value_list);
max_cell=Z(pos);
count=count+1;
mv(count,:)=[mod(max_cell-1,R)+1,ceil(max_cell/R),0];
b=ProcessMove(b,mask,max_cell,R);
if (count==nmv)
break;
end
end
mv=mv(1:count,:);
function [Z,value_list,mask]=Calculatemv(R,C,b)
mask=zeros(R,C);
first_row=find(any(b,2),1);
if (first_row == 1)
bk=b(1);
if bk
mask(1)=1;
end
k=1;
for j=2:C
m=k;
k=k+R;
bm=bk;
bk=b(k);
if bk
mask(k)=k;
if (bm == bk)
mask(m)=k;
end
end
end
end
for i=max(2,first_row):R
k=i;
bk=b(k);
if (bk)
mask(k)=k;
m=k-1;
if (b(m) == bk)
n=-1;
while (n ~= m)
n=m;
m=mask(n);
mask(n)=k;
end
end
end
for j=2:C
k=k+R;
bm=bk;
bk=b(k);
if (bk)
mask(k)=k;
if (bm==bk)
mask(k-R)=k;
end
if (b(k-1)==bk)
n=-1;
m=k - 1;
while (n ~= m)
n=m;
m=mask(n);
mask(n)=k;
end
end
end
end
end
Z=zeros(1,256);
G=0;
G_matrix=zeros(R, C);
for i=R:-1:first_row
k=i+R*(C-1);
for j=1:C
if b(k)
m=mask(k);
if (m == k)
G_matrix(k)=1;
else
while G_matrix(m) == 0
m=mask(m);
end
mask(k)=mask(m);
group_block_count=G_matrix(m)+1;
G_matrix(m)=group_block_count;
if (group_block_count == 2)
G=G+1;
Z(1,G)=m;
end
mask(m)= k;
end
end
k=k - R;
end
end
Z=Z(1:G);
value_list=zeros(1,G);
for k=1:G
m=Z(k);
Z(k)=mask(m);
value_list(k)=G_matrix(m) * b(m);
mask(m)=m;
end
function B=ProcessMove(B,dj,cell,R)
y=cell;
B(y)=0;
col=ceil(y/R);
minCol=col;maxCol=col;
while dj(y)~=y
y=dj(y);
B(y)=0;
col=ceil(y/R);
minCol=min(minCol, col);
maxCol=max(maxCol, col);
end;
for i=minCol:maxCol,
k=B(B(:,i)>0,i);
B(:,i)=0;B(R-numel(k)+1:R,i)=k;
end
function [swapmv,outb]=CheckForSwap(R,C,b)
swapper=[-1 R 1 -R];
lentmp=R*C;
swapmv=zeros(1,3);
outb=b;
maxswap=0;
list=find(b~=0)';
nList=numel(list);
for k=1:nList
jj=list(k);
for swapdir=1:4
np=jj+swapper(swapdir);
if np>0 && np<=lentmp && b(np)>0 && b(np)~=b(jj)
tb=DoSwap(b,jj,np);
[s_ceil,s_value]=Calculatemv(R,C,tb);
if (~isempty(s_value))
if (max(s_value)> maxswap)
maxswap=max(s_value);
idxq=jj;idxr=swapdir;idxs=np;
end
else
for k2=max(1,k-10):min(nList,k+10)
jj2=list(k2);
for swapdir2=1:4
np2=jj2+swapper(swapdir2);
if np2>0 && np2<=lentmp && tb(np2)>0 && tb(np2)~=tb(jj2)
tb2=DoSwap(tb,jj2,np2);
[s_ceil2,s_value2,s_mask2]=Calculatemv(R,C,tb2);
if (~isempty(s_value2) && max(s_value2)>maxswap)
[s_max,s_idx]=max(s_value2);
Y=s_ceil2(s_idx);
while (s_mask2(Y)~=Y)
Y=s_mask2(Y);
end
if (Y==np || Y==jj)
maxswap=max(s_value2);
idxq=jj;idxr=swapdir;idxs=np;
end
end
end
end
end
end
end
end
end
if (maxswap>0)
swapmv=[mod(idxq-1,R)+1,ceil(idxq/R),idxr];
outb=DoSwap(b,idxq,idxs);
end
function b=DoSwap(b,e1,e2)
b([e1,e2])=b([e2,e1]);