# Diffing "no snow yet" and "TLL223"

 Title: no snow yet TLL223 Author: Niilo Sirola Timothy Alderson Submitted: 2005-11-09 04:35:21 UTC 2005-11-09 06:00:24 UTC Status: Passed Passed Score: 100.769 100.786 Result: 967.4185 967.4185 CPU Time: 59.981 60.0238 Code: ```function [solution] = solver(puzzle,list) rand('seed',1); list=list(:,end:-1:1); global h iX iN col_selection blockmap rowmap colmap; h = reshape(1:9,3,3); g = ceil((1:9)/3); h = uint8((h(g,g)-1)*9 + repmat(h,3)); h1 = reshape(1:81,9,9); iX = uint8([h h1 h1']); iN = ones(81,81)*3; for rcgi=1:27 for ci=1:9 for ci2=ci+1:9 index1=iX(ci,rcgi);index2=iX(ci2,rcgi); iN(index1,index2)=iN(index1,index2)-1; end end for ci=1:9 for ci2=ci+1:9 index1=iX(ci,rcgi);index2=iX(ci2,rcgi); iN(index1,index2)=iN(index1,index2)-1; end end end for ci=1:81 for ci2=ci+1:81 iN(ci2,ci)=iN(ci,ci2); end for ci2=ci+1:81 iN(ci2,ci)=iN(ci,ci2); end end col_selection = [[4 5 6 7 8 9];[7 8 9 7 8 9]]; blockmap=kron(reshape(1:9,3,3),ones(3)); rowmap = repmat((1:9)',1,9); colmap = repmat((1:9),9,1); [solution,s] =solverC(puzzle,list); if floor(s) == 19; [sol2,s2]=solverC(puzzle(:,end:-1:1),list); if s2 200; [sol2,s2]=solverC(puzzle(end:-1:1,:),list); if s2100 [solution1,s2]=improver3(puzzle,list,solution); if s2 200 [sol2,s2] =solverC(puzzle(end:-1:1,:),list); if s2100 [solution1,s2] =improver3(puzzle,list,solution); if s29 ) reruns=reruns+1; elseif ( reruns==1 & bestscore2>25 ) reruns=reruns+1; else reruns=1e8; end end solution = bestsol; % --- prepare for final improvers n=ceil(bestscore2); X = solution(iX); sX = sum(X); mX = sum(sX)/27; XX=zeros(81,3); for i=q XX(i,:)=find(sum(iX==i)); end bv=1; for i=1:n bVerb=0; for iEl=q I=XX(iEl,:); s1=sum(sX(I)-mX); if (s1>0&&sum(sX(I)>mX)<2)||(s1<0&&sum(sX(I)0 j=find(dx<0.8&dx+s1*2>0&dx~=0); else j=find(dx>-0.8&dx+s1*2<0&dx~=0); end if ~isempty(j) S0=sX-mX; s=sum(abs(S0)); m=0; for k=1:numel(j) S=S0; S(I)=S(I)+dx(j(k)); J=XX(q(j(k)),:); S(J)=S(J)-dx(j(k)); T=sum(abs(S)); if T9 ) reruns=reruns+1; elseif ( reruns==1 & bestscore2>25 ) reruns=reruns+1; else reruns=1e8; end end solution = bestsol; % --- prepare for final improvers n=ceil(bestscore2); X = solution(iX); sX = sum(X); mX = sum(sX)/27; XX=zeros(81,3); for i=q XX(i,:)=find(sum(iX==i)); end bv=1; for i=1:n bVerb=0; for iEl=q I=XX(iEl,:); s1=sum(sX(I)-mX); if (s1>0&&sum(sX(I)>mX)<2)||(s1<0&&sum(sX(I)0 j=find(dx<0.8&dx+s1*2>0&dx~=0); else j=find(dx>-0.8&dx+s1*2<0&dx~=0); end if ~isempty(j) S0=sX-mX; s=sum(abs(S0)); m=0; for k=1:numel(j) S=S0; S(I)=S(I)+dx(j(k)); J=XX(q(j(k)),:); S(J)=S(J)-dx(j(k)); T=sum(abs(S)); if T=vprev) break end vprev=v; end ii=yy; if (ii==size(S,1)) ii=1; cnt=cnt+1; if (cnt==4) break end end yy=ii+1; tmp=S(zeros(numel(a)-ii,1)+ii,:); tmp=tmp+a(yy:end,[1 1 1])-a(ii); tmp=sum(abs(tmp),2)-sum(abs(S(ii,:))); tmp2=S(yy:end,:)-a(yy:numel(idx),[1 1 1])+a(ii); tmp2=[sum(abs(tmp2),2)-sum(abs(S(yy:end,:)),2) ; zeros(N,1)]; tmp=tmp+tmp2; [tmp,idx3]=min(tmp); if (tmp<0) % Replace one list value by another zz = idx3+ii; tmp=a(zz); a(zz)=a(ii); a(ii)=tmp; out(x(ii),y(ii))=a(ii); if (zz<=size(S,1)) % Swaps the two currently used list values out(x(zz),y(zz))=a(zz); else % Re-calculate the optimal sum optsum=optsum+(a(ii)-a(zz))/9; end % Re-calculate the various sums rowsum=sum(out,2); colsum=sum(out,1)'; sqsum=sum(out(isquare),2); S=[rowsum(x) colsum(y) sqsum(square(idx))]-optsum; end if (ii==1) sums = [rowsum ; colsum ; sqsum]; v = sum(abs(sum(sums)/numel(sums)-sums)); if (v>=vprev) break end vprev=v; end ii=yy; if (ii==size(S,1));ii=1;cnt=cnt+1;if (cnt==4);break;end;end; end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % All of the previous algorithms have focussed on pairwise switching % of weights. The main loop is a fast random method for choosing the % blocks to be switched. What follows that (formerly improver2) is a % slower method comparing the scores before and after each pair of blocks % already in the matrix have been swapped. Then improver3 is a faster % method of doing the same thing, but only approximates the change in % score, and also allows swaps with unassigned elements in the list. % This improver looks at swapping three elements at a time (although % not exhaustively), and can trivially be altered for more than three % elements (increasing to more than 3 would probably minimally affect % blocks to be switched. What follows that (formerly improver2) is a % slower method comparing the scores before and after each pair of blocks % already in the matrix have been swapped. Then improver3 is a faster % method of doing the same thing, but only approximates the change in % score, and also allows swaps with unassigned elements in the list. % This improver looks at swapping three elements at a time (although % not exhaustively), and can trivially be altered for more than three % elements (increasing to more than 3 would probably minimally affect % the score though). function [out,flag]=improver4(in,list,solution) global iX; %Initialize idx=find(in==0); a=solution(idx); N=numel(a); a=[a ; list(~ismembc(list,sort(a)))]; sums = sum(solution(iX)); bsc = sum(abs(sum(sums)/27-sums)); bsc2=bsc; ba = a; [b,idx2]=sort(a); zok=length(b)-2; for ii=1:zok tmp=a(idx2(ii:ii+2)); tmp=a(idx2(ii:ii+2)); a=ba; a(idx2(ii:ii+2))=[tmp(2:3) ; tmp(1)]; solution(idx)=a(1:N); sums = sum(solution(iX)); score = sum(abs(sum(sums)/27-sums)); if (score