| Code: |
function move = solver(aInit, aFinal, wt)
[move,isPerfect] = solverA(aInit, aFinal, wt);
function [move,isPerfect] = solverA(aInit, aFinal, wt)
% This combines my home-made recurent program (solve1)
% with the best program on the queue at that time (solve2)
% My program can be optimized a lot but it is probably
% tough to combine the two since one is completelly recurrent
% and the other not at all. Good luck.
[move,isPerfect] = solver2(aInit, aFinal, wt);
if ~isPerfect
[move1,isPerfect1] = solver1(aInit, aFinal, wt, 0);
if isPerfect1
move = move1;
isPerfect = 1;
else
[move3,isPerfect1] = solver1(aInit, aFinal, wt, 1);
if isPerfect1
move = move3;
isPerfect = 1;
else
%try another solver
[move2,isPerfect2] = solver3(aInit,aFinal,wt);
if isPerfect2
move = move2;
isPerfect = 1;
%disp('bingo');
else
s0 = sum(wt( move(:,1)));
s1 = sum(wt(move1(:,1)));
s2 = sum(wt(move2(:,1)));
s3 = sum(wt(move3(:,1)));
sL = [s0,s1,s2, s3];
%disp(sL);
[mins, sLind] = min(sL);
if sLind == 2
move = move1;
move = prunemovelist(aInit,move,0);
elseif sLind == 3
move = move2;
%disp('good');
end;
end;
end;
end;
end;
function [move,perfectMV] = solver1(aInit, aFinal, wt, mode)
perfectMV=0;
% clear the way for heaviest block
% --------------------------------
allmoves = [];
wtinitori = wt;
verbose = 0;
aInitori = aInit;
sortbydist = 0;
sortbyweight = 1; % will switch at each iteration (see below)
if mode == 1
sortbyweight = sortbydist;
sortbydist = ~sortbyweight;
addd = 0;
else
addd = 5;
end;
if verbose,
aInitori
aFinal
end;
recur = 24;
if any(abs(wt) > 10000), gen_error; end;
if any(wt < -2000), gen_error; end;
minw = 10000;
% optimize by weight
% ------------------
if sortbyweight
[tmp inds] = sort(-wt);
wtinit = wtinitori;
end;
lenwt = length(wt);
absx = zeros(lenwt,1);
absy = absx;
for index = 1:lenwt
[hvix hviy] = find(aInit == index);
[hvfx hvfy] = find(aFinal == index);
absx(index) = abs(hvix-hvfx);
absy(index) = abs(hviy-hvfy);
end;
% optimize by distance
% --------------------
if sortbydist
% for index = 1:lenwt
% [hvix hviy] = find(aInit == index);
% [hvfx hvfy] = find(aFinal == index);
% end;
dist = absx + absy;
[tmp inds] = sort(-dist);
wtinit = wtinitori;
end;
% scan blocks (first pass)
% ------------------------
for index = 1:length(inds)
hv = inds(index);
[hvix hviy] = find(aInit == hv);
[hvfx hvfy] = find(aFinal == hv);
dist = abs(hvix-hvfx)+abs(hviy-hvfy);
wt(hv) = -Inf; % remove from list
wtinit(hv) = wtinit(hv)+minw+10000; % cannot move piece back
[move cost aInit] = movefrompos(hv, [hvix hviy], [hvfx hvfy], aInit, aFinal, wtinit, 1, dist+add);
[move cost aInit] = movefrompos(hv, [hvix hviy], [hvfx hvfy], aInit, aFinal, wtinit, 1, dist+addd);
%wtinit(hv) = wtinit(hv)-minv-10000; % allow to move piece back
if isinf(cost)
if verbose, fprintf('could not fit %d\n', hv); end;
else
allmoves = [allmoves; move];
end;
end;
% scan blocks (other pass)
% ------------------------
count = 1;
oldinds = [];
while ~all(aFinal(:) == aInit(:)) %% still some differences
if verbose,
disp ('----------------')
fprintf('Iteration %d\n', count);
disp ('----------------')
end;
sortbyweight = sortbydist;
sortbydist = ~sortbyweight;
% find all pieces to move
% -----------------------
if sortbyweight
inds = find(aFinal ~= aInit);
inds = aFinal(inds);
inds = inds(inds > 0);
[tmp indices] = sort(wt(inds),1,'descend');
inds = inds(indices);
end;
% optimize by distance
% --------------------
if sortbydist
for index = 1:length(wt)
[hvix hviy] = find(aInit == index);
[hvfx hvfy] = find(aFinal == index);
dist(index) = abs(hvix-hvfx)+abs(hviy-hvfy);
end;
[tmp inds] = sort(dist,2,'descend');
firstzeros = find(tmp == 0);
inds(firstzeros:end) = [];
end;
% make blocks move on last iteration not movable
% ----------------------------------------------
wtinit = wtinitori;
notmove = setdiff(oldinds, inds);
for hv = 1:length(notmove)
wtinit(notmove(hv)) = wtinit(notmove(hv))+minw+10000; % cannot move piece back
end;
% scan block list
% ---------------
for hind = 1:length(inds)
hv = inds(hind);
[hvix hviy] = find(aInit == hv);
[hvfx hvfy] = find(aFinal == hv);
dist = abs(hvix-hvfx)+abs(hviy-hvfy);
wtinit(hv) = wtinit(hv)+minw+10000; % cannot move piece back
[move cost aInit] = movefrompos(hv, [hvix hviy], [hvfx hvfy], aInit, aFinal, wtinit, 1, dist+addd+1);
if hind > 1
wtinit(inds(hind-1)) = wtinit(inds(hind-1))-minw-10000; % can move piece back but not last one
end;
if isinf(cost)
if verbose, fprintf('could not fit %d\n', hv); end;
else
allmoves = [allmoves; move];
end;
end;
oldinds = inds;
count = count+1;
end;
% convert moves to contest format
% -------------------------------
move = [allmoves(:,1) 3*abs(allmoves(:,4))-allmoves(:,4)+2*abs(allmoves(:,5))-allmoves(:,5) ];
if verbose,
move
end;
%check whether it is the perfect move
lenB = length(wtinitori);
mviH = zeros(lenB,1);
mviV = mviH;
for i=1:lenB
mvi = (move(:,1) == i);
mviH(i) = sum( move(mvi,2)==1 | move(mvi,2)==3 );
mviV(i) = sum( move(mvi,2)==2 | move(mvi,2)==4 );
end;
if all( absx == mviV ) && all( absy == mviH )
%disp('yes 1');
perfectMV = 1;
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
return;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%% movefrompos %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [move, cost, curposnew] = movefrompos(item, pinit, pfin, curpos, finpos, wt, strategy, recur)
cost = 0;
curposnew = curpos;
if all(pinit == pfin), move = []; return; end;
if recur == 0, move = []; cost = 0; return; end;
if curpos(pinit(1), pinit(2)) == 0
disp('Error: Attempt to move empty slot'); gen_error;
end;
diffx = pfin(1)-pinit(1);
diffy = pfin(2)-pinit(2);
dirx = sign(diffx);
diry = sign(diffy);
moveall = {};
curall = {};
costall = [];
verb = 0;
if (strategy < 10 && abs(diffx) > abs(diffy)) || (strategy == 11 && abs(diffx) < abs(diffy))
if dirx && curpos(pinit(1)+dirx, pinit(2)) <= 0
[move cost curposnew] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur);
if length(move) > 0 && cost/size(move,1) == mod(wt(curpos(pinit(1),pinit(2))),10000), return; end; % no piece moved (optimal)
moveall{end+1} = move;
costall(end+1) = cost;
curall {end+1} = curposnew;
end;
if diry && curpos(pinit(1), pinit(2)+diry) <= 0
[move cost curposnew] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur);
if length(move) > 0 && cost/size(move,1) == mod(wt(curpos(pinit(1),pinit(2))),10000), return; end; % no piece moved (optimal)
moveall{end+1} = move;
costall(end+1) = cost;
curall {end+1} = curposnew;
end;
else
% second strategy
% ---------------
if diry && curpos(pinit(1), pinit(2)+diry) <= 0
[move cost curposnew] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur);
if length(move) > 0 && cost/size(move,1) == mod(wt(curpos(pinit(1),pinit(2))),10000), return; end; % no piece moved (optimal)
moveall{end+1} = move;
costall(end+1) = cost;
curall {end+1} = curposnew;
end;
if dirx && curpos(pinit(1)+dirx, pinit(2)) <= 0
[move cost curposnew] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur);
if length(move) > 0 && cost/size(move,1) == mod(wt(curpos(pinit(1),pinit(2))),10000), return; end; % no piece moved (optimal)
moveall{end+1} = move;
costall(end+1) = cost;
curall {end+1} = curposnew;
end;
end;
% there is a block in the way
% ---------------------------
if isinf(cost) || cost == 0
if dirx && diry && curpos(pinit(1), pinit(2)+diry) > 0 && curpos(pinit(1)+dirx, pinit(2)) > 0 % 2 possibilities
[moveall{end+1} costall(end+1) curall{end+1}] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur);
[moveall{end+1} costall(end+1) curall{end+1}] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur);
else
if dirx && curpos(pinit(1)+dirx, pinit(2)) > 0
[moveall{end+1} costall(end+1) curall{end+1}] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur);
end;
if diry && curpos(pinit(1), pinit(2)+diry) > 0
[moveall{end+1} costall(end+1) curall{end+1}] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur);
end;
end;
end;
% find minimal move
% -----------------
if ~isempty(costall)
[tmp indmin] = min(costall);
cost = costall(indmin);
move = moveall{indmin};
curposnew = curall {indmin};
else
cost = Inf;
end;
% try alternative move (any direction)
% ------------------------------------
if isinf(cost) && recur > 1 && abs(strategy) < 5
% search for empty position
% -------------------------
mv = [dirx diry];
mv1 = abs(mv)-1;
if any(mv1)
mv2 = abs(mv1);
mv3 = -mv;
ok3 = 1;
else
mv1 = [-mv(1) 0];
mv2 = [0 -mv(2)];
ok3 = 0;
end;
sz = size(curpos);
strategy = strategy + sign(strategy)*1;
if 0
if all(pinit+mv1 > 0) && all(pinit+mv1 <= sz) && ~curpos(pinit(1)+mv1(1),pinit(2)+mv1(2))
[move cost curposnew] = onemove(item, pinit, mv1, pfin, curpos, finpos, wt, strategy, recur-1);
elseif isinf(cost) && all(pinit+mv2 > 0) && all(pinit+mv2 <= sz) && ~curpos(pinit(1)+mv2(1),pinit(2)+mv2(2))
[move cost curposnew] = onemove(item, pinit, mv2, pfin, curpos, finpos, wt, strategy, recur-1);
elseif isinf(cost) && ok3 && all(pinit+mv3 > 0) && all(pinit+mv3 <= sz) && ~curpos(pinit(1)+mv3(1),pinit(2)+mv3(2))
[move cost curposnew] = onemove(item, pinit, mv3, pfin, curpos, finpos, wt, strategy, recur-1);
elseif isinf(cost) && all(pinit+mv1 > 0) && all(pinit+mv1 <= sz)
[move cost curposnew] = onemove(item, pinit, mv1, pfin, curpos, finpos, wt, strategy, recur-1);
elseif isinf(cost) && all(pinit+mv2 > 0) && all(pinit+mv2 <= sz)
[move cost curposnew] = onemove(item, pinit, mv2, pfin, curpos, finpos, wt, strategy, recur-1);
elseif isinf(cost) && ok3 && all(pinit+mv3 > 0) && all(pinit+mv3 <= sz)
[move cost curposnew] = onemove(item, pinit, mv3, pfin, curpos, finpos, wt, strategy, recur-1);
end;
end;
if all(pinit+mv1 > 0) && all(pinit+mv1 <= sz) && ~curpos(pinit(1)+mv1(1),pinit(2)+mv1(2))
[moveall{end+1} costall(end+1) curall{end+1}] = onemove(item, pinit, mv1, pfin, curpos, finpos, wt, strategy, recur-1);
end;
if all(pinit+mv2 > 0) && all(pinit+mv2 <= sz) && ~curpos(pinit(1)+mv2(1),pinit(2)+mv2(2))
[moveall{end+1} costall(end+1) curall{end+1}] = onemove(item, pinit, mv2, pfin, curpos, finpos, wt, strategy, recur-1);
end;
if ok3 && all(pinit+mv3 > 0) && all(pinit+mv3 <= sz) && ~curpos(pinit(1)+mv3(1),pinit(2)+mv3(2))
[moveall{end+1} costall(end+1) curall{end+1}] = onemove(item, pinit, mv3, pfin, curpos, finpos, wt, strategy, recur-1);
end;
if all(pinit+mv1 > 0) && all(pinit+mv1 <= sz) && curpos(pinit(1)+mv1(1),pinit(2)+mv1(2)) > 0
[moveall{end+1} costall(end+1) curall{end+1}] = onemove(item, pinit, mv1, pfin, curpos, finpos, wt, strategy, recur-1);
end;
if all(pinit+mv2 > 0) && all(pinit+mv2 <= sz) && curpos(pinit(1)+mv2(1),pinit(2)+mv2(2)) > 0
[moveall{end+1} costall(end+1) curall{end+1}] = onemove(item, pinit, mv2, pfin, curpos, finpos, wt, strategy, recur-1);
end;
if ok3 && all(pinit+mv3 > 0) && all(pinit+mv3 <= sz) && curpos(pinit(1)+mv3(1),pinit(2)+mv3(2)) > 0
[moveall{end+1} costall(end+1) curall{end+1}] = onemove(item, pinit, mv3, pfin, curpos, finpos, wt, strategy, recur-1);
end;
% find minimal move
% -----------------
if ~isempty(costall)
[tmp indmin] = min(costall);
cost = costall(indmin);
move = moveall{indmin};
curposnew = curall {indmin};
else
cost = Inf;
end;
end;
if isinf(cost)
curposnew = curpos;
if verb, disp('Warning: Cannot move piece to target'); end;
end;
return;
%%%%%%%%%%%%%%%%%%%%%%%%%%%% make one move %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [move, cost, curpos] = onemove(item, pinit, movedir, pfin, curpos, finpos, wt, strategy, recur)
% showprogress(pinit, pfin, movedir, curpos, wt, 1)
verb = 0;
% test final position
% -------------------
oldcurpos = curpos;
curcost = mod(wt(curpos(pinit(1), pinit(2))), 10000); % unmovable pieces have 10000 or 20000 added
move3 = [];
costnew3 = 0;
newpos = pinit+movedir;
if curpos(newpos(1), newpos(2)) > 0 % already another block in place
% test if piece can be moved or not
% ---------------------------------
if wt(curpos(newpos(1), newpos(2))) > 8000
cost = Inf;
move = [];
return;
end;
% test simple contournement
% -------------------------
if wt(curpos(newpos(1), newpos(2))) > 2*curcost && recur > 0 && strategy > 0
% compute moves
% -------------
tmppos1 = abs(movedir)-1 + pinit;
tmppos2 = (abs(movedir)-1) + pinit;
tmppos3 = movedir + tmppos1;
tmppos4 = movedir + tmppos2;
sz = size(curpos);
wt2 = [0; wt];
curpos2 = curpos;
curpos2(curpos2 < 0) = 0;
curpos2 = curpos2+1;
tmpcost = [Inf Inf];
if all(tmppos1 > 0) && all(tmppos1 <= sz)
if all(tmppos3 > 0) && all(tmppos3 <= sz)
tmpcost(1) = wt2(curpos2(tmppos1(1), tmppos1(2))) + wt2(curpos2(tmppos1(1), tmppos1(2))) + 2*curcost;
end;
end;
if all(tmppos2 > 0) && all(tmppos2 <= sz)
if all(tmppos4 > 0) && all(tmppos4 <= sz)
tmpcost(2) = wt2(curpos2(tmppos2(1), tmppos2(2))) + wt2(curpos2(tmppos4(1), tmppos4(2))) + 2*curcost;
end;
end;
% test if the move is worth it (if yes, put strategy to -1 to avoid doing it recursivelly)
% ----------------------------------------------------------------------------------------
if tmpcost(1) < wt(curpos(newpos(1), newpos(2))) && tmpcost(1) < tmpcost(2)
[move3 costnew3 curpostmp] = onemove(item, pinit, tmppos1-pinit, pfin, curpos, finpos, wt, strategy, -1);
if ~isinf(costnew3)
[move4 costnew4 curpostmp] = onemove(item, tmppos1, tmppos3-tmppos1, pfin, curpostmp, finpos, wt, strategy, -1);
if ~isinf(costnew4)
[move5 costnew5 curpostmp] = movefrompos(item, tmppos3, pfin, curpostmp, finpos, wt, -strategy, recur-1);
move = [move3; move4; move5];
cost = costnew3 + costnew4 + costnew5;
if ~isinf(cost), curpos = curpostmp; end;
return;
end;
end;
elseif tmpcost(2) < wt(curpos(newpos(1), newpos(2)))
[move3 costnew3 curpostmp] = onemove(item, pinit, tmppos2-pinit, pfin, curpos, finpos, wt, strategy, -1);
if ~isinf(costnew3)
[move4 costnew4 curpostmp] = onemove(item, tmppos2, tmppos4-tmppos2, pfin, curpostmp, finpos, wt, strategy, -1);
if ~isinf(costnew4)
[move5 costnew5 curpostmp] = movefrompos(item, tmppos4, pfin, curpostmp, finpos, wt, -strategy, recur-1);
cost = costnew3 + costnew4 + costnew5;
move = [move3; move4; move5];
if ~isinf(cost), curpos = curpostmp; end;
return;
end;
end;
end;
end;
% find blocking piece position and destination
% --------------------------------------------
newitem = curpos(newpos(1), newpos(2));
[pfin2(1) pfin2(2)] = find(finpos == newitem);
% check for reciprocal move
% -------------------------
dirx2 = sign(pfin2(1)-newpos(1));
diry2 = sign(pfin2(2)-newpos(2));
wt(newitem) = wt(newitem) + 20000;
if all( [dirx2 diry2] == -movedir ) || all(newpos == pfin2)
costnew3 = Inf;
else
% move blocking piece to its destination (1 move max)
% --------------------------------------
if verb, fprintf('Piece %d: Move other piece to destination %d\n', item, newitem); end;
[move3 costnew3 curposnew] = movefrompos(newitem, newpos, pfin2, curpos, finpos, wt, strategy, -1);
if costnew3 == 0, costnew3 = Inf; end;
if ~isinf(costnew3), curpos = curposnew; end;
end;
if isinf(costnew3)
% search for empty position for blocking piece (1 move max)
% --------------------------------------------
wtdir = [ Inf Inf Inf Inf ];
diffpos = pfin - newpos;
if (diffpos(1) && movedir(1)) || (diffpos(2) && movedir(2)) % if not change of direction
mv1 = abs(movedir)-1;
else
if any(sign(diffpos) > 0) % positive direction
mv1 = abs(movedir)-1; % negative move
else
mv1 = abs(abs(movedir)-1);
end;
end;
mv2 = -mv1;
mv3 = movedir;
sz = size(curpos);
if all(newpos+mv1 > 0) && all(newpos+mv1 <= sz)
if curpos(newpos(1)+mv1(1),newpos(2)+mv1(2)) <= 0
if verb, fprintf('Piece %d: Random move for other piece %d\n', item, newitem); end;
[move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv1, curpos, finpos, wt, strategy, -1);
else wtdir(1) = wt(curpos(newpos(1)+mv1(1),newpos(2)+mv1(2)));
end;
end;
if isinf(costnew3) && all(newpos+mv2 > 0) && all(newpos+mv2 <= sz)
if curpos(newpos(1)+mv2(1),newpos(2)+mv2(2)) <= 0
if verb, fprintf('Piece %d: Random move for other piece %d\n', item, newitem); end;
[move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv2, curpos, finpos, wt, strategy, -1);
else wtdir(2) = wt(curpos(newpos(1)+mv2(1),newpos(2)+mv2(2)));
end;
end;
if isinf(costnew3) && all(newpos+mv3 > 0) && all(newpos+mv3 <= sz)
if curpos(newpos(1)+mv3(1),newpos(2)+mv3(2)) <= 0
if verb, fprintf('Piece %d: Random move for other piece %d\n', item, newitem); end;
[move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv3, curpos, finpos, wt, strategy, -1);
else wtdir(3) = wt(curpos(newpos(1)+mv3(1),newpos(2)+mv3(2)));
end;
end;
% use non-empty position for blocking piece (1 move max)
% ------------------------------------------------------
if isinf(costnew3)
[wtdir si] = sort(wtdir);
for index = 1:length(wtdir)
if ~isinf(wtdir(index)) && isinf(costnew3)
if verb, fprintf('Piece %d: Random move for other piece (non-empty target) %d\n', item, newitem); end;
switch si(index),
case 1, [move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv1, curpos, finpos, wt, strategy, -1);
case 2, [move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv2, curpos, finpos, wt, strategy, -1);
case 3, [move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv3, curpos, finpos, wt, strategy, -1);
end;
end;
end;
end;
end;
wt(newitem) = wt(newitem) - 20000;
% impossible move
% ---------------
if isinf(costnew3) || costnew3 == 0 % impossible move
cost = Inf;
move = [];
return;
end;
end;
% prevent to go back
% ------------------
if curpos(newpos(1), newpos(2)) == -item % negative value => already come there
cost = Inf;
move = [];
return;
end;
if curpos(newpos(1), newpos(2)) > 0 % already something there: should not happen
disp('Error: Attempt to move to non-empty location'); gen_error;
end;
% update curpos
% ------------------
curpos(newpos(1), newpos(2)) = curpos(pinit(1), pinit(2));
curpos(pinit(1) , pinit(2) ) = -curpos(pinit(1), pinit(2)); % prevent from going back
% move to new position and compute cost
% -------------------------------------
if verb, fprintf('Piece %d: Standard move\n', item); end;
if recur > 0
[move2 costnew curposnew] = movefrompos(item, pinit+movedir, pfin, curpos, finpos, wt, strategy, recur-1);
else
[move2 costnew curposnew] = movefrompos(item, pinit+movedir, pfin, curpos, finpos, wt, strategy, 0);
end;
if isempty(curposnew)
disp('Warning: Empty curpos'); gen_error;
else
curpos = curposnew;
end;
% erase memory for not going back
% -------------------------------
if curpos(pinit(1), pinit(2))<0
curpos(pinit(1), pinit(2)) = 0;
end;
% compute move and cost
% ---------------------
move = [ move3; item pinit movedir; move2];
cost = costnew3+costnew+curcost;
function showprogress(pinit, pfin, movedir, curpos, wt, havepause)
% show progression (weights on left and indices on right)
% X = not movable
% + = piece trajectory (prevent from going back)
% * = target position
% >,<,v,^ = direction
% - = empty slot
% -------------------
sp = 4; % spaces
for i1 = 1:size(curpos,1)
for i2 = 1:size(curpos,2)
c = ' ';
if all([i1 i2] == pinit)
if movedir(1) > 0, c = 'v';
elseif movedir(1) < 0, c = '^';
elseif movedir(2) > 0, c = '>';
elseif movedir(2) < 0, c = '<';
end;
end;
if all([i1 i2] == pfin), c = '*'; end;
if curpos(i1, i2) > 0,
if wt(curpos(i1, i2)) > 8000 , val = [ 'X' num2str(mod(wt(curpos(i1, i2)),10000)) ];
else val = num2str(wt(curpos(i1, i2)));
end;
elseif c == ' '
if curpos(i1, i2) < 0,
val = '+';
else val = '-';
end;
else val = c; c = ' ';
end;
fprintf([ '%' int2str(sp) 's%s ' ], val, c);
end;
fprintf('\t\t\t');
for i2 = 1:size(curpos,2)
c = ' ';
if all([i1 i2] == pinit)
if movedir(1) > 0, c = 'v';
elseif movedir(1) < 0, c = '^';
elseif movedir(2) > 0, c = '>';
elseif movedir(2) < 0, c = '<';
end;
end;
if all([i1 i2] == pfin), c = '*'; end;
if curpos(i1, i2) > 0,
if wt(curpos(i1, i2)) > 8000 , val = [ 'X' num2str(curpos(i1, i2)) ];
else val = num2str(curpos(i1, i2));
end;
elseif c == ' '
if curpos(i1, i2) < 0,
val = '+';
else val = '-';
end;
else val = c; c = ' ';
end;
fprintf([ '%' int2str(sp) 's%s ' ], val, c);
end;
fprintf('\n');
end;
fprintf('\n');
fprintf('\n');
if havepause
%pause
end;
return;
function [mv,perfectMV] = solver2(ai,af,w)
perfectMV = 0;
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;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
absx = zeros(nBlocks,1);
absy = absx;
for i=1:nBlocks
[tix,tiy]=find(ai==i);
[tfx,tfy]=find(af==i);
absx(i) = abs(tix-tfx);
absy(i) = abs(tiy-tfy);
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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(~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(:));
temp = zeros(1,length(obs1));
i=1;
q=0;
pOK1=pOK;
while i<=length(obs1)
temp(obs1==obs1(i))=1;
if sum(temp)>1
j=find(obs1==obs1(i));
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
rand('state',1111);
mv2=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
score=sum(w(mv2(:,1)));
rand('state',2222);
mv1=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
score1=sum(w(mv1(:,1)));
if score1==score;
mv2 = prunemovelist(ai,mv2,0);
mv2=remove_dupes(mv2,ai);
mv=mv2;
return
end
if score1<score;mv2=mv1;score=score1;end;
rand('state',3333);
mv1=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
score1=sum(w(mv1(:,1)));
if score1<score;mv2=mv1;score=score1;end;
mv2 = prunemovelist(ai,mv2,0);
mv2=remove_dupes(mv2,ai);
mv=mv2;
end
%check perfect mv
%check whether it is the perfect move
lenB = nBlocks;
mviH = zeros(lenB,1);
mviV = mviH;
for i=1:lenB
mvi = (mv(:,1) == i);
mviH(i) = sum( mv(mvi,2)==1 | mv(mvi,2)==3 );
mviV(i) = sum( mv(mvi,2)==2 | mv(mvi,2)==4 );
end;
if all( absx == mviV ) && all( absy == mviH )
%disp('yes 2');
perfectMV = 1;
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 = 10;
if(max(size(init)) > 30)
numtimes = 8;
elseif(max(size(init)) < 11)
numtimes = 6;
end
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 = length(wts)+1+zeros(size(init)+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);
%movelist=remove_dupes(movelist,init);
score = sum(wts(movelist(:,1)));
if score<bscore
bmovelist = movelist;
bscore=score;
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [movelist,c] = matrixsolver(init,final,wts)
% matrix based version of the solver
% embed matrices in a larger matrix with walls
biggermatrix = length(wts)+1+zeros(size(init)+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
% 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
pic = picky(opendirs,desireddirs);
if ~isempty(pic)
if length(pic)>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 = pic;
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>.51)+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
pic = picky(opendirs,desireddirs);
if ~isempty(pic)
if length(pic)>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 = pic;
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];
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
cc=c(:);
cmat = cc(:,ones(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(:);
end
pml = movelist;
% Remove unnecessary moves
pml(pml(:,1)==0,:) = [];
function c = picky(a,b);
[tf,pos] = ismember(a,b);
where = zeros(size(b));
where(pos(tf)) = find(pos);
c = b(where > 0);
function mv=remove_dupes(mv,ai);
%check for wasted moves 1 delay (Where piece moves and then later back with noone using his spot
for i=1:max(ai(:));
Wastes=1;while ~isempty(Wastes);
MovesI=find(mv(:,1)==i);
Potential_Wastes=[MovesI(1:end-1) MovesI(2:end)];
if length(Potential_Wastes)<2;break;end;
Potential_Wastes=Potential_Wastes((Potential_Wastes(:,2)-Potential_Wastes(:,1))==2,:);
Wastes=Potential_Wastes(abs(mv(Potential_Wastes(:,1),2)-mv(Potential_Wastes(:,2),2))==2,:);
if ~isempty(Wastes);Wastes=Wastes(1,:);mv([Wastes(1);Wastes(2)],:)=[];end;
end;end;
%check for wasted moves big delay (Where piece moves and then later back with noone using his spot
for i=1:max(ai(:));
cnt=1;Wastes=1;while ~isempty(Wastes);
MovesI=find(mv(:,1)==i);
Potential_Wastes=[MovesI(1:end-1) MovesI(2:end)];
if length(Potential_Wastes)<2;break;end;
Wastes=Potential_Wastes(abs(mv(Potential_Wastes(:,1),2)-mv(Potential_Wastes(:,2),2))==2,:);
if ~isempty(Wastes);
if size(Wastes,1)<cnt;break;end;
Wastes=Wastes(cnt,:);mv1=mv;mv1([Wastes(1);Wastes(2)],:)=[];
valid=validity(mv1(1:Wastes(2)-2,:),ai);
if valid;mv=mv1;else;cnt=cnt+1;end;
end;
end;end;
function valid = validity(mv,ai)
I = [0 1 0 -1];
J = [1 0 -1 0];
a = ai;
valid=1;
I1=[];J1=[];for p=1:max(a(:));[i,j]=find(ai==p);I1(p)=i;J1(p)=j;end;
for k = 1:size(mv,1);
row=I1(mv(k,1));col=J1(mv(k,1));
a(row,col) = 0;
row = row + I(mv(k,2));
col = col + J(mv(k,2));
if (a(row,col) ~= 0);valid=0;return;end;
I1(mv(k,1))=row;J1(mv(k,1))=col;
a(row, col) = mv(k,1);
end
function [tf,loc] = ismember(a,s)
numelA = numel(a);
numelS = numel(s);
tf = false(size(a));
loc = zeros(size(a));
if numelA == 0 || numelS <= 1
if (numelA == 0 || numelS == 0)
return
elseif numelS == 1
tf = (a == s);
loc = double(tf);
return
end
else
scalarcut = 5;
if numelA <= scalarcut
for i=1:numelA
found = find(a(i)==s(:)); % FIND returns indices for LOC.
if ~isempty(found)
tf(i) = 1;
loc(i) = found(end);
end
end
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [mv,perfectMV] = solver3(ai,af,w)
global mv a airow aicol afrow afcol rowDis colDis I J b m n wn
mv = [];
aiMap = ai>0;
a = ai;
[m,n] = size(aiMap);
aiBlock = ai(aiMap);
nBlocks = length(aiBlock);
%sort the blocks in order of their ids
[aiOrder, aiPos] = sort(aiBlock);
[airow,aicol] = find(aiMap);
airow = airow(aiPos)';
aicol = aicol(aiPos)';
w0 = w;
w = w(aiPos);
wn = w;
%get the final state
afMap = af>0;
[afOrder, afPos ] = sort( af(afMap) );
[afrow,afcol] = find(afMap);
afrow = afrow(afPos)';
afcol = afcol(afPos)';
rowDis = airow-afrow;
colDis = aicol-afcol;
rowDis0 = rowDis;
colDis0 = colDis;
[nw,nd]=sort(-w);
%halfid = ceil(nBlocks/2);
%nd = [nd(halfid+1:end); nd(1:halfid)];
ds = sum(abs(w.*rowDis') + abs(w.*colDis'));
I = [0 1 0 -1];
J = [1 0 -1 0];
recurP = [1:4; 3 4 1 2; 1:4];
iter = 0;
while ( sum(abs(rowDis) + abs(colDis))>0 ) > 0 && iter<2
iter = iter + 1;
%for ir=1:nBlocks
%use randperm
%for ir = randperm(nBlocks)
%from weight to light
%while ( sum(abs(rowDis) + abs(colDis))>0 )
for irr = 1:nBlocks
ir = nd(irr);
priority = 0;
len=0;
iterr = 0;
while abs(rowDis(ir))+abs(colDis(ir)) > 0 && iterr < 10
iterr = iterr+1;
b=ai*0;
x = airow(ir);
y = aicol(ir);
b(x,y) = ir; %the current block occupying a position, which cannot be
%further occupied by other blocks due to chain effect
%and no backforth
if ~chainMV( ir,priority )
break;
end;
len = len+1;
%check reoccurent patterns
%to reinforce the priority
if len>3
if all( mv(end:-1:end-2,1) == ir ) && any( all( repmat( mv(end:-1:end-2,2), 1, 4 ) == recurP ) )
%disp([-1 ir]);
priority = Inf;
mv(end-1:end,:) = [];
%break;
end; % if all
end % if len
end % while
end % for
end % while
res = sum(abs(rowDis) + abs(colDis));
if res > 0
rand('state',1111);
mv2=[mv;Faster10IntReps2(a,af,w0)];
score=sum(w(mv2(:,1)));
rand('state',2222);
mv1=[mv;Faster10IntReps2(a,af,w0)];
score1=sum(w(mv1(:,1)));
if score1==score;
mv2 = prunemovelist(ai,mv2,0);
mv2= remove_dupes(mv2,ai);
mv=mv2;
else
if score1<score
mv2=mv1;
score=score1;
end;
rand('state',3333);
mv1=[mv;Faster10IntReps2(a,af,w0)];
score1=sum(w(mv1(:,1)));
if score1<score;mv2=mv1;score=score1;end;
mv2 = prunemovelist(ai,mv2,0);
mv2=remove_dupes(mv2,ai);
mv=mv2;
end;
else
mv = prunemovelist(ai,mv,0);
end;
%check perfect mv
%check whether it is the perfect move
lenB = nBlocks;
mviH = zeros(lenB,1);
mviV = mviH;
perfectMV = 0;
for i=1:lenB
mvi = (mv(:,1) == i);
mviH(i) = sum( mv(mvi,2)==1 | mv(mvi,2)==3 );
mviV(i) = sum( mv(mvi,2)==2 | mv(mvi,2)==4 );
end;
if all( abs(rowDis0') == mviV ) && all( abs(colDis0') == mviH )
%disp('yes 2');
perfectMV = 1;
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%55
function isMovable = chainMV( ir , priority)
global mv a airow aicol afrow afcol rowDis colDis I J b m n wn
isMovable = 0;
x = airow(ir);
y = aicol(ir);
np = (y-1)*m + x;
tx = afrow(ir);
ty = afcol(ir);
tnp = (ty-1)*m + tx;
disr = rowDis(ir);
disc = colDis(ir);
tp = rand;
if ( abs( disr ) + abs( disc ) > 0 ) || ( priority > wn(ir) )
%the direction to final state
mvDirects = ( disr * I + disc * J );
[goodMv, mvInd] = sort(mvDirects);
for k = 1:2 %loop over all possible four directions, for any one
%feasible direction, and stop, do update
i = I(mvInd(k));
j = J(mvInd(k));
nx = x + i;
ny = y + j;
succMv = 0;
if (nx>0) && (nx<=m) && (ny>0) && (ny<=n)
if a(nx,ny) == 0 %available
succMv = 1;
else
if b(nx,ny) == 0 %check whether the block can be kicked
b(nx,ny) = 1;
succMv = chainMV( a(nx,ny) , priority ); %return value for the obstacle can be moved
else
b(nx,ny) = 0; %restore the b(nx,ny) for loop other k
end;
end;
end;
if succMv == 1
%make a successful mv
airow(ir) = nx;
aicol(ir) = ny;
rowDis(ir) = rowDis(ir) + I(mvInd(k));
colDis(ir) = colDis(ir) + J(mvInd(k));
a(x,y) = 0;
a(nx,ny) = ir;
mv(end+1,:) = [ir,mvInd(k)];
isMovable = 1;
break;
end;
end; %for
end; %if
|
