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;
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] = 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);
bad = (abs(board-guess)>20*abs(rmd));
for i = nrow:-1:1
offset = 0;
for j = ceil(ncol/2):ncol
if bad(i,j)
offset = offset+1;
else
moves(nmove+1:nmove+offset,:) = [pos(i,j:-1:j-offset+1)' pos(i,j-1:-1:j-offset)'];
nmove = nmove+offset;
if (nmove>=limit)
break;
end;
end;
end;
offset = 0;
for j = ceil(ncol/2):-1:1
if bad(i,j)
offset = offset+1;
else
moves(nmove+1:nmove+offset,:) = [pos(i,j:1:j+offset-1)' pos(i,j+1:1:j+offset)'];
nmove = nmove+offset;
if (nmove>=limit)
break;
end;
end;
end;
if (nmove>=limit)
break;
end;
end;
moves = moves(1:min(nmove,limit),:);
for i = 1:size(moves,1)
board(moves(i,2)) = board(moves(i,1));
board(moves(i,1)) = 0;
%imagesc(board);
%axis image;
%drawnow;
end;
[vine,scr] = SimpleLongestPath(board);
else
scr = -inf;
moves = [];
vine = [];
end
end
%% alfi
function [moves, vine, gain] = alfi(board, limit)
moves=[];
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));
% maskout=tP&~isinf(D)&board>board(tiC(1));
% nmaskout=sum(D(maskout));
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');
%idxZ=find(~tP(tempA)|maskout(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');
%idxZ=find(~tP(tempB)|maskout(tempA),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
if ~isempty(idxB)&&idxB<idxZ&&idxA+idxB-2<=limit,%-nmaskout,%.0*boardab(tiC(1))*(n+m)/2, %%%
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
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
[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
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
[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;
add_moves = [add_moves(1:end-1)', add_moves(2:end)'];
if any(ismember(add_moves(:),vine))
possible_moves(1) = [];
moves_req(1) = [];
else
% possible_moves = [];
moves = [moves; add_moves];
extra_moves = limit - size(moves,1);
vine = [vine, moves(end,2)];
for i = 1:size(add_moves,1)
board(add_moves(i,:)) = [0 board(add_moves(i,1))];
end
end_row = mod(vine(end),m);
if end_row == 0
end_row = m;
end
end_col = ceil(vine(end)/m);
larger_i = find(board >= max(board(vine)));
larger_i = setdiff(larger_i,vine);
larger_rows = mod(larger_i,m);
larger_rows(larger_rows == 0) = m;
larger_cols = ceil(larger_i/m);
moves_req = abs(end_row - larger_rows) + abs(end_col - larger_cols) - 1;
possible_moves = larger_i(moves_req < extra_moves);
moves_req = moves_req(moves_req < extra_moves);
end
end
end
end
%% 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] = kurt(cboard);
end
|
