Winner the cyclist (typ2)

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

always pop 6.5d2

by Ragnar

Status: Passed
Results: 108611
CPU Time: 29.2619
Score: 1086.15
Submitted at: 2006-04-12 16:50:05 UTC
Scored at: 2006-04-12 23:20:43 UTC

Current Rank: 3844th
Based on: always pop 6.5d (diff)

Comments
Ragnar
12 Apr 2006
bug fix
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
%solverPopTheFat65d score: 114192, time:30.5

moves = [];
[NN, NS, NW] = initMaps(board);
for iMove=1:nMoves
    [thisMove, board, NN, NS, NW] = popFatNeighbour(board, NN, NS, NW); 
    moves = [moves; thisMove];
end
end %end of solver



%Init maps
%--------------------------------------------------------------------------
function [NN, NS, NW] = initMaps(board)
global N
[R, C] = size(board);
NN = zeros(R,C); %neighbour number
NS = zeros(R,C); %neighbour sizes
NW = zeros(R,C); %neighbour weight
check = ones(R,C);

%ignore zeros
NN(find(board==0)) = 0;
NS(find(board==0)) = 0;
NW(find(board==0)) = 0;
check(find(board==0)) = 0;

%ignore singles
% V 0 | 0 V | H | 0
%             0   H
V = board(:, 1:end-1) == board(:, 2:end);
H = board(1:end-1,:) == board(2:end,:);
singles = ~([V zeros(R,1)] | [zeros(R,1) V] | [H; zeros(1,C)] | [zeros(1,C); H]) & board>0;
check = check&~singles;
NN(find(singles)) = 0;
NS(find(singles)) = 1;
NW(find(singles)) = 0;

%size neighbours
nNeighbour = max(NN(:))+1;
while any(check(:))
    [I, J]=find(check);
    i = I(1); j=J(1);
    N = zeros(R,C);
    findNeighbors(i,j,board);%N passed global
    NN = NN.*~N + N*nNeighbour;
    NS = NS.*~N + N*sum(N(:));
    NW = NW.*~N + N*sum(N(:))*board(i,j);
    check = check&~N;
    nNeighbour = nNeighbour+1;
end
end %function initMap



%Pop fat neighbours
%--------------------------------------------------------------------------
function [moves, board, NN, NS, NW] = popFatNeighbour(board, NN, NS, NW)
global N

%Init
[R, C] = size(board);
moves = [];

%Pop the fat
[I, J]=find(NW == max(NW(:)));
i = I(1); j=J(1);
if NS(i,j)<2, return; end;%no more pops 
moves= [i j 0];

%update board
N = NN==NN(i,j);
anyN = any(N);
check=zeros(R,C);%
for k = 1:size(board,2)
    if anyN(k)
        tmp = board(~N(:,k),k);
        board(:,k) = 0;
        topRow = R-sum(~N(:,k))+1; 
        board(topRow:end,k) = tmp;
%        check(topRow:end,max(k-1,1):min(k+1,C))=1;
        bottomRow = min(max(find(N(:,k)))+1,R);
        check(1:bottomRow,max(k-1,1):min(k+1,C))=1;
    end
end

%update state

%ignore zeros
NN(find(board==0)) = 0;
NS(find(board==0)) = 0;
NW(find(board==0)) = 0;
check(find(board==0)) = 0;

%ignore singles
% V 0 | 0 V | H | 0
%             0   H
V = board(:, 1:end-1) == board(:, 2:end);
H = board(1:end-1,:) == board(2:end,:);
singles = ~([V zeros(R,1)] | [zeros(R,1) V] | [H; zeros(1,C)] | [zeros(1,C); H]) & board>0;
check = check&~singles;
NN(find(singles)) = 0;
NS(find(singles)) = 1;
NW(find(singles)) = 0;

%update reshaped area
nNeighbour = max(NN(:))+1;
while any(check(:))
    [I, J]=find(check);
    i = I(1); j=J(1);
    N = zeros(R,C);
    findNeighbors(i,j,board);%N passed global
    NN = NN.*~N + N*nNeighbour;
    NS = NS.*~N + N*sum(N(:));
    NW = NW.*~N + N*sum(N(:))*board(i,j);
    check = check&~N;
    nNeighbour = nNeighbour+1;
end

end %function



%--------------------------------------------------------------------------
function findNeighbors(i,j,A)
global N
c = A(i,j);
if ~N(i,j);
    N(i,j) = true;
    if i>1         && A(i-1,j)==c; findNeighbors(i-1,j,A); end
    if j<size(A,2) && A(i,j+1)==c; findNeighbors(i,j+1,A); end
    if i<size(A,1) && A(i+1,j)==c; findNeighbors(i+1,j,A); end
    if j>1         && A(i,j-1)==c; findNeighbors(i,j-1,A); end
end
end % end of findNeighbors (nested function)