function mv = solver(ai,af,w)
global Ac Ar m2
nBlocks = length(w);
[m,n] = size(ai);
m2=m+2;
n2=n+2;
A = -ones(m2,n2);
Af = A;
A( 2:m+1, 2:n+1 ) = ai;
Af( 2:m+1, 2:n+1 ) = af;
di=[m2 1 -m2 -1];
dc=[1 0 -1 0];
dr=[0 1 0 -1];
Ac=1:n2;
Ac=Ac(ones(m2,1),:);
Ar=(1:m2)';
Ar=Ar(:,ones(n2,1));
Pi=w;
Pf=w;
r1=m+1;
c1=n+1;
for i=m2+2:numel(A)-m2-1
if A(i)>0, Pi(A(i)) = i; end
if Af(i)>0, Pf(Af(i)) = i; end
end
P=Pi;
nmv=1;
mv = zeros(500,2);
nNOK=sum(P~=Pf);
Paths=zeros(m+n,nBlocks);
lPaths=w;
fPaths=w;
Pend=w;
bOK=w;
obs=zeros(nBlocks,2);
nmv0=0;
while nmv0<nmv&&nNOK
obs(:)=0;
nmv0=nmv;
nR=0;
for i=1:nBlocks
if P(i)==Pf(i)
lPaths(i)=0;
fPaths(i)=0;
bOK(i)=1;
else
[P1,f1]=SearchPath(A,P(i),Pf(i));
if isempty(P1)
lPaths(i)=0;
fPaths(i)=0;
obs(i,1:length(f1))=f1;
else
if isempty(f1)
fPaths(i)=1;
else
fPaths(i)=0;
obs(i,1:length(f1))=f1;
end
lPaths(i)=length(P1);
Paths(1:lPaths(i),i)=P1;
Pend(i)=P1(end);
end
bOK(i)=0;
end
end
% find possible collisions with end-points
%iP=find(fPaths);
iP=find(~bOK&lPaths);
PCol=zeros(length(iP));
L=lPaths(iP);
for i=1:length(iP)
li=L(i);
Pe=Pend(iP(i));
for j=1:length(iP)
if i~=j
lj=L(j);
PCol(i,j)=any(Paths(1:lj,iP(j))==Pe);
end
end
end
sPCol=sum(PCol,2);
pOK=find(sPCol==0);
pNOK=find(sPCol~=0); % (the others)
if isempty(pOK)
if length(pNOK)==1
pOK(end+1)=pNOK;
elseif ~isempty(pNOK)
if length(pNOK)>1&&any(fPaths(iP(pNOK)))
pNOK(~fPaths(iP(pNOK)))=[];
end
iNOK1=pNOK(find(sPCol(pNOK)==1));
for i=iNOK1'
j=find(PCol(i,:));
jj=iP(j);
p=iP(i);
pe=Pend(p);
A(P(p))=0;
A(pe)=p;
[P1,f1]=SearchPath(A,P(jj),Pf(jj));
A(P(p))=p;
A(pe)=0;
if isempty(f1)
pOK(end+1)=i;
break
end
end
end
end
if length(pOK)>1
obs1=abs(obs(:));
obs1(obs1==0)=[];
i=1;
q=0;
pOK1=pOK;
while i<=length(obs1)
j=find(obs1==obs1(i));
if length(j)>1
obs1(j(2:end))=[];
end
if any(obs1(i)==pOK)
q=1;
j=find(obs1(i)==pOK);
pOK1(j)=0;
end
i=i+1;
end
if q
pOK(pOK1~=0)=[];
end
if length(pOK)>1&&any(fPaths(iP(pOK)))
pOK(~fPaths(iP(pOK)))=[];
end
end
j=1;
while j<=length(pOK)
i=pOK(j);
b=iP(i);
k=nmv+1:nmv+L(i);
mv(k,1)=b;
mv(k,2)=Paths(1:L(i),b); % !!have to be reworked
nmv=nmv+L(i);
A(P(b))=0;
A(Pend(b))=b;
P(b)=Pend(b);
if fPaths(b)
nNOK=nNOK-1;
end
j=j+1;
end
end
% rework mv
P=Pi; % start again
for i=2:nmv
b=mv(i);
p=mv(i,2);
dp=p-P(b);
if dp==1
mv(i,2)=2;
elseif dp==-1
mv(i,2)=4;
elseif dp==m2
mv(i,2)=1;
else
mv(i,2)=3;
end
P(b)=p;
end
mv=mv(2:nmv,:);
if nNOK
mv=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
mv = prunemovelist(ai,mv,0);
end
function [P,stopped]=SearchPath(A, p1, p2)
global Ac Ar m2
c1=Ac(p1);c2=Ac(p2);
r1=Ar(p1);r2=Ar(p2);
% search for a possible full path
stopped=[];
P=zeros(sum(size(A)),1);
if r1>r2
d_r=-1;
elseif r1<r2
d_r=1;
else
d_r=0;
end
if c1>c2
d_c=-1;
elseif c1<c2
d_c=1;
else
d_c=0;
end
n=0;
p=p1;
if d_r==0||d_c==0 % straight line
while p~=p2
np=p+d_c*m2+d_r;
if A(np)
stopped=A(np);
break
end
p=np;
n=n+1;
P(n)=p;
end
else
% find possible full line between start and end
% first find available space for shortest line
% therefore remove some (not all) "dead space"
Ah=A;
c=c2;
i1=p2-d_r;
r_1=r2-d_r;
while c~=c1
r=r_1;
r_1=0;
i2=i1;
while r~=r1
if Ah(i2)
Afil=-Ah(i2); % currently not really used
if r==r2
r_1=r2;
i1=i2-d_c*m2;
else
r_1=r+d_r;
i1=i2-d_c*m2+d_r;
end
r=r-d_r;
i2=i2-d_r;
while r~=r1
if Ah(i2)==0
Ah(i2)=Afil;
end
r=r-d_r;
i2=i2-d_r;
end
if Ah(i2)==0
Ah(i2)=Afil;
end
break;
end
r=r-d_r;
i2=i2-d_r;
end
if r_1==0&&Ah(i2)
i1=i2-d_c*m2+d_r;
r_1=r+d_r;
end
c=c-d_c;
if r_1==0
break;
end
end
r=r2;
i1=p2-d_c*m2;
c_1=c2-d_c;
while r~=r1
c=c_1;
c_1=0;
i2=i1;
while c~=c1
if Ah(i2)
if Ah(i2)<0
Afil=Ah(i2);
else
Afil=-Ah(i2);
end
if c==c2
c_1=c2;
i1=i2-d_r;
else
c_1=c+d_c;
i1=i2-d_r+d_c*m2;
end
c=c-d_c;
i2=i2-d_c*m2;
while c~=c1
if Ah(i2)==0
Ah(i2)=Afil;
end
c=c-d_c;
i2=i2-d_c*m2;
end
if Ah(i2)==0
Ah(i2)=Afil;
end
break;
end
c=c-d_c;
i2=i2-d_c*m2;
end
if c_1==0&&Ah(i2)
i1=i2-d_r+d_c*m2;
c_1=c+d_c;
end
r=r-d_r;
if c_1==0
break;
end
end
% now search for a possible line
while p~=p2
if c1~=c2&&Ah(p+m2*d_c)==0
di=m2*d_c;
dc=d_c;
dr=0;
elseif r1~=r2&&Ah(p+d_r)==0
di=d_r;
dc=0;
dr=d_r;
else
if c1==c2
stopped=Ah(p+d_r);
elseif r1==r2
stopped=Ah(p+m2*d_c);
else
stopped=[Ah(p+d_r) Ah(p+m2*d_c)];
end
break;
end
p=p+di;
n=n+1;
P(n)=p;
r1=r1+dr;
c1=c1+dc;
end
end
P=P(1:n);
function bmovelist = Faster10IntReps2(init,final,wts)
% Code runs fast, so why not try a few times and use the best score?
numtimes = 11;
bscore=1e20;
for repcount = 1:numtimes
%try inverse weighting(didn't work), prunemoves on mathworks solver
%other idea was smarter getting out of the way
[movelist,c] = matrixsolver(init,final,wts);
% save length of this movelist for later pruning, not yet used, not really
% needed
firstmovelength = size(movelist,1);
bf = repmat(length(wts)+1,[size(init,1)+2,size(init,2)+2]);
bf(2:end-1,2:end-1) = final;
tries = 1;
% I got better results by completely ignoring weights
% Try randomizing weights?
maxtries = 15;
while any(c(:)~=bf(:)) & tries < maxtries
%do it again, but randomize wts
randwts = rand(size(wts));
[addtomovelist,c] = matrixsolver(c(2:end-1,2:end-1),final,randwts);
movelist = [movelist;addtomovelist];
tries = tries+1;
end
if any(c(:)~=bf(:))
% try moving the goals for the problematic boxes
movegoaltries = 0;
while any(c(:)~=bf(:)) & movegoaltries<20
problemboxes = c(c~=bf & c~=0);
%find open slots
openspots = find(c==0);
tempfinal = bf;
%Move goals
for i = 1:length(problemboxes)
%find current goal index
cgind = find(bf==problemboxes(i));
tempfinal(cgind) =0;
newind = ceil(rand*length(openspots));
tempfinal(openspots(newind)) = problemboxes(i);
openspots(newind) = [];
end
% Now, for one time, use tempfinal instead of final
randwts = rand(size(wts));
[addtomovelist,c] = matrixsolver(c(2:end-1,2:end-1),tempfinal(2:end-1,2:end-1),randwts);
movelist = [movelist;addtomovelist];
movegoaltries = movegoaltries+1;
aftermovegoaltries = 0;
while any(c(:)~=bf(:)) & aftermovegoaltries<5
randwts = rand(size(wts));
[addtomovelist,c] = matrixsolver(c(2:end-1,2:end-1),final,randwts);
movelist = [movelist;addtomovelist];
aftermovegoaltries = aftermovegoaltries+1;
end
end
end
% Prune move list, by removing anything between repeated positions
movelist = prunemovelist(init,movelist,firstmovelength);
score = sum(wts(movelist(:,1)));
if score<bscore
bmovelist = movelist;
bscore=score;
%elseif score==bscore
%break;
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [movelist,c] = matrixsolver(init,final,wts)
% matrix based version of the solver
% embed matrices in a larger matrix with walls
biggermatrix = repmat(length(wts)+1,[size(init,1)+2,size(init,2)+2]);
bi = biggermatrix;
bf = bi;
bi(2:end-1,2:end-1) = init; % initial with walls
bf(2:end-1,2:end-1) = final; % final with walls
c = bi; % current arrangement with walls
[m,n] = size(c);
numboxes = length(wts);
% Ok, now pick which box to move first
% My first thought is to sort by weight
[dum,wtorder] = sort(wts);
% Initialize movelist
movelist = zeros(0,2);
% Now try moving them one at a time
for i = 1:numboxes
% Current box is the heaviest one which has not been moved yet
cbn = wtorder(i); % current box number
cr = 0; cc = 0; fr = 0; fc = 0;
for j=2:m-1,
for k=2:n-1,
if c(j,k)==cbn, cr = j; cc = k; if fr>0, break; end;end;
if bf(j,k)==cbn, fr = j; fc = k; if cr>0, break; end; end
end
if fr>0&&cr>0, break; end
end
%find distance between current position and final position
dr = fr-cr;
dc = fc-cc;
while dr~=0 | dc~=0 %current position~=final positon
%look at possible moves (submatrix or 4 values)
neighborhood = [c(cr,cc+1),c(cr+1,cc),c(cr,cc-1),c(cr-1,cc)]; %right,down,left,up
%neigborhood = c(cr-1:cr+1,cc-1:cc+1);
% Possible directions
opendirs = find(~neighborhood);
% Identify desired directions for current box:
desireddirs = [];
if dr~=0
desireddirs(end+1) = -sign(dr)+3;
end
if dc~=0
desireddirs(end+1) = -sign(dc)+2;
end
% desireddirs is a 1 or 2 element vector
% opendirs is a 0 to 4 element vector
% if there is an intersection between open and desired directions,
% take one of those
if ~isempty(intersect(opendirs,desireddirs))
opendesired = intersect(opendirs,desireddirs);
if length(opendesired)>1
%choose direction with longest difference
if abs(dr)>abs(dc)
movedir = desireddirs(1);
else
movedir = desireddirs(2);
end
else %only one direction is open and desired
movedir = opendesired;
end
else
% boxes in the way, move one
% choose which one to move
% move the lighter one?
[dum,ind] = min(wts(neighborhood(desireddirs)));
% or to increase the variety of answers, let's try choosing one
% randomly
% ind = ceil(rand*length(desireddirs));
boxtomove = neighborhood(desireddirs(ind));
% decide preferred axis
switch desireddirs(ind)
case {1,3}
rcaxis = -1; %move out along rows
case {2,4}
rcaxis = 1;
end
% move it
[c,movelist,rejectflag] = outoftheway(boxtomove,rcaxis,cbn,c,movelist,bf);
ootwtries = 1;
while rejectflag && ootwtries<10
%try again
[c,movelist,rejectflag] = outoftheway(boxtomove,rcaxis,cbn,c,movelist,bf);
ootwtries = ootwtries+1;
end
% move in after it
movedir = desireddirs(ind);
end
% Move away from current position
c(cr,cc) = 0;
% Move in chosen direction
switch movedir
case 1
cc = cc+1;
case 2
cr = cr+1;
case 3
cc = cc-1;
case 4
cr = cr-1;
end
c(cr,cc) = cbn;
% Add current move to list
movelist(end+1,:) = [cbn,movedir];
% Recalculate distance
dr = fr-cr;
dc = fc-cc;
end
end
%idea, don't voluntarily repeat a position if the only choices repeat a
%position, stop moving and try again later
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [c,movelist,rejectflag] = outoftheway(boxnumber,rcaxis,dontmovetheseboxes,c,movelist,bf)
% this function should move a box which is in the way out of the way
% if it cannot immediately move out of the way, then this function should call itself
% to get the next box out of the way. As soon as one box is out of the
% way, all previous ones in the stack should be able to move.
% the rcaxis input is either -1 for rows or 1 for columns and is the preferred
% axis along which to get out of the way.
% save intital settings in case of rejection
c_in = c;
movelist_in = movelist;
rejectflag = 0;
% Find box position
[cr,cc] = find(c==boxnumber);
% Find neigborhood
neighborhood = [c(cr,cc+1),c(cr+1,cc),c(cr,cc-1),c(cr-1,cc)]; % right,down,left,up
% Find open directions
opendirs = find(~neighborhood);
% Try to move box along axis out of the way
if isempty(opendirs)
% Move the next one out of the way
% Choose a neighbor along the desired rcaxis which is not on the don't
% move list
switch rcaxis
case -1 %move along rows axis
bettercandidates = neighborhood([2,4]);
worsecandidates = neighborhood([1,3]);
case 1 %cols
bettercandidates = neighborhood([1,3]);
worsecandidates = neighborhood([2,4]);
end
wallnum = c(1,1);
% need to remove wall boxes and boxes already on the don't move list
remainingcandidates = setdiff(bettercandidates,[dontmovetheseboxes,wallnum]);
if isempty(remainingcandidates)
remainingcandidates = setdiff(worsecandidates,[dontmovetheseboxes,wallnum]);
if isempty(remainingcandidates)
rejectflag = 1;
c = c_in;
movelist = movelist_in;
return
end
end
if length(remainingcandidates)>1
remainingcandidates = remainingcandidates((rand>.5)+1);
end
[c,movelist,rejectflag] = outoftheway(remainingcandidates,-rcaxis,[dontmovetheseboxes,boxnumber],c,movelist,bf);
if rejectflag
c = c_in;
movelist = movelist_in;
return
end
% Move into vacated spot
movedir = find(neighborhood==remainingcandidates);
else
% Move into one of the open directions
% randomly, for now
%movedir = opendirs(ceil(rand*length(opendirs)));
%OK, now let's take the preferred direction for the current box
%instead of random (lots of code for small benefit, but probably worth it)
% Need to determine preferred directions as above
[cr,cc] = find(c==boxnumber);
%find distance between current position and final position
[fr,fc] = find(bf==boxnumber);
dr = fr-cr;
dc = fc-cc;
desireddirs = [];
if dr~=0
desireddirs(end+1) = -sign(dr)+3;
end
if dc~=0
desireddirs(end+1) = -sign(dc)+2;
end
% desireddirs is a 0, 1, or 2 element vector
% opendirs is a 0 to 3 element vector
% if there is an intersection between open and desired directions,
% take one of those
if ~isempty(intersect(opendirs,desireddirs))
opendesired = intersect(opendirs,desireddirs);
if length(opendesired)>1
%choose direction with longest difference
if abs(dr)>abs(dc)
movedir = desireddirs(1);
else
movedir = desireddirs(2);
end
else %only one direction is open and desired
movedir = opendesired;
end
else
% no good open direction, so choose randomly
movedir = opendirs(ceil(rand*length(opendirs)));
end
end
% Move away from current position
c(cr,cc) = 0;
% Move in chosen direction
switch movedir
case 1
cc = cc+1;
case 2
cr = cr+1;
case 3
cc = cc-1;
case 4
cr = cr-1;
end
c(cr,cc) = boxnumber;
% Add current move to list
movelist(end+1,:) = [boxnumber,movedir];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function pml = prunemovelist(init,movelist,firstmovelength)
% next improvement is to detect when positions are repeated, then remove
% anything between repetitions.
%I've got some time, so this might not need to be that efficient
% one idea is to keep track of the last depth positions, and if any of them are
% identical, drop all things in between those moves as pointless
depth = 12; %doesn't seem to matter much what the depth is, I think most things happen
% with a small period, but having 50 or 100 here still only
% takes about 6 s on the testsuite
% preallocate comparison matrix
compmat = zeros(length(init(:)),depth);
compmat(:,depth) = init(:);
c = init;
I = [0 1 0 -1];
J = [1 0 -1 0];
% n =0;
% while n < size(movelist,1)
% n = n+1;
for n = 1:size(movelist,1)
% The index into compmat will be
ind = mod(n-1,depth)+1;
% Do the move (mostly stolen from viewsolution in runcontest.m)
bid = movelist(n,1);
[i,j] = find(c==bid);
r = movelist(n,2);
ni = i + I(r);
nj = j + J(r);
c(ni,nj) = bid;
c(i,j) = 0;
% Do the comparison
% is c == any previous position
cmat = repmat(c(:),1,depth);
if ~all(any(compmat-cmat)) % comes out true if a col of compmat matches c
%Find the index of the match
matchind = find(any(compmat-cmat)==0);
%Find the index difference
inddiff = ind-matchind;
if inddiff<0 %then matching index wraps
inddiff = inddiff+depth;
% Remove from compmat
compmat(:,[1:ind-1,matchind:end]) = 0;
else
compmat(:,matchind:ind-1) = 0;
end
%Remove from movelist and from compmat
movelist(n-inddiff+1:n,:) = 0; % or [] is another possibility
end
% Add current position to the comparison matrix
compmat(:,ind) = c(:);
%movelist
end
pml = movelist;
% Remove unnecessary moves
pml(pml(:,1)==0,:) = [];
|
