# Diffing "Super recur weight (3)" and "Super recur weight (4) optiimization"

 Title: Super recur weight (3) Super recur weight (4) optiimization Author: Arnaud Delorme Arnaud Delorme Submitted: 2004-11-06 10:11:42 UTC 2004-11-06 10:25:40 UTC Status: Failed Failed Score: Result: CPU Time: 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 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); % !!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 score1r2 d_r=-1; elseif r1c2 d_c=-1; elseif c1 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 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 %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)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 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```