function [moves, vine] = nochaff5(board, limit)
% Better filtering
%
% N. Howe
[vine1,scr1] = trickle2(board);
moves1 = [];
[moves2,vine2,scr2] = pusher(board,limit);
[nrow,ncol] = size(board);
ntot = nrow*ncol;
[moves3,vine3,scr3] = pusher(board',limit);
[moves4,vine4,scr4] = pusher(fliplr(board),limit);
[moves5,vine5,scr5] = pusher(fliplr(board'),limit);
[moves6,vine6,scr6] = dofilter(board,limit);
if (scr1==max([scr1 scr2 scr3 scr4 scr5 scr6]))
moves = moves1;
vine = vine1;
elseif (scr2==max([scr1 scr2 scr3 scr4 scr5 scr6]))
moves = moves2;
vine = vine2;
elseif (scr3==max([scr1 scr2 scr3 scr4 scr5 scr6]))
id = reshape(1:ntot,nrow,ncol);
id3 = id';
moves = id3(moves3);
vine = id3(vine3);
elseif (scr4==max([scr1 scr2 scr3 scr4 scr5 scr6]))
id = reshape(1:ntot,nrow,ncol);
id4 = fliplr(id);
moves = id4(moves4);
vine = id4(vine4);
elseif (scr5==max([scr1 scr2 scr3 scr4 scr5 scr6]))
id = reshape(1:ntot,nrow,ncol);
id5 = fliplr(id');
moves = id5(moves5);
vine = id5(vine5);
else
moves = moves6;
vine = vine6;
end;
end
function [moves, vine, scr] = pusher(board, limit)
moves = zeros(limit,2);
[nrow,ncol] = size(board);
if (limit < nrow)
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));
[s,r] = sort(board(:),'descend');
rank = zeros(nrow,ncol);
rank(r) = 1:ntot;
remain = true(1,ntot);
nextfit = 1;
steps = 0;
cboard = board;
for i = 1:ntot
if remain(i)
[cy,cx] = find(rank==i);
tx = xg(fitloc(nextfit));
ty = yg(fitloc(nextfit));
while (cx~=tx)|(cy~=ty)
dx = sign(tx-cx);
dy = sign(ty-cy);
if (dx~=0)&(dy~=0)
if cboard(cy,cx+dx)<=cboard(cy+dy,cx)
dy = 0;
else
dx = 0;
end;
end;
if (rank(cy+dy,cx+dx)>0)
vx = cx+dx;
vy = cy+dy;
if (dx==0)
if (vx>1)&(cboard(vy,vx)>cboard(vy,vx-1))&((vx==ncol)|(cboard(vy,vx+1)>cboard(vy,vx-1)))
% move left
steps = steps+1;
if (steps > limit)
break;
end;
moves(steps,1) = pos(vy,vx);
moves(steps,2) = pos(vy,vx-1);
cboard(vy,vx-1) = cboard(vy,vx);
cboard(vy,vx) = 0;
if (rank(vy,vx-1)>0)
remain(rank(vy,vx-1)) = 0;
end;
rank(vy,vx-1) = rank(vy,vx);
rank(vy,vx) = 0;
%imagesc(cboard);
%axis image;
%drawnow;
elseif (vx < ncol)&(cboard(vy,vx)>cboard(vy,vx+1))
% move right
steps = steps+1;
if (steps > limit)
break;
end;
moves(steps,1) = pos(vy,vx);
moves(steps,2) = pos(vy,vx+1);
cboard(vy,vx+1) = cboard(vy,vx);
cboard(vy,vx) = 0;
if (rank(vy,vx+1)>0)
remain(rank(vy,vx+1)) = 0;
end;
rank(vy,vx+1) = rank(vy,vx);
rank(vy,vx) = 0;
%imagesc(cboard);
%axis image;
%drawnow;
else
remain(rank(cy+dy,cx+dx)) = 0;
end;
else
if (vy>1)&(cboard(vy,vx)>cboard(vy-1,vx))&((vy==nrow)|(cboard(vy+1,vx)>cboard(vy-1,vx)))
% move north
steps = steps+1;
if (steps > limit)
break;
end;
moves(steps,1) = pos(vy,vx);
moves(steps,2) = pos(vy-1,vx);
cboard(vy-1,vx) = cboard(vy,vx);
cboard(vy,vx) = 0;
if (rank(vy-1,vx)>0)
remain(rank(vy-1,vx)) = 0;
end;
rank(vy-1,vx) = rank(vy,vx);
rank(vy,vx) = 0;
%imagesc(cboard);
%axis image;
%drawnow;
elseif (vy < nrow)&(cboard(vy,vx)>cboard(vy+1,vx))
% move right
steps = steps+1;
if (steps > limit)
break;
end;
moves(steps,1) = pos(vy,vx);
moves(steps,2) = pos(vy+1,vx);
cboard(vy+1,vx) = cboard(vy,vx);
cboard(vy,vx) = 0;
if (rank(vy+1,vx)>0)
remain(rank(vy+1,vx)) = 0;
end;
rank(vy+1,vx) = rank(vy,vx);
rank(vy,vx) = 0;
%imagesc(cboard);
%axis image;
%drawnow;
else
remain(rank(cy+dy,cx+dx)) = 0;
end;
end;
end;
steps = steps+1;
if (steps > limit)
break;
end;
moves(steps,1) = pos(cy,cx);
moves(steps,2) = pos(cy+dy,cx+dx);
cboard(cy+dy,cx+dx) = s(i); %cboard(cy,cx);
cboard(cy,cx) = 0;
%rank(cy+dy,cx+dx) = i; %cboard(cy,cx);
rank(cy,cx) = 0;
cx = cx+dx;
cy = cy+dy;
%imagesc(cboard);
%axis image;
%drawnow;
end;
if (steps > limit)
break;
end;
rank(ty,tx) = i;
nextfit = nextfit+1;
end;
end;
moves = moves(1:min(steps,limit),:);
[vine,scr] = trickle2(cboard);
end
function [vine,scr] = trickle2(board)
% Second effort
% Somewhat better handling of ties.
%
%N. Howe
moves = [];
[nrow,ncol] = size(board);
xg = repmat(1:ncol,nrow,1);
yg = repmat((1:nrow)',1,ncol);
limbo = nrow*ncol+1;
vals = [board(:)' -inf];
%up = [zeros(1,ncol); board(1:end-1,:)];
%down = [board(2:end,:);zeros(1,ncol)];
%left = [zeros(nrow,1); board(:,1:end-1)];
%right = [board(:,2:end);zeros(nrow,1)];
ind = reshape(1:nrow*ncol,nrow,ncol);
up = [repmat(limbo,1,ncol); ind(1:end-1,:)];
down = [ind(2:end,:);repmat(limbo,1,ncol)];
left = [repmat(limbo,nrow,1) ind(:,1:end-1)];
right = [ind(:,2:end) repmat(limbo,nrow,1)];
nbr = [[up(:) down(:) left(:) right(:)]; limbo limbo limbo limbo];
%vnbr = vals(nbr);
%big = repmat(board(:),1,4)<=vnbr;
cum = vals;
next = zeros(1,nrow*ncol+1);
next(limbo) = -1;
levels = unique(vals);
done(nrow*ncol+1) = true;
for lvl = levels(end:-1:2)
lvli = find(board==lvl);
lvln = numel(lvli);
for ii = 1:lvln
moves = (vals(nbr(lvli,:))>=lvl).*done(nbr(lvli,:));
[heur,jheur] = max(cum(nbr(lvli,:)).*moves,[],2);
heur(done(lvli)) = 0;
[mheur,mheuri] = max(heur);
if (mheur==0)
done(lvli) = true;
break;
end;
i = lvli(mheuri);
cum(i) = cum(i)+mheur;
next(i) = nbr(i,jheur(mheuri));
done(i) = true;
end;
end;
vine = zeros(1,nrow*ncol);
[scr,vine(1)] = max(cum);
vlen = 1;
while (next(vine(vlen))>0)
vine(vlen+1) = next(vine(vlen));
vlen = vlen+1;
end;
% add on at end
i = vine(vlen);
done(i) = false;
lvl = board(i);
mv = (vals(nbr(i,:))==lvl).*done(nbr(i,:));
while any(mv)
vine(vlen+1) = nbr(i,find(mv,1));
vlen = vlen+1;
i = vine(vlen);
done(i) = false;
lvl = board(i);
mv = (vals(nbr(i,:))==lvl).*done(nbr(i,:));
end;
vine = vine(1:vlen);
% now do augmentation
j = 1;
used = false(nrow,ncol);
used(vine) = true;
while (j < vlen)
i1 = vine(j);
i2 = vine(j+1);
x1 = xg(i1);
x2 = xg(i2);
y1 = yg(i1);
%y2 = yg(i2);
if (x1==x2)
% vertical move
if (x1>1)&&(~used(i1-nrow))&&(~used(i2-nrow))&&(board(i1)<=board(i1-nrow))&&(board(i1-nrow)<=board(i2-nrow))&&(board(i2-nrow)<=board(i2))
% augment to the left
vlen = vlen+2;
vine = [vine(1:j) i1-nrow i2-nrow vine(j+1:end)];
used(i1-nrow) = true;
used(i2-nrow) = true;
elseif (x1<ncol)&&(~used(i1+nrow))&&(~used(i2+nrow))&&(board(i1)<=board(i1+nrow))&&(board(i1+nrow)<=board(i2+nrow))&&(board(i2+nrow)<=board(i2))
% augment to the right
vlen = vlen+2;
vine = [vine(1:j) i1+nrow i2+nrow vine(j+1:end)];
used(i1+nrow) = true;
used(i2+nrow) = true;
else
% no augmentation; move on
j = j+1;
end;
else
% horizontal move
if (y1>1)&&(~used(i1-1))&&(~used(i2-1))&&(board(i1)<=board(i1-1))&&(board(i1-1)<=board(i2-1))&&(board(i2-1)<=board(i2))
% augment to the north
vlen = vlen+2;
vine = [vine(1:j) i1-1 i2-1 vine(j+1:end)];
used(i1-1) = true;
used(i2-1) = true;
elseif (y1<nrow)&&(~used(i1+1))&&(~used(i2+1))&&(board(i1)<=board(i1+1))&&(board(i1+1)<=board(i2+1))&&(board(i2+1)<=board(i2))
% augment to the south
vlen = vlen+2;
vine = [vine(1:j) i1+1 i2+1 vine(j+1:end)];
used(i1+1) = true;
used(i2+1) = true;
else
% no augmentation; move on
j = j+1;
end;
end;
end;
scr = sum(board(vine));
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);
sd = sign(d);
rs = median(sd,2);
guess = rmb+kron(md,-(ncol-1)/2:(ncol-1)/2);
bad = true(nrow,ncol);
%(abs(board-guess)>20*abs(rmd));
for i = 1:nrow
rdg = abs(board(i,:)-guess(i,:));
[rsd,rsr] = sort(rdg,'descend');
for k = 1:ncol
if all(sign(diff(board(i,rdg<rsd(k))))==rs(i))
bad(i,:)=(rdg>=rsd(k));
break;
end;
end;
end;
% sd = sign(d);
% rs = median(sd,2);
% rrs = repmat(rs,1,ncol);
% spd = [rs sd rs];
% while any
% bad = ((spd(:,1:end-1)~=gd)&(gd>0))|((spd(:,2:end)~=gd)&(gd<0));
%
%
% 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;
% b2 = board;
% b2(bad) = guess(bad);
%
% sd = sign(d);
% rs = median(sd,2);
% rrs = repmat(rs,1,ncol);
% for i = 1:nrow
% end;
%
% spd = [rs sd rs];
% bad = ((spd(:,1:end-1)~=gd)&(gd>0))|((spd(:,2:end)~=gd)&(gd<0));
% b2 = board;
% b2(bad) = guess(bad);
% for i = 1:nrow
% for j = 1:ncol
%
% 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] = trickle2(board);
else
scr = -inf;
moves = [];
vine = [];
end;
end
|
