# Diffing "DperfectCalc_03___" and "DperfectCalc_04__"

 Title: DperfectCalc_03___ DperfectCalc_04__ Author: Stijn Helsen Stijn Helsen Submitted: 2004-11-09 03:26:18 UTC 2004-11-09 03:27:11 UTC Status: Passed Passed Score: 42.4652 42.4589 Result: 42315 42315 CPU Time: 47.8851 47.4625 Code: ```function moves = solver(A, B, w0) n = length(w0); ipos=zeros(n,2); fpos=zeros(n,2); for i=1:n [ipos(i,1) ipos(i,2)] = find(A==i); [fpos(i,1) fpos(i,2)] = find(B==i); end optmove = sum(sum(abs(fpos-ipos))); if n~=28 || (numel(A)/n) <= 1.98 moves = TLL79(A,B,w0); flag =0; else flag=1; end if ((n >= 18 && n <= 20) || n==28 || n==23 || (n>=13 && n <= 16)) &&... (flag || length(moves) > 1.17*optmove) && (numel(A)/n) > 1.98 if flag==0 moves = checksummer(A,moves); end ym = size(A,1); M = [ym 1 -ym -1]; mask = isfinite(w0(:))'; w = abs(w0(:)')+.1; rand('seed',42); [mov, ok] = mainsolver(A,B,w,mask,' '); if ok && flag==0 mov = 1*(mov==M(1)) + 2*(mov==M(2)) + 3*(mov==M(3)) + 4*(mov==M(4)); mov = [(mov>0)*(1:n)' sum(mov,2)]; mov=optimize(A,mov); res1 = sum(w0(moves(:,1))); res2 = sum(w0(mov(:,1))); if res20)*(1:n)' sum(mov,2)]; moves=optimize(A,mov); end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [mov, ok] = mainsolver(A,B,w,mask,reclevel) n = sum(mask); if n==0 ok = 0; return end [mov, ok] = easysolver(A,B,w,mask); if ok return end ipos = zeros(size(mask)); for i=find(mask) ipos(i) = find(A==i); end pos = cumsum([ipos; mov]); okmov = 1; newipos = pos(okmov,:); invw = max(w)+1-w; blockers = sum(findoverlaps(pos)); for leaveout = ceil(2*log(n)):(n-1) mmask = mask; choosew = sum(blockers).*invw; for i = 1:leaveout randi = rand*sum(mmask.*choosew); choose = find(cumsum(mmask.*choosew)>=randi,1,'first'); mmask(choose) = false; end Ap = zeros(size(A)); Bp = zeros(size(B)); for i = find(mmask) Ap(newipos(i)) = i; Bp(B==i) = i; end [partialmov, ok] = mainsolver(Ap, Bp, w+min(w)*rand(size(w)), mmask, [reclevel ' ']); blockers = blockers + sum(findoverlaps(cumsum([newipos;partialmov]))); if ~ok continue end for i = find(mask) Ap(newipos(i)) = i; end for i = 1:3*sum(mask) randi = rand*sum(w.*(~mmask & mask)); choose = find(cumsum(w.*(~mmask & mask))>=randi,1,'first'); [trymov, ok] = imoves(choose,partialmov,Ap,B,mmask); if ok partialmov = trymov; mmask(choose) = true; if isequal(mmask,mask) ok = 1; mov = [mov(1:okmov-1,:); partialmov]; return end else dropw = blockers.*invw; randi = rand*sum(dropw.*(mmask&mask)); choose = find(cumsum(dropw.*(mmask&mask))>=randi,1,'first'); mmask(choose) = false; partialmov(find(partialmov(:,choose)),:) = []; end end ok = 0; end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [mov, ok] = imoves(c,mov,A,B,mask) mov(find(mov(:,c)),:) = []; nmov = size(mov,1); n = length(mask); [crow,ccol] = find(A==c); [trow,tcol] = find(B==c); if nmov == 0 && crow==trow && ccol==tcol ok = 1; return end [rows,cols] = size(A); slices = false(rows, cols, nmov+1); ipos = zeros(1,n); for i=find(mask) ipos(i) = find(A(:)==i); end pos = cumsum([ipos; mov],1); for k=1:(nmov+1) R = zeros(size(A)); R(pos(k,mask)) = -1; slices(:,:,k) = (R==-1); end target = sub2ind(size(slices),trow,tcol,nmov+1); optlen = abs(crow-trow) + abs(ccol-tcol); [path] = dijkstra(numel(slices),find(A==c), target, slices, optlen); if isempty(path) ok = 0; return end for i=length(path):-1:2 if path(i)-path(i-1) < rows*cols k = floor((path(i-1)-1)/(rows*cols))+1; mov = [mov(1:(k-1),:); zeros(1,n); mov(k:end,:)]; mov(k,c) = path(i)-path(i-1); end end ok = 1; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [moves, ok] = easysolver(A,B,w,mask) global TEST TEST=1; NFIDDLE = 5; ok = 0; ym = size(A,1); n = length(mask); M = [ym 1 -ym -1]; moves = []; ipos = zeros(1,n); for i = find(mask) [row,col] = find(A==i); [rowt,colt] = find(B==i); nm = abs(col-colt) + abs(row-rowt); moves = [moves; zeros(nm,i-1) ... [M(1)*ones(max((colt-col),0),1); ... M(2)*ones(max((rowt-row),0),1); ... M(3)*ones(max((col-colt),0),1); ... M(4)*ones(max((row-rowt),0),1)] ... zeros(nm,n-i)]; ipos(i) = (col-1)*ym + row; end nmov = size(moves,1); if nmov == 0 ok = 1; return end moves = moves(randperm(nmov),:); for i=1:NFIDDLE pos = cumsum([ipos; moves]); okmov = min(find(any(findoverlaps(pos),2)))-1; if isempty(okmov) ok = 1; return end indperm = localfiddler(pos(okmov,:),moves(okmov:nmov,:),w); moves(okmov:nmov,:) = moves(okmov-1+indperm,:); end pos = cumsum([ipos; moves]); okmov = min(find(any(findoverlaps(pos),2)))-1; if isempty(okmov) ok=1; return end oldmoves = moves; for i = 1:ceil(sqrt(nmov-okmov)) pos = cumsum([ipos; moves]); overlap = findoverlaps(pos); if ~any(overlap(:)) ok = 1; return else oli = min(find(any(overlap,2))); one = min(find(overlap(oli,:))); other = max(find(overlap(oli,:))); rowinds = [oli-1 ... min(find(moves(:,one) & (1:nmov)'>=oli)) ... min(find(moves(:,other) & (1:nmov)'>=oli)) ... max(find(moves(:,one) & (1:nmov)'last break else u = stack(next); next = next + 1; end visited(u) = true; ndx = u - 1; k = floor(ndx/(rows*cols)) + 1; ndx = rem(ndx, rows*cols); col = floor(ndx/rows) + 1; ndx = rem(ndx, rows); row = floor(ndx) + 1; v = u + 1; if v>0 && v<=n && ~R(v) && row0 && v<=n && ~R(v) && row>1 if distance(u) + 1 < distance(v) distance(v) = distance(u) + 1; parent(v) = u; if ~visited(v) if (v==d) && (distance(d) <= RELAX*optlen) break end last = last + 1; stack(last) = v; end end end v = u + rows; if v>0 && v<=n && ~R(v) && col0 && v<=n && ~R(v) && col>1 if distance(u) + 1 < distance(v) distance(v) = distance(u) + 1; parent(v) = u; if ~visited(v) if (v==d) && (distance(d) <= RELAX*optlen) break end last = last + 1; stack(last) = v; end end end v = u + rows*cols; if v>0 && v<=n && ~R(v) && k < depth if distance(u) < distance(v) distance(v) = distance(u); parent(v) = u; if ~visited(v) if (v==d) && (distance(d) <= RELAX*optlen) break end last = last + 1; stack(last) = v; end end end end path = []; if parent(d) ~= 0 t = d; path = d; while t ~= s p = parent(t); path = [p path]; t = p; end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function mv = TLL79(Ai,Af,w) global Dperfect CHECKER I1=[];J1=[];I2=[];J2=[];for p=1:nnz(Ai);[i,j]=find(Ai==p);I1(p)=i;J1(p)=j;[i,j]=find(Af==p);I2(p)=i;J2(p)=j;end;Dperfect=sum(abs(I1-I2)+abs(J1-J2)); b=Ai;b(:)=1:numel(b);b=b.*rand(size(b));b=b(:);CHECKER=b; n_blk = length(w); [n_row,n_col] = size(Ai); I = [0 1 0 -1]; J = [1 0 -1 0]; Ci = zeros(n_blk,2); Cf = Ci; for row = 1:n_row, for col = 1:n_col, b = Ai(row,col); if b > 0, Ci(b,:) = [row,col]; end b = Af(row,col); if b > 0, Cf(b,:) = [row,col]; end end end mv = solv(Ai,Af,w); if size(mv,1)== Dperfect;return;end mv_len = size(mv,1); sc = sum(w(mv(:,1))); dist = w' * sum(abs(Cf - Ci),2); num_fail = 0; max_try = 75; max_fail = max_try; for j_try = 1:max_try, sc_old = sc; A = Ai; C = Ci; j = 1; while j < mv_len, if (mv(j,1) == mv(j+1,1)) && (abs(mv(j,2) - mv(j+1,2)) == 2), sc = sc - 2*w(mv(j,1)); mv = mv([1:j-1,j+2:mv_len],:); mv_len = mv_len - 2; if sc == dist, return end else if A(C(mv(j+1,1),1) + I(mv(j+1,2)),C(mv(j+1,1),2) + J(mv(j+1,2))) == 0, mv([j j+1],:)=mv([j+1 j],:); else if j+3 <= mv_len, if (mv(j,1) == mv(j+3,1)) && (abs(mv(j,2) - mv(j+3,2)) == 2) b = mv(j,1); sit = 0; if (mv(j,1) == mv(j+1,1)) && (mv(j,1) == mv(j+2,1)) && (mv(j+1,2) == mv(j+2,2)), b1 = A(C(b,1) + I(mv(j+1,2)),C(b,2) + J(mv(j+1,2))); sit = 1; else if (mv(j,1) == mv(j+1,1)) && (mv(j,1) ~= mv(j+2,1)) && (abs(mv(j+1,2) - mv(j+2,2)) == 2), b1 = mv(j+2,1); sit = 1; else if (mv(j,1) ~= mv(j+1,1)) && (mv(j,1) == mv(j+2,1)) && (abs(mv(j+1,2) - mv(j+2,2)) == 2), b1 = mv(j+1,1); sit = 1; else if (mv(j,1) == mv(j+1,1)) && (mv(j,1) ~= mv(j+2,1)), b1 = mv(j+2,1); sit = 3; else if (mv(j,1) ~= mv(j+1,1)) && (mv(j,1) == mv(j+2,1)), b1 = mv(j+1,1); sit = 2; end end end end end if sit == 1, if w(b1) < w(b), mv(j,1) = b1; mv(j+3,1) = b1; sc = sc - 2*(w(b)-w(b1)); end else if sit ~= 0, if A(C(b1,1) + I(mv(j+sit-1,2)),C(b1,2) + J(mv(j+sit-1,2))) == 0, sc = sc - w(b) - w(b1); mv(j:j+1,:) = mv([j+sit-1 j+4-sit],:); mv = mv([1:j+1,j+4:end],:); mv_len = mv_len - 2; if sc == dist, return end end end end end end end b = mv(j,1); r = C(b,1); c = C(b,2); nr = r + I(mv(j,2)); nc = c + J(mv(j,2)); A(r,c) = 0; A(nr,nc) = b; C(b,1) = nr; C(b,2) = nc; j = j + 1; end end if sc_old == sc, num_fail = num_fail+1; if num_fail == max_fail, break end else num_fail = 0; end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function move = solv(aInit, aFinal, wt) global Dperfect o = [3; 4; 1; 2]; [move,score] = solverA(aInit, aFinal, wt); if (score>100)||((length(move)-Dperfect)>3); [mv2,score2] = solverA(aFinal, aInit, wt); if score > score2 move = mv2(end:-1:1,:); score = score2; move(:,2)=o(move(:,2)); end if (score>100)||((length(move)-Dperfect)>3); a = aInit; midmoves = floor(size(move,1)/2); I = [0 1 0 -1]; J = [1 0 -1 0]; for k = 1:midmoves [row, col] = find(a==move(k,1)); a(row,col) = 0; % new position of the block row = row + I(move(k,2)); col = col + J(move(k,2)); % place the block in the new position a(row, col) = move(k,1); end oldscore1 = sum(wt(move(1:midmoves,1))); oldscore2 = sum(wt(move(midmoves+1:size(move,1),1))); [newmove,newscore] = solverA(aInit, a, wt); [newmove2,newscore2] = solverA(a, aFinal, wt); newscore1 = sum(wt(newmove(:,1))); newscore2 = sum(wt(newmove2(:,1))); oldmove = move; if(newscore1 < oldscore1) move = newmove; if(newscore2 < oldscore2) for itr = 1:size(newmove2,1) move(end+1,[1 2]) = [newmove2(itr,1) newmove2(itr,2)]; end else for itr = midmoves+1:size(oldmove,1) move(end+1,[1 2]) = [oldmove(itr,1) oldmove(itr,2)]; end end else if(newscore2 < oldscore2) move = []; for itr = 1:midmoves move(end+1,[1 2]) = [oldmove(itr,1) oldmove(itr,2)]; end for itr = 1:size(newmove2,1) move(end+1,[1 2]) = [newmove2(itr,1) newmove2(itr,2)]; end end end end end; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [move,score] = solverA(aInit, aFinal, wt) global Dperfect [move,isPerfect,score]=solver2(aInit,aFinal,wt,1111); if ~isPerfect; move1=solver1(aInit,aFinal,wt,score); if ( ~isempty(move1) ) isPerfect=length(move1)==Dperfect; score1=sum(wt(move1(:,1))); if score15); move1=solver3(aInit,aFinal,wt,1111); if ( ~isempty(move1) ) isPerfect=length(move1)==Dperfect; score1=sum(wt(move1(:,1))); if score1bscore ) move=[]; return; end end; end; count = 1; oldinds = []; while ~isequal(aFinal,aInit) sortbyweight = sortbydist; sortbydist = ~sortbyweight; if sortbyweight inds = find(aFinal ~= aInit); inds = aFinal(inds); inds = inds(inds > 0); [tmp indices] = sort(-wt(inds)); inds = inds(indices); end; 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); firstzeros = find(tmp == 0); inds(firstzeros:end) = []; end; wtinit = wtinitori; notmove = setdiff(oldinds, inds); for hv = 1:length(notmove) wtinit(notmove(hv)) = wtinit(notmove(hv))+minw+10000; end; 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; [move cost aInit] = movefrompos(hv, [hvix hviy], [hvfx hvfy], aInit, aFinal, wtinit, 1, dist+6); if hind > 1 wtinit(inds(hind-1)) = wtinit(inds(hind-1))-minw-10000; end; if isinf(cost) || isempty(move) else move = [move(:,1) 3*abs(move(:,4))-move(:,4)+2*abs(move(:,5))-move(:,5) ]; allmoves = [allmoves; move]; if ( sum(wtinitori(allmoves(:,1)))>bscore ) move=[]; return; end end; end; oldinds = inds; count = count+1; end; move = allmoves; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [move, cost, curposnew] = movefrompos(item, pinit, pfin, curpos, finpos, wt, strategy, recur) cost = 0; curposnew = curpos; if isequal(pinit,pfin), move = []; return; end; if recur == 0, move = []; cost = 0; return; end; diffx = pfin(1)-pinit(1); diffy = pfin(2)-pinit(2); dirx = sign(diffx); diry = sign(diffy); cost = Inf; 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; end; if diry && curpos(pinit(1), pinit(2)+diry) <= 0 [move1 cost1 curposnew1] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur); if length(move1) > 0 && cost1/size(move1,1) == mod(wt(curpos(pinit(1),pinit(2))),10000) move=move1; cost=cost1; curposnew=curposnew1; return; end; if cost1 0 && cost/size(move,1) == mod(wt(curpos(pinit(1),pinit(2))),10000), return; end; end; if dirx && curpos(pinit(1)+dirx, pinit(2)) <= 0 [move1 cost1 curposnew1] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur); if length(move1) > 0 && cost1/size(move1,1) == mod(wt(curpos(pinit(1),pinit(2))),10000) move=move1; cost=cost1; curposnew=curposnew1; return; end; if cost1 0 && curpos(pinit(1)+dirx, pinit(2)) > 0 [move1 cost1 curposnew1] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur); if cost1 0 [move1 cost1 curposnew1] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur); if cost1 0 [move1 cost1 curposnew1] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur); if cost1 1 && abs(strategy) < 5 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 all(pinit+mv1 > 0) && all(pinit+mv1 <= sz) && ~curpos(pinit(1)+mv1(1),pinit(2)+mv1(2)) [move1 cost1 curposnew1] = onemove(item, pinit, mv1, pfin, curpos, finpos, wt, strategy, recur-1); if cost1 0) && all(pinit+mv2 <= sz) && ~curpos(pinit(1)+mv2(1),pinit(2)+mv2(2)) [move1 cost1 curposnew1] = onemove(item, pinit, mv2, pfin, curpos, finpos, wt, strategy, recur-1); if cost1 0) && all(pinit+mv3 <= sz) && ~curpos(pinit(1)+mv3(1),pinit(2)+mv3(2)) [move1 cost1 curposnew1] = onemove(item, pinit, mv3, pfin, curpos, finpos, wt, strategy, recur-1); if cost1 0) && all(pinit+mv1 <= sz) && curpos(pinit(1)+mv1(1),pinit(2)+mv1(2)) > 0 [move1 cost1 curposnew1] = onemove(item, pinit, mv1, pfin, curpos, finpos, wt, strategy, recur-1); if cost1 0) && all(pinit+mv2 <= sz) && curpos(pinit(1)+mv2(1),pinit(2)+mv2(2)) > 0 [move1 cost1 curposnew1] = onemove(item, pinit, mv2, pfin, curpos, finpos, wt, strategy, recur-1); if cost1 0) && all(pinit+mv3 <= sz) && curpos(pinit(1)+mv3(1),pinit(2)+mv3(2)) > 0 [move1 cost1 curposnew1] = onemove(item, pinit, mv3, pfin, curpos, finpos, wt, strategy, recur-1); if cost1 0 if wt(curpos(newpos(1), newpos(2))) > 8000 cost = Inf; move = []; return; end; if wt(curpos(newpos(1), newpos(2))) > 2*curcost && recur > 0 && strategy > 0 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; tmpcost(2)=tmpcost(1); if 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; newitem = curpos(newpos(1), newpos(2)); [pfin2(1) pfin2(2)] = find(finpos == newitem); dirx2 = sign(pfin2(1)-newpos(1)); diry2 = sign(pfin2(2)-newpos(2)); wt(newitem) = wt(newitem) + 20000; if isequal([dirx2 diry2],-movedir) || isequal(newpos,pfin2) costnew3 = Inf; else [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) wtdir = [ Inf Inf Inf Inf ]; diffpos = pfin - newpos; if (diffpos(1) && movedir(1)) || (diffpos(2) && movedir(2)) mv1 = abs(movedir)-1; else if any(sign(diffpos) > 0) mv1 = abs(movedir)-1; 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 [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 [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 [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; if isinf(costnew3) [wtdir si] = sort(wtdir); for index = 1:length(wtdir) if ~isinf(wtdir(index)) && isinf(costnew3) 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; if isinf(costnew3) || costnew3 == 0 cost = Inf; move = []; return; end; end; if curpos(newpos(1), newpos(2)) == -item cost = Inf; move = []; return; end; curpos(newpos(1), newpos(2)) = curpos(pinit(1), pinit(2)); curpos(pinit(1) , pinit(2) ) = -curpos(pinit(1), pinit(2)); 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; curpos = curposnew; if curpos(pinit(1), pinit(2))<0 curpos(pinit(1), pinit(2)) = 0; end; if numel(move3)==1 && isempty(move2); move = [item pinit movedir]; elseif numel(move3)==1 move = [item pinit movedir; move2]; elseif isempty(move2) move = [ move3; item pinit movedir]; else; move = [ move3; item pinit movedir; move2]; end; cost = costnew3+costnew+curcost; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [mv,perfectMV,score] = solver2(ai,af,w,states) global TEST global Ac Ar m2 Dperfect perfectMV=false; 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; Ac=1:n2; Ac=Ac(ones(m2,1),:); Ar=(1:m2)'; Ar=Ar(:,ones(n2,1)); notPerfect=false; if TEST TEST=0; Ax=A; Ax(P(~bOK))=0; %Pimp=zeros(nBlocks,1); for i=1:nBlocks if ~bOK(i) [P1,f1]=SearchPath(Ax,P(i),Pf(i)); if ~isempty(f1) % "impossible point" %Pimp(i)=1; Dperfect=Dperfect+2; % minimal increase score=inf; return notPerfect=true; break; end end end end Pi=w; Pf=w; 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(300,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 nmv01&&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); 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 P=Pi; 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',states); mv2=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)]; score=sum(w(mv2(:,1))); if notPerfect % not worth trying too much perfectMV = Dperfect==size(mv,1); mv=mv2; return end rand('state',states*2); mv1=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)]; score1=sum(w(mv1(:,1))); if score1==score; mv=mv2; score=score1; else if score1r2 d_r=-1; elseif r1c2 d_c=-1; elseif c1 30) && max(size(wts))/(size(init,1)*size(init,2))>0.25 numtimes = 10; elseif(max(size(init)) > 30) numtimes = 7; elseif(max(size(init)) < 11) numtimes = 2; end bscore=1e20; for repcount = 1:numtimes [movelist,c] = matrixsolver(init,final,wts); bf = length(wts)+1+zeros(size(init)+2); bf(2:end-1,2:end-1) = final; tries = 1; maxtries = 15; while ~isequal(c,bf) && (tries < maxtries) randwts = rand(size(wts)); [addtomovelist,c] = matrixsolver(c(2:end-1,2:end-1),final,randwts); movelist = [movelist;addtomovelist]; tries = tries+1; end if ~isequal(c,bf) movegoaltries = 0; while ~isequal(c,bf) && (movegoaltries<20) problemboxes = c(c~=bf & c~=0); openspots = find(c==0); tempfinal = bf; for i = 1:length(problemboxes) cgind = find(bf==problemboxes(i)); tempfinal(cgind) =0; newind = ceil(rand*length(openspots)); tempfinal(openspots(newind)) = problemboxes(i); openspots(newind) = []; end 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 ~isequal(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 score = sum(wts(movelist(:,1))); if score0, 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 dr = fr-cr; dc = fc-cc; while dr~=0 || dc~=0 neighborhood = [c(cr,cc+1),c(cr+1,cc),c(cr,cc-1),c(cr-1,cc)]; opendirs = find(~neighborhood); desireddirs = []; if dr~=0 desireddirs(end+1) = -sign(dr)+3; end if dc~=0 desireddirs(end+1) = -sign(dc)+2; end pic = opendirs(ismember1(opendirs,desireddirs)); if ~isempty(pic) if length(pic)>1 if abs(dr)>abs(dc) movedir = desireddirs(1); else movedir = desireddirs(2); end else movedir = pic; end else ind = ceil(rand*length(desireddirs)); boxtomove = neighborhood(desireddirs(ind)); switch desireddirs(ind) case {1,3} rcaxis = -1; case {2,4} rcaxis = 1; end [c,movelist,rejectflag] = outoftheway(boxtomove,rcaxis,cbn,c,movelist,bf); ootwtries = 1; while rejectflag && ootwtries<10 [c,movelist,rejectflag] = outoftheway(boxtomove,rcaxis,cbn,c,movelist,bf); ootwtries = ootwtries+1; end movedir = desireddirs(ind); end c(cr,cc) = 0; 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; movelist(end+1,:) = [cbn,movedir]; dr = fr-cr; dc = fc-cc; end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [c,movelist,rejectflag] = outoftheway(boxnumber,rcaxis,dontmovetheseboxes,c,movelist,bf) c_in = c; movelist_in = movelist; rejectflag = 0; [cr,cc] = find(c==boxnumber); neighborhood = [c(cr,cc+1),c(cr+1,cc),c(cr,cc-1),c(cr-1,cc)]; opendirs = find(~neighborhood); if isempty(opendirs) switch rcaxis case -1 bettercandidates = neighborhood([2,4]); worsecandidates = neighborhood([1,3]); case 1 bettercandidates = neighborhood([1,3]); worsecandidates = neighborhood([2,4]); end wallnum = c(1,1); 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 movedir = find(neighborhood==remainingcandidates); else [cr,cc] = find(c==boxnumber); [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 pic = opendirs(ismember1(opendirs,desireddirs)); if ~isempty(pic) if length(pic)>1 if abs(dr)>abs(dc) movedir = desireddirs(1); else movedir = desireddirs(2); end else movedir = pic; end else movedir = opendirs(ceil(rand*length(opendirs))); end end c(cr,cc) = 0; 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; movelist(end+1,:) = [boxnumber,movedir]; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function mv = checksummer(ai,mv) global CHECKER I = [0 1 0 -1]; J = [1 0 -1 0]; a = ai; I1=mv(:,1);J1=I1;chk=I1; for p=1:nnz(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);return;end; I1(mv(k,1))=row;J1(mv(k,1))=col; a(row, col) = mv(k,1); chk(k)=sum(CHECKER.*a(:)); end while 1; a=sort(chk);a=a(diff(a)==0); if isempty(a);break;end; idx=find(chk==a(1)); mv(idx(1)+1:idx(end),:)=[];chk(idx(1)+1:idx(end))=[]; end; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function mv = solver3(ai,af,w,states) global mv a airow aicol afrow afcol rowDis colDis I J b m n wn Dperfect mv = []; aiMap = ai>0; a = ai; [m,n] = size(aiMap); aiBlock = ai(aiMap); nBlocks = length(aiBlock); [aiOrder, aiPos] = sort(aiBlock); [airow,aicol] = find(aiMap); airow = airow(aiPos); aicol = aicol(aiPos); w0 = w; w = w(aiPos); wn = w; afMap = af>0; [afOrder, afPos ] = sort( af(afMap) ); [afrow,afcol] = find(afMap); afrow = afrow(afPos); afcol = afcol(afPos); rowDis = airow-afrow; colDis = aicol-afcol; [nw,nd]=sort(-w); I = [0 1 0 -1]; J = [1 0 -1 0]; recurP = [1:4; 3 4 1 2; 1:4]; iter = 0; while (iter<2) && (( sum(abs(rowDis) + abs(colDis))>0 ) > 0) iter = iter + 1; for irr = 1:nBlocks ir = nd(irr); priority = 0; len=0; iterr = 0; while (iterr < 10) && (abs(rowDis(ir))+abs(colDis(ir)) > 0) iterr = iterr+1; b=ai*0; x = airow(ir); y = aicol(ir); b(x,y) = ir; if ~chainMV( ir,priority ) break; end; len = len+1; if len>3 if all( mv(end:-1:end-2,1) == ir ) && any( all( mv(end:-1:end-2,[2 2 2 2]) == recurP ) ) priority = Inf; mv(end-1:end,:) = []; end; end end end end res = sum(abs(rowDis) + abs(colDis)); if res > 0 rand('state',states);mv1=[mv;Faster10IntReps2(a,af,w0)];score=sum(w(mv1(:,1))); if ((length(mv1)-Dperfect)>1)&&(score>4450);rand('state',states*2);mv2=[mv;Faster10IntReps2(a,af,w0)];score1=sum(w(mv2(:,1)));if score1wn(ir))||(abs(disr)+abs(disc)>0) mvDirects = ( disr * I + disc * J ); [DNC, mvInd] = sort(mvDirects); for k = 1:2 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 succMv = 1; else if b(nx,ny) == 0 b(nx,ny) = 1; succMv = chainMV( a(nx,ny) , priority ); else b(nx,ny) = 0; end; end; end; if succMv == 1 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; end; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [tf,loc] = ismember(a,s) numelA = numel(a); numelS = numel(s); if numelA == 0 || numelS <= 1 if (numelA == 0 || numelS == 0) tf = false(size(a)); loc = zeros(size(a)); return elseif numelS == 1 tf = (a == s); loc = double(tf); return end else tf = false(size(a)); loc = zeros(size(a)); for i=1:numelA found = find(a(i)==s(:)); if ~isempty(found) tf(i) = 1; loc(i) = found(end); end end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [tf] = ismember1(a,s) numelA = numel(a); numelS = numel(s); if numelA == 0 || numelS <= 1 if (numelA == 0 || numelS == 0) tf = false(size(a)); return elseif numelS == 1 tf = (a == s); return end else tf = false(size(a)); for i=1:numelA found = (a(i)==s(:)); if any(found) tf(i) = 1; end end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [c] = setdiff(a,b) c = unique(a(~(ismember(a(:),b(:))))); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [b] = unique(a) numelA = numel(a); if numelA<2 b = a; else b = sort(a); db = diff(b); d = db ~= 0; d(numelA) = true; b = b(d); end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function ndx = sub2ind(siz,varargin) siz = [siz ones(1,nargin-length(siz)-1)]; mt = cellfun('isempty',varargin); if any(mt) ndx = zeros(~mt); return; end k = [1 cumprod(siz(1:end-1))]; ndx = 1; for i = 1:length(siz), v = varargin{i}; ndx = ndx + (v-1)*k(i); end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function p = randperm(n) [DNC,p] = sort(rand(1,n)); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function P = perms(V) V = V(:).'; n = length(V); if n <= 1, P = V; return; end q = perms(1:n-1); m = size(q,1); P = zeros(n*m,n); P(1:m,:) = [n * ones(m,1) q]; for i = n-1:-1:1 t = q; t(t == i) = n; P((n-i)*m+1:(n-i+1)*m,:) = [i*ones(m,1) t]; end P = V(P); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function move = optimize(ai,move1) ty = [0 1 0 -1]; tx = [1 0 -1 0]; op = [3 4 1 2]; move = move1; move1 = zeros(0,2); while size(move,1) ~= size(move1,1) w = zeros(size(ai)); i = 1; move1 = move; a = ai; while i <= length(move) w = w + 1; f = move(i,1); d = move(i,2); [y,x] = find(a == f); y2 = y + ty(d); x2 = x + tx(d); a(y,x) = 0; a(y2,x2) = f; h = find(move(1:i-1,1) == f); for z = (2*floor((length(h)+1)/2)):-2:2 zh = z/2; da = sort([d;(move(h(end-zh+2:end),2))]); db = move(h(end-z+2:end-zh+1),2); if all(da' == sort(op(db))) if w(y2,x2) == (i-h(end-z+2)+1) move(i,:) = []; move(h(end-z+2:end),:) = []; i = i - z; w = w - z; break; end end end w(a>0) = 0; i = i + 1; end end```