Diffing "Survival of the Fittest !!!!" and "Survival of the Obfuscated !!"

Title: Survival of the Fittest !!!! Survival of the Obfuscated !!
Author: David David
Submitted: 2006-04-12 14:55:40 UTC 2006-04-12 15:56:27 UTC
Status: Passed Passed
Score: 847.508 847.496
Result: 84348 84348
CPU Time: 66.4078 66.384
Code:
function moves=solver(board,nMoves)
[rows, cols] = size(board);
moves = ones(nMoves,3);
count=0;
function mv=solver(B,nmv)
[R, C]=size(B);
mv=ones(nmv,3);
J=0;
r=rand(16,1);
% set move calculation parameters
if (rows*cols) > (10.5+(rand-0.5))*nMoves
    next_move_count = 40;
    choke_factor = .847;
    depth_factor = 2.93;
    rot          = 1.566;
elseif (rows*cols) > (8.5+(rand-0.5))*nMoves
    next_move_count = 29;
    choke_factor = .847;
    depth_factor = 2.93;
    rot          = 1.566;
elseif rows*cols >= 256 + round((rand-0.5)*10)
    next_move_count = 26;
    choke_factor = .951;
    depth_factor = 2.8;
    rot = 1.4; 
if (R*C)>(10.5+(rand-0.5))*nmv
next_move_J=40;
chokeF=.847;
depthF=2.93;
rot         =1.566;
elseif (R*C)>(8.5+(rand-0.5))*nmv
next_move_J=29;
chokeF=.847;
depthF=2.93;
rot         =1.566;
elseif R*C >= 256+round((rand-0.5)*10)
next_move_J=26;
chokeF=.951;
depthF=2.8;
rot=1.4; 
else
    next_move_count = 26;
    choke_factor = 0.945;
    depth_factor = 2.97;
    rot          = 1.46;
next_move_J=26;
chokeF=0.945;
depthF=2.97;
rot         =1.46;
end
% adjust block weights
board = nthroot(board,rot);

depth = ceil(depth_factor*nMoves/10);
flip = floor((0.66+(rand-0.5)*0.1)*nMoves);
B=nthroot(B,rot);
depth=ceil(depthF*nmv/10);
flip=floor((0.66+(rand-0.5)*0.1)*nmv);
while 1
    % restore original colour values half-way through game
    if count==flip, board = nthroot(board,2/(1+rot)); end
    
    % find highest value moves
    [cell_list,value_list,mask] = CalculateMoves(rows,cols,board);
    if isempty(cell_list),
        [swapmv,board]=CheckForSwap(rows,cols,board);
        if swapmv(1)
            count = count+1;
            moves(count,:) = swapmv;
            if (count==nMoves)
                break;
            end
            continue
        end
        break
    end

    % check future move values and re-weight current moves
    if count<nMoves-1
        [value_list,pos]=sort(value_list,2,'descend');
        cell_list=cell_list(pos);
        for k=1:min(numel(cell_list),next_move_count)
            new_board = ProcessMove(board,mask,cell_list(k),rows);
            [new_cell_list,new_value_list] = CalculateMoves(rows,cols,new_board);

            if (~isempty(new_cell_list))
                depth_ = max(min(depth,nMoves-count-3),1);
                if numel(new_value_list)<=depth_
                    value_list(k) = value_list(k) + sum(new_value_list);
                else
                    new_value_list=sort(new_value_list,2,'descend');
                    value_list(k) = value_list(k) + sum(new_value_list(1:depth_));
                end
            end
            if (value_list(k) < choke_factor * value_list(1))
                break;
            end
        end
    end

    % take new most-valuable move
    [max_val,pos] = max(value_list);
    max_cell = cell_list(pos);
    count = count+1;
    moves(count,:) = [mod(max_cell-1,rows)+1,ceil(max_cell/rows),0];
    board = ProcessMove(board,mask,max_cell,rows);

    if (count==nMoves)
        break;
    end
if J==flip, B=nthroot(B,2/(1+rot)); end
[P,Q,M]=Calculatemv(R,C,B);
if isempty(P),
[swapmv,B]=CheckForSwap(R,C,B);
if swapmv(1)
J=J+1;
mv(J,:)=swapmv;
if (J==nmv)
break;
end
moves = moves(1:count,:);

function [cell_list,value_list,mask] = CalculateMoves(rows,cols,board)

mask = zeros(rows,cols);

% find first row from top that has non-zeros
first_row = find(any(board,2),1);

if (first_row == 1)
  % first row is non-zero so build column weighted match value
  bk=board(1);
  if bk
    mask(1)=1;
  end
  k=1;
  for j=2:cols
    m = k;
    k = k + rows;
    bm=bk;
    bk=board(k);
    if bk
      mask(k) = k;
      if (bm == bk)
        % block to left matches current
        mask(m) = k;
      end
    end
  end
continue
end
% Start at first row (or second if first is top and loop to bottom)
for i = max(2,first_row):rows
  k=i;
  bk=board(k);
  if (bk)
    % first block in row is non-zero
    mask(k) = k;
    m = k-1;
    if (board(m) == bk)
      % block above matches current
      n = -1;
      while (n ~= m)
        n = m;
        m = mask(n);
        mask(n) = k;
      end
    end
  end

  % loop through columns and build column+row weighted match value
  for j=2:cols
%    m = k;
    k = k + rows;   % move over one column
    bm=bk;
    bk=board(k);
    if (bk)
      mask(k) = k;
      if (bm==bk)
        % block to left matches current
        mask(k-rows) = k;
      end
      if (board(k-1)==bk)
        % block above matches current
        n = -1;
      m = k - 1;
        while (n ~= m)
          n = m;
          m = mask(n);
          mask(n) = k;
        end
      end
    end
  end
break
end

cell_list = zeros(1,256);
group_count = 0;
group_count_matrix = zeros(rows, cols);
for i=rows:-1:first_row
  k = i + rows*(cols-1);
  for j=1:cols
    if board(k)
      m = mask(k);
      if (m == k)
        group_count_matrix(k) = 1;
      else
        while group_count_matrix(m) == 0
          m = mask(m);
        end
        mask(k) = mask(m);
        group_block_count = group_count_matrix(m) + 1;
        group_count_matrix(m) = group_block_count;
        if (group_block_count == 2)
          group_count = group_count + 1;
          cell_list(1,group_count) = m;
        end
        mask(m)= k;
      end
    end
    k = k - rows;
  end
if J<nmv-1
[Q,pos]=sort(Q,2,'descend');
P=P(pos);
for k=1:min(numel(P),next_move_J)
new_B=ProcessMove(B,M,P(k),R);
[new_P,new_Q]=Calculatemv(R,C,new_B);
if (~isempty(new_P))
D=max(min(depth,nmv-J-3),1);
if numel(new_Q)<=D
Q(k)=Q(k)+sum(new_Q);
else
new_Q=sort(new_Q,2,'descend');
Q(k)=Q(k)+sum(new_Q(1:D));
end

cell_list = cell_list(1:group_count);
value_list = zeros(1,group_count);

for k = 1:group_count
  m = cell_list(k);
  cell_list(k) = mask(m);
  value_list(k) = group_count_matrix(m) * board(m);
  mask(m) = m;
end
if (Q(k) < chokeF * Q(1))
break;
end
end
end
[max_val,pos]=max(Q);
max_cell=P(pos);
J=J+1;
mv(J,:)=[mod(max_cell-1,R)+1,ceil(max_cell/R),0];
B=ProcessMove(B,M,max_cell,R);
if (J==nmv)
break;
end
end
mv=mv(1:J,:);
function [P,Q,M]=Calculatemv(R,C,B)
M=zeros(R,C);
first_row=find(any(B,2),1);
if (first_row == 1)
bk=B(1);
if bk
M(1)=1;
end
k=1;
for j=2:C
m=k;
k=k+R;
bm=bk;
bk=B(k);
if bk
M(k)=k;
if (bm == bk)
M(m)=k;
end
end
end
end
for i=max(2,first_row):R
k=i;
bk=B(k);
if (bk)
M(k)=k;
m=k-1;
if (B(m) == bk)
n=-1;
while (n ~= m)
n=m;
m=M(n);
M(n)=k;
end
end
end
for j=2:C
k=k+R;
bm=bk;
bk=B(k);
if (bk)
M(k)=k;
if (bm==bk)
M(k-R)=k;
end
if (B(k-1)==bk)
n=-1;
m=k - 1;
while (n ~= m)
n=m;
m=M(n);
M(n)=k;
end
end
end
end
end
P=zeros(1,256);
group_J=0;
group_J_matrix=zeros(R, C);
for i=R:-1:first_row
k=i+R*(C-1);
for j=1:C
if B(k)
m=M(k);
if (m == k)
group_J_matrix(k)=1;
else
while group_J_matrix(m) == 0
m=M(m);
end
M(k)=M(m);
group_block_J=group_J_matrix(m)+1;
group_J_matrix(m)=group_block_J;
if (group_block_J == 2)
group_J=group_J+1;
P(1,group_J)=m;
end
M(m)= k;
end
end
k=k - R;
end
end
P=P(1:group_J);
Q=zeros(1,group_J);
for k=1:group_J
m=P(k);
P(k)=M(m);
Q(k)=group_J_matrix(m) * B(m);
M(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);
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;
k=B(B(:,i)>0,i);
B(:,i)=0;B(R-numel(k)+1:R,i)=k;
end
function [swapmv,outboard]=CheckForSwap(rows,cols,board)
swapper=[-1 rows 1 -rows];
lentmp=rows*cols;
function [swapmv,outB]=CheckForSwap(R,C,B)
swapper=[-1 R 1 -R];
lentmp=R*C;
swapmv=zeros(1,3);
outboard=board;
outB=B;
maxswap=0;
list=find(board~=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 && board(np)>0 && board(np)~=board(jj)
            tboard=DoSwap(board,jj,np);
            [s_ceil,s_value]=CalculateMoves(rows,cols,tboard);
            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 && tboard(np2)>0 && tboard(np2)~=tboard(jj2)
                            tboard2=DoSwap(tboard,jj2,np2);
                            [s_ceil2,s_value2,s_mask2]=CalculateMoves(rows,cols,tboard2);
                            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
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_M2]=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_M2(Y)~=Y)
Y=s_M2(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,rows)+1,ceil(idxq/rows),idxr];
    outboard=DoSwap(board,idxq,idxs);
swapmv=[mod(idxq-1,R)+1,ceil(idxq/R),idxr];
outB=DoSwap(B,idxq,idxs);
end
function board = DoSwap(board,el1,el2)
board([el1,el2]) = board([el2,el1]);
function B=DoSwap(B,el1,el2)
B([el1,el2])=B([el2,el1]);