2011-11-09 12:00:00 UTC

# pushmix

Status: Failed
Results: Failed (execution): Undefined function ''simpleLongestPath'' for input arguments of type ''double''.

Nicholas Howe
09 Nov 2011
I don't understand why this failed. The call to simpleLongestPath is identical to the one in Alex P.'s ? what now? entry, which passed just fine. I didn't modify that part of the code, and it runs just fine on the testsuite on my own computer. Huh.
Alfonso Nieto-Castanon
09 Nov 2011
the one in Kurt seems to be lower case?
09 Nov 2011
I'm also guessing it's a case sensitivity issue, and different versions of MATLAB have handled things differently (http://www.mathworks.com/help/techdoc/rn/f8-1009921.html#f8-1011835). Perhaps on your version of MATLAB calls to subfunctions are not case sensitive, while on the contest machine, they are. This code worked on my machine just fine (R2009a).
Nicholas Howe
09 Nov 2011
I'm also guessing it is the case mismatch, but the same mismatch was already present in Alex P.'s code, and it passed. Very weird.
Code
```function [moves, vine] = pushmix(board, limit)

% combination of localpush and fastspiral

[moves1, vine1, score1] = alfi(board, limit);

score2 = -Inf;
score3 = -Inf;
score4 = -Inf;
score5 = -Inf;
score6 = -Inf;
score7 = -Inf;
score8 = -Inf;
score9 = -Inf;

largestValue = max(board(:));

if largestValue > 200
if (limit > 1)
[moves3, vine3, score3] = robert(board, limit);
[moves9,vine9,score9] = 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)
[vine4,score4] = kurt(board);
end

if (limit < 3500)
[moves5,vine5,score5] = nick(board,limit);
[moves6,vine6,score6] = nick(board',limit);
if max(score5, score6) < 1.2 * max([score1 score3 score9 score4]);
[moves7,vine7,score7] = nick(rot90(board,2),limit);
[moves8,vine8,score8] = nick(rot90(board,3),limit);
end
else
[moves5,vine5,score5] = spiral(board,limit);
end;
end
[bs,best] = max([score1 score2 score3 score4 score5 score6 score7 score8 score9]);

[nrow,ncol] = size(board);
ntot = nrow*ncol;
switch best
case 1
moves=moves1;
vine=vine1;
case 2
moves=moves2;
vine=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);
id3 = id';
moves = id3(moves6);
vine = id3(vine6);
case 7
id = reshape(1:ntot,nrow,ncol);
id4 = rot90(id,2);
moves = id4(moves7);
vine = id4(vine7);
case 8
id = reshape(1:ntot,nrow,ncol);
id5 = rot90(id,3);
moves = id5(moves8);
vine = id5(vine8);
case 9
moves = moves9;
vine = vine9;
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);
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;
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
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] = kurt(cboard);
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);
for i = nrow:-1:1
offset = 0;
for j = ceil(ncol/2):ncol
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
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=[];
ab=accumarray(1+board(:),1);
cab=flipud(cumsum(flipud(ab)))-ab(end);
[m,n]=size(board);
board=[zeros(1,n+2);[zeros(m,1),board,zeros(m,1)];zeros(1,n+2)];
[m,n]=size(board);
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);
end
% post-processing moves
if limit>0
[board,iC,moves,limit] = postprocess(board,iC,moves,limit,boardab);
[iC1,iC2]=ind2sub([m,n],moves);
moves=sub2ind([m-2,n-2],iC1-1,iC2-1);
end

[iC1,iC2]=ind2sub([m,n],iC);
vine=sub2ind([m-2,n-2],iC1-1,iC2-1);
vine=vine(end:-1:1);
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);
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:1e3,
[board,moves,tiC,tP,E,limit,ok]=postprocess_lateral(board,moves,tiC,tP,E,limit,BorderDown,BorderUp,boardab);
if ~ok, break; end
end
end
if limit>0
% grow end-points
tP=board>0;
tP(tiC)=false;
for n1=1:1e3,
[board,moves,tiC,tP,limit,ok]=postprocess_endpoint(board,moves,tiC,tP,limit,1);
if ~ok, break; end
end
for n1=1:1e3,
[board,moves,tiC,tP,limit,ok]=postprocess_endpoint(board,moves,tiC,tP,limit,2);
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,boardab)
[m,n]=size(board);
ok=0;
% D=Dijkstra(tP,tiC(1));
for ndir=1:4
K=size(tiC,2);
switch(ndir)
case 1, 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)));
case 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)));
case 3, 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)));
case 4, 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)));
end
%for n2=1:numel(idx1),
for n2=numel(idx1):-1:1, %%%
switch(ndir)
case 1,
tempA=tiC(2*idx1(n2)-1)+E(2,2*idx1(n2)-1):E(2,2*idx1(n2)-1):BorderDown{1+(E(2,2*idx1(n2)-1)==m)}(tiC(2*idx1(n2)-1));
tempB=tiC(2*idx1(n2))+E(2,2*idx1(n2)-1):E(2,2*idx1(n2)-1):BorderDown{1+(E(2,2*idx1(n2)-1)==m)}(tiC(2*idx1(n2)));
case 2,
tempA=tiC(2*idx1(n2)-1)-E(2,2*idx1(n2)-1):-E(2,2*idx1(n2)-1):BorderUp{1+(E(2,2*idx1(n2)-1)==m)}(tiC(2*idx1(n2)-1));
tempB=tiC(2*idx1(n2))-E(2,2*idx1(n2)-1):-E(2,2*idx1(n2)-1):BorderUp{1+(E(2,2*idx1(n2)-1)==m)}(tiC(2*idx1(n2)));
case 3,
tempA=tiC(2*idx1(n2))+E(2,2*idx1(n2)):E(2,2*idx1(n2)):BorderDown{1+(E(2,2*idx1(n2))==m)}(tiC(2*idx1(n2)));
tempB=tiC(2*idx1(n2)+1)+E(2,2*idx1(n2)):E(2,2*idx1(n2)):BorderDown{1+(E(2,2*idx1(n2))==m)}(tiC(2*idx1(n2)+1));
case 4,
tempA=tiC(2*idx1(n2))-E(2,2*idx1(n2)):-E(2,2*idx1(n2)):BorderUp{1+(E(2,2*idx1(n2))==m)}(tiC(2*idx1(n2)));
tempB=tiC(2*idx1(n2)+1)-E(2,2*idx1(n2)):-E(2,2*idx1(n2)):BorderUp{1+(E(2,2*idx1(n2))==m)}(tiC(2*idx1(n2)+1));
end
idxZ=find(~tP(tempA),1,'first');
switch(ndir)
case {1,2},
%idxA=find(board(tiC(2*idx1(n2)-1))>=board(tempA)&board(tempA)>=board(tiC(2*idx1(n2))),1,'first');
[nill,idxA]=max((1./(abs(board(tiC(2*idx1(n2)-1))-board(tempA))+1)).*(board(tiC(2*idx1(n2)-1))>=board(tempA)&board(tempA)>=board(tiC(2*idx1(n2)))));
if ~nill,idxA=[]; end
case {3,4},
%idxA=find(board(tiC(2*idx1(n2)))>=board(tempA)&board(tempA)>=board(tiC(2*idx1(n2)+1)),1,'first');
[nill,idxA]=max((1./(abs(board(tiC(2*idx1(n2)))-board(tempA))+1)).*(board(tiC(2*idx1(n2)))>=board(tempA)&board(tempA)>=board(tiC(2*idx1(n2)+1))));
if ~nill,idxA=[]; end
end
if ~isempty(idxA)&&idxA<idxZ
idxZ=find(~tP(tempB),1,'first');
switch(ndir)
case {1,2},
idxB=find(board(tempA(idxA))>=board(tempB)&board(tempB)>=board(tiC(2*idx1(n2))),1,'first');
case {3,4},
idxB=find(board(tempA(idxA))>=board(tempB)&board(tempB)>=board(tiC(2*idx1(n2)+1)),1,'first');
end
ok=1;
switch(ndir)
case 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)];
case 2, 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)];
case 3, 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)];
case 4, 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)];
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);
%break;
end
end
end
end
end

function [board,moves,tiC,tP,limit,ok]=postprocess_endpoint(board,moves,tiC,tP,limit,type)
[m,n]=size(board);
ok=1;
switch(type)
case 1
if isempty(idx1),
if isempty(idx1),ok=0;end
end
if ok
[nill,idx2]=min(board(idx1)+1e-3*D(idx1)); %%%t3
idx0=idx1(idx2);
limit=limit-(D(idx0)-1);
for n2=D(idx0)-1:-1:1
if      D(idx0+1)==n2, tidx0=idx0+1;
elseif  D(idx0-1)==n2, tidx0=idx0-1;
elseif  D(idx0+m)==n2, tidx0=idx0+m;
elseif  D(idx0-m)==n2, tidx0=idx0-m;
end
moves=[moves; idx0, tidx0];
board(tidx0)=board(idx0);
board(idx0)=0;
idx0=tidx0;
end
tiC=[idx0,tiC];
tP(idx0)=false;
end
case 2
if isempty(idx1),ok=0;end
if ok
[nill,idx2]=min(-board(idx1)+1e-3*D(idx1)); %%%t3
idx0=idx1(idx2);
limit=limit-(D(idx0)-1);
for n2=D(idx0)-1:-1:1
if      D(idx0+1)==n2, tidx0=idx0+1;
elseif  D(idx0-1)==n2, tidx0=idx0-1;
elseif  D(idx0+m)==n2, tidx0=idx0+m;
elseif  D(idx0-m)==n2, tidx0=idx0-m;
end
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_pixel(board,limit,boardab)
[m,n]=size(board);
cD=board;
IDX=zeros(m,n);
touched=board>0;
valid=touched;
while any(touched(:))
touch=find(touched);
touched(touch)=false;
for dx=[1,-1,m,-m],
cDnew=board(touch+dx)+cD(touch); %%%
idx=find(board(touch+dx)>board(touch)&cDnew>cD(touch+dx));
touched(touch(idx)+dx)=valid(touch(idx)+dx);
cD(touch(idx)+dx)=cDnew(idx);
IDX(touch(idx)+dx)=touch(idx);
end
end
[nill,idx]=max(cD(:));
iC=zeros(1,m*n);
for n1=1:m*n,
if idx>0
iC(n1)=idx;
idx=IDX(idx);
else break;
end
end
iC=iC(1:n1-1);
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};%find(C(:,touch));
cDnew=D(idx)+cD(touch);
idx2=find(cD(idx)<cDnew);
if ~isempty(idx2)
cD(idx(idx2))=cDnew(idx2);
touched(idx(idx2))=true;
IDX(idx(idx2))=touch;
end
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(1:n1-1);
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,m,n);
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
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,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
D(i1)=1;
for n1=2:m*n,
idx1=D(i1+1)>n1;
idx2=D(i1-1)>n1;
idx3=D(i1+m)>n1;
idx4=D(i1-m)>n1;
%i1=unique([i1(idx1)+1,i1(idx2)-1,i1(idx3)+m,i1(idx4)-m]);
X=false(m,n);
X(i1(idx1)+1)=true;
X(i1(idx2)-1)=true;
X(i1(idx3)+m)=true;
X(i1(idx4)-m)=true;
i1=find(X);
if isempty(i1), break; end
D(i1)=n1;
end
if mode, D(D>0)=D(D>0)-1; end
end

%% kurt
function [vine,scr] = kurt(board)
doclusters=any(any(board(:,2:end)==board(:,1:end-1)))||any(any(board(1:end-1,:)==board(2:end,:)));
if doclusters,
[vine,scr] = real_kurt(board);
else
[vine,scr] = simpleLongestPath(board);
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 ~any(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 ~any(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 ~any(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 ~any(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 );

[~, 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] = robert2(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));
if lastdir > 0 && vine(i)+lastdir <= boardsize-cols
% a right edge in mid board
moveToCol = col+1;
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; [sub2ind([rows,cols],row,j+1), ...
sub2ind([rows,cols],row,j)]   ];
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 % First row while loop.  Break out when complete and apply
% same logic to second row

row = row - 1;
if row > 0          % Needed?
moveToCol = col+1;
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; [sub2ind([rows,cols],row,j+1), ...
sub2ind([rows,cols],row,j)]   ];
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 % second row while loop
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; [sub2ind([rows,cols],row,j), ...
sub2ind([rows,cols],row,j+1)]   ];
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 [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);

% First move onto a channel that will be cleared of blocks
[Vb,Ub] = ind2sub([rows,cols],BlockAt);
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.

finddups = sort(board(:));
if any( finddups(1:end-1) == finddups(2:end) )
% Have some repeated values so use more watermark

dir   = zeros([size(board),4]);  % points way down vine, 0 at root
[rows,cols] = size(board);
boardsize   = numel(board);
watermark = zeros([size(board),4]);
watermark(:,:,1) = reshape(1:boardsize,size(board)) * 1e-6;
watermark(:,2:2:cols,1) = flipud(watermark(:,2:2:cols,1));
watermark(:,:,2) = reshape(1:boardsize,fliplr(size(board)))' * 1e-6;
watermark(2:2:rows,:,2) = fliplr(watermark(2:2:rows,:,2));
watermark(:,:,[3,4]) = -watermark(:,:,[1,2]);
watermark = watermark + repmat(board,[1,1,4]);       % Don't use repmat...
score = repmat(board,[1,1,4]);
% score for a vine (at first starting and ending here) with each watermark
offset = (0:3) * boardsize;      % Point into the four pages

[ABHI, ind]  = sort(reshape(watermark,boardsize,4));
% Each column indexes into board in the order
% of one of the watermarks

for i = 1:boardsize;
for j = 1:4
test = ind(i,j);
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)) && (score(test+offset(j))+board(targ) > score(targ))
% Target scores on higher plateau must all be equal so
todo = targ+offset;
score(todo) = score(test+offset(j)) + board(targ);
% update them all
dir(todo) = -step-offset+offset(j);
% and note where score came from
elseif (board(targ) == board(test)) && ...
watermark(targ+offset(j)) > watermark(test+offset(j)) && ...
score(test+offset(j)) + board(targ) > score(targ+offset(j))
% On same plateau respect weave
score(targ+offset(j)) = score(test+offset(j)) + board(targ);
% add test vine to targ score
dir(targ+offset(j)) = -step;
% and note where it came from

end

end % on board
end % each step
end % weave
end % i

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

else        % No repeated values so can ignore watermark

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

end  % if plateaux

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

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

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;

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)
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

%% 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;
tops = inf;
avail = true(nrow,ncol);
th = atan2(yg-nrow/2,xg-ncol/2);
fitn = 0;
fitloc = zeros(nrow,ncol);
for i = reshape(unique(sqrad),1,[]);
[~,r] = sort(th(ring1));
fitloc(ring1(r)) = fitn+1:fitn+numel(ring1);
fitn = fitn+numel(ring1);
[~,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] = kurt(cboard);
end
```