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

pf3pushmixfull

by Nicholas Howe

Status: Passed
Results: 65341252 (cyc: 106, node: 11832)
CPU Time: 87.686
Score: 654729.0
Submitted at: 2011-11-09 16:48:57 UTC
Scored at: 2011-11-09 17:22:32 UTC

Current Rank: 7th (Highest: 1st )

Comments
Nicholas Howe
09 Nov 2011
Check out the spiral on board #8 of the sample testsuite. If you want to see how it gets built, uncomment lines 1576-1583.
Alfonso Nieto-Castanon
09 Nov 2011
Very nice trajectories! (my own spiral code in lasttry03 uses a worse path finding strategy but it limits the candidate movements to within a fixed radius of the current vine, which might explain why it still works better in some cases)
Please login or create a profile.
Code
function [moves, vine] = pf3pushmixfull(board, limit)

    [m,n] = size(board);

    % Gwendolyn's neat board-tuning
    if limit > 0
        board(board<median(board(:))/110)=0;
    end

    %Allocate result cell
    resultcell(:,3) = num2cell(-inf(10,1));

    id = reshape( 1:m*n, m, n);

    limitlimit = 15100;
    if limit < limitlimit
        [resultcell{1,1}, resultcell{1,2}, resultcell{1,3}] = alfi(rot90(board,3), limit);
        idtemp = rot90(id,3);
        resultcell{1,1} = idtemp(resultcell{1,1});
        resultcell{1,2} = idtemp(resultcell{1,2});
    end

    largestValue = max(board(:));

    if largestValue > 200
        if limit > 0
            [movestemp, vinetemp, resultcell{2,3}] = robert(fliplr(board),limit); % monotonous should work good on flipping lr/ud as well
            idtemp = fliplr(id);
            resultcell{2,1} = idtemp(movestemp);
            resultcell{2,2} = idtemp(vinetemp);
            [movestemp, vinetemp, resultcell{3,3}] = robert((board),limit);
            idtemp = (id);
            resultcell{3,1} = idtemp(movestemp);
            resultcell{3,2} = idtemp(vinetemp);
            [movestemp, vinetemp, resultcell{10,3}] = robert(flipud(board),limit);
            idtemp = flipud(id);
            resultcell{10,1} = idtemp(movestemp);
            resultcell{10,2} = idtemp(vinetemp);
            [resultcell{9,1}, resultcell{9,2}, resultcell{9,3}] = dofilter(board,limit);
        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)
            [resultcell{4,2}, resultcell{4,3}] = real_kurt(board);
        end
        if (limit < 3500)
            [moves5,vine5,score5] = nick(board,limit);
            [moves6,vine6,score6] = nick(board',limit);
            [resultcell{5,1}, resultcell{5,2}, resultcell{5,3}] = nick(board,limit);
            [movestemp, vinetemp, resultcell{7,3}] = nick(rot90(board,2),limit);
            idtemp = rot90(id,2);
            resultcell{7,1} = idtemp(movestemp);
            resultcell{7,2} = idtemp(vinetemp);
            if max(cell2mat(resultcell([5 7],3))) < 2 * max(cell2mat(resultcell([1 2 3 4 9 10],3)))
                [movestemp, vinetemp, resultcell{6,3}] = nick(board',limit);
                idtemp = id';
                resultcell{6,1} = idtemp(movestemp);
                resultcell{6,2} = idtemp(vinetemp);
                [movestemp, vinetemp, resultcell{8,3}] = nick(rot90(board,3),limit);
                idtemp = rot90(id,3);
                resultcell{8,1} = idtemp(movestemp);
                resultcell{8,2} = idtemp(vinetemp);
            end
        else
            [moves6,vine6,score6] = spiral(board',limit);
            [resultcell{5,1}, resultcell{5,2}, resultcell{5,3}] = nick(board,limit);
            [movestemp, vinetemp, resultcell{7,3}] = spiral(rot90(board,2),limit);
            idtemp = rot90(id,2);
            resultcell{7,1} = idtemp(movestemp);
            resultcell{7,2} = idtemp(vinetemp);
            if max(cell2mat(resultcell([5 7],3))) < 2 * max(cell2mat(resultcell([1 2 3 4 9 10],3)))
                [movestemp, vinetemp, resultcell{6,3}] = spiral(board',limit);
                idtemp = id';
                resultcell{6,1} = idtemp(movestemp);
                resultcell{6,2} = idtemp(vinetemp);
                [movestemp, vinetemp, resultcell{8,3}] = spiral(rot90(board,3),limit);
                idtemp = rot90(id,3);
                resultcell{8,1} = idtemp(movestemp);
                resultcell{8,2} = idtemp(vinetemp);
            end
        end;
    end
    [~,best_index]=max(cell2mat(resultcell(:,3)));

    moves = resultcell{best_index,1};
    vine = resultcell{best_index,2};

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

end

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

moves = zeros(limit,2);
[nrow,ncol] = size(board);
if (limit < nrow-1)
    scr = -inf;
    moves = [];
    vine = [];
    return;
end;
ntot = nrow*ncol;
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));
nextfit = 1;
steps = 0;
cboard = board;
radius = ceil((nrow+ncol)/10);
tops = inf;
avail = true(nrow,ncol);
local = ~all(min(board(:,1:end-1))>max(board(:,2:end)))&(limit<3000);
for i = 1:ntot
    tx = xg(fitloc(nextfit));
    ty = yg(fitloc(nextfit));
    if (i > 4)&local
        fylo = max(1,min(ty-radius,nrow-2*radius));
        fyhi = min(nrow,max(ty+radius,1+2*radius));
        fxhi = min(ncol,tx+2*radius);
    else 
        % special case for outliers
        fylo = 1;
        fyhi = nrow;
        fxhi = ncol;
    end;
    fboard = cboard(fylo:fyhi,tx:fxhi).*avail(fylo:fyhi,tx:fxhi);
    [cy,cx] = find(fboard==max(fboard(:).*(fboard(:)<=tops)));
    if (numel(cy)>1)
        % pick nearest
        dsq = (cx-tx).^2+(cy-ty).^2;
        [~,mini] = min(dsq);
        cx = cx(mini);
        cy = cy(mini);
    end;
    if isempty(cx)
        break;
    end;
    cy = cy+fylo-1;
    cx = cx+tx-1;
    tops = cboard(cy,cx);
    if (tops==0)
        break;
    end;
    while (cx~=tx)||(cy~=ty)
        dx = sign(tx-cx);
        dy = sign(ty-cy);
        if (dx~=0)&&(dy~=0)
            if ((cboard(cy,cx+dx)>tops)|(cboard(cy,cx+dx)<=cboard(cy+dy,cx)))&avail(cy,cx+dx)
                dy = 0;
            else
                dx = 0;
            end;
        end;
        if (board(cy+dy,cx+dx)>0)
            vx = cx+dx;
            vy = cy+dy;
            if (dx==0)&(cboard(vy,vx)<tops)
                if (vx>1)&&(((cboard(vy,vx-1)>tops)&avail(vy,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;
                    %assert(avail(vy,vx-1));
                    moves(steps,1) = pos(vy,vx);
                    moves(steps,2) = pos(vy,vx-1);
                    cboard(vy,vx-1) = cboard(vy,vx);
                    cboard(vy,vx) = 0;
                elseif (vx < ncol)&((cboard(vy,vx)>cboard(vy,vx+1))|((cboard(vy,vx+1)>tops)&avail(vy,vx+1)))
                    % move right
                    steps = steps+1;
                    if (steps > limit)
                        break;
                    end;
                    %assert(avail(vy,vx+1));
                    moves(steps,1) = pos(vy,vx);
                    moves(steps,2) = pos(vy,vx+1);
                    cboard(vy,vx+1) = cboard(vy,vx);
                    cboard(vy,vx) = 0;
                end;
            elseif (cboard(vy,vx)<tops)
                if (vy>1)&&(((cboard(vy-1,vx)>tops)&avail(vy-1,vx))|((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;
                    %assert(avail(vy-1,vx));
                    moves(steps,1) = pos(vy,vx);
                    moves(steps,2) = pos(vy-1,vx);
                    cboard(vy-1,vx) = cboard(vy,vx);
                    cboard(vy,vx) = 0;
                elseif (vy < nrow)&&((cboard(vy,vx)>cboard(vy+1,vx))|((cboard(vy+1,vx)>tops)&avail(vy+1,vx)))
                    % move right
                    steps = steps+1;
                    if (steps > limit)
                        break;
                    end;
                    %assert(avail(vy+1,vx));
                    moves(steps,1) = pos(vy,vx);
                    moves(steps,2) = pos(vy+1,vx);
                    cboard(vy+1,vx) = cboard(vy,vx);
                    cboard(vy,vx) = 0;
                end;
            end;
        end;
        steps = steps+1;
        if (steps > limit)
            break;
        end;
        %assert(avail(cy+dy,cx+dx));
        moves(steps,1) = pos(cy,cx);
        moves(steps,2) = pos(cy+dy,cx+dx);
        cboard(cy+dy,cx+dx) = cboard(cy,cx);
        cboard(cy,cx) = 0;
        cx = cx+dx;
        cy = cy+dy;
    end;
    if (steps > limit)
        break;
    end;
    avail(ty,tx) = false;
    nextfit = nextfit+1;
end;
moves = moves(1:min(steps,limit),:);
% visualize
% cboard = board;
% for i = 1:size(moves,1)
%     cboard(moves(i,2)) = cboard(moves(i,1));
%     cboard(moves(i,1)) = 0;
%     imagesc(cboard);
%     axis image;
%     drawnow;
% end;
% end visualize
[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);
    %% Uncomment to get this running with TMW's
    %% test environment.
    %% Comment it out prior to submission. :-/
    % tmp = max(board(vine));
    % if ~isempty(tmp)
        % larger_i = find(board >= tmp);
        % larger_i = larger_i( ~ismemberSimpl(larger_i, vine) ); % setdiff( larger_i, vine )
    % else
        % larger_i = [];
    % end
    if isempty(vine)
        moves = [];
        return;
    end;
    larger_i = find(board >= max(board(vine)));
    larger_i = larger_i( ~ismemberSimpl(larger_i, vine) ); % setdiff( larger_i, vine )
    if ~isempty(larger_i)
        end_row = mod(vine(end)-1,m)+1;
        end_col = ceil(vine(end)/m);

        larger_rows = mod(larger_i-1,m)+1;
        larger_cols = ceil(larger_i/m);

        moves_req = abs(end_row - larger_rows) + abs(end_col - larger_cols) - 1;
        msk = moves_req < extra_moves;
        possible_moves = larger_i( msk );
        moves_req = moves_req( msk );

        while ~isempty(possible_moves) && extra_moves > 0
            [~, sort_i] = sort(moves_req);

            possible_moves = possible_moves(sort_i);

            test_move = possible_moves(1);
            test_row = mod(test_move-1,m)+1;
            test_col = ceil(test_move/m);
            move_cols = test_col(ones(1, 1+abs(end_row-test_row)));

            if end_row > test_row
                move_rows = test_row:end_row;
            elseif end_row < test_row
                move_rows = test_row:-1:end_row;
            else
                move_rows = [];
                move_cols = [];
            end

            if end_col == test_col
                move_rows(end) = [];
                move_cols(end) = [];
            elseif end_col > test_col
                move_cols = [move_cols, test_col+1:end_col-1];
                move_rows = [move_rows, end_row(ones(1, end_col-test_col-1))];
            else
                move_cols = [move_cols, test_col-1:-1:end_col+1];
                move_rows = [move_rows, end_row(ones(1, test_col-end_col-1))];
            end

            add_moves = move_cols(:)*m + move_rows(:) - m;
            add_moves = [add_moves(1:end-1), add_moves(2:end)];

            if any( ismemberSimpl(add_moves(:),vine) )
                possible_moves(1) = [];
                moves_req(1) = [];
            else
                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)-1,m)+1;
                end_col = ceil(vine(end)/m);

                larger_i = find(board >= max(board(vine)));
                larger_i = larger_i( ~ismemberSimpl(larger_i, vine) );   % setdiff( larger_i, vine )
                larger_rows = mod(larger_i-1,m)+1;
                larger_cols = ceil(larger_i/m);

                moves_req = abs(end_row - larger_rows) + abs(end_col - larger_cols) - 1;
                msk = moves_req < extra_moves;
                possible_moves = larger_i(msk);
                moves_req = moves_req(msk);
            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)
            correction = cboard(cy,cx+dx)<=cboard(cy+dy,cx);
            dy = dy*(1-correction);
            dx = dx*correction;
        end
        if (rank(cy+dy,cx+dx)>0)
            vx = cx+dx;
            vy = cy+dy;
            if (dx==0)
                [steps,moves,cboard,rank,remain,breakmarker]=oftl5(steps,limit,moves,pos,vy,vx,cboard,rank,remain,1,0,vx,ncol,cy,dy,cx,dx);
            else
                [steps,moves,cboard,rank,remain,breakmarker]=oftl5(steps,limit,moves,pos,vy,vx,cboard,rank,remain,0,1,vy,nrow,cy,dy,cx,dx);
            end;
            if breakmarker
                break
            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 [steps,moves,cboard,rank,remain,breakmarker]=oftl5(steps,limit,moves,pos,vy,vx,cboard,rank,remain,stepx,stepy,v_main,n_main,cy,dy,cx,dx)

    if v_main > 1 && cboard(vy,vx)>cboard(vy-(stepy~=0),vx-(stepx~=0)) && ( v_main==n_main || (cboard(vy+(stepy~=0),vx+(stepx~=0))>cboard(vy-(stepy~=0),vx-(stepx~=0))) )
        [steps,moves,cboard,rank,remain,breakmarker]=oftl3(steps,limit,moves,pos,vy,vx,cboard,rank,remain,-stepx,-stepy);
    elseif (v_main < n_main)&&(cboard(vy,vx)>cboard(vy+(stepy~=0),vx+(stepx~=0)))
        [steps,moves,cboard,rank,remain,breakmarker]=oftl3(steps,limit,moves,pos,vy,vx,cboard,rank,remain,stepx,stepy);
    else
        remain(rank(cy+dy,cx+dx)) = 0;
        breakmarker = 0;
    end;

end

function [steps,moves,cboard,rank,remain,breakmarker]=oftl3(steps,limit,moves,pos,vy,vx,cboard,rank,remain,stepx,stepy)
    steps = steps+1;
    if (steps > limit)
        breakmarker = 1;
    else
        breakmarker = 0;
        moves(steps,1) = pos(vy,vx);
        moves(steps,2) = pos(vy+stepy,vx+stepx);
        cboard(vy+stepy,vx+stepx) = cboard(vy,vx);
        cboard(vy,vx) = 0;
        if (rank(vy+stepy,vx+stepx)>0)
            remain(rank(vy+stepy,vx+stepx)) = 0;
        end;
        rank(vy+stepy,vx+stepx) = rank(vy,vx);
        rank(vy,vx) = 0;
    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
            [nmove,moves]=oftl6(i,ncol,bad,moves,nmove,limit,pos);
            if (nmove>=limit)
                break
            end;
        end;
        moves = moves(1:min(nmove,limit),:);
        for i = 1:size(moves,1)
            board(moves(i,:)) = [0 board(moves(i,1))];
        end;
        [vine,scr] = SimpleLongestPath(board);
    else
        scr = -inf;
        moves = [];
        vine = [];
    end
end

function [nmove,moves]=oftl6(i,ncol,bad,moves,nmove,limit,pos)
    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;

end

%% alfi
function [moves, vine, gain] = alfi(board, limit)
    moves=[];
    ab=accumarray(1+board(:),1);
    cab=flipud(cumsum(flipud(ab)))-ab(end);

    m = size(board,1) + 2;
    n = size(board,2) + 2;

    board2 = zeros( m, n );
    board2(2:end-1,2:end-1) = board;
    board = board2;
    board2 = [];

    boardab=cab(1+board);
    if max(ab(2:end))>1,
        % 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(:).*sqrt(ClusterSize(:)));
        % search within-clusters
        iC=bellman_postprocess(ClustersOrder,IdxList,IdxSegments,BoardCluster);
    else
        % search between-pixels
        %     iC = bellman_pixel(board,limit,boardab);
        iC = SimpleLongestPath( board );
        iC = fliplr(iC);
        iC = iC(board(iC)>0);
    end
    % post-processing moves
    if limit>0
        [board,iC,moves,limit] = postprocess(board,iC,moves,limit,boardab);
        %    [iC1,iC2]=ind2sub([m,n],moves);
        iC1=rem(moves-1,m)+1;
        iC2=(moves-iC1)/m+1;
        %    moves=sub2ind([m-2,n-2],iC1-1,iC2-1);
        moves=iC1-1+(m-2)*(iC2-2);
    end

    %[iC1,iC2]=ind2sub([m,n],iC);
    iC1=rem(iC-1,m)+1;
    iC2=(iC-iC1)/m+1;
    %vine=sub2ind([m-2,n-2],iC1-1,iC2-1);
    vine=iC1-1+(m-2)*(iC2-2);
    vine=fliplr(vine);
    board=board(2:end-1,2:end-1);
    gain=sum(board(vine));

end

function [board,tiC,moves,limit] = postprocess(board,tiC,moves,limit,boardab)
    [m,n]=size(board);
    nC=numel(tiC);
    tP=board>0;
    maxIter = 1e2;
    if nC>1&&limit>0, %%%
        % grow laterally
        d=abs(diff(tiC))==1;
        E=[m*~d+d; m*d+~d];
        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:maxIter
            [board,moves,tiC,tP,E,limit,ok]=postprocess_lateral(board,moves,tiC,tP,E,limit,BorderDown,BorderUp,m);
            if ~ok, break; end
        end
    end
    if limit>0
        % grow end-points
        %    tP=board>0;
        tP(tiC)=false;
        for n1=1:maxIter
            [board,moves,tiC,tP,limit,ok]=postprocess_endpoint(board,moves,tiC,tP,limit,1,m,n);
            if ~ok, break; end
        end
        for n1=1:10*maxIter
            [board,moves,tiC,tP,limit,ok]=postprocess_endpoint(board,moves,tiC,tP,limit,2,m,n);
            if ~ok, break; end
        end
    end
end

function [board,moves,tiC,tP,E,limit,ok]=postprocess_lateral(board,moves,tiC,tP,E,limit,BorderDown,BorderUp,m)
    ok=0;
    for ndir=1:4
        offset = ndir>2.5;
        coeff = (2*mod(ndir,2)-1);
        K=size(tiC,2);
        idx1=find(tP(tiC((1+offset):2:K-1)+coeff*E(2,(1+offset):2:K-1))&tP(tiC((2+offset):2:K)+coeff*E(2,(1+offset):2:K-1)));
        for n2=numel(idx1):-1:1, %%%
            switch(ndir)
                case {1,3}
                    tempA=tiC(2*idx1(n2)-1+offset)+E(2,2*idx1(n2)-1+offset):E(2,2*idx1(n2)-1+offset):BorderDown{1+(E(2,2*idx1(n2)-1+offset)==m)}(tiC(2*idx1(n2)-1+offset));
                    tempB=tiC(2*idx1(n2)+offset)+E(2,2*idx1(n2)-1+offset):E(2,2*idx1(n2)-1+offset):BorderDown{1+(E(2,2*idx1(n2)-1+offset)==m)}(tiC(2*idx1(n2)+offset));
                case {2,4}
                    tempA=tiC(2*idx1(n2)-1+offset)-E(2,2*idx1(n2)-1+offset):-E(2,2*idx1(n2)-1+offset):BorderUp{1+(E(2,2*idx1(n2)-1+offset)==m)}(tiC(2*idx1(n2)-1+offset));
                    tempB=tiC(2*idx1(n2)+offset)-E(2,2*idx1(n2)-1+offset):-E(2,2*idx1(n2)-1+offset):BorderUp{1+(E(2,2*idx1(n2)-1+offset)==m)}(tiC(2*idx1(n2)+offset));
            end
            idxZ=find(~tP(tempA),1,'first');
            [nill,idxA]=max((1./(abs(board(tiC(2*idx1(n2)-1+offset))-board(tempA))+1)).*(board(tiC(2*idx1(n2)-1+offset))>=board(tempA)&board(tempA)>=board(tiC(2*idx1(n2)+offset))));
            if ~nill,idxA=[]; end
            if ~isempty(idxA)&&idxA<idxZ
                idxZ=find(~tP(tempB),1,'first');
                idxB=find(board(tempA(idxA))>=board(tempB)&board(tempB)>=board(tiC(2*idx1(n2)+offset)),1,'first');
                if ~isempty(idxB)&&idxB<idxZ&&idxA+idxB-2<=limit
                    ok=1;
                    tiC=[tiC(1:2*idx1(n2)-1+offset),tiC(2*idx1(n2)-1+offset)+coeff*E(2,2*idx1(n2)-1+offset), tiC(2*idx1(n2)+offset)+coeff*E(2,2*idx1(n2)-1+offset), tiC((2*idx1(n2)+offset):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;
                    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);
                end
            end
        end
    end
end

function [board,moves,tiC,tP,limit,ok]=postprocess_endpoint(board,moves,tiC,tP,limit,type,m,n)
    %[m,n]=size(board);
    ok=1;
    switch(type)
        case 1
            mask=tP&board<2*board(tiC(1));
            D=Dijkstra(mask,tiC(1),m,n);
            idx1=find(mask&D-1<=limit&board>=board(tiC(1)));
            if isempty(idx1),
                mask=tP;
                D=Dijkstra(mask,tiC(1),m,n);
                idx1=find(mask&D-1<=limit&board>=board(tiC(1)));
                if isempty(idx1),ok=0;end
            end
            if ok
                if limit>150
                    [~,idx2]=min(board(idx1)+1e-3*D(idx1)); %%%t3
                else
                    [~,idx2]=min(board(idx1).*(D(idx1)/limit).^0.2); %%%t3
                end

                idx0=idx1(idx2);
                limit=limit-(D(idx0)-1);
                for n2=D(idx0)-1:-1:1
                    tidx0 = idx0 + (D(idx0+1)==n2) + (~(D(idx0+1)==n2))*(-(D(idx0-1)==n2)+(~(D(idx0-1)==n2))*(m*(D(idx0+m)==n2)+(~(D(idx0+m)==n2))*(-m*(D(idx0-m)==n2))));
                    moves=[moves; idx0, tidx0];
                    board(tidx0)=board(idx0);
                    board(idx0)=0;
                    idx0=tidx0;
                end
                tiC=[idx0,tiC];
                tP(idx0)=false;
            end
        case 2
            mask=tP;
            D=Dijkstra(mask,tiC(end),m,n);
            idx1=find(mask&D-1<=limit&board<=board(tiC(end))&board>0);
            if isempty(idx1),ok=0;end
            if ok
                if limit>300
                    [~,idx2]=min(-board(idx1)+1e-3*D(idx1)); %%%t3
                else
                    [~,idx2]=min(-board(idx1).*(limit./D(idx1)).^0.085); %%%t3
                end
                idx0=idx1(idx2);
                limit=limit-(D(idx0)-1);
                for n2=D(idx0)-1:-1:1
                    tidx0 = idx0 + (D(idx0+1)==n2) + (~(D(idx0+1)==n2))*(-(D(idx0-1)==n2)+(~(D(idx0-1)==n2))*(m*(D(idx0+m)==n2)+(~(D(idx0+m)==n2))*(-m*(D(idx0-m)==n2))));
                    moves=[moves; idx0, tidx0];
                    board(tidx0)=board(idx0);
                    board(idx0)=0;
                    idx0=tidx0;
                end
                tiC=[tiC,idx0];
                tP(idx0)=false;
            end
    end
end

function iC = bellman(C,D)
    N=size(C,1);
    c=cell(1,N); for n1=1:N,c{n1}=find(C(:,n1)); end
    %C=full(C);
    IDX=zeros(N,1);
    cD=D;
    touched=true(1,N);
    while any(touched)
        for touch=find(touched),

            touched(touch) = false;
            idx = c{touch};
            cDnew = D(idx) + cD(touch);
            idx2 = (cD(idx)<cDnew);

            if any(idx2(:))
                idx         = idx(idx2);
                cD(idx)     = cDnew(idx2);
                touched(idx) = true;
                IDX(idx)    = touch;
            end
        end
    end
    [~,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(1:n1-1);
end

function iC = bellman_postprocess(ClustersOrder,IdxList,IdxSegments,BoardCluster)
    [m,n]=size(BoardCluster);
    iC=[];
    false1N = false(1,n);
    falseM1 = false(m,1);
    falseMN = false(m,n);
    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=falseMN;
            ThisCluster(idx)=true;
            D=Dijkstra(ThisCluster,iC,m,n);
            if n1==numel(ClustersOrder)
                temp=D(ThisCluster);
            else
                temp=D(ThisCluster).*(BoardCluster([false1N;ThisCluster(1:m-1,:)])==ClustersOrder(n1+1)|BoardCluster([ThisCluster(2:m,:);false1N])==ClustersOrder(n1+1)|BoardCluster([falseM1,ThisCluster(:,1:n-1)])==ClustersOrder(n1+1)|BoardCluster([ThisCluster(:,2:n),falseM1])==ClustersOrder(n1+1));
            end
            [~,idx0]=max(temp(:));
            idx0=idx(idx0);
            E=zeros(2,D(idx0)-1);
            tiC=zeros(1,D(idx0));
            tiC(end)=idx0;
            [E, tiC]=oftl8(D, idx0, E, m,tiC);
            % 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
            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 [E, tiC]=oftl8(D, idx0, E, m,tiC)
    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
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, ~, 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,m,n)
    D=inf(m,n);
    D(~A)=0;
    falseMN = false( m*n, 1);
    if isempty(i1),
        i1=find(A,1,'first');
        mode=0;
    else
        i1=i1(end);
        mode=1;
    end
    D(i1)=1;
    for n1=2:m*n,
        X = falseMN;

        X(i1(isinf(D(i1+1)))+1) = true;
        X(i1(isinf(D(i1-1)))-1) = true;
        X(i1(isinf(D(i1+m)))+m) = true;
        X(i1(isinf(D(i1-m)))-m) = true;
        %i1=unique([i1(idx1)+1,i1(idx2)-1,i1(idx3)+m,i1(idx4)-m]);

        i1=find(X);
        if isempty(i1), break; end
        D(i1)=n1;
    end
    if mode
        msk = D>0;
        D(msk)=D(msk)-1;
    end
end

%% kurt
function [vine, bestsom] = real_kurt(A)

    [m,n]=size(A);

    Asort = sort(A(:));
    content = unique(Asort);
    cumS = cumsum(Asort);
    tttt = cumS( diff(Asort) ~= 0 );    % tttt is to find non-plateaus...?
    t2 = zeros(size(content,1),1);
    t2(content+1) = [0; tttt];
    H = t2(A+1);
    if size(H,1) ~= m
        H=H';
    end

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

    updated = true(size(A));

    G = A+H;
    [maxG,idxStart] = max(G(:));
    B=A;

    while (maxG > max(B(:))) && maxG

        ii = mod(idxStart-1,m)+1;
        jj = ceil(idxStart/m);

        flag1 = ii > 1  && A(idxStart - 1) <= A(idxStart);
        flag2 = ii < m  && A(idxStart + 1) <= A(idxStart);
        flag3 = jj < n  && A(idxStart + m) <= A(idxStart);
        flag4 = jj > 1  && A(idxStart - m) <= A(idxStart);

        if flag1
            [B,C,updated] = oftl4( idxStart-1, idxStart,A,B,C,updated );
        end
        if flag2
            [B,C,updated] = oftl4( idxStart+1, idxStart,A,B,C,updated );
        end
        if flag3
            [B,C,updated] = oftl4( idxStart+m, idxStart,A,B,C,updated );
        end
        if flag4
            [B,C,updated] = oftl4( idxStart-m, idxStart,A,B,C,updated );
        end

        updated(idxStart) = false;

        G=(B+H).*updated;
        [maxG,idxStart] = max(G(:));
    end

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

end

function [B,C,updated]=oftl4(verplaatsindex,currIdx,A,B,C,updated )

    if (B(currIdx)+A(verplaatsindex) > B(verplaatsindex)) && ~sum(verplaatsindex==C{currIdx})   % Gwendothanks

        B(verplaatsindex) = B(currIdx) + A(verplaatsindex);
        updated(verplaatsindex)=true;
        C{verplaatsindex} = [C{currIdx} verplaatsindex];
    end

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

    [m, n] = size( board );
    count = m * n;
    sentinel = count + 1;

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

    nOnes = ones( 1,n );
    mOnes = ones( m,1 );

    seq = reshape( 1:count, m, n );

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

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

    west = [sentinel(mOnes); (1:count-m)'];
    west(board<score(west)) = sentinel;

    east = [(m+1:count)'; sentinel(mOnes)];
    east(board<score(east)) = sentinel;

    prev = zeros( sentinel, 1 );

    [~, order] = sort( board );

    for ii = seq(:).'
        curr = order(ii);

        % 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 ii = 1:count
        seq(ii) = c;
        c = prev(c);
        if c == sentinel
            break
        end
    end
    vine = seq(ii:-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
    if IsMonotonous && vscorem > vscoreb
        vine = vinem;
        moves = movesm;
        score = vscorem;
    else
        vine = vineb;
        moves = movesb;
        score = vscoreb;
    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;
                [board,moves]=oftl7(board,moves,limit,row,moveToCol,valmin,valmax,rows);
            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] = oftl7(board,moves,limit,row,moveToCol,valmin,valmax,rows)
    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

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;
    Target      = 1;                    % Pick a corner, any corner
    [Biggest,BlockAt] = max(board(:));    % Move biggest
    while mv < limit && Biggest > 0        % Find another block to move
        Vt=rem(Target-1,rows)+1;
        Ut=(Target-Vt)/rows+1;

        % First move onto a channel that will be cleared of blocks
        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)
                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

        [mv,moves,board]=oftl9(U, V, mv, limit, moves, BlockAt, rows, board);
        board(Target) = -board(Target);  % Ignore moved blocks
        Target=Target+(mod(Ut,2))*(Vt<rows)-(~mod(Ut,2))*(Vt>1)+rows*(mod(Ut,2))*(~(Vt<rows))+rows*(~mod(Ut,2))*(~(Vt>1));
        [Biggest,BlockAt] = max(board(:));    % Move biggest
    end % Finding blocks to slide
    board = abs(board);
    moves=moves(1:mv,:);
end % function boardwalk

function [mv,moves,board]=oftl9(U, V, mv, limit, moves, BlockAt, rows, board)
    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
end

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
    [~, 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

    stepvec = [-rows,-1,1,rows];

    for i = 1:boardsize;
        test = ind(i);
        if board(test) < .1
           continue
        end
        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
    [~,leaf] = max(score(:));
    vine = [];
    while dir(leaf)~=0
        vine = [vine;leaf];
        leaf = leaf+dir(leaf);
    end

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

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

function tf = ismemberSimpl( a, s )
    % behaves like ismember(a,s) for typical input and one output,
    % but has no error checking and is faster
    % MiVö

    [m,n] = size(a);
    tf = false(m,n);
    for ii = 1:m*n
        tf(ii) = any(a(ii)==s(:));
    end

end

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

moves = zeros(limit,2);
[nrow,ncol] = size(board);
if (limit < nrow-1)
    scr = -inf;
    moves = [];
    vine = [];
    return;
end;
ntot = nrow*ncol;
xg = repmat(1:ncol,nrow,1);
yg = repmat((1:nrow)',1,ncol);
pos = reshape(1:ntot,nrow,ncol);
nextfit = 1;
steps = 0;
cboard = board;
radius = ceil((nrow+ncol)/12);
tops = inf;
avail = true(nrow,ncol);
sqrad = max(abs(xg-ncol/2),abs(yg-nrow/2));
%th = mod(atan2(yg-nrow/2,xg-ncol/2)+pi/2-4*pi./(sqrad+2).^2,2*pi);
th = atan2(yg-nrow/2,xg-ncol/2);
%[~,fitloc] = sort(sqrad(:)+th(:)/8);
fitn = 0;
fitloc = zeros(nrow,ncol);
for i = reshape(unique(sqrad),1,[]);
    xmp = find(sqrad==i,1);
    ring1 = find((sqrad==i)&(th>th(xmp)));
    [~,r] = sort(th(ring1));
    fitloc(ring1(r)) = fitn+1:fitn+numel(ring1);
    fitn = fitn+numel(ring1);
    ring2 = find((sqrad==i)&(th<=th(xmp)));
    [~,r] = sort(th(ring2));
    fitloc(ring2(r)) = fitn+1:fitn+numel(ring2);
    fitn = fitn+numel(ring2);
end;
[~,fitloc] = sort(fitloc(:));
sxlo = xg(fitloc(1));
sxhi = xg(fitloc(1));
sylo = yg(fitloc(1));
syhi = yg(fitloc(1));
active = true(nrow,ncol);
for i = 1:ntot
    tx = xg(fitloc(nextfit));
    ty = yg(fitloc(nextfit));

    vect = [tx-ncol/2,ty-nrow/2];
    dir = vect./norm(vect,2);
    center = round([ncol/2 nrow/2]+vect+radius*dir);
    active(ty,tx) = true;
    active(ty+1:end,tx) = (ty==nrow)||(avail(ty+1,tx));
    active(1:ty-1,tx) = (ty==1)||(avail(ty-1,tx));
    active(ty,tx+1:end) = (tx==ncol)||(avail(ty,tx+1));
    active(ty,1:tx-1) = (tx==1)||(avail(ty,tx-1));
    active(ty+1:end,tx+1:end) = (ty==nrow)||(tx==ncol)||(avail(ty+1,tx+1));
    active(1:ty-1,1:tx-1) = (ty==1)||(tx==1)||(avail(ty-1,tx-1));
    active(1:ty-1,tx+1:end) = (ty==1)||(tx==ncol)||(avail(ty-1,tx+1));
    active(ty+1:end,1:tx-1) = (ty==nrow)||(tx==1)||(avail(ty+1,tx-1));
    
    [cy,cx] = find(avail&(cboard==max(cboard(avail(:)))));
    
    if (numel(cy)>1)
        % pick nearest
        dsq = (cx-tx).^2+(cy-ty).^2;
        [~,mini] = min(dsq);
        cx = cx(mini);
        cy = cy(mini);
    end;
    if isempty(cx)
        break;
    end;
    tops = cboard(cy,cx);
    if (tops==0)
        break;
    end;
    if ~active(cy,cx)
        % first move into active zone
        if (sylo==1)|(sxlo==1)|(syhi==nrow)|(sxhi==ncol)
            break;
        end;
        corners = [sylo-1 sxlo-1; sylo-1 sxhi+1; syhi+1 sxlo-1; syhi+1 sxhi+1];
        corners = corners(active(corners(:,1)+nrow*corners(:,2)-nrow),:);
        dcorner = sum((corners-repmat([cy cx],size(corners,1),1)).^2,2);
        [~,mini] = min(dcorner,[],1);
        ty2 = corners(mini,1);
        tx2 = corners(mini,2);
        
        while (cx~=tx2)||(cy~=ty2)
            dx = sign(tx2-cx);
            dy = sign(ty2-cy);
            if ((cx+dx<1)|(cx+dx>ncol))||~avail(cy,cx+dx)
                dx = 0;
            end;
            if ((cy+dy<1)|(cy+dy>nrow))||~avail(cy+dy,cx)
                dy = 0;
            end;
            if (dx~=0)&&(dy~=0)
                if ((cboard(cy,cx+dx)>tops)|(cboard(cy,cx+dx)<=cboard(cy+dy,cx)))&avail(cy,cx+dx)
                    dy = 0;
                else
                    dx = 0;
                end;
            end;
            if (board(cy+dy,cx+dx)>0)
                vx = cx+dx;
                vy = cy+dy;
                if (dx==0)&(cboard(vy,vx)<tops)
                    if (vx>1)&&(((cboard(vy,vx-1)>tops)&avail(vy,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;
                        %assert(avail(vy,vx-1));
                        moves(steps,1) = pos(vy,vx);
                        moves(steps,2) = pos(vy,vx-1);
                        cboard(vy,vx-1) = cboard(vy,vx);
                        cboard(vy,vx) = 0;
                    elseif (vx < ncol)&((cboard(vy,vx)>cboard(vy,vx+1))|((cboard(vy,vx+1)>tops)&avail(vy,vx+1)))
                        % move right
                        steps = steps+1;
                        if (steps > limit)
                            break;
                        end;
                        %assert(avail(vy,vx+1));
                        moves(steps,1) = pos(vy,vx);
                        moves(steps,2) = pos(vy,vx+1);
                        cboard(vy,vx+1) = cboard(vy,vx);
                        cboard(vy,vx) = 0;
                    end;
                elseif (cboard(vy,vx)<tops)
                    if (vy>1)&&(((cboard(vy-1,vx)>tops)&avail(vy-1,vx))|((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;
                        %assert(avail(vy-1,vx));
                        moves(steps,1) = pos(vy,vx);
                        moves(steps,2) = pos(vy-1,vx);
                        cboard(vy-1,vx) = cboard(vy,vx);
                        cboard(vy,vx) = 0;
                    elseif (vy < nrow)&&((cboard(vy,vx)>cboard(vy+1,vx))|((cboard(vy+1,vx)>tops)&avail(vy+1,vx)))
                        % move right
                        steps = steps+1;
                        if (steps > limit)
                            break;
                        end;
                        %assert(avail(vy+1,vx));
                        moves(steps,1) = pos(vy,vx);
                        moves(steps,2) = pos(vy+1,vx);
                        cboard(vy+1,vx) = cboard(vy,vx);
                        cboard(vy,vx) = 0;
                    end;
                end;
            end;
            steps = steps+1;
            if (steps > limit)
                break;
            end;
            %assert(avail(cy+dy,cx+dx));
            moves(steps,1) = pos(cy,cx);
            moves(steps,2) = pos(cy+dy,cx+dx);
            cboard(cy+dy,cx+dx) = cboard(cy,cx);
            cboard(cy,cx) = 0;
            cx = cx+dx;
            cy = cy+dy;
        end;
        if (steps > limit)
            break;
        end;
        % end of movement to active zone
    end;
    while (cx~=tx)||(cy~=ty)
        dx = sign(tx-cx);
        dy = sign(ty-cy);
        if ~active(cy,cx+dx)
            dx = 0;
        elseif ~active(cy+dy,cx)
            dy = 0;
        end;
        if (dx~=0)&&(dy~=0)
            if ((cboard(cy,cx+dx)>tops)|(cboard(cy,cx+dx)<=cboard(cy+dy,cx)))&avail(cy,cx+dx)
                dy = 0;
            else
                dx = 0;
            end;
        end;
        if (board(cy+dy,cx+dx)>0)
            vx = cx+dx;
            vy = cy+dy;
            if (dx==0)&(cboard(vy,vx)<tops)
                if (vx>1)&&(((cboard(vy,vx-1)>tops)&avail(vy,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;
                    %assert(avail(vy,vx-1));
                    moves(steps,1) = pos(vy,vx);
                    moves(steps,2) = pos(vy,vx-1);
                    cboard(vy,vx-1) = cboard(vy,vx);
                    cboard(vy,vx) = 0;
                elseif (vx < ncol)&((cboard(vy,vx)>cboard(vy,vx+1))|((cboard(vy,vx+1)>tops)&avail(vy,vx+1)))
                    % move right
                    steps = steps+1;
                    if (steps > limit)
                        break;
                    end;
                    %assert(avail(vy,vx+1));
                    moves(steps,1) = pos(vy,vx);
                    moves(steps,2) = pos(vy,vx+1);
                    cboard(vy,vx+1) = cboard(vy,vx);
                    cboard(vy,vx) = 0;
                end;
            elseif (cboard(vy,vx)<tops)
                if (vy>1)&&(((cboard(vy-1,vx)>tops)&avail(vy-1,vx))|((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;
                    %assert(avail(vy-1,vx));
                    moves(steps,1) = pos(vy,vx);
                    moves(steps,2) = pos(vy-1,vx);
                    cboard(vy-1,vx) = cboard(vy,vx);
                    cboard(vy,vx) = 0;
                elseif (vy < nrow)&&((cboard(vy,vx)>cboard(vy+1,vx))|((cboard(vy+1,vx)>tops)&avail(vy+1,vx)))
                    % move right
                    steps = steps+1;
                    if (steps > limit)
                        break;
                    end;
                    %assert(avail(vy+1,vx));
                    moves(steps,1) = pos(vy,vx);
                    moves(steps,2) = pos(vy+1,vx);
                    cboard(vy+1,vx) = cboard(vy,vx);
                    cboard(vy,vx) = 0;
                end;
            end;
        end;
        steps = steps+1;
        if (steps > limit)
            break;
        end;
        %assert(avail(cy+dy,cx+dx));
        moves(steps,1) = pos(cy,cx);
        moves(steps,2) = pos(cy+dy,cx+dx);
        cboard(cy+dy,cx+dx) = cboard(cy,cx);
        cboard(cy,cx) = 0;
        cx = cx+dx;
        cy = cy+dy;
    end;
    if (steps > limit)
        break;
    end;
    avail(ty,tx) = false;
    nextfit = nextfit+1;
    sxlo = min(sxlo,tx);
    sxhi = max(sxhi,tx);
    sylo = min(sylo,ty);
    syhi = max(syhi,ty);
end;
moves = moves(1:min(steps,limit),:);
% visualize
% cboard = board;
% for i = 1:size(moves,1)
%     cboard(moves(i,2)) = cboard(moves(i,1));
%     cboard(moves(i,1)) = 0;
%     imagesc(cboard);
%     axis image;
%     drawnow;
% end;
% end visualize
[vine,scr] = real_kurt(cboard);
end