Winner the cyclist (typ2)

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

silent lucidity #3

by Rajiv Narayan

Status: Failed
Results:

Comments
Rajiv Narayan
12 Apr 2006
bug fixes
Please login or create a profile.
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));