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));
|
