Winner the cyclist (typ2)

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)

Ragnar
12 Apr 2006
bug fix
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)

```