Finish 2011-11-09 12:00:00 UTC

lasttry02

by Alfonso Nieto-Castanon

Status: Passed
Results: 64528599 (cyc: 29, node: 12067)
CPU Time: 61.278
Score: 645603.0
Submitted at: 2011-11-09 16:55:43 UTC
Scored at: 2011-11-09 18:19:01 UTC

Current Rank: 4th (Highest: 1st )

Comments
Please login or create a profile.
Code
function [moves, vine] = solver(board, limit)
% based on: rsk-red vs tm by amit rajora
% 
% alfnie
% testsuite: 56528916

scorevec = -inf(12,1);
limitlimit = 15100;
if limit < limitlimit
    [moves1, vine1, scorevec(1)] = alfi(board, limit);
end

largestValue = max(board(:));

if largestValue > 200
    if (limit > 0)
        [moves3, vine3, scorevec(3)] = robert(board, limit);
        [moves2,vine2,scorevec(2)] = robert(fliplr(board),limit); % monotonous should work good on flipping lr/ud as well
        [moves9,vine9,scorevec(9)] = dofilter(board,limit);
        if size(board,1)>2&&size(board,2)>2
            [vine10,moves10,board10,scorevec(10)] = spiral(board,limit,0);
%             [vine11,moves11,board11,scorevec(11)] = spiral(board,limit,0.3);
%             [vine12,moves12,board12,scorevec(12)] = spiral(board,limit,0.5);
        end
    end
    
    doclusters=any(any(board(:,2:end)==board(:,1:end-1)))||any(any(board(1:end-1,:)==board(2:end,:))); %%%%
    if doclusters && limit<numel(board)
        [vine4,scorevec(4)] = real_kurt(board);
    end
    
    [moves5,vine5,scorevec(5)] = nick(board,limit);
    [moves7,vine7,scorevec(7)] = nick(rot90(board,2),limit);
    if max(scorevec([5 7])) < 2 * max(scorevec([1 2 3 4 9 ]));
        [moves6,vine6,scorevec(6)] = nick(board',limit);
        [moves8,vine8,scorevec(8)] = nick(rot90(board,3),limit);
    end
end
if max(scorevec)<0
    [moves1, vine1, scorevec(1)] = alfi(board, limit);
end
[bs,best] = max(scorevec);

[nrow,ncol] = size(board);
ntot = nrow*ncol;


switch best
    case 1
        moves=moves1;
        vine=vine1;
    case 2
        id = reshape(1:ntot,nrow,ncol);
        id = fliplr(id);
        moves = id(moves2);
        vine = id(vine2);
    case 3
        moves=moves3;
        vine=vine3;
    case 4
        moves = [];
        vine = vine4;
    case 5
        moves = moves5;
        vine = vine5;
    case 6
        id = reshape(1:ntot,nrow,ncol);
        id = id';
        moves = id(moves6);
        vine = id(vine6);
    case 7
        id = reshape(1:ntot,nrow,ncol);
        id = rot90(id,2);
        moves = id(moves7);
        vine = id(vine7);
    case 8
        id = reshape(1:ntot,nrow,ncol);
        id = rot90(id,3);
        moves = id(moves8);
        vine = id(vine8);
    case 9
        moves = moves9;
        vine = vine9;
    case 10
        moves = moves10;
        vine = vine10;
    case 11
        moves = moves11;
        vine = vine11;
    case 12
        moves = moves12;
        vine = vine12;
    
    
end

if size(moves,1) < limit
    [moves, vine] = use_more_moves(board, moves, vine, limit);
end

end

%% nick
function [moves, vine, scr] = nick(board, limit)

moves = zeros(limit,2);
[nrow,ncol] = size(board);
ntot = nrow*ncol;

if (limit < nrow-1)
    scr = -inf;
    moves = [];
    vine = [];
    return;
end;

xg = repmat(1:ncol,nrow,1);
yg = repmat((1:nrow)',1,ncol);
pos = reshape(1:ntot,nrow,ncol);
fitloc = reshape(1:ntot,nrow,ncol);
fitloc(:,2:2:end) = flipud(fitloc(:,2:2:end));
%[s,r] = sort(board(:),'descend');
[s,r] = sort(-board(:));
s=-s;
rank = zeros(nrow,ncol);
rank(r) = 1:ntot;
remain = true(1,ntot);
nextfit = 1;
steps = 0;
cboard = board;
for i = 1:ntot
    if remain(i)
        [cy,cx] = find(rank==i);
        tx = xg(fitloc(nextfit));
        ty = yg(fitloc(nextfit));
        [cboard,moves,remain,rank,steps]=oftl2(cx,tx,cy,ty,cboard,rank,steps,moves,pos,remain,ncol,nrow,limit,s,i);
        if (steps > limit)
            break;
        end;
        rank(ty,tx) = i;
        nextfit = nextfit+1;
    end;
end;
moves = moves(1:min(steps,limit),:);
[vine,scr] = real_kurt(cboard);
end

%% michael
% http://www.mathworks.com/matlabcentral/contest/contests/34/submissions/64578
function [moves, vine] = use_more_moves(board, moves, vine, limit)

m = size(board,1);

for i = 1:size(moves,1)
    board(moves(i,:)) = [0 board(moves(i,1))];
end

extra_moves = limit - size(moves,1);
% disp('Moves left over')
larger_i = find(board >= max(board(vine)));
larger_i = setdiff(larger_i,vine);
if ~isempty(larger_i)
    end_row = mod(vine(end),m);
    if end_row == 0
        end_row = m;
    end
    end_col = ceil(vine(end)/m);
    
    larger_rows = mod(larger_i,m);
    larger_rows(larger_rows == 0) = m;
    larger_cols = ceil(larger_i/m);
    
    moves_req = abs(end_row - larger_rows) + abs(end_col - larger_cols) - 1;
    possible_moves = larger_i(moves_req < extra_moves);
    moves_req = moves_req(moves_req < extra_moves);
    
    while ~isempty(possible_moves) & extra_moves > 0
        [junk, sort_i] = sort(moves_req);
        
        possible_moves = possible_moves(sort_i);
        
        test_move = possible_moves(1);
        test_row = mod(test_move,m);
        if test_row == 0
            test_row = m;
        end
        test_col = ceil(test_move/m);
        
        if end_row > test_row
            move_rows = test_row:end_row;
            move_cols = zeros(size(move_rows)) + test_col;
        elseif end_row < test_row
            move_rows = test_row:-1:end_row;
            move_cols = zeros(size(move_rows)) + test_col;
        else
            move_rows = [];
            move_cols = [];
        end
        
        if end_col == test_col
            move_rows(end) = [];
            move_cols(end) = [];
        else
            if end_col > test_col
                move_cols = [move_cols, test_col+1:end_col-1];
                move_rows = [move_rows, zeros(size(test_col+1:end_col-1))+end_row];
            elseif end_col < test_col
                move_cols = [move_cols, test_col-1:-1:end_col+1];
                move_rows = [move_rows, zeros(size(test_col-1:-1:end_col+1))+end_row];
            end
        end
        
        add_moves = move_cols*m + move_rows - m;
        add_moves = [add_moves(1:end-1)', add_moves(2:end)'];
        
        if any(ismember(add_moves(:),vine))
            possible_moves(1) = [];
            moves_req(1) = [];
        else
            %             possible_moves = [];
            moves = [moves; add_moves];
            extra_moves = limit - size(moves,1);
            vine = [vine, moves(end,2)];
            
            for i = 1:size(add_moves,1)
                board(add_moves(i,:)) = [0 board(add_moves(i,1))];
            end
            
            end_row = mod(vine(end),m);
            if end_row == 0
                end_row = m;
            end
            end_col = ceil(vine(end)/m);
            
            larger_i = find(board >= max(board(vine)));
            larger_i = setdiff(larger_i,vine);
            larger_rows = mod(larger_i,m);
            larger_rows(larger_rows == 0) = m;
            larger_cols = ceil(larger_i/m);
            
            moves_req = abs(end_row - larger_rows) + abs(end_col - larger_cols) - 1;
            possible_moves = larger_i(moves_req < extra_moves);
            moves_req = moves_req(moves_req < extra_moves);
        end
        
    end
end
end

function [cboard,moves,remain,rank,steps]=oftl2(cx,tx,cy,ty,cboard,rank,steps,moves,pos,remain,ncol,nrow,limit,s,i)
while (cx~=tx)||(cy~=ty)
    dx = sign(tx-cx);
    dy = sign(ty-cy);
    if (dx~=0)&&(dy~=0)
        if cboard(cy,cx+dx)<=cboard(cy+dy,cx)
            dy = 0;
        else
            dx = 0;
        end;
    end;
    if (rank(cy+dy,cx+dx)>0)
        vx = cx+dx;
        vy = cy+dy;
        if (dx==0)
            if (vx>1)&&(cboard(vy,vx)>cboard(vy,vx-1))&&((vx==ncol)||(cboard(vy,vx+1)>cboard(vy,vx-1)))
                % move left
                steps = steps+1;
                if (steps > limit)
                    break;
                end;
                moves(steps,1) = pos(vy,vx);
                moves(steps,2) = pos(vy,vx-1);
                cboard(vy,vx-1) = cboard(vy,vx);
                cboard(vy,vx) = 0;
                if (rank(vy,vx-1)>0)
                    remain(rank(vy,vx-1)) = 0;
                end;
                rank(vy,vx-1) = rank(vy,vx);
                rank(vy,vx) = 0;
            elseif (vx < ncol)&(cboard(vy,vx)>cboard(vy,vx+1))
                % move right
                steps = steps+1;
                if (steps > limit)
                    break;
                end;
                moves(steps,1) = pos(vy,vx);
                moves(steps,2) = pos(vy,vx+1);
                cboard(vy,vx+1) = cboard(vy,vx);
                cboard(vy,vx) = 0;
                if (rank(vy,vx+1)>0)
                    remain(rank(vy,vx+1)) = 0;
                end;
                rank(vy,vx+1) = rank(vy,vx);
                rank(vy,vx) = 0;
            else
                remain(rank(cy+dy,cx+dx)) = 0;
            end;
        else
            if (vy>1)&(cboard(vy,vx)>cboard(vy-1,vx))&((vy==nrow)|(cboard(vy+1,vx)>cboard(vy-1,vx)))
                % move north
                steps = steps+1;
                if (steps > limit)
                    break;
                end;
                moves(steps,1) = pos(vy,vx);
                moves(steps,2) = pos(vy-1,vx);
                cboard(vy-1,vx) = cboard(vy,vx);
                cboard(vy,vx) = 0;
                if (rank(vy-1,vx)>0)
                    remain(rank(vy-1,vx)) = 0;
                end;
                rank(vy-1,vx) = rank(vy,vx);
                rank(vy,vx) = 0;
            elseif (vy < nrow)&(cboard(vy,vx)>cboard(vy+1,vx))
                % move right
                steps = steps+1;
                if (steps > limit)
                    break;
                end;
                moves(steps,1) = pos(vy,vx);
                moves(steps,2) = pos(vy+1,vx);
                cboard(vy+1,vx) = cboard(vy,vx);
                cboard(vy,vx) = 0;
                if (rank(vy+1,vx)>0)
                    remain(rank(vy+1,vx)) = 0;
                end;
                rank(vy+1,vx) = rank(vy,vx);
                rank(vy,vx) = 0;
            else
                remain(rank(cy+dy,cx+dx)) = 0;
            end;
        end;
    end;
    steps = steps+1;
    if (steps > limit)
        break;
    end;
    moves(steps,1) = pos(cy,cx);
    moves(steps,2) = pos(cy+dy,cx+dx);
    cboard(cy+dy,cx+dx) = s(i); %cboard(cy,cx);
    cboard(cy,cx) = 0;
    rank(cy,cx) = 0;
    cx = cx+dx;
    cy = cy+dy;
end;
end

function [moves,vine,scr] = dofilter(board,limit)
[nrow,ncol] = size(board);
ntot = nrow*ncol;
moves = zeros(limit,2);
nmove = 0;
pos = reshape(1:ntot,nrow,ncol);
m1 = median(board,1);
m2 = median(board,2);
if (sum(sign(diff(m1)))>0.67*ncol)||(sum(sign(diff(m2)))>0.67*nrow)||(sum(sign(diff(m2)))<-0.67*nrow)||(sum(sign(diff(m2)))<-0.67*nrow)
    d = diff(board,1,2);
    mb = median(board,2);
    md = median(d,2);
    rmb = repmat(mb,1,ncol);
    rmd = repmat(md,1,ncol);
    guess = rmb+kron(md,-(ncol-1)/2:(ncol-1)/2);
    bad = (abs(board-guess)>20*abs(rmd));
    for i = nrow:-1:1
        offset = 0;
        for j = ceil(ncol/2):ncol
            if bad(i,j)
                offset = offset+1;
            else
                moves(nmove+1:nmove+offset,:) = [pos(i,j:-1:j-offset+1)' pos(i,j-1:-1:j-offset)'];
                nmove = nmove+offset;
                if (nmove>=limit)
                    break;
                end;
            end;
        end;
        offset = 0;
        for j = ceil(ncol/2):-1:1
            if bad(i,j)
                offset = offset+1;
            else
                moves(nmove+1:nmove+offset,:) = [pos(i,j:1:j+offset-1)' pos(i,j+1:1:j+offset)'];
                nmove = nmove+offset;
                if (nmove>=limit)
                    break;
                end;
            end;
        end;
        if (nmove>=limit)
            break;
        end;
    end;
    moves = moves(1:min(nmove,limit),:);
    for i = 1:size(moves,1)
        board(moves(i,2)) = board(moves(i,1));
        board(moves(i,1)) = 0;
        %imagesc(board);
        %axis image;
        %drawnow;
    end;
    [vine,scr] = SimpleLongestPath(board);
else
    scr = -inf;
    moves = [];
    vine = [];
end
end


%% alfi
function [moves, vine, gain] = alfi(board, limit)
moves=[];
doclusters=any(any(board(:,2:end)==board(:,1:end-1)))|any(any(board(2:end,:)==board(1:end-1,:))); %%%%
[m,n]=size(board);
board=[zeros(1,n+2);[zeros(m,1),board,zeros(m,1)];zeros(1,n+2)];
[m,n]=size(board);
if doclusters,
    % compute same-valued clusters
    [BoardCluster,ClusterValue,IdxList,IdxSegments,Nclusters]=connected(board);
    ClusterSize=diff(IdxSegments);
    ClusterNeighb=neighb(BoardCluster,board,Nclusters);
    % search between-clusters
    ClustersOrder = bellman(ClusterNeighb,ClusterValue,ClusterValue'.*sqrt(ClusterSize'));
    % search within-clusters
    iC=bellman_postprocess(ClustersOrder,IdxList,IdxSegments,BoardCluster);
else
    % search between-pixels
    iC = SimpleLongestPath( board );
    iC = iC(end:-1:1);
    iC = iC(board(iC)>0);
end
% post-processing moves
if limit>0
    [board,iC,moves,limit] = postprocess(board,iC,moves,limit);
    iC1=rem(moves-1,m)+1;
    iC2=(moves-iC1)/m+1;
    moves=iC1-1+(m-2)*(iC2-2);
end

iC1=rem(iC-1,m)+1;
iC2=(iC-iC1)/m+1;
vine=iC1-1+(m-2)*(iC2-2);
vine=vine(end:-1:1);
board=board(2:end-1,2:end-1);
gain=sum(board(vine));

% disp(gain)
% imagesc(board);hold on;[i1,i2]=ind2sub(size(board),vine);plot(i2,i1,'k.-'); hold off;

end

function [board,tiC,moves,limit] = postprocess(board,tiC,moves,limit)
[m,n]=size(board);
% grow laterally
d=abs(diff(tiC))==1;
E=[m*~d+d; m*d+~d];
checkLateral=[];
checkEndpoints=[];
BorderUp={repmat(1+(0:n-1)*m,[m,1]),repmat((1:m)',[1,n])};
BorderDown={repmat(m+(0:n-1)*m,[m,1]),repmat(m*(n-1)+(1:m)',[1,n])};
tP=board>0;
tP(tiC)=false;
for n1=1:1e3,
    [checkLateral,checkEndpoints]=postprocess_update(board,moves,tiC,tP,E,checkLateral,checkEndpoints,limit,BorderDown,BorderUp);
    [board,moves,tiC,tP,E,checkLateral,checkEndpoints,limit,ok]=postprocess_move(board,moves,tiC,tP,E,checkLateral,checkEndpoints,limit,BorderDown,BorderUp);
    if ~ok, break; end
end
end

function [check,check2]=postprocess_update(board,moves,tiC,tP,E,check,check2,limit,BorderDown,BorderUp)
[m,n]=size(board);
K=size(tiC,2);
if isempty(check)
    check=zeros(m*n,2,4);
    check(tiC(1:K-1),1)=tP(tiC(1:K-1)+E(2,1:K-1))&tP(tiC(2:K)+E(2,1:K-1));
    check(tiC(1:K-1),2)=tP(tiC(1:K-1)-E(2,1:K-1))&tP(tiC(2:K)-E(2,1:K-1));
    check2={zeros(2,4),[]};
    tm=max(board(~tP));check2{1}(1,1)=tm>=board(tiC(1));
    tm=min(board(~tP&board>0));check2{1}(2,1)=tm<=board(tiC(end));
end
% Grow laterally
for ndir=1:2,
    switch(ndir)
        case 1, idx1=find(check(tiC(1:K-1),1)>0&(~check(tiC(1:K-1),1,2)|(check(tiC(1:K-1),1,3)+check(tiC(1:K-1),1,4)-2>limit)));
        case 2, idx1=find(check(tiC(1:K-1),2)>0&(~check(tiC(1:K-1),2,2)|(check(tiC(1:K-1),2,3)+check(tiC(1:K-1),2,4)-2>limit)));
    end
    for n2=1:numel(idx1),
        check(tiC(idx1(n2)),ndir)=false;
        switch(ndir)
            case 1
                tempA=tiC(idx1(n2))+E(2,idx1(n2)):E(2,idx1(n2)):BorderDown{1+(E(2,idx1(n2))==m)}(tiC(idx1(n2)));
                tempB=tiC(idx1(n2)+1)+E(2,idx1(n2)):E(2,idx1(n2)):BorderDown{1+(E(2,idx1(n2))==m)}(tiC(idx1(n2)+1));
            case 2
                tempA=tiC(idx1(n2))-E(2,idx1(n2)):-E(2,idx1(n2)):BorderUp{1+(E(2,idx1(n2))==m)}(tiC(idx1(n2)));
                tempB=tiC(idx1(n2)+1)-E(2,idx1(n2)):-E(2,idx1(n2)):BorderUp{1+(E(2,idx1(n2))==m)}(tiC(idx1(n2)+1));
        end
        idxZ=find(~tP(tempA),1,'first');
        if ~isempty(idxZ), tempA(idxZ:end)=[]; end
        [nill,idxA]=find(board(tiC(idx1(n2)))>=board(tempA)&board(tempA)>=board(tiC(idx1(n2)+1)));
        if ~isempty(idxA),
            [nill,idxA1]=min(board(tiC(idx1(n2)))-board(tempA(idxA)));
            idxA=idxA(idxA1);
            idxZ=find(~tP(tempB),1,'first');
            if ~isempty(idxZ), tempB(idxZ:end)=[]; end
            [nill,idxB]=find(board(tempA(idxA))>=board(tempB)&board(tempB)>=board(tiC(idx1(n2)+1)));
            if ~isempty(idxB),
                [nill,idxB1]=min(board(tempB(idxB))-board(tiC(idx1(n2)+1)));
                idxB=idxB(idxB1);
                value=(board(tempA(idxA))+board(tempB(idxB)))/max(eps,idxA+idxB-2);
                check(tiC(idx1(n2)),ndir)=value>0;
                check(tiC(idx1(n2)),ndir,2)=value;
                check(tiC(idx1(n2)),ndir,3)=idxA;
                check(tiC(idx1(n2)),ndir,4)=idxB;
            else
                check(tiC(idx1(n2)),ndir,2)=-1;
            end
        else
            check(tiC(idx1(n2)),ndir,2)=-1;
        end
    end
end

% Grow end-points
ndirs=find(check2{1}(:,1)>0&(~check2{1}(:,2)|(check2{1}(:,2)>0&check2{1}(:,3)>limit)));
for ndir=ndirs(:)',
    eok=true;
    if ndir==1,
        mask=tP&board<2*board(tiC(1));
        D=Dijkstra(mask,tiC(1),limit+1);
        idx1=find(mask&D-1<=limit&board>=board(tiC(1)));
        if isempty(idx1),
            mask=tP;
            D=Dijkstra(mask,tiC(1),limit+1);
            idx1=find(mask&D-1<=limit&board>=board(tiC(1)));
            if isempty(idx1),eok=false;end
        end
    elseif ndir==2
        mask=tP;
        D=Dijkstra(mask,tiC(end),limit+1);
        idx1=find(mask&D-1<=limit&board<=board(tiC(end))&board>0);
        if isempty(idx1),eok=false;end
    end
    if eok
        if ndir==1
            if limit>150
                [nill,idx2]=min(board(idx1)+1e-3*D(idx1)); %%%t3
            else
                [nill,idx2]=min(board(idx1).*(D(idx1)/limit).^0.2); %%%t3
            end
        else
            if limit>300
                [nill,idx2]=min(-board(idx1)+1e-3*D(idx1)); %%%t3
            else
                [nill,idx2]=min(-board(idx1).*(limit./D(idx1)).^0.085); %%%t3
            end
        end
        idx0=idx1(idx2);
        value=board(idx0)/max(eps,D(idx0)-1);
        check2{2+ndir-1}=idx0;
        check2{1}(ndir,1)=value>0;
        check2{1}(ndir,2)=value;
        check2{1}(ndir,3)=D(idx0)-1;
        dx=[1,-1,m,-m];
        for n2=D(idx0)-1:-1:1
            dxi1=D(idx0+dx)==n2;
            [nill,dxi2]=max(dxi1-1e-10*board(idx0+dx));
            tidx0=idx0+dx(dxi2);
            check2{2+ndir-1}=[check2{2+ndir-1},tidx0];
            idx0=tidx0;
        end
    else
        check2{1}(ndir,2)=-1;
    end
end
end

function [board,moves,tiC,tP,E,check,check2,limit,ok]=postprocess_move(board,moves,tiC,tP,E,check,check2,limit,BorderDown,BorderUp)
[m,n]=size(board);
ok=false;
K=size(tiC,2);

optm_idx=find(check(tiC(1:K-1),:,1)&check(tiC(1:K-1),:,2)>0)';
if isempty(optm_idx), 
    optm_idx1=[];
    optm_idx2=[];
    optm_idx3=[];
    optm=[]; 
    optm_type=[];
else
    optm_idx1=1+rem(optm_idx-1,K-1);
    optm_idx2=1+(optm_idx-optm_idx1)/(K-1);
    optm_idx3=tiC(optm_idx1)+(optm_idx2-1)*size(check,1);
    optm=check(optm_idx3+size(check,2)*size(check,1)).*(check(optm_idx3+2*size(check,2)*size(check,1))+check(optm_idx3+3*size(check,2)*size(check,1))-2<=limit);
    optm_type=ones(1,numel(optm_idx1));
end
optm=[optm,(check2{1}(:,2))'];
optm_type=[optm_type,[2,2]];
optm_idx1=[optm_idx1,[1,2]];
optm_idx2=[optm_idx2,[1,2]];
optm_idx3=[optm_idx3,[1,2]];

% Choose next move
[maxvalue,idx2]=sort(optm,'descend');
for nmaxvalue=1:numel(maxvalue),
	if ok||maxvalue(nmaxvalue)<=0, break; end
    if optm_type(idx2(nmaxvalue))==1
        idx1=optm_idx1(idx2(nmaxvalue));
        ndir=optm_idx2(idx2(nmaxvalue));
        idxA=check(optm_idx3(idx2(nmaxvalue))+2*size(check,2)*size(check,1));
        idxB=check(optm_idx3(idx2(nmaxvalue))+3*size(check,2)*size(check,1));
        switch(ndir)
            case 1
                tempA=tiC(idx1)+E(2,idx1):E(2,idx1):BorderDown{1+(E(2,idx1)==m)}(tiC(idx1));
                tempB=tiC(idx1+1)+E(2,idx1):E(2,idx1):BorderDown{1+(E(2,idx1)==m)}(tiC(idx1+1));
            case 2
                tempA=tiC(idx1)-E(2,idx1):-E(2,idx1):BorderUp{1+(E(2,idx1)==m)}(tiC(idx1));
                tempB=tiC(idx1+1)-E(2,idx1):-E(2,idx1):BorderUp{1+(E(2,idx1)==m)}(tiC(idx1+1));
        end
        if all(tP(tempA(1:idxA)))&&all(tP(tempB(1:idxB)))&&board(tiC(idx1))>=board(tempA(idxA))&&board(tempA(idxA))>=board(tempB(idxB))&&board(tempB(idxB))>=board(tiC(idx1+1)),
            ok=true;
            switch(ndir)
                case 1,
                    tiC=[tiC(1:idx1),tiC(idx1)+E(2,idx1), tiC(idx1+1)+E(2,idx1), tiC(idx1+1:end)];
                    E=[E(:,1:idx1-1),E([2,1],idx1), E([1,2],idx1), E([2,1],idx1), E(:,idx1+1:end)];
                case 2,
                    tiC=[tiC(1:idx1),tiC(idx1)-E(2,idx1), tiC(idx1+1)-E(2,idx1), tiC(idx1+1:end)];
                    E=[E(:,1:idx1-1),E([2,1],idx1), E([1,2],idx1), E([2,1],idx1), E(:,idx1+1:end)];
            end
            K=size(tiC,2);
            tP(tiC)=false;
            check(tiC(1:K-1),1)=tP(tiC(1:K-1)+E(2,1:K-1))&tP(tiC(2:K)+E(2,1:K-1));
            check(tiC(1:K-1),2)=tP(tiC(1:K-1)-E(2,1:K-1))&tP(tiC(2:K)-E(2,1:K-1));
            check(tiC(idx1+[0,1,2]),1,2)=0;
            check(tiC(idx1+[0,1,2]),2,2)=0;
            newmoveA=[tempA(2:idxA)',tempA(1:idxA-1)'];
            newmoveB=[tempB(2:idxB)',tempB(1:idxB-1)'];
            board(newmoveA(:,2))=board(tempA(idxA));
            board(newmoveB(:,2))=board(tempB(idxB));
            board(newmoveA(:,1))=0;
            board(newmoveB(:,1))=0;
            moves=[moves;flipud(newmoveA);flipud(newmoveB)];
            limit=limit-size(newmoveA,1)-size(newmoveB,1);
        else
            check(tiC(idx1),ndir,2)=0;
        end
    elseif optm_type(idx2(nmaxvalue))==2
        ndir=optm_idx1(idx2(nmaxvalue));
        idx0=check2{2+ndir-1};
        if ~all(tP(idx0))||(ndir==1&&board(idx0(1))<board(tiC(1)))||(ndir==2&&board(idx0(1))>board(tiC(end))),
            check2{1}(ndir,2)=0;
        else
            ok=true;
            for n2=1:numel(idx0)-1,
                moves=[moves; idx0(n2), idx0(n2+1)];
                board(idx0(n2+1))=board(idx0(n2));
                board(idx0(n2))=0;
            end
            if ndir==1,     
                d=abs(tiC(1)-idx0(end))==1;
                tiC=[idx0(end),tiC];
                E=[[m*~d+d; m*d+~d],E];
            elseif ndir==2, 
                d=abs(tiC(end)-idx0(end))==1;
                tiC=[tiC,idx0(end)];
                E=[E,[m*~d+d; m*d+~d]];
            end
            tP(idx0(end))=false;
            K=size(tiC,2);
            check(tiC(1:K-1),1)=tP(tiC(1:K-1)+E(2,1:K-1))&tP(tiC(2:K)+E(2,1:K-1));
            check(tiC(1:K-1),2)=tP(tiC(1:K-1)-E(2,1:K-1))&tP(tiC(2:K)-E(2,1:K-1));
            if ndir==1,     tm=max(board(~tP));check2{1}(1,1)=tm>=board(tiC(1));
            elseif ndir==2, tm=min(board(~tP));check2{1}(2,1)=tm<=board(tiC(end));
            end
            check2{1}(ndir,2)=0;
            limit=limit-(numel(idx0)-1);
        end
    end
end
if ~ok&&any(maxvalue>0), ok=true; end

end

function iC = bellman(C,V,D)
N=size(C,1);
c=cell(1,N); for n1=1:N,c{n1}=find(C(:,n1)); end
IDX=zeros(N,1);
cD=D;
[nill,sorted]=sort(V,'descend');
for n1=1:N,
    curr=sorted(n1);
    neighb=c{curr};
    if ~isempty(neighb)
        [nill,idx]=max(cD(neighb));
        cD(curr)=cD(curr)+cD(neighb(idx));
        IDX(curr)=neighb(idx);
    end
end
[nill,idx]=max(cD);
iC=zeros(N,1);
for n1=1:N,
    if idx>0
        iC(n1)=idx;
        idx=IDX(idx);
    else break;
    end
end
iC=iC(n1-1:-1:1);
iC=iC(V(iC)>0);
end

function  iC=bellman_postprocess(ClustersOrder,IdxList,IdxSegments,BoardCluster)
[m,n]=size(BoardCluster);
iC=[];
for n1=1:numel(ClustersOrder)
    idx=IdxList(IdxSegments(ClustersOrder(n1)):IdxSegments(ClustersOrder(n1)+1)-1);
    if numel(idx)==1, iC=[iC,idx(1)];
    else
        % longest shortest-path
        ThisCluster=false(m,n);
        ThisCluster(idx)=true;
        D=Dijkstra(ThisCluster,iC);
        if n1==numel(ClustersOrder)
            temp=D(ThisCluster);
        else
            temp=D(ThisCluster).*(BoardCluster([false(1,n);ThisCluster(1:m-1,:)])==ClustersOrder(n1+1)|BoardCluster([ThisCluster(2:m,:);false(1,n)])==ClustersOrder(n1+1)|BoardCluster([false(m,1),ThisCluster(:,1:n-1)])==ClustersOrder(n1+1)|BoardCluster([ThisCluster(:,2:n),false(m,1)])==ClustersOrder(n1+1));
        end
        [nill,idx0]=max(temp(:));
        idx0=idx(idx0);
        E=zeros(2,D(idx0)-1);
        tiC=zeros(1,D(idx0));
        tiC(end)=idx0;
        for n2=D(idx0)-1:-1:1
            if      D(idx0+1)==n2, idx0=idx0+1; E(1,n2)=1;E(2,n2)=m;
            elseif  D(idx0-1)==n2, idx0=idx0-1; E(1,n2)=1;E(2,n2)=m;
            elseif  D(idx0+m)==n2, idx0=idx0+m; E(1,n2)=m;E(2,n2)=1;
            elseif  D(idx0-m)==n2, idx0=idx0-m; E(1,n2)=m;E(2,n2)=1;
            end
            tiC(n2)=idx0;
        end
        % now grow it
        tP=ThisCluster;
        tP(tiC)=false;
        ok=1;
        while ok
            ok=0;
            K=size(tiC,2);
            idx1=find(tP(tiC(1:2:K-1)+E(2,1:2:K-1))&tP(tiC(2:2:K)+E(2,1:2:K-1)));
            for n2=numel(idx1):-1:1
                ok=1;
                tiC=[tiC(1:2*idx1(n2)-1),tiC(2*idx1(n2)-1)+E(2,2*idx1(n2)-1), tiC(2*idx1(n2))+E(2,2*idx1(n2)-1), tiC(2*idx1(n2):end)];
                E=[E(:,1:2*idx1(n2)-2),E([2,1],2*idx1(n2)-1), E([1,2],2*idx1(n2)-1), E([2,1],2*idx1(n2)-1), E(:,2*idx1(n2):end)];
                tP(tiC)=false;
            end
            K=size(tiC,2);
            idx1=find(tP(tiC(1:2:K-1)-E(2,1:2:K-1))&tP(tiC(2:2:K)-E(2,1:2:K-1)));
            for n2=numel(idx1):-1:1
                ok=1;
                tiC=[tiC(1:2*idx1(n2)-1),tiC(2*idx1(n2)-1)-E(2,2*idx1(n2)-1), tiC(2*idx1(n2))-E(2,2*idx1(n2)-1), tiC(2*idx1(n2):end)];
                E=[E(:,1:2*idx1(n2)-2),E([2,1],2*idx1(n2)-1), E([1,2],2*idx1(n2)-1), E([2,1],2*idx1(n2)-1), E(:,2*idx1(n2):end)];
                tP(tiC)=false;
            end
            K=size(tiC,2);
            idx1=find(tP(tiC(2:2:K-1)+E(2,2:2:K-1))&tP(tiC(3:2:K)+E(2,2:2:K-1)));
            for n2=numel(idx1):-1:1
                ok=1;
                tiC=[tiC(1:2*idx1(n2)),tiC(2*idx1(n2))+E(2,2*idx1(n2)), tiC(2*idx1(n2)+1)+E(2,2*idx1(n2)), tiC(2*idx1(n2)+1:end)];
                E=[E(:,1:2*idx1(n2)-1),E([2,1],2*idx1(n2)), E([1,2],2*idx1(n2)), E([2,1],2*idx1(n2)), E(:,2*idx1(n2)+1:end)];
                tP(tiC)=false;
            end
            K=size(tiC,2);
            idx1=find(tP(tiC(2:2:K-1)-E(2,2:2:K-1))&tP(tiC(3:2:K)-E(2,2:2:K-1)));
            for n2=numel(idx1):-1:1
                ok=1;
                tiC=[tiC(1:2*idx1(n2)),tiC(2*idx1(n2))-E(2,2*idx1(n2)), tiC(2*idx1(n2)+1)-E(2,2*idx1(n2)), tiC(2*idx1(n2)+1:end)];
                E=[E(:,1:2*idx1(n2)-1),E([2,1],2*idx1(n2)), E([1,2],2*idx1(n2)), E([2,1],2*idx1(n2)), E(:,2*idx1(n2)+1:end)];
                tP(tiC)=false;
            end
            if ~ok
                if numel(tiC)>=4
                    dtiC=tiC(2:end)-tiC(1:end-1);
                    ditCidx=find(dtiC(2:end-2)==dtiC(4:end)&dtiC(1:end-3)==dtiC(3:end-1)&dtiC(1:end-3)~=dtiC(2:end-2)&BoardCluster(tiC(2:end-3)+dtiC(1:end-3))==ClustersOrder(n1));
                    if ~isempty(ditCidx);
                        lnditCidx=-inf;
                        for n2=1:numel(ditCidx), 
                            if ditCidx(n2)>lnditCidx+2 && tP(tiC(ditCidx(n2)+1)+dtiC(ditCidx(n2))),
                                ok=1;
                                tiC(ditCidx(n2)+2)=tiC(ditCidx(n2)+1)+dtiC(ditCidx(n2));
                                E(:,ditCidx(n2)+[1,2])=E(:,ditCidx(n2)+[2,1]);
                                tP(tiC(ditCidx(n2)+2))=true;
                                tP(tiC)=false;
                                lnditCidx=ditCidx(n2);
                            end
                        end
                    end
                end
            end
        end
        
        iC=[iC,tiC];
    end
end
end

function B = neighb(A,V,nA)
[m,n] = size(A);
B=sparse(A(:,1:n-1),A(:,2:n),double(V(:,1:n-1)>V(:,2:n)),nA,nA)+sparse(A(:,2:n),A(:,1:n-1),double(V(:,2:n)>V(:,1:n-1)),nA,nA)+sparse(A(1:m-1,:),A(2:m,:),double(V(1:m-1,:)>V(2:m,:)),nA,nA)+sparse(A(2:m,:),A(1:m-1,:),double(V(2:m,:)>V(1:m-1,:)),nA,nA);
B=B>0;
end

function [B,C,p,r,nc] = connected(A)
[m,n] = size(A);
N = m*n ;
K = reshape (1:N, m, n) ;
V = A(:,1:n-1) == A(:,2:n);
H = A(1:m-1,:) == A(2:m,:);
G = sparse(K([V,false(m,1)]),K([false(m,1),V]),1,N,N)+sparse(K([H; false(1,n)]),K([false(1,n); H]),1,N,N);
G = G + G' + speye(N);
[p q r] = dmperm(G);
nc = numel(r) - 1;
C = A(p(r(1:nc)));
B = ones(m, n);
for a = 2:nc
    B(p(r(a):r(a+1)-1)) = a;
end
end

function D = Dijkstra(A,i1,nmax)
[m,n]=size(A);
mn=m*n;
D=inf(m,n);
D(~A)=0;
if isempty(i1),
    i1=find(A,1,'first');
    mode=0;
else
    i1=i1(end);
    mode=1;
end
if nargin<3, nmax=mn; 
else nmax=min(mn,nmax+mode); 
end
D(i1)=1;
Y=A>0;
Y(i1)=false;

for n1=2:nmax,
    X=false(m,n);
    idx1=i1+1;
    idx2=i1-1;
    idx3=i1+m;
    idx4=i1-m;
    X(idx1)=Y(idx1);
    X(idx2)=Y(idx2);
    X(idx3)=Y(idx3);
    X(idx4)=Y(idx4);
    i1=find(X);
    Y(i1)=false;
    if isempty(i1), break; end
    D(i1)=n1;
end
if mode, D(D>0)=D(D>0)-1; end
D(~A)=inf;
end

function [vine,moves,board,scr] = spiral(board,limit,factor)
limit0=limit;
moves=zeros(limit,2);
nmoves=0;
[m,n]=size(board);
board=[zeros(1,n+2);[zeros(m,1),board,zeros(m,1)];zeros(1,n+2)];
[m,n]=size(board);
mn=m*n;
if nargin<3||~factor, factor=limit/mn/4; end
nl=ceil(min(m,n)/2);
np=floor(min(m,n)/2);
order=zeros(m,n);
level=zeros(m,n);
corners=zeros(nl,4);
n0=0;
sp=0;
for n1=1:nl
    corners(n1,:)=[n1,m-n1+1,n1,n-n1+1];
    s=n0+(1:n-2*n1+2);n0=n0+(n-2*n1+2);
    order(n1,n1:n-n1+1)=s; 
    level(n1,n1:n-n1+1)=n1;
    s=n0+(1:m-2*n1+1);n0=n0+m-2*n1;
    order(n1+1:m-n1+1,n-n1+1)=s;
    level(n1+1:m-n1+1,n-n1+1)=n1;
    if n1<=np
        s=n0+(1:n-2*n1+2);n0=n0+n-2*n1+2;
        order(m-n1+1,n-n1+1:-1:n1)=s;
        level(m-n1+1,n-n1+1:-1:n1)=n1;
        s=n0+(1:m-2*n1);n0=n0+m-2*n1;
        order(m-n1:-1:n1+1,n1)=s;
        level(m-n1:-1:n1+1,n1)=n1;
    end
end
[nill,porder]=sort(order(:),'descend');
[nill,iorder]=sort(board(:),'descend');
index=reshape(1:m*n,[m,n]);
rows=repmat((1:m)',[1,n]);
cols=repmat((1:n),[m,1]);
np=1;
dx=[1,-1,m,-m];
targ=porder(np);
targ_r=rows(targ);
targ_c=cols(targ);
targ_l=level(targ);
for ni=1:mn
    if limit<=0||targ_l<=2, break; end
    cur=iorder(ni);
    cur_r=rows(cur);
    cur_c=cols(cur);
    cur_b=board(cur);
    dr=abs(cur_r-targ_r);
    dc=abs(cur_c-targ_c);
    if cur_b>0&&order(cur)<order(targ)&&(dr+dc<limit)
        if (dr<m*factor&&dc<n*factor)
            pretarg_r=max(corners(targ_l-1,1),min(corners(targ_l-1,2),cur_r));
            pretarg_c=max(corners(targ_l-1,3),min(corners(targ_l-1,4),cur_c));
            while level(cur)<targ_l-1
                [nill,idx]=min(abs(rows(cur+dx)-pretarg_r)+abs(cols(cur+dx)-pretarg_c)+(1e-10*board(cur+dx)));
                newcur=cur+dx(idx);
                moves(nmoves+1,:)=[cur,newcur];nmoves=nmoves+1;
                board(newcur)=board(cur);
                board(cur)=0;
                limit=limit-1;
                cur=newcur;
            end
            cur_r=rows(cur);
            cur_c=cols(cur);
            cur_l=level(cur);
            if cur_l<targ_l
                [newcur,newmoves]=spiral_movetorightside(cur,cur_r,cur_c,cur_l,targ_r,targ_c,targ_l,corners,index,rows,cols,m,n);
                if ~isempty(newmoves)
                    cur=newcur;
                    moves(nmoves+(1:size(newmoves,1)),:)=newmoves;nmoves=nmoves+size(newmoves,1);
                    board(newmoves(:,1))=0;
                    board(newmoves(end,2))=cur_b;
                    limit=limit-size(newmoves,1);
                    cur_r=rows(cur);
                    cur_c=cols(cur);
                end
            end
            for niter=1:mn,
                if rows(cur)==targ_r&&cols(cur)==targ_c,break; end
                [nill,idx]=min(m*n*(order(cur+dx)>order(targ))+abs(rows(cur+dx)-targ_r).^2+abs(cols(cur+dx)-targ_c).^2+1e-10*board(cur+dx));
                newcur=cur+dx(idx);
                moves(nmoves+1,:)=[cur,newcur]; nmoves=nmoves+1;
                board(newcur)=board(cur);
                board(cur)=0;
                limit=limit-1;
                cur=newcur;
            end
            if limit<0, break; end
            np=np+1;
            sp=sp+cur_b;
            targ=porder(np);
            targ_r=rows(targ);
            targ_c=cols(targ);
            targ_l=level(targ);
        end
    end
end
vine=porder(1:np-1);
moves=moves(1:nmoves,:);
[iC1,iC2]=ind2sub([m,n],vine);
vine=sub2ind([m-2,n-2],iC1-1,iC2-1);
[iC1,iC2]=ind2sub([m,n],moves);
moves=sub2ind([m-2,n-2],iC1-1,iC2-1);
board=board(2:end-1,2:end-1);
scr=sum(board(vine));
moves=moves(1:min(limit0,size(moves,1)),:);
vine=vine(end:-1:1);
end

function [cur,newmoves]=spiral_movetorightside(cur,cur_r,cur_c,cur_l,targ_r,targ_c,targ_l,corners,index,rows,cols,m,n)
newmoves=[];
if (cur_r==corners(cur_l,1)&&targ_r==corners(targ_l,2)&&targ_r~=corners(targ_l,1)) || (cur_r==corners(cur_l,2)&&targ_r==corners(targ_l,1)&&targ_r~=corners(targ_l,2)), % opposite rows
    if targ_c-corners(targ_l,3)+cur_c-corners(cur_l,3)<corners(targ_l,4)-targ_c+corners(cur_l,4)-cur_c,
        newmoves=[cur-m*(0:cur_c-corners(cur_l,3)-1)', cur-m*(1:cur_c-corners(cur_l,3))'];
        cur=index(cur_r,corners(cur_l,3));
    else
        newmoves=[cur+m*(0:corners(cur_l,4)-cur_c-1)', cur+m*(1:corners(cur_l,4)-cur_c)'];
        cur=index(cur_r,corners(cur_l,4));
    end
    cur_r=rows(cur);
    cur_c=cols(cur);
elseif (cur_c==corners(cur_l,3)&&targ_c==corners(targ_l,4)&&targ_c~=corners(targ_l,3)) || (cur_c==corners(cur_l,4)&&targ_c==corners(targ_l,3)&&targ_c~=corners(targ_l,4)), % opposite cols
    if targ_r-corners(targ_l,1)+cur_r-corners(cur_l,1)<corners(targ_l,2)-targ_r+corners(cur_l,2)-cur_r,
        newmoves=[cur-(0:cur_r-corners(cur_l,1)-1)', cur-(1:cur_r-corners(cur_l,1))'];
        cur=index(corners(cur_l,1),cur_c);
    else
        newmoves=[cur+(0:corners(cur_l,2)-cur_r-1)', cur+(1:corners(cur_l,2)-cur_r)'];
        cur=index(corners(cur_l,2),cur_c);
    end
    cur_r=rows(cur);
    cur_c=cols(cur);
end
if targ_r==corners(targ_l,1)&&cur_r~=corners(cur_l,1)&&targ_r<corners(targ_l,2)
    newmoves=[newmoves; cur-(0:cur_r-corners(cur_l,1)-1)', cur-(1:cur_r-corners(cur_l,1))'];
    cur=index(corners(cur_l,1),cur_c);
elseif targ_r==corners(targ_l,2)&&cur_r~=corners(cur_l,2)&&targ_r>corners(targ_l,1)
    newmoves=[newmoves;cur+(0:corners(cur_l,2)-cur_r-1)', cur+(1:corners(cur_l,2)-cur_r)'];
    cur=index(corners(cur_l,2),cur_c);
elseif targ_c==corners(targ_l,3)&&cur_c~=corners(cur_l,3)&&targ_c<corners(targ_l,4)
    newmoves=[newmoves;cur-m*(0:cur_c-corners(cur_l,3)-1)', cur-m*(1:cur_c-corners(cur_l,3))'];
    cur=index(cur_r,corners(cur_l,3));
elseif targ_c==corners(targ_l,4)&&cur_c~=corners(cur_l,4)&&targ_c>corners(targ_l,3)
    newmoves=[newmoves;cur+m*(0:corners(cur_l,4)-cur_c-1)', cur+m*(1:corners(cur_l,4)-cur_c)'];
    cur=index(cur_r,corners(cur_l,4));
end
end

%% kurt
function [vine, bestsom] = real_kurt(A)
moves = [];
%[bestsom,bestvine] = max(A(:));

[m,n]=size(A);

% inhoud = unique(A)';
% heur = sparse(0);
% for i=inhoud;
%     heur(i+1) = sum(sum(A(A<=i)));
% end
% H=full(heur(A+1));

content = unique(A);
t=sort(A(:));
tt = cumsum(t);
%ttt = find(diff([t; 0]));
%tttt = tt(ttt);
tttt = tt(diff([t; 0])~=0);
t2 = zeros(1,size(content,1));
t2(content+1) = tttt;
H = t2(A+1);
if size(H,1) ~= size(A,1)
    H=H';
end

B=A;

IND =  reshape(1:m*n,[m,n]);
C = num2cell(IND);

updated = true(size(A));

iteration = 0;
while 1
    G=B+H;
    G=G.*updated;
    [maxg,startindex] = max(G(:));
    
    [bestsom] = max(B(:));
    
    if maxg<=bestsom
        break
    end
    
    if maxg==0
        break
    end
    
    iteration = iteration+1;
    i = mod(startindex,m);
    j = ceil(startindex/m);
    if i==0
        i=m;
    end
    
    if 1<i && A(i-1,j)<=A(i,j)
        verplaatsindex = IND(i-1,j);
        if all(verplaatsindex~=C{i,j})
            [B(verplaatsindex),which] = max([B(verplaatsindex),B(i,j)+A(verplaatsindex)]);
            if which == 2
                updated(verplaatsindex)=true;
                C{verplaatsindex} = [C{i,j} verplaatsindex];
            end
        end
    end
    
    if i<size(A,1) && A(i+1,j)<=A(i,j)
        verplaatsindex = IND(i+1,j);
        if all(verplaatsindex~=C{i,j})
            [B(verplaatsindex),which] = max([B(verplaatsindex),B(i,j)+A(verplaatsindex)]);
            if which == 2
                updated(verplaatsindex)=true;
                C{verplaatsindex} = [C{i,j} verplaatsindex];
            end
        end
    end
    if j<size(A,2) && A(i,j+1)<=A(i,j)
        verplaatsindex = IND(i,j+1);
        if all(verplaatsindex~=C{i,j})
            [B(verplaatsindex),which] = max([B(verplaatsindex),B(i,j)+A(verplaatsindex)]);
            if which == 2
                updated(verplaatsindex)=true;
                C{verplaatsindex} = [C{i,j} verplaatsindex];
            end
        end
    end
    if 1<j && A(i,j-1)<=A(i,j)
        verplaatsindex = IND(i,j-1);
        if all(verplaatsindex~=C{i,j})
            [B(verplaatsindex),which] = max([B(verplaatsindex),B(i,j)+A(verplaatsindex)]);
            if which == 2
                updated(verplaatsindex)=true;
                C{verplaatsindex} = [C{i,j} verplaatsindex];
            end
        end
    end
    
    updated(i,j)=false;
    
end

[bestsom,index]=max(B(:));
vine = fliplr(C{index});

end

function [vine bestScore] = SimpleLongestPath( board )
% Treats the board as a directed-acyclic-graph and finds the best
% possible solution. Upper-left wins to break cycles in the graph
% (when adjacent squares have the same value).
%
% This is basically a completely rewritten version of the sebastian()
% function, and is about 15 times faster than sebastian() on the contest
% machine.
%
% This function is only called 8 times presently on the sample set so it
% doesn't make much difference. I optimised it so extremely expecting to use it as
% a candidate-scoring/fitness function as part of some sort of larger algorithm.
%
% - Wesley

[rows cols] = size( board );
count = rows * cols;
sentinel = count + 1;

board = board(:);
score = [board; 0];

seq = reshape( 1:count, rows, cols );

north = [sentinel(ones( 1, cols )); seq(1:end-1,:)];
north = north(:);
north(board<score(north)) = sentinel;

south = [seq(2:end,:); sentinel(ones( 1, cols ))];
south = south(:);
south(board<score(south)) = sentinel;

west = [sentinel(ones( rows, 1 )); (1:count-rows)'];
west(board<score(west)) = sentinel;

east = [(rows+1:count)'; sentinel(ones( rows, 1 ))];
east(board<score(east)) = sentinel;

prev = zeros( sentinel, 1 );

[nill, order] = sort( board );
for i = 1:count
    curr = order(i);
    
    % Yes, this fixed size (4) sorting network really
    % is faster than using max() for some reason.
    
    northNeighbour = north(curr);
    northScore = score(northNeighbour);
    
    southNeighbour = south(curr);
    southScore = score(southNeighbour);
    
    if northScore >= southScore
        scoreNS = northScore;
        neighbourNS = northNeighbour;
    else
        scoreNS = southScore;
        neighbourNS = southNeighbour;
    end
    
    westNeighbour = west(curr);
    westScore = score(westNeighbour);
    
    eastNeighbour = east(curr);
    eastScore = score(eastNeighbour);
    
    if westScore >= eastScore
        scoreEW = westScore;
        neighbourEW = westNeighbour;
    else
        scoreEW = eastScore;
        neighbourEW = eastNeighbour;
    end
    
    if scoreEW >= scoreNS
        prev(curr) = neighbourEW;
        score(curr) = score(curr) +  scoreEW;
    else
        prev(curr) = neighbourNS;
        score(curr) = score(curr) +  scoreNS;
    end
end

[bestScore c] = max( score );
for i = 1:count
    seq(i) = c;
    c = prev(c);
    if c == sentinel
        break
    end
end
vine = seq(i:-1:1);
end

% robert
function [moves, vine, score] = robert(board, limit)

% The Fragrant Honeysuckle gives up on moving and just tries to produce
% some prettier vines 8-)

% Faster to use isconnected logic, or to embed in a zeros(m+1,n+1) and guard?


% Grow a simple vine on given board
%[vine, score, dirsimple, moves]  = robert2(board);


% Try constructing a boardwalk down left side
[movesb, boardb] = robert1(board, limit);
[vineb, vscoreb, dirsimple] = robert2(boardb);     % Rerun vine code on modified board


% Improve score on board 47 and similar that feature a steady slope and speckle

IsMonotonous = ~(any(dirsimple(vineb) == 1) && any(dirsimple(vineb) == -1));
if IsMonotonous
    % Only bother if I have a decent score already and vine goes
    % solely up or solely down.
    [movesm, boardm] = monotonous(board, vineb, dirsimple, limit);
    [vinem, vscorem] = SimpleLongestPath(boardm);     % Rerun vine code on modified board
end

% Pick best
vine = vineb;
moves = movesb;
score = vscoreb;
if IsMonotonous && vscorem > score
    vine = vinem;
    moves = movesm;
    score = vscorem;
end

end % solver function

function [moves, board] = monotonous(boardin, vine, dir, limit)

% Focus n high-scoring vines with strong vertical orientation and high limit,
% and aim to shuffle blocking values out of high-scoring rows.
% Should never damage a unidirectional vine but ineffective unless the
% board has the structure of board 47

moves = [];
board = boardin;
[rows,cols] = size(board);
boardsize   = numel(board);
lastdir = dir(vine(end));       % initialise with vine top
for i = size(vine,1)-1:-1:2     % walk down vine to polish high scores first
    if abs(dir(vine(i))) == 1   % found a vertical step
        valmin = board(vine(i)+dir(vine(i)));
        valmax = board(vine(i)); % range of non-blocking values
        %            [row,col] = ind2sub([rows,cols],vine(i));
        row=rem(vine(i)-1,rows)+1;
        col=(vine(i)-row)/rows+1;
        if lastdir > 0 && vine(i)+lastdir <= boardsize-cols
            % a right edge in mid board
            moveToCol = col+1;
            [board,moves]=oftl(board,moves,limit,row,moveToCol,valmin,valmax,cols,rows);
            row = row - 1;
            if row > 0          % Needed?
                moveToCol = col+1;
                [board,moves]=oftl(board,moves,limit,row,moveToCol,valmin,valmax,cols,rows);
            end % if second row > 0
        end % if we have a midboard right edge
        
        
        % Now repeat whole thing for left edges.  Should be a minor pickup
        % from having more moves in high-scoring areas.
        % Check lastedge logic when I make 2 upward moves in a row
        
        
        if lastdir == -cols && vine(i) > cols
            % a left edge in mid board.  Check logic.
            moveToCol = col-1;
            while size(moves,1) < limit  % loop through all blockages (if any)
                while ( board(row,moveToCol) >= valmin && ...
                        board(row,moveToCol) <= valmax    )  && moveToCol > 1
                    moveToCol = moveToCol - 1;
                end
                if moveToCol > 1 % Found a blockage I'd like to replace
                    moveFromCol = moveToCol-1;
                    while moveFromCol > 0 && ...
                            ( board(row,moveFromCol) < valmin || ...
                            board(row,moveFromCol) > valmax        )
                        moveFromCol = moveFromCol - 1;
                    end
                    if moveFromCol > 0
                        % Something to replace it with exists, so do slide
                        for j = moveFromCol:moveToCol-1
                            if size(moves,1) < limit
                                moves = [moves; [row+rows*(j-1), row+rows*j]];
                                board(row,j+1) = board(row,j);
                                board(row,j) = 0;
                            else
                                break;  % Used up all moves
                            end
                        end
                    else
                        break;  % no more nonblocks to use so row finished
                    end
                else
                    break;      % no blocks so row finished
                end             % (needed in case block is in other row...?)
            end % First row while loop.  Break out when complete and apply
            % same logic to second row
        end % if we have a midboard left edge
        
    end % vertical step
    lastdir = dir(vine(i));
end % for each leaf of vine

% Have now modified board, hopefully improved it in a few high-scoring cases

end % function monotonous

function [board,moves]=oftl(board,moves,limit,row,moveToCol,valmin,valmax,cols,rows)

while size(moves,1) < limit  % loop through all blockages (if any)
    while ( board(row,moveToCol) >= valmin && ...
            board(row,moveToCol) <= valmax    )  && moveToCol <= cols-1
        moveToCol = moveToCol + 1;
    end
    if moveToCol < cols % Found a blockage I'd like to replace
        moveFromCol = moveToCol+1;
        while moveFromCol <= cols && ...
                ( board(row,moveFromCol) < valmin || ...
                board(row,moveFromCol) > valmax        )
            moveFromCol = moveFromCol + 1;
        end
        if moveFromCol <= cols
            % Something to replace it with exists, so do slide
            for j = moveToCol:moveFromCol-1
                if size(moves,1) < limit
                    moves = [moves; [(row+rows*j), (row+rows*(j-1))]];
                    board(row,j) = board(row,j+1);
                    board(row,j+1) = 0;
                else
                    break;  % Used up all moves
                end
            end
        else
            break;  % no more nonblocks to use so row finished
        end
    else
        break;      % no blocks so row finished
    end             % (needed in case block is in other row...?)
end
end

function [moves, board] = robert1(boardin, limit)
% Focus n high-score boards like 8 where there is a high limit but no structure.
% Aim to construct a path from scratch. To keep the movement choices simple do
% this along an edge; a spiral in centre would require far fewer moves on
% average but would require more complex pathfinding

% Minor bug with equal values, which may upset vine constructor so add a small
% amount of noise.

moves = zeros(limit,2); mv=0;
[rows,cols] = size(boardin);
boardsize   = numel(boardin);
board = boardin - reshape(1:boardsize,size(boardin))*1e-4;
PathLenEst  = (rows+cols) / 2;
NMovesEst   = limit / PathLenEst;   % Could update during process...
Channels    = 1:3:rows;             % Move blocks down these
Target      = 1;                    % Pick a corner, any corner
while mv < limit         % Find another block to move
    [Biggest,BlockAt] = max(board(:));    % Move biggest
    if Biggest <= 0                 % Prob not needed
        break;
    end
    %    [Vt,Ut] = ind2sub([rows,cols],Target);
    Vt=rem(Target-1,rows)+1;
    Ut=(Target-Vt)/rows+1;
    
    % First move onto a channel that will be cleared of blocks
    %    [Vb,Ub] = ind2sub([rows,cols],BlockAt);
    Vb=rem(BlockAt-1,rows)+1;
    Ub=(BlockAt-Vb)/rows+1;
    if Ub-Ut > 1     % Only if not next to target column
        Nudge = 1-mod(Vb-1,3);    % [+1,0,-1,...]
        if (Nudge ~= 0) && ~(Vb==rows && Nudge==1)
            %moves = [moves; [BlockAt,BlockAt+Nudge]];
            mv=mv+1; moves(mv,1:2) = [BlockAt,BlockAt+Nudge];
            board(BlockAt+Nudge) = board(BlockAt);
            board(BlockAt) = 0;
            BlockAt = BlockAt+Nudge;
        end
    end
    
    % Now move towards target
    Vb = rem(BlockAt-1,rows)+1; U = Ut-(BlockAt-Vb)/rows-1;
    V = Vt-Vb;      % Horiz and Vert moves required
    
    while (U~=0 || V~=0) && mv<limit
        if U<-1 || V==0
            mv=mv+1; moves(mv,1:2) = [BlockAt,BlockAt-rows];
            board(BlockAt-rows) = board(BlockAt);
            board(BlockAt) = 0;
            BlockAt = BlockAt-rows;
            U = U+1;
        elseif V>0         % Just ignore erases until I get it working
            mv=mv+1; moves(mv,1:2) = [BlockAt,BlockAt+1];
            board(BlockAt+1) = board(BlockAt);
            board(BlockAt) = 0;
            BlockAt = BlockAt+1;
            V=V-1;
        else
            mv=mv+1; moves(mv,1:2) = [BlockAt,BlockAt-1];
            board(BlockAt-1) = board(BlockAt);
            board(BlockAt) = 0;
            BlockAt = BlockAt-1;
            V=V+1;
        end
    end  % Sliding this block
    board(Target) = -board(Target);  % Ignore moved blocks
    if mod(Ut,2)                     % Walk Target forward
        if Vt < rows
            Target=Target+1;
        else
            Target=Target+rows;
        end
    else
        if Vt > 1
            Target=Target-1;
        else
            Target=Target+rows;
        end
    end
end % Finding blocks to slide
board = abs(board);
moves=moves(1:mv,:);
end % function boardwalk

function [vine, vscore, dir, moves] = robert2(board)

% Test each square on the board from low to high values to find whether vine
% can grow upwards onto an adjacent target square.

% To handle plateaux I superimpose a faint watermark on flat areas to nudge vine
% towards a space-covering pattern.  On each plateau I track 4 orientations
% separately, but whenever looking up to a higher level I can pick the best.

% Quite pretty, but as all plateaux problems in testset are low-scoring I don't
% think it makes much difference.

%

dir   = zeros(size(board));  % points way down vine, 0 at root
%   done  = false(size(board));  % have already examined this one
[rows,cols] = size(board);
boardsize   = numel(board);
watermark = reshape(1:boardsize,size(board)) * 1e-6;
watermark(:,2:2:cols) = flipud(watermark(:,2:2:cols));
board = board + watermark .* (mod(board,2)-0.5);
% superimpose a faint watermark on flat areas.  Direction should change
% between adjacent levels (but will fail if steps are even)
score = board;                % score for a vine starting and ending here
[val, ind]  = sort(board(:));

% Loop through board from low to high values to find the score associated
% with the best vine growing down from each square
% Needs more care on equal values, for now just weave up and down
%   -- Could try 4 weaves and pick best, or proper handling of plateaux

for i = 1:boardsize;
    test = ind(i);
    stepvec = [-rows,-1,1,rows];
    for step = stepvec;
        targ = test + step;
        if targ > 0 && targ <= boardsize && ...
                (abs(step)==rows || mod(min(test,targ), rows))
            % consider only adjacent squares on board
            if (board(targ) > board(test)) && (board(targ)+score(test) > score(targ))
                % Targ can grow from me (and has nothing better yet)
                score(targ) = score(test) + board(targ);
                % add test vine to targ score
                dir(targ) = -step;
                % and note where it came from
            end
        end
    end
end

% Assemble vine from top down
[ABHI,leaf] = max(score(:));
vine = [];
while leaf
    vine = [vine;leaf];
    if dir(leaf)
        leaf = leaf+dir(leaf);
    else
        leaf = 0;
    end
end

vine = flipud(vine);  % return it in correct order

vscore = score(vine(end));
moves = [];
end % growvine