Winner the cyclist (typ2)

2006-04-12 09:00:00 UTC

# silent lucidity #3

Status: Failed
Results:

Rajiv Narayan
12 Apr 2006
bug fixes
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

sz=size(board);

%main loop
moves = zeros(nMoves,3);

mctr=0;

isDone=0;

while (~isDone)

[ng,gm,gl,gs,gv,uc]=findgroups(board,sz);

bgidx=0;
bgwt=0;

if (ng)
[bgidx,bgwt]=findbestgroup(sz,ng,gl,gs,gv);
end

[bsmove,bswt] = findbestswap_largest(board,gm,gl,gs,gv,uc,bgidx);

ps=1/(mctr+1);
pp=5/(nMoves-mctr+1);

if ((bswt*ps > bgwt*pp) & mctr < nMoves-1)

mctr=mctr+1;
d=direc(sz,bsmove(1), bsmove(2));
[i,j]=ind2sub(sz,bsmove(1));
moves(mctr,:)=[i,j,d];
board = doswap(board,bsmove(1),bsmove(2));

elseif (bgwt)
mctr=mctr+1;
[i,j]=ind2sub(sz,gl{bgidx}(1));
moves(mctr,:)=[i,j,0];
board = dopop(board,gl{bgidx});
else
isDone=1;

end

if (mctr==nMoves) isDone=1;end

end

moves=moves(1:mctr,:);

% end main loop
%----------------

% -------------------------------------
function [gctr,gm,gl,gs,gv,uc] = findgroups(board,sz)

gm = zeros(sz);
gl = {};
gs=[];
gv=[];
uc=[];
allgps=[];

gctr = 0;
mctr = 0;

pboard = zeros(sz+1);
pboard(2:end,2:end) = board;

hd = diff(pboard(2:end,:),1,2);
[hi,hj] = find(hd==0);
if(~isempty(hi))
hidx = sub2ind(sz,hi,hj);
hidxn =  sub2ind(sz,hi,hj-1);
nh=length(hidx);
allgps=[hidx;hidxn];
end

vd = diff(pboard(:,2:end),1,1);
[vi,vj] = find(vd==0);
if (~isempty(vi))
vidx=sub2ind(sz,vi,vj);
vidxn=sub2ind(sz,vi-1,vj);
nv=length(vidx);
allgps=[allgps;vidx;vidxn];
end

if(~isempty(allgps))

[posgps,gpi,gpj] = unique(allgps);

nposgps = length(posgps);

[ai,aj]=ind2sub(sz,posgps);

for uu=1:nposgps

if (~gm(posgps(uu)))
gctr=gctr+1;
gm(posgps(uu))=gctr;
gv(gctr)=board(posgps(uu));
gl{gctr} = posgps(uu);

nb=neigh(sz,posgps(uu));
nb=nb(nb(:)~=0)';
vnb=nb(board(nb)==board(posgps(uu)))';

while ~isempty(vnb)

gm(vnb)=gctr;
gl{gctr}=union(gl{gctr},vnb);
nb=neigh(sz,vnb);
nb=setdiff(nb(:),[0,gl{gctr}]);
vnb=nb(board(nb)==board(posgps(uu)))';

end

end

end
for ii=1:gctr;gs(ii)=length(gl{ii});end

end

uc=setdiff(1:prod(sz),allgps);

%------------------------
function [bidx,bwt] = findbestgroup(sz,ng,gl,gs,gv)

wt=gs.*gv;
[bwt,bidx]=max(wt);

function [move,wt] = findbestswap_largest(board,gm,gl,gs,gv,uc,gpidx)

ng=length(gl);
sz=size(board);

%from to
move=[0 0];
wt=0;

if (~ng)
hf=1;
nb=swapneigh(sz,uc);
z=find(~nb);
nb(z)=1;
vals=board(nb);
vals(z)=0;

x=floor(rand(1)*length(uc)+1);
move = [uc(x) find(nb(x,:),1)];
for ii=1:length(uc)
matches = find(vals(ii,:)==board(uc(ii)));
if matches

l=length(matches);
r=mod(uc(ii),sz(1));
r(~r)=sz(1);
r=mean(r);
thisswap = board(uc(ii))*l + (hf*r);
if (thisswap > wt)
wt=thisswap;
n1=setdiff(neigh(sz,nb(ii,matches(1))),0);
n2=setdiff(neigh(sz,uc(ii)),0);
swap=intersect(n1,n2);
move=[uc(ii) swap];
end
end

end

else

for ii=gpidx

nb = neigh(sz,gl{ii});
nb=nb(find(nb(:)))';
vnb = nb(find(~gm(nb)));

nb2 = neigh(sz,vnb);
nb2=unique(nb2(find(nb2(:))));

ucs=nb2(find(~gm(nb2)));

vuc = ucs(find(board(ucs) == gv(ii)));
nvuc=length(vuc);

for jj=1:nvuc

swaps=intersect(neigh(sz,vuc(jj)),vnb);
nswaps = length(swaps);

for kk=1:nswaps

snb=neigh(sz,swaps(kk));
snb=setdiff(snb,[0,gl{ii},vuc(jj)]);

gain = board(vuc(jj))+gv(ii)*gs(ii);
for ll=1:length(snb);

if (gm(snb(ll)))
gain = gain + (gs(gm(snb(ll)))*gv(gm(snb(ll))));
elseif (board(snb(ll))==board(vuc(jj)))
gain = gain + board(vuc(jj));
end

end

if (gain > wt)
move = [vuc(jj) swaps(kk)];
wt = gain;
end

end

end

end
end

%-------------------------
function board = doswap(board,p1,p2)

t=board(p1);
board(p1)=board(p2);
board(p2)=t;

%-----------------------------
function board=dopop(board,gp)

sz=size(board);
N=false(sz);
N(gp)=1;
anych = any(N);
for j=1:sz(2)
if (anych(j))
tmp=board(~N(:,j),j);
board(:,j)=nan;
board(end-sum(~N(:,j))+1:end,j)=tmp;
end
end

% ------------------------------------
function nb = swapneigh(sz,linpos)

nel=length(linpos);
linpos=linpos(:);

nb=zeros(nel,1);

nb(:,1) = (linpos-2);
nb(:,1) = nb(:,1) * nb(:,1)>0;
nb(:,1) = nb(:,1) .* (mod(nb(:,1),sz(1))>0);
nb(:,2) = (linpos+2);
nb(:,2) = nb(:,2) .* (nb(:,2) <= (ceil(linpos/sz(1)) * sz(1)));

nb(:,3) = (linpos - (2*sz(1)));
nb(:,3) = nb(:,3) .* (nb(:,3)>0);

nb(:,4) = (linpos + (2*sz(1)));
nb(:,4) = nb(:,4) .* (nb(:,4)<=(sz(1)*sz(2)));

% ------------------------------------
function nb = neigh(sz,linpos)

nel=length(linpos);
linpos=linpos(:);

nb=zeros(nel,1);

nb(:,1) = (linpos-1);
nb(:,1) = nb(:,1) .* (mod(nb(:,1),sz(1))>0);

nb(:,2) = (linpos+1);
nb(:,2) = nb(:,2) .* (nb(:,2) <= (ceil(linpos/sz(1)) * sz(1)));

nb(:,3) = (linpos-sz(1));
nb(:,3) = nb(:,3) .* (nb(:,3)>0);

nb(:,4) = (linpos+sz(1));
nb(:,4) = nb(:,4) .* (nb(:,4)<=(sz(1)*sz(2)));

%---------------------------
function d = direc(sz,p1,p2)

m=[0,1,0;4,0,2;0,3,0];
[i1,j1]=ind2sub(sz,p1);
[i2,j2]=ind2sub(sz,p2);
d = m(2-(i1-i2),2-(j1-j2));
```