# Diffing "grainy soup on the floor" and "cleaned floor"

 Title: grainy soup on the floor cleaned floor Author: Michael Völker Michael Völker Submitted: 2011-11-09 16:34:34 UTC 2011-11-09 16:57:10 UTC Status: Passed Passed Score: 664888.0 665488.0 Result: 66202177 (cyc: 13, node: 8936) 66207815 (cyc: 13, node: 8945) CPU Time: 105.999 107.352 Code: ```function [moves, vine] = solver(board, limit) [m,n] = size(board); % Gwendolyn's neat board-tuning if limit > 0 original = board; board(board resultcell{1,3} idtemp = rot90(id,1); resultcell{1,1} = idtemp(tmp1); resultcell{1,2} = idtemp(tmp2); resultcell{1,3} = gain; end end largestValue = max(board(:)); if largestValue > 200 if limit > 0 [movestemp, vinetemp, resultcell{2,3}] = robert(fliplr(board),limit); % monotonous should work good on flipping lr/ud as well idtemp = fliplr(id); resultcell{2,1} = idtemp(movestemp); resultcell{2,2} = idtemp(vinetemp); [movestemp, vinetemp, resultcell{3,3}] = robert((board),limit); idtemp = (id); resultcell{3,1} = idtemp(movestemp); resultcell{3,2} = idtemp(vinetemp); [movestemp, vinetemp, resultcell{10,3}] = robert(flipud(board),limit); idtemp = flipud(id); resultcell{10,1} = idtemp(movestemp); resultcell{10,2} = idtemp(vinetemp); [resultcell{9,1}, resultcell{9,2}, resultcell{9,3}] = dofilter(board,limit); end doclusters=any(any(board(:,2:end)==board(:,1:end-1)))||any(any(board(1:end-1,:)==board(2:end,:))); %%%% if doclusters && limit 200 if limit > 0 [movestemp, vinetemp, resultcell{2,3}] = robert(fliplr(board),limit); % monotonous should work good on flipping lr/ud as well idtemp = fliplr(id); resultcell{2,1} = idtemp(movestemp); resultcell{2,2} = idtemp(vinetemp); [movestemp, vinetemp, resultcell{3,3}] = robert((board),limit); idtemp = (id); resultcell{3,1} = idtemp(movestemp); resultcell{3,2} = idtemp(vinetemp); [movestemp, vinetemp, resultcell{10,3}] = robert(flipud(board),limit); idtemp = flipud(id); resultcell{10,1} = idtemp(movestemp); resultcell{10,2} = idtemp(vinetemp); [resultcell{9,1}, resultcell{9,2}, resultcell{9,3}] = dofilter(board,limit); end doclusters=any(any(board(:,2:end)==board(:,1:end-1)))||any(any(board(1:end-1,:)==board(2:end,:))); %%%% if doclusters && limit 0 && any(board(:) ~= original(:)) [moves, vine] = robert3(original, moves, vine, limit); end end %% nick function [moves, vine, scr] = nick(board, limit) moves = zeros(limit,2); [m,n] = size(board); ntot = m*n; if limit < m-1 scr = -inf; moves = []; vine = []; return; end; xg = repmat(1:n,m,1); yg = repmat((1:m)',1,n); pos = reshape(1:ntot,m,n); fitloc = pos; fitloc(:,2:2:end) = flipud(fitloc(:,2:2:end)); [s,r] = sort(board(:),'descend'); % [s,r] = sort(-board(:)); % is this construct really faster on % s=-s; % TMW's machine...? myRank = zeros(m,n); myRank(r) = pos; remain = true(1,ntot); nextfit = 1; steps = 0; cboard = board; for ii = 1:ntot if remain(ii) [cy,cx] = find(myRank==ii); tx = xg(fitloc(nextfit)); ty = yg(fitloc(nextfit)); [cboard,moves,remain,myRank,steps] = oftl2(cx,tx,cy,ty,cboard,myRank,steps,moves,pos,remain,n,m,limit,s,ii); if steps > limit break end myRank(ty,tx) = ii; nextfit = nextfit+1; end end moves = moves(1:min(steps,limit),:); [vine,scr] = real_kurt(cboard); end %% michael % http://www.mathworks.com/matlabcentral/contest/contests/34/submissions/64578 function [moves, vine] = use_more_moves(board, moves, vine, limit) m = size(board,1); for i = 1:size(moves,1) board(moves(i,:)) = [0 board(moves(i,1))]; end extra_moves = limit - size(moves,1); %% Uncomment to get this running with TMW's %% test environment. %% Comment it out prior to submission. :-/ % tmp = max(board(vine)); % if ~isempty(tmp) % larger_i = find(board >= tmp); % larger_i = larger_i( ~ismemberSimpl(larger_i, vine) ); % setdiff( larger_i, vine ) % else % larger_i = []; % end larger_i = find(board >= max(board(vine))); larger_i = larger_i( ~ismemberSimpl(larger_i, vine) ); % setdiff( larger_i, vine ) if ~isempty(larger_i) end_row = mod(vine(end)-1,m)+1; end_col = ceil(vine(end)/m); larger_rows = mod(larger_i-1,m)+1; larger_cols = ceil(larger_i/m); moves_req = abs(end_row - larger_rows) + abs(end_col - larger_cols) - 1; msk = moves_req < extra_moves; possible_moves = larger_i( msk ); moves_req = moves_req( msk ); while ~isempty(possible_moves) && extra_moves > 0 [~, sort_i] = sort(moves_req); possible_moves = possible_moves(sort_i); test_move = possible_moves(1); test_row = mod(test_move-1,m)+1; test_col = ceil(test_move/m); move_cols = test_col(ones(1, 1+abs(end_row-test_row))); if end_row > test_row move_rows = test_row:end_row; elseif end_row < test_row move_rows = test_row:-1:end_row; else move_rows = []; move_cols = []; end if end_col == test_col move_rows(end) = []; move_cols(end) = []; elseif end_col > test_col move_cols = [move_cols, test_col+1:end_col-1]; move_rows = [move_rows, end_row(ones(1, end_col-test_col-1))]; else move_cols = [move_cols, test_col-1:-1:end_col+1]; move_rows = [move_rows, end_row(ones(1, test_col-end_col-1))]; end add_moves = move_cols(:)*m + move_rows(:) - m; add_moves = [add_moves(1:end-1), add_moves(2:end)]; if any( ismemberSimpl(add_moves(:),vine) ) possible_moves(1) = []; moves_req(1) = []; else moves = [moves; add_moves]; extra_moves = limit - size(moves,1); vine = [vine, moves(end,2)]; for i = 1:size(add_moves,1) board(add_moves(i,:)) = [0 board(add_moves(i,1))]; end end_row = mod(vine(end)-1,m)+1; end_col = ceil(vine(end)/m); larger_i = find(board >= max(board(vine))); larger_i = larger_i( ~ismemberSimpl(larger_i, vine) ); % setdiff( larger_i, vine ) larger_rows = mod(larger_i-1,m)+1; larger_cols = ceil(larger_i/m); moves_req = abs(end_row - larger_rows) + abs(end_col - larger_cols) - 1; msk = moves_req < extra_moves; possible_moves = larger_i(msk); moves_req = moves_req(msk); end end end end function [cboard,moves,remain,rank,steps]=oftl2(cx,tx,cy,ty,cboard,rank,steps,moves,pos,remain,ncol,nrow,limit,s,i) while (cx~=tx)||(cy~=ty) dx = sign(tx-cx); dy = sign(ty-cy); if (dx~=0)&&(dy~=0) correction = cboard(cy,cx+dx)<=cboard(cy+dy,cx); dy = dy*(1-correction); dx = dx*correction; end if (rank(cy+dy,cx+dx)>0) vx = cx+dx; vy = cy+dy; if (dx==0) [steps,moves,cboard,rank,remain,breakmarker]=oftl5(steps,limit,moves,pos,vy,vx,cboard,rank,remain,1,0,vx,ncol,cy,dy,cx,dx); else [steps,moves,cboard,rank,remain,breakmarker]=oftl5(steps,limit,moves,pos,vy,vx,cboard,rank,remain,0,1,vy,nrow,cy,dy,cx,dx); end; if breakmarker break end end; steps = steps+1; if (steps > limit) break end; moves(steps,1) = pos(cy,cx); moves(steps,2) = pos(cy+dy,cx+dx); cboard(cy+dy,cx+dx) = s(i); %cboard(cy,cx); cboard(cy,cx) = 0; rank(cy,cx) = 0; cx = cx+dx; cy = cy+dy; end; end function [steps,moves,cboard,rank,remain,breakmarker]=oftl5(steps,limit,moves,pos,vy,vx,cboard,rank,remain,stepx,stepy,v_main,n_main,cy,dy,cx,dx) if v_main > 1 && cboard(vy,vx)>cboard(vy-(stepy~=0),vx-(stepx~=0)) && ( v_main==n_main || (cboard(vy+(stepy~=0),vx+(stepx~=0))>cboard(vy-(stepy~=0),vx-(stepx~=0))) ) [steps,moves,cboard,rank,remain,breakmarker]=oftl3(steps,limit,moves,pos,vy,vx,cboard,rank,remain,-stepx,-stepy); elseif (v_main < n_main)&&(cboard(vy,vx)>cboard(vy+(stepy~=0),vx+(stepx~=0))) [steps,moves,cboard,rank,remain,breakmarker]=oftl3(steps,limit,moves,pos,vy,vx,cboard,rank,remain,stepx,stepy); else remain(rank(cy+dy,cx+dx)) = 0; breakmarker = 0; end; end function [steps,moves,cboard,rank,remain,breakmarker]=oftl3(steps,limit,moves,pos,vy,vx,cboard,rank,remain,stepx,stepy) steps = steps+1; if (steps > limit) breakmarker = 1; else breakmarker = 0; moves(steps,1) = pos(vy,vx); moves(steps,2) = pos(vy+stepy,vx+stepx); cboard(vy+stepy,vx+stepx) = cboard(vy,vx); cboard(vy,vx) = 0; if (rank(vy+stepy,vx+stepx)>0) remain(rank(vy+stepy,vx+stepx)) = 0; end; rank(vy+stepy,vx+stepx) = rank(vy,vx); rank(vy,vx) = 0; end end function [moves,vine,scr] = dofilter(board,limit) [nrow,ncol] = size(board); ntot = nrow*ncol; moves = zeros(limit,2); nmove = 0; pos = reshape(1:ntot,nrow,ncol); m1 = median(board,1); m2 = median(board,2); if (sum(sign(diff(m1)))>0.67*ncol)||(sum(sign(diff(m2)))>0.67*nrow)||(sum(sign(diff(m2)))<-0.67*nrow)||(sum(sign(diff(m2)))<-0.67*nrow) d = diff(board,1,2); mb = median(board,2); md = median(d,2); rmb = repmat(mb,1,ncol); rmd = repmat(md,1,ncol); guess = rmb+kron(md,-(ncol-1)/2:(ncol-1)/2); bad = (abs(board-guess)>20*abs(rmd)); for i = nrow:-1:1 [nmove,moves]=oftl6(i,ncol,bad,moves,nmove,limit,pos); if (nmove>=limit) break end; end; moves = moves(1:min(nmove,limit),:); for i = 1:size(moves,1) board(moves(i,:)) = [0 board(moves(i,1))]; end; [vine,scr] = SimpleLongestPath(board); else scr = -inf; moves = []; vine = []; end end function [nmove,moves]=oftl6(i,ncol,bad,moves,nmove,limit,pos) offset = 0; for j = ceil(ncol/2):ncol if bad(i,j) offset = offset+1; else moves(nmove+1:nmove+offset,:) = [pos(i,j:-1:j-offset+1)' pos(i,j-1:-1:j-offset)']; nmove = nmove+offset; if (nmove>=limit) break end; end; end; offset = 0; for j = ceil(ncol/2):-1:1 if bad(i,j) offset = offset+1; else moves(nmove+1:nmove+offset,:) = [pos(i,j:1:j+offset-1)' pos(i,j+1:1:j+offset)']; nmove = nmove+offset; if (nmove>=limit) break end; end; end; end %% alfi function [moves, vine, gain] = alfi(board, limit) moves=[]; ab=accumarray(1+board(:),1); cab=flipud(cumsum(flipud(ab)))-ab(end); m = size(board,1) + 2; n = size(board,2) + 2; board2 = zeros( m, n ); board2(2:end-1,2:end-1) = board; board = board2; board2 = []; boardab=cab(1+board); if max(ab(2:end))>1, % compute same-valued clusters [BoardCluster,ClusterValue,IdxList,IdxSegments,Nclusters] = connected(board); ClusterSize = diff(IdxSegments); ClusterNeighb = neighb(BoardCluster,board,Nclusters); % search between-clusters ClustersOrder = bellman(ClusterNeighb,ClusterValue(:).*sqrt(ClusterSize(:))); % search within-clusters iC=bellman_postprocess(ClustersOrder,IdxList,IdxSegments,BoardCluster); else % search between-pixels % iC = bellman_pixel(board,limit,boardab); iC = SimpleLongestPath( board ); iC = fliplr(iC); iC = iC(board(iC)>0); end % post-processing moves if limit>0 [board,iC,moves,limit] = postprocess(board,iC,moves,limit,boardab); % [iC1,iC2]=ind2sub([m,n],moves); iC1=rem(moves-1,m)+1; iC2=(moves-iC1)/m+1; % moves=sub2ind([m-2,n-2],iC1-1,iC2-1); moves=iC1-1+(m-2)*(iC2-2); end %[iC1,iC2]=ind2sub([m,n],iC); iC1=rem(iC-1,m)+1; iC2=(iC-iC1)/m+1; %vine=sub2ind([m-2,n-2],iC1-1,iC2-1); vine=iC1-1+(m-2)*(iC2-2); vine=fliplr(vine); board=board(2:end-1,2:end-1); gain=sum(board(vine)); end function [board,tiC,moves,limit] = postprocess(board,tiC,moves,limit,boardab) [m,n]=size(board); nC=numel(tiC); tP=board>0; maxIter = 1e2; if nC>1&&limit>0, %%% % grow laterally d=abs(diff(tiC))==1; E=[m*~d+d; m*d+~d]; BorderUp={repmat(1+(0:n-1)*m,[m,1]),repmat((1:m)',[1,n])}; BorderDown={repmat(m+(0:n-1)*m,[m,1]),repmat(m*(n-1)+(1:m)',[1,n])}; % tP=board>0; tP(tiC)=false; for n1=1:maxIter [board,moves,tiC,tP,E,limit,ok]=postprocess_lateral(board,moves,tiC,tP,E,limit,BorderDown,BorderUp,m); if ~ok, break; end end end if limit>0 % grow end-points % tP=board>0; tP(tiC)=false; for n1=1:maxIter [board,moves,tiC,tP,limit,ok]=postprocess_endpoint(board,moves,tiC,tP,limit,1,m,n); if ~ok, break; end end for n1=1:10*maxIter [board,moves,tiC,tP,limit,ok]=postprocess_endpoint(board,moves,tiC,tP,limit,2,m,n); if ~ok, break; end end end end function [board,moves,tiC,tP,E,limit,ok]=postprocess_lateral(board,moves,tiC,tP,E,limit,BorderDown,BorderUp,m) ok=0; for ndir=1:4 offset = ndir>2.5; coeff = (2*mod(ndir,2)-1); K=size(tiC,2); idx1=find(tP(tiC((1+offset):2:K-1)+coeff*E(2,(1+offset):2:K-1))&tP(tiC((2+offset):2:K)+coeff*E(2,(1+offset):2:K-1))); for n2=numel(idx1):-1:1, %%% switch(ndir) case {1,3} tempA=tiC(2*idx1(n2)-1+offset)+E(2,2*idx1(n2)-1+offset):E(2,2*idx1(n2)-1+offset):BorderDown{1+(E(2,2*idx1(n2)-1+offset)==m)}(tiC(2*idx1(n2)-1+offset)); tempB=tiC(2*idx1(n2)+offset)+E(2,2*idx1(n2)-1+offset):E(2,2*idx1(n2)-1+offset):BorderDown{1+(E(2,2*idx1(n2)-1+offset)==m)}(tiC(2*idx1(n2)+offset)); case {2,4} tempA=tiC(2*idx1(n2)-1+offset)-E(2,2*idx1(n2)-1+offset):-E(2,2*idx1(n2)-1+offset):BorderUp{1+(E(2,2*idx1(n2)-1+offset)==m)}(tiC(2*idx1(n2)-1+offset)); tempB=tiC(2*idx1(n2)+offset)-E(2,2*idx1(n2)-1+offset):-E(2,2*idx1(n2)-1+offset):BorderUp{1+(E(2,2*idx1(n2)-1+offset)==m)}(tiC(2*idx1(n2)+offset)); end idxZ=find(~tP(tempA),1,'first'); [nill,idxA]=max((1./(abs(board(tiC(2*idx1(n2)-1+offset))-board(tempA))+1)).*(board(tiC(2*idx1(n2)-1+offset))>=board(tempA)&board(tempA)>=board(tiC(2*idx1(n2)+offset)))); if ~nill,idxA=[]; end if ~isempty(idxA)&&idxA=board(tempB)&board(tempB)>=board(tiC(2*idx1(n2)+offset)),1,'first'); if ~isempty(idxB)&&idxB=board(tiC(1))); if isempty(idx1), mask=tP; D=Dijkstra(mask,tiC(1),m,n); idx1=find(mask&D-1<=limit&board>=board(tiC(1))); if isempty(idx1),ok=0;end end if ok if limit>150 [~,idx2]=min(board(idx1)+1e-3*D(idx1)); %%%t3 else [~,idx2]=min(board(idx1).*(D(idx1)/limit).^0.2); %%%t3 end idx0=idx1(idx2); limit=limit-(D(idx0)-1); for n2=D(idx0)-1:-1:1 tidx0 = idx0 + (D(idx0+1)==n2) + (~(D(idx0+1)==n2))*(-(D(idx0-1)==n2)+(~(D(idx0-1)==n2))*(m*(D(idx0+m)==n2)+(~(D(idx0+m)==n2))*(-m*(D(idx0-m)==n2)))); moves=[moves; idx0, tidx0]; board(tidx0)=board(idx0); board(idx0)=0; idx0=tidx0; end tiC=[idx0,tiC]; tP(idx0)=false; end case 2 mask=tP; D=Dijkstra(mask,tiC(end),m,n); idx1=find(mask&D-1<=limit&board<=board(tiC(end))&board>0); if isempty(idx1),ok=0;end if ok if limit>300 [~,idx2]=min(-board(idx1)+1e-3*D(idx1)); %%%t3 else [~,idx2]=min(-board(idx1).*(limit./D(idx1)).^0.085); %%%t3 end idx0=idx1(idx2); limit=limit-(D(idx0)-1); for n2=D(idx0)-1:-1:1 tidx0 = idx0 + (D(idx0+1)==n2) + (~(D(idx0+1)==n2))*(-(D(idx0-1)==n2)+(~(D(idx0-1)==n2))*(m*(D(idx0+m)==n2)+(~(D(idx0+m)==n2))*(-m*(D(idx0-m)==n2)))); moves=[moves; idx0, tidx0]; board(tidx0)=board(idx0); board(idx0)=0; idx0=tidx0; end tiC=[tiC,idx0]; tP(idx0)=false; end end end function iC = bellman(C,D) N=size(C,1); c=cell(1,N); for n1=1:N,c{n1}=find(C(:,n1)); end %C=full(C); IDX=zeros(N,1); cD=D; touched=true(1,N); while any(touched) for touch=find(touched), touched(touch) = false; idx = c{touch}; cDnew = D(idx) + cD(touch); idx2 = (cD(idx)0 iC(n1)=idx; idx=IDX(idx); else break end end iC=iC(1:n1-1); end function iC = bellman_postprocess(ClustersOrder,IdxList,IdxSegments,BoardCluster) [m,n]=size(BoardCluster); iC=[]; false1N = false(1,n); falseM1 = false(m,1); falseMN = false(m,n); for n1=1:numel(ClustersOrder) idx=IdxList(IdxSegments(ClustersOrder(n1)):IdxSegments(ClustersOrder(n1)+1)-1); if numel(idx)==1 iC=[iC,idx(1)]; else % longest shortest-path ThisCluster=falseMN; ThisCluster(idx)=true; D=Dijkstra(ThisCluster,iC,m,n); if n1==numel(ClustersOrder) temp=D(ThisCluster); else temp=D(ThisCluster).*(BoardCluster([false1N;ThisCluster(1:m-1,:)])==ClustersOrder(n1+1)|BoardCluster([ThisCluster(2:m,:);false1N])==ClustersOrder(n1+1)|BoardCluster([falseM1,ThisCluster(:,1:n-1)])==ClustersOrder(n1+1)|BoardCluster([ThisCluster(:,2:n),falseM1])==ClustersOrder(n1+1)); end [~,idx0]=max(temp(:)); idx0=idx(idx0); E=zeros(2,D(idx0)-1); tiC=zeros(1,D(idx0)); tiC(end)=idx0; [E, tiC]=oftl8(D, idx0, E, m,tiC); % now grow it tP=ThisCluster; tP(tiC)=false; ok=1; while ok ok=0; K=size(tiC,2); idx1=find(tP(tiC(1:2:K-1)+E(2,1:2:K-1))&tP(tiC(2:2:K)+E(2,1:2:K-1))); for n2=numel(idx1):-1:1 ok=1; tiC=[tiC(1:2*idx1(n2)-1),tiC(2*idx1(n2)-1)+E(2,2*idx1(n2)-1), tiC(2*idx1(n2))+E(2,2*idx1(n2)-1), tiC(2*idx1(n2):end)]; E=[E(:,1:2*idx1(n2)-2),E([2,1],2*idx1(n2)-1), E([1,2],2*idx1(n2)-1), E([2,1],2*idx1(n2)-1), E(:,2*idx1(n2):end)]; tP(tiC)=false; end K=size(tiC,2); idx1=find(tP(tiC(1:2:K-1)-E(2,1:2:K-1))&tP(tiC(2:2:K)-E(2,1:2:K-1))); for n2=numel(idx1):-1:1 ok=1; tiC=[tiC(1:2*idx1(n2)-1),tiC(2*idx1(n2)-1)-E(2,2*idx1(n2)-1), tiC(2*idx1(n2))-E(2,2*idx1(n2)-1), tiC(2*idx1(n2):end)]; E=[E(:,1:2*idx1(n2)-2),E([2,1],2*idx1(n2)-1), E([1,2],2*idx1(n2)-1), E([2,1],2*idx1(n2)-1), E(:,2*idx1(n2):end)]; tP(tiC)=false; end K=size(tiC,2); idx1=find(tP(tiC(2:2:K-1)+E(2,2:2:K-1))&tP(tiC(3:2:K)+E(2,2:2:K-1))); for n2=numel(idx1):-1:1 ok=1; tiC=[tiC(1:2*idx1(n2)),tiC(2*idx1(n2))+E(2,2*idx1(n2)), tiC(2*idx1(n2)+1)+E(2,2*idx1(n2)), tiC(2*idx1(n2)+1:end)]; E=[E(:,1:2*idx1(n2)-1),E([2,1],2*idx1(n2)), E([1,2],2*idx1(n2)), E([2,1],2*idx1(n2)), E(:,2*idx1(n2)+1:end)]; tP(tiC)=false; end K=size(tiC,2); idx1=find(tP(tiC(2:2:K-1)-E(2,2:2:K-1))&tP(tiC(3:2:K)-E(2,2:2:K-1))); for n2=numel(idx1):-1:1 ok=1; tiC=[tiC(1:2*idx1(n2)),tiC(2*idx1(n2))-E(2,2*idx1(n2)), tiC(2*idx1(n2)+1)-E(2,2*idx1(n2)), tiC(2*idx1(n2)+1:end)]; E=[E(:,1:2*idx1(n2)-1),E([2,1],2*idx1(n2)), E([1,2],2*idx1(n2)), E([2,1],2*idx1(n2)), E(:,2*idx1(n2)+1:end)]; tP(tiC)=false; end end iC=[iC,tiC]; end end end function B = neighb(A,V,nA) [m,n] = size(A); B=sparse(A(:,1:n-1),A(:,2:n),double(V(:,1:n-1)>V(:,2:n)),nA,nA)+sparse(A(:,2:n),A(:,1:n-1),double(V(:,2:n)>V(:,1:n-1)),nA,nA)+sparse(A(1:m-1,:),A(2:m,:),double(V(1:m-1,:)>V(2:m,:)),nA,nA)+sparse(A(2:m,:),A(1:m-1,:),double(V(2:m,:)>V(1:m-1,:)),nA,nA); B=B>0; end function [E, tiC]=oftl8(D, idx0, E, m,tiC) for n2=D(idx0)-1:-1:1 if D(idx0+1)==n2, idx0=idx0+1; E(1,n2)=1;E(2,n2)=m; elseif D(idx0-1)==n2, idx0=idx0-1; E(1,n2)=1;E(2,n2)=m; elseif D(idx0+m)==n2, idx0=idx0+m; E(1,n2)=m;E(2,n2)=1; elseif D(idx0-m)==n2, idx0=idx0-m; E(1,n2)=m;E(2,n2)=1; end tiC(n2)=idx0; end end function [B,C,p,r,nc] = connected(A) [m,n] = size(A); N = m*n ; K = reshape (1:N, m, n) ; V = A(:,1:n-1) == A(:,2:n); H = A(1:m-1,:) == A(2:m,:); G = sparse(K([V,false(m,1)]),K([false(m,1),V]),1,N,N) + sparse(K([H; false(1,n)]),K([false(1,n); H]),1,N,N); G = G + G' + speye(N); [p, ~, r] = dmperm(G); nc = numel(r) - 1; C = A(p(r(1:nc))); B = ones(m, n); for a = 2:nc B(p(r(a):r(a+1)-1)) = a; end end function D = Dijkstra(A,i1,m,n) D=inf(m,n); D(~A)=0; falseMN = false( m*n, 1); if isempty(i1), i1=find(A,1,'first'); mode=0; else i1=i1(end); mode=1; end D(i1)=1; for n1=2:m*n, X = falseMN; X(i1(isinf(D(i1+1)))+1) = true; X(i1(isinf(D(i1-1)))-1) = true; X(i1(isinf(D(i1+m)))+m) = true; X(i1(isinf(D(i1-m)))-m) = true; %i1=unique([i1(idx1)+1,i1(idx2)-1,i1(idx3)+m,i1(idx4)-m]); i1=find(X); if isempty(i1), break; end D(i1)=n1; end if mode msk = D>0; D(msk)=D(msk)-1; end end %% kurt function [vine, bestsom] = real_kurt(A) [m,n]=size(A); Asort = sort(A(:)); content = unique(Asort); cumS = cumsum(Asort); tttt = cumS( diff(Asort) ~= 0 ); % tttt is to find non-plateaus...? t2 = zeros(size(content,1),1); t2(content+1) = [0; tttt]; H = t2(A+1); if size(H,1) ~= m H=H'; end C = num2cell(reshape(1:m*n, m, n)); updated = true(size(A)); G = A+H; [maxG,idxStart] = max(G(:)); B=A; while (maxG > max(B(:))) && maxG ii = mod(idxStart-1,m)+1; jj = ceil(idxStart/m); flag1 = ii > 1 && A(idxStart - 1) <= A(idxStart); flag2 = ii < m && A(idxStart + 1) <= A(idxStart); flag3 = jj < n && A(idxStart + m) <= A(idxStart); flag4 = jj > 1 && A(idxStart - m) <= A(idxStart); if flag1 [B,C,updated] = oftl4( idxStart-1, idxStart,A,B,C,updated ); end if flag2 [B,C,updated] = oftl4( idxStart+1, idxStart,A,B,C,updated ); end if flag3 [B,C,updated] = oftl4( idxStart+m, idxStart,A,B,C,updated ); end if flag4 [B,C,updated] = oftl4( idxStart-m, idxStart,A,B,C,updated ); end updated(idxStart) = false; G=(B+H).*updated; [maxG,idxStart] = max(G(:)); end [bestsom,index]=max(B(:)); vine = fliplr(C{index}); end function [B,C,updated]=oftl4(verplaatsindex,currIdx,A,B,C,updated ) if (B(currIdx)+A(verplaatsindex) > B(verplaatsindex)) && ~sum(verplaatsindex==C{currIdx}) % Gwendothanks B(verplaatsindex) = B(currIdx) + A(verplaatsindex); updated(verplaatsindex)=true; C{verplaatsindex} = [C{currIdx} verplaatsindex]; end end function [vine, bestScore] = SimpleLongestPath( board ) % Treats the board as a directed-acyclic-graph and finds the best % possible solution. Upper-left wins to break cycles in the graph % (when adjacent squares have the same value). % % This is basically a completely rewritten version of the sebastian() % function, and is about 15 times faster than sebastian() on the contest % machine. % % This function is only called 8 times presently on the sample set so it % doesn't make much difference. I optimised it so extremely expecting to use it as % a candidate-scoring/fitness function as part of some sort of larger algorithm. % % - Wesley [m, n] = size( board ); count = m * n; sentinel = count + 1; board = board(:); score = [board; 0]; nOnes = ones( 1,n ); mOnes = ones( m,1 ); seq = reshape( 1:count, m, n ); north = reshape( [sentinel(nOnes); seq(1:end-1,:)], [], 1); north(board= southScore scoreNS = northScore; neighbourNS = northNeighbour; else scoreNS = southScore; neighbourNS = southNeighbour; end westNeighbour = west(curr); westScore = score(westNeighbour); eastNeighbour = east(curr); eastScore = score(eastNeighbour); if westScore >= eastScore scoreEW = westScore; neighbourEW = westNeighbour; else scoreEW = eastScore; neighbourEW = eastNeighbour; end if scoreEW >= scoreNS prev(curr) = neighbourEW; score(curr) = score(curr) + scoreEW; else prev(curr) = neighbourNS; score(curr) = score(curr) + scoreNS; end end [bestScore, c] = max( score ); for ii = 1:count seq(ii) = c; c = prev(c); if c == sentinel break end end vine = seq(ii:-1:1); end % robert function [moves, vine, score] = robert(board, limit) % The Fragrant Honeysuckle gives up on moving and just tries to produce % some prettier vines 8-) % Faster to use isconnected logic, or to embed in a zeros(m+1,n+1) and guard? % Grow a simple vine on given board %[vine, score, dirsimple, moves] = robert2(board); % Try constructing a boardwalk down left side [movesb, boardb] = robert1(board, limit); [vineb, vscoreb, dirsimple] = robert2(boardb); % Rerun vine code on modified board % Improve score on board 47 and similar that feature a steady slope and speckle IsMonotonous = ~(any(dirsimple(vineb) == 1) && any(dirsimple(vineb) == -1)); if IsMonotonous % Only bother if I have a decent score already and vine goes % solely up or solely down. [movesm, boardm] = monotonous(board, vineb, dirsimple, limit); [vinem, vscorem] = SimpleLongestPath(boardm); % Rerun vine code on modified board end % Pick best if IsMonotonous && vscorem > vscoreb vine = vinem; moves = movesm; score = vscorem; else vine = vineb; moves = movesb; score = vscoreb; end end % solver function function [moves, board] = monotonous(boardin, vine, dir, limit) % Focus n high-scoring vines with strong vertical orientation and high limit, % and aim to shuffle blocking values out of high-scoring rows. % Should never damage a unidirectional vine but ineffective unless the % board has the structure of board 47 moves = []; board = boardin; [rows,cols] = size(board); boardsize = numel(board); lastdir = dir(vine(end)); % initialise with vine top for i = size(vine,1)-1:-1:2 % walk down vine to polish high scores first if abs(dir(vine(i))) == 1 % found a vertical step valmin = board(vine(i)+dir(vine(i))); valmax = board(vine(i)); % range of non-blocking values % [row,col] = ind2sub([rows,cols],vine(i)); row=rem(vine(i)-1,rows)+1; col=(vine(i)-row)/rows+1; if lastdir > 0 && vine(i)+lastdir <= boardsize-cols % a right edge in mid board moveToCol = col+1; [board,moves]=oftl(board,moves,limit,row,moveToCol,valmin,valmax,cols,rows); row = row - 1; if row > 0 % Needed? moveToCol = col+1; [board,moves]=oftl(board,moves,limit,row,moveToCol,valmin,valmax,cols,rows); end % if second row > 0 end % if we have a midboard right edge % Now repeat whole thing for left edges. Should be a minor pickup % from having more moves in high-scoring areas. % Check lastedge logic when I make 2 upward moves in a row if lastdir == -cols && vine(i) > cols % a left edge in mid board. Check logic. moveToCol = col-1; [board,moves]=oftl7(board,moves,limit,row,moveToCol,valmin,valmax,rows); end % if we have a midboard left edge end % vertical step lastdir = dir(vine(i)); end % for each leaf of vine % Have now modified board, hopefully improved it in a few high-scoring cases end % function monotonous function [board,moves] = oftl7(board,moves,limit,row,moveToCol,valmin,valmax,rows) while size(moves,1) < limit % loop through all blockages (if any) while ( board(row,moveToCol) >= valmin && ... board(row,moveToCol) <= valmax ) && moveToCol > 1 moveToCol = moveToCol - 1; end if moveToCol > 1 % Found a blockage I'd like to replace moveFromCol = moveToCol-1; while moveFromCol > 0 && ... ( board(row,moveFromCol) < valmin || ... board(row,moveFromCol) > valmax ) moveFromCol = moveFromCol - 1; end if moveFromCol > 0 % Something to replace it with exists, so do slide for j = moveFromCol:moveToCol-1 if size(moves,1) < limit moves = [moves; [row+rows*(j-1), row+rows*j]]; board(row,j+1) = board(row,j); board(row,j) = 0; else break % Used up all moves end end else break % no more nonblocks to use so row finished end else break % no blocks so row finished end % (needed in case block is in other row...?) end % First row while loop. Break out when complete and apply % same logic to second row end function [board,moves]=oftl(board,moves,limit,row,moveToCol,valmin,valmax,cols,rows) while size(moves,1) < limit % loop through all blockages (if any) while ( board(row,moveToCol) >= valmin && ... board(row,moveToCol) <= valmax ) && moveToCol <= cols-1 moveToCol = moveToCol + 1; end if moveToCol < cols % Found a blockage I'd like to replace moveFromCol = moveToCol+1; while moveFromCol <= cols && ... ( board(row,moveFromCol) < valmin || ... board(row,moveFromCol) > valmax ) moveFromCol = moveFromCol + 1; end if moveFromCol <= cols % Something to replace it with exists, so do slide for j = moveToCol:moveFromCol-1 if size(moves,1) < limit moves = [moves; [(row+rows*j), (row+rows*(j-1))]]; board(row,j) = board(row,j+1); board(row,j+1) = 0; else break % Used up all moves end end else break % no more nonblocks to use so row finished end else break % no blocks so row finished end % (needed in case block is in other row...?) end end function [moves, board] = robert1(boardin, limit) % Focus n high-score boards like 8 where there is a high limit but no structure. % Aim to construct a path from scratch. To keep the movement choices simple do % this along an edge; a spiral in centre would require far fewer moves on % average but would require more complex pathfinding % Minor bug with equal values, which may upset vine constructor so add a small % amount of noise. moves = zeros(limit,2); mv=0; [rows,cols] = size(boardin); boardsize = numel(boardin); board = boardin - reshape(1:boardsize,size(boardin))*1e-4; Target = 1; % Pick a corner, any corner [Biggest,BlockAt] = max(board(:)); % Move biggest while mv < limit && Biggest > 0 % Find another block to move Vt=rem(Target-1,rows)+1; Ut=(Target-Vt)/rows+1; % First move onto a channel that will be cleared of blocks Vb=rem(BlockAt-1,rows)+1; Ub=(BlockAt-Vb)/rows+1; if Ub-Ut > 1 % Only if not next to target column Nudge = 1-mod(Vb-1,3); % [+1,0,-1,...] if (Nudge ~= 0) && ~(Vb==rows && Nudge==1) mv=mv+1; moves(mv,1:2) = [BlockAt,BlockAt+Nudge]; board(BlockAt+Nudge) = board(BlockAt); board(BlockAt) = 0; BlockAt = BlockAt+Nudge; end end % Now move towards target Vb = rem(BlockAt-1,rows)+1; U = Ut-(BlockAt-Vb)/rows-1; V = Vt-Vb; % Horiz and Vert moves required [mv,moves,board]=oftl9(U, V, mv, limit, moves, BlockAt, rows, board); board(Target) = -board(Target); % Ignore moved blocks Target=Target+(mod(Ut,2))*(Vt1)+rows*(mod(Ut,2))*(~(Vt1)); [Biggest,BlockAt] = max(board(:)); % Move biggest end % Finding blocks to slide board = abs(board); moves=moves(1:mv,:); end % function boardwalk function [mv,moves,board]=oftl9(U, V, mv, limit, moves, BlockAt, rows, board) while (U~=0 || V~=0) && mv0 % Just ignore erases until I get it working mv=mv+1; moves(mv,1:2) = [BlockAt,BlockAt+1]; board(BlockAt+1) = board(BlockAt); board(BlockAt) = 0; BlockAt = BlockAt+1; V=V-1; else mv=mv+1; moves(mv,1:2) = [BlockAt,BlockAt-1]; board(BlockAt-1) = board(BlockAt); board(BlockAt) = 0; BlockAt = BlockAt-1; V=V+1; end end % Sliding this block end function [vine, vscore, dir, moves] = robert2(board) % Test each square on the board from low to high values to find whether vine % can grow upwards onto an adjacent target square. % To handle plateaux I superimpose a faint watermark on flat areas to nudge vine % towards a space-covering pattern. On each plateau I track 4 orientations % separately, but whenever looking up to a higher level I can pick the best. % Quite pretty, but as all plateaux problems in testset are low-scoring I don't % think it makes much difference. % dir = zeros(size(board)); % points way down vine, 0 at root % done = false(size(board)); % have already examined this one [rows,cols] = size(board); boardsize = numel(board); watermark = reshape(1:boardsize,size(board)) * 1e-6; watermark(:,2:2:cols) = flipud(watermark(:,2:2:cols)); board = board + watermark .* (mod(board,2)-0.5); % superimpose a faint watermark on flat areas. Direction should change % between adjacent levels (but will fail if steps are even) score = board; % score for a vine starting and ending here [~, ind] = sort(board(:)); % Loop through board from low to high values to find the score associated % with the best vine growing down from each square % Needs more care on equal values, for now just weave up and down % -- Could try 4 weaves and pick best, or proper handling of plateaux stepvec = [-rows,-1,1,rows]; for i = 1:boardsize; test = ind(i); if board(test) < .1 continue end for step = stepvec; targ = test + step; if targ > 0 && targ <= boardsize && ... (abs(step)==rows || mod(min(test,targ), rows)) % consider only adjacent squares on board if (board(targ) > board(test)) && (board(targ)+score(test) > score(targ)) % Targ can grow from me (and has nothing better yet) score(targ) = score(test) + board(targ); % add test vine to targ score dir(targ) = -step; % and note where it came from end end end end % Assemble vine from top down [~,leaf] = max(score(:)); vine = []; while dir(leaf)~=0 vine = [vine;leaf]; leaf = leaf+dir(leaf); end vine = flipud([vine;leaf]); % return it in correct order vscore = score(vine(end)); moves = []; end % growvine function [moves,vine] = robert3(board, moves, vine, limit) % modified version of robert2 to finish off an incomplete vine % Perform moves on the board: for i = 1:size(moves,1) board(moves(i,:)) = [0 board(moves(i,1))]; end % clear out unneeded parts of board last = board(vine(1)); board(~board)=NaN; board(board>last)=NaN; board(vine(1))=last; dir = zeros(size(board)); % points way down vine, 0 at root [rows,cols] = size(board); boardsize = numel(board); score = board; % score for a vine starting and ending here [ign, ind] = sort(board(:)); % Loop through board from low to high values to find the score associated % with the best vine growing down from each square stepvec = [-rows,-1,1,rows]; for i = 1:boardsize; test = ind(i); if isnan(board(test)) break; end for step = stepvec; targ = test + step; if targ > 0 && targ <= boardsize && ... (abs(step)==rows || mod(min(test,targ), rows)) % consider only adjacent squares on board if (board(targ) > board(test)) && (board(targ)+score(test) > score(targ)) % Targ can grow from me (and has nothing better yet) score(targ) = score(test) + board(targ); % add test vine to targ score dir(targ) = -step; % and note where it came from end end end end % Assemble vine from top down leaf = vine(1); tip = []; while dir(leaf)~=0 leaf = leaf+dir(leaf); tip = [tip leaf]; end vine = [fliplr(tip) vine]; end function tf = ismemberSimpl( a, s ) % behaves like ismember(a,s) for typical input and one output, % but has no error checking and is faster % MiVö [m,n] = size(a); tf = false(m,n); for ii = 1:m*n tf(ii) = any(a(ii)==s(:)); end end```