# Diffing " better maxcolor_sievesmall_b" and "better maxcolor_sievesmall_b4"

 Title: better maxcolor_sievesmall_b better maxcolor_sievesmall_b4 Author: Francois Glineur Francois Glineur Submitted: 2001-09-21 09:39:14 UTC 2001-09-21 10:46:42 UTC Status: Passed Passed Score: 1257.07 1257.84 Result: 64.16,  35.84 (78.81 taken) 64.20,  35.80 (78.88 taken) CPU Time: 129.636 129.608 Code: ```function finalAnswer = solver(numPegs,numColors,guessLimit,puzzleID) if numColors <= 1 finalAnswer = ones(1, numPegs); end vecColors = 1:numColors; vecPegs = 1:numPegs; if numColors^numPegs < 5e4 % a sieve for small puzzles boards = make(numPegs, numColors); boards = boards(:, randperm(size(boards, 2))); nb = size(boards,2); nguess = 0; while size(boards,2) > 1 & nguess <= guessLimit guess = boards(:, 1); [black,white,nguess]=scoreme(guess',puzzleID); boards(:, sum(guess*(ones(1, size(boards,2))) == boards) ~= black) = []; boards(:, sum(min(histc(guess, vecColors)*ones(1, size(boards,2)), histc(boards, vecColors))) ~= (black+white)); end finalAnswer = boards(:, 1)'; return end % ifsmall small = (numColors^numPegs < 5e4); if (small) % a sieve for small puzzles boards = make(numPegs, numColors); nb = size(boards,2); nguess = 0; sg = 0; while (nb > 1) & (nguess <= guessLimit) guess = boards(:,ceil(rand * nb)); [black,white,nguess]=scoreme(guess',puzzleID); boards = prune(black, white, guess, boards, numColors); nb = size(boards,2); end finalAnswer = boards(:,ceil(rand * nb))'; return end % ifsmall [cs,numCallsMade,fr,finalAnswer,lsr] = findcols(numPegs,numColors,guessLimit,puzzleID); if lsr>= numPegs | numCallsMade>= guessLimit | isempty(cs) return; end [rows,cols] = size(cs); % to cancel consequentive calls to size(). % for i = 1:size(cs,1) for i = 1:rows [ind,numCallsMade] = ffc(finalAnswer,fr,cs(i,2),cs(i,1),lsr,guessLimit,puzzleID); finalAnswer(fr(ind)) = cs(i,1); fr(ind) = []; if numCallsMade >= guessLimit, for j = i+1:rows finalAnswer(fr(1:cs(j,2))) = cs(j,1); fr = fr(cs(j,2)+1:end); end; return; end; lsr = lsr + cs(i,2); if lsr >= numPegs, return; end; end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [ind,numCallsMade] = ffc(gs,x,n,col,b0,gsLim,puzzleID) if length(x) == n, ind = 1:n; numCallsMade = 0; return; end; if (length(x)<14) & (n~= 1) [ind,numCallsMade] = ffclp(gs,x,n,col,b0,gsLim,puzzleID); return; end i = floor(length(x)/2); g = gs; g(x(1:i)) = col; [black,white,numCallsMade] = scoreme(g,puzzleID); nv = n-black+b0; if black>b0, if numCallsMade>= gsLim, ind = [1:black-b0,(i+1:i+nv)]; return; end; [i1,numCallsMade] = ffc(gs,x(1:i),black-b0,col,b0,gsLim,puzzleID); if numCallsMade>= gsLim, ind = [i1,(i+1:i+nv)]; return; end elseif numCallsMade>= gsLim, ind = i+1:i+nv; return; else i1 = []; end if nv, [i2,numCallsMade] = ffc(gs,x(i+1:end),nv,col,b0,gsLim,puzzleID); i2 = i2+i; else i2 = []; end; ind = [i1 i2]; function boards = prune(black, white, guess, boards, nc) nb = size(boards,2); boards(:, sum(repmat(guess,1,nb) == boards) ~= black) = []; nb = size(boards,2); if nb > 0 w = sum(min(repmat(histc(guess, 1:nc),1,nb), histc(boards, 1:nc))) ~= (black+white); boards(:, w) = []; end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [cs,numCallsMade,fr,a,lsr] = findcols(numPegs,numColors,guessLimit,puzzleID) fr = 1:numPegs; %Unidentified columns? cs = zeros(numColors,2); % Second column is number of unidentified pegs of a given color a = ones(1,numPegs); %Our guess T = 0; j = 0; k = 1; colors_found=[]; lsr = 0; %Number of pegs identified? l = 1; %The secondary color we're testing mc = 0; for i = 1:numColors-1 a(fr) = i; if l<= j a(fr(k)) = cs(l,1); [black,white,numCallsMade] = scoreme(a,puzzleID); black = black + white - 1 - lsr; if white if white>1 a(fr(k)) = i; fr(k) = []; lsr = lsr + 1; black = black - 1; T = T + 1; else k = k + 1; end else fr(k) = []; cs(l,2) = cs(l,2)-1; lsr = lsr+1; if cs(l,2)==0 mc = cs(l,1); % l = l+1; colors_found=[colors_found l]; if sum(cs(:,2))~=0 [buh,l]=max(cs(:,2)); else l=l+1; end; k = 1; end; end; else [black,white,numCallsMade] = scoreme(a,puzzleID); black = black-lsr; end if black, j = j+1; cs(j,:) = [i,black]; T = T+black; else mc = i; end if numCallsMade>= guessLimit | T>= numPegs, break; end; end if T= guessLimit, j = 1; for i = 1:size(cs,1) a(fr(j:j+cs(i,2)-1)) = cs(i,1); j = j+cs(i,2); end lsr = numPegs; return; end if mc, a(fr) = mc; [i,j] = sort(-cs(:,2)); cs = cs(j,:); else cs = cs([2 1 3:end],:); i = k; n1 = cs(1,2); n2 = cs(2,2); c1 = cs(1,1); c2 = cs(2,1); a(fr) = c1; while n2 a(fr(i)) = c2; [black,white,numCallsMade] = scoreme(a,puzzleID); if white==0 fr(i) = []; n2 = n2-1; lsr = lsr+1; elseif white > 1 a(fr(i)) = c1; fr(i) = []; cs(1,2) = cs (1,2) - 1; lsr = lsr+1; else a(fr(i)) = c1; i = i+1; end if numCallsMade>= guessLimit, a(fr(1:n2)) = c2; fr = fr(n2+1:end); for i = 3:size(cs,1) a(fr(1:cs(i,2))) = cs(i,1); fr = fr(cs(i,2)+1:end); end; lsr = numPegs; return; end; end; a(fr) = c2; cs(2,:) = []; [i,j] = sort(-cs(:,2)); cs = cs([j(end);j(1:end-1)],:); if size(cs,1) == 1, a(fr) = cs(1,1); lsr = numPegs; end; end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [ind,numCallsMade] = ffclp(gs,index,n,cl,b0,guessLimit,puzzleID) persistent guessesCache numCallsMade = 0; l = length(index); oneToL=1:l; if isempty(guessesCache) | length(guessesCache) < l | isempty(guessesCache{l}) twoexp = 1; guesses = zeros(1, 0); for i = oneToL guesses = [guesses zeros(twoexp, 1);guesses ones(twoexp, 1)]; twoexp = twoexp * 2; end; guessesCache{l} = guesses; else guesses = guessesCache{l}; end answers = guesses(sum(guesses,2) == n,:)'; count = 0; while (size(answers,2)~= 1) & (numCallsMadel/2; elseif count == 2 bestguess = (oneToL <= l/4)+(oneToL > l*0.75); else [m,bestguessn] = min(sum(histc(guesses*answers,0:n,2).^2,2)); bestguess = guesses(bestguessn,:); end g = gs; g(index(find(bestguess))) = cl; [black,white,numCallsMade] = scoreme(g,puzzleID); answers = answers(:,find(bestguess*answers == black-b0)); end ind = find(answers(:,1+floor(rand(1)*size(answers,2))))'; function boards = make(np, nc) if (np <= 1), boards = 1:nc; else boards = [repmat(make(np-1, nc), 1, nc); reshape(repmat(1:nc, nc^(np-1),1), 1, nc^np)]; persistent boardsCache if np == 1 boards = 1:nc; else if isempty(boardsCache) | size(boardsCache, 1) < np | size(boardsCache, 2) < nc | isempty(boardsCache{np, nc}) boardsCache{np, nc} = [repmat(make(np-1, nc), 1, nc); reshape(repmat(1:nc, nc^(np-1),1), 1, nc^np)]; end boards = boardsCache{np, nc}; end ```