Winner the cyclist (typ2)

2006-04-12 09:00:00 UTC

# SHsolver3

Status: Passed
Results: 127213
CPU Time: 13.1911
Score: 1272.14
Submitted at: 2006-04-07 05:33:22 UTC
Scored at: 2006-04-07 06:26:00 UTC

Current Rank: 4169th

Stijn Helsen
07 Apr 2006
Did I test this - it is an old piece of code
Code
```function moves = solver(board,nMoves)
%SOLVER Solve the Blockbuster Contest problem
%
% MOVES = SOLVER(BOARD,NMOVES) BlockBuster solver.
%
% MOVES -> [row,column,action]
% action -> 0 busts, 1 swap up, 2 swap right, 3 swap down, 4 swap left

[M,N]=size(board);
M2=M+2;
D=[-1 M2 1 M2];
Di=[3 4 1 2];
A=[zeros(1,N+2);zeros(M,1) board zeros(M,1);zeros(1,N+2)];
iEl=find(A);
b=unique(board(:));
nb=b;
for i=1:length(b)
nb(i)=sum(board(:)==b(i));
end
nb1=nb==1;
nb(nb1)=[];
if isempty(nb)
% probably not necessary
moves=zeros(0,3);
return
end
b(nb1)=[];
moves=zeros(nMoves,3);
iMoves=0;
bLoop=0;
nblok=zeros(1,max(nb));
iblok=nblok;
MN=numel(A);

if nMoves>2
single=A(iEl)~=A(iEl+1)&A(iEl)~=A(iEl-1)&A(iEl)~=A(iEl+M2)&A(iEl)~=A(iEl-M2);
mOK=zeros(MN,5);
m1OK=false;
for i=1:length(iEl)
if single(i)
mOK1=false;
l1=iEl(i);
mOK(l1,5)=-1;
a=A(l1);
if A(l1-1)
if A(l1-1-M2)==a|A(l1-1+M2)==a
mOK(l1,1)=1;
mOK1=true;
end
end
if A(l1+M2)
if A(l1-1+M2)==a|A(l1+1+M2)==a
mOK(l1,2)=1;
mOK1=true;
end
end
if A(l1+1)
if A(l1+1-M2)==a|A(l1+1+M2)==a
mOK(l1,3)=1;
mOK1=true;
end
end
if A(l1-M2)
if A(l1-1-M2)==a|A(l1+1+M2)==a
mOK(l1,4)=1;
mOK1=true;
end
end
if mOK1
m1OK=mOK1;
else
single(i)=false;
end
end
end
if m1OK
for i=1:length(iEl)
if single(i)
l1=iEl(i);
for j=1:4
if mOK(l1,j)
l2=l1+D(j);
if mOK(l2,5)
if mOK(l1,Di(j))
mOK(l1,j)=5;
else
mOK(l1,j)=2;	% ??
end
% else ...
end	% single l2
end % mOK
end % for j
end % if single
end % for
% ???hoe meerdere combineren
[mx,imx]=max(mOK(:));
iMoves=iMoves+1;
l1=rem(imx,MN);
c=floor(l1/M2);
d=ceil(imx/MN);
moves(iMoves,1)=l1-c*M2-1;
moves(iMoves,2)=c;
moves(iMoves,3)=d;
a=A(l1);
A(l1)=A(l1+D(d));
A(l1+D(d))=a;
end	% no useful single
end

while iMoves<nMoves
[mx,ib]=max(nb);
if mx<2
if bLoop
bLoop=0;
mx=0;
for i=1:length(b)
nb(i)=sum(board(:)==b(i));
if mx<nb(i)
mx=nb(i);
ib=i;
end
end
else
break
end
end
%i=find(nb==mx);
%ib=i(end);
%ib=i(ceil(rand(1)*length(i)));
b1=b(ib);
lijst=find(A==b1);
ibl=1;
nbl=0;
i0=1;
mx=1;
while i0<length(lijst)
[lijst,nI]=contblock(lijst,A,i0,M2);
nbl=nbl+1;
n1=nI-i0;
iblok(nbl)=i0;
nblok(nbl)=n1;
i0=nI;
if n1>mx
mx=n1;
i=nbl;
end
end

if mx>1
bLoop=1;
iMoves=iMoves+1;
i1=iblok(i);
i0=lijst(i1);
c=floor(i0/M2);
moves(iMoves,1)=i0-c*M2-1;
moves(iMoves,2)=c;
moves(iMoves,3)=0;
A=popblock(A,lijst(i1:i1+mx-1));
nb(ib)=nb(ib)-mx;
if nb(ib)<2
b(ib)=[];
nb(ib)=[];
end
else
nb(ib)=0;
end
end
moves = moves(1:iMoves,:);

function [lijst,n]=contblock(lijst,A,i0,M)
n=i0+1;
l1=lijst(i0);
a=A(l1);
A(l1)=0;
N=length(lijst);
while i0<n
if A(l1+1)==a
ii=ff(lijst,n,l1+1);
if ii>n
lijst(ii)=lijst(n);
lijst(n)=l1+1;
end
A(l1+1)=0;
n=n+1;
if n>N
break;
end
end
if A(l1-1)==a
ii=ff(lijst,n,l1-1);
if ii>n
lijst(ii)=lijst(n);
lijst(n)=l1-1;
end
A(l1-1)=0;
n=n+1;
if n>N
break;
end
end
if A(l1+M)==a
ii=ff(lijst,n,l1+M);
if ii>n
lijst(ii)=lijst(n);
lijst(n)=l1+M;
end
A(l1+M)=0;
n=n+1;
if n>N
break;
end
end
if A(l1-M)==a
ii=ff(lijst,n,l1-M);
if ii>n
lijst(ii)=lijst(n);
lijst(n)=l1-M;
end
A(l1-M)=0;
n=n+1;
if n>N
break;
end
end
i0=i0+1;
l1=lijst(i0);
end

function A=popblock(A,I)
A(I)=0;
N=size(A,1);
c=unique(ceil(I/N))';
jj=N-1:-1:2;
for ic=c
i=N;
for j=jj
if A(j,ic)
i=i-1;
A(i,ic)=A(j,ic);
end
end
while i>1
i=i-1;
A(i,ic)=0;
end
end

function i=ff(L,i,a)
while L(i)~=a
i=i+1;
end
```