Winner the cyclist (typ2)

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

small jump on top!

by David

Status: Passed
Results: 86392
CPU Time: 65.6037
Score: 867.563
Submitted at: 2006-04-11 22:10:38 UTC
Scored at: 2006-04-11 22:34:33 UTC

Current Rank: 1134th

Comments
David
11 Apr 2006
I have been getting little nibbling jumps here and there, with 2 big ones, but Markus got the biggest of all leaps today! Congrats Markus!
Please login or create a profile.
Code
function moves=solver(board,nMoves)
[rows, cols] = size(board);
moves = ones(nMoves,3);
count=0;

% set move calculation parameters
next_move_count = 26;
if rows*cols >= 258
    choke_factor = .951;
    depth_factor = 2.8;
    rot          = 1.4;
elseif (rows*cols) > 8.5*nMoves
    choke_factor = 0.94;
    depth_factor = 3.1;
    rot          = 1.49;
else
    choke_factor = .945;
    depth_factor = 2.97;
    rot          = 1.46;
end

% adjust block weights
board = nthroot(board,rot);

depth = ceil(depth_factor*nMoves/10);
flip = floor(0.56*nMoves);
while 1
    % restore original colour values half-way through game
    if count==flip, board = board .^ ((0.25+rot)/1.25); end
    
    % find highest value moves
    [cell_list,value_list,mask] = CalculateMoves(board);
    if isempty(cell_list),
        [swapmv,board]=CheckForSwap(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));
            [new_cell_list,new_value_list] = CalculateMoves(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); %#ok
    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);

    if (count==nMoves)
        break;
    end
end
moves = moves(1:count,:);

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

[rows,cols] = size(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
    if board(1)
        mask(1)=1;
    end
    k=1;
    for j=2:cols
        m = k;
        k = k + rows;
        if board(k)
            mask(k) = k;
            if (board(m) == board(k))
                % block to left matches current
                mask(m) = k;
            end
        end
    end
end

% Start at first row (or second if first is top and loop to bottom)
for i = max(2,first_row):rows
    k=i;
    if (board(k))
        % first block in row is non-zero
        mask(k) = k;
        m = k-1;
        if (board(m) == board(k))
            % 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
        if (board(k))
            mask(k) = k;
            if (board(m)==board(k))
                % block to left matches current
                mask(m) = k;
            end
            m = k - 1;
            if (board(m)==board(k))
                % block above matches current
                n = -1;
                while (n ~= m)
                    n = m;
                    m = mask(n);
                    mask(n) = k;
                end
            end
        end
    end
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=cols:-1:1
        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
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

function B=ProcessMove(B,dj,y)
R=size(B,1);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);
end;
for i=minCol:maxCol,
    k=B(B(:,i)>0,i);
    B(:,i)=0;B(R-numel(k)+1:R,i)=k;
end

function [swapmv,outboard]=CheckForSwap(board)
[rows cols]=size(board);
swapper=[-1 rows 1 -rows];
lentmp=rows*cols;
swapmv=zeros(1,3);
outboard=board;
maxswap=0;
list=find(board~=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)
            % djones (inline) tboard=DoSwap(board,jj,np);
            tboard=board;tboard([jj,np])=tboard([np,jj]);
            [s_ceil,s_value]=CalculateMoves(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-20):min(nList,k+20)
                    jj2=list(k2);
                    for swapdir2=1:4
                        np2=jj2+swapper(swapdir2);
                        if np2>0 && np2<=lentmp && tboard(np2)>0 && tboard(np2)~=tboard(jj2)
                            % djones (inline) tboard2=DoSwap(tboard,jj2,np2);
                            tboard2=board;tboard2([jj,np])=tboard2([np,jj]);
                            [s_ceil2,s_value2,s_mask2]=CalculateMoves(tboard2);
                            if (~isempty(s_value2) && max(s_value2)>maxswap)
                                isok=false;
                                [s_max,s_idx]=max(s_value2);
                                Y=s_ceil2(s_idx);
                                while (s_mask2(Y)~=Y)
                                    Y = s_mask2(Y);
                                    if (Y==np || Y==jj)
                                        isok=true;
                                    end
                                end
                                if (Y==np || Y==jj)
                                    isok=true;
                                end
                                if (isok)
                                    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];
    % djones (inline) outboard=DoSwap(board,idxq,idxs);
    outboard=board;outboard([idxq,idxs])=outboard([idxs,idxq]);
end

% function board = DoSwap(board,el1,el2)
% board([el1,el2]) = board([el2,el1]);