Winner the cyclist (typ2)

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

Chuck Norris 2

by Hannes Naud

Status: Passed
Results: 84020
CPU Time: 65.8595
Score: 843.961
Submitted at: 2006-04-12 16:55:11 UTC
Scored at: 2006-04-13 00:15:19 UTC

Current Rank: 13th
Based on: Chuck Norris (diff)
Basis for: Chuck Norris 3 (diff)

Comments
Please login or create a profile.
Code
function m=solver(tb,nM)

[m,b]=solveri(tb,nM,1);
sthis=sum(sum(b));
if (sthis > 1000)
    [m2,b]=solveri(tb,nM,0);
    sthis2=sum(sum(b));
    if sthis2<sthis
        m=m2;
    end
end;

function [moves,board] =solveri(tboard,nMoves,z)

board=zeros(size(tboard,1)+1,size(tboard,2)+2);
board(2:end,2:end-1)=tboard;
[rows, cols] = size(board);
moves = ones(nMoves,3);
count=0;

zz=zeros(1,floor(((rows-1)*(cols-2))/2));
i=1;
for r=rows:-1:2
 for cl=cols-2:-1:1
     if mod(r+cl,2)
         zz(i)=(cl*rows)+r;
         i=i+1;
     end
 end
end

celbuf=zeros(1,900);
valbuf=zeros(1,900);
ibuf=zeros(1,400);
new_mask_l=zeros(numel(board),1);

% set move calculation parameters
if (rows*cols) > 10.5*nMoves
    next_move_count = 40;
    choke_factor = .817;
    depth_factor = 2.93;
    rot          = 1.566;
elseif (rows*cols) > 8.5*nMoves
    next_move_count = 29;
    choke_factor = .817;
    depth_factor = 2.93;
    rot          = 1.566;
elseif rows*cols >= 256
    next_move_count = 26;
    choke_factor = .951;
    depth_factor = 2.8;
    rot = 1.4;
else
    next_move_count = 26;
    choke_factor = 0.945;
    depth_factor = 2.97;
    rot          = 1.46;
end
choke_factor=choke_factor*z;
% adjust block weights
board = nthroot(board,rot);

depth = ceil(depth_factor*nMoves/10);
flip = floor(0.66*nMoves);
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(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),ceil(max_cell/rows)-1,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)


function [new_cell_list,new_value_list,new_mask] = CalculateMoves(board);
    [rows,cols]=size(board);
%     N=true(rows,cols);
%     areal=rows*cols;
%     new_mask_l=zeros(numel(board),1);
    group_index=0;    
%     tscore=0;
    ii=0;
    prev=0;
    readpoint=0;
    writepoint=0;
    c=0;
%     for r=rows:-1:rw
%         for cl=cols-2:-1:1
%             i=(cl*rows)+r;
        for zi=1:numel(zz)
%         if N(i)
        i=zz(zi);
        c=board(i);
        if c && (board(i+1)==c || board(i+rows)==c || board(i-1)==c || board(i-rows)==c)
                group_index=group_index+1;
%                 tscore=row_offset(i);
                ibuf(1)=i;
                board(i)=0;
                prev=i;
                readpoint=0;
                writepoint=1;
                while (writepoint-readpoint)
                    readpoint=readpoint+1;
                    ii=ibuf(readpoint);
%                     if N(ii)
%                         N(ii)=false;
%                         tscore=tscore+c;
                        new_mask_l(ii)=prev;
%                         celbuf(group_index)=ii;
                        prev=ii;
                        if board(ii+1)==c
                            writepoint=writepoint+1;
                            ibuf(writepoint)=ii+1;
                            board(ii+1)=0;
                        end
                        if board(ii-1)==c
                            writepoint=writepoint+1;
                            ibuf(writepoint)=ii-1;
                            board(ii-1)=0;
                        end
                        if board(ii+rows)==c
                            writepoint=writepoint+1;
                            ibuf(writepoint)=ii+rows;
                            board(ii+rows)=0;
                        end
                        if board(ii-rows)==c
                            writepoint=writepoint+1;
                            ibuf(writepoint)=ii-rows;
                            board(ii-rows)=0;
                        end
%                     end
                end
%                 valbuf(group_index)=tscore;
                valbuf(group_index)=c*readpoint;%+row_offset(i);
                celbuf(group_index)=ii;
            end
%         end
    end
    new_cell_list=celbuf(1:group_index);
    new_value_list=valbuf(1:group_index);
    new_mask=new_mask_l;
end

function B=ProcessMove(B,dj,y)
% R=size(B,1);
B(y)=0;
col=ceil(y/rows);
minCol=col;maxCol=col;
while dj(y)~=y
    y=dj(y);
    B(y)=0;
    col=ceil(y/rows);
    minCol=min(minCol, col);
    maxCol=max(maxCol, col);
end;
for ip=minCol:maxCol,
    kp=B(B(:,ip)>0,ip);
    B(:,ip)=0;B(rows-numel(kp)+1:rows,ip)=kp;
end
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 kc=1:nList
    jj=list(kc);
    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(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,kc-20):min(nList,kc+20)
                    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(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),ceil(idxq/rows)-1,idxr];
    outboard=DoSwap(board,idxq,idxs);
end
end

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