| Code: |
function finalAnswer = solver(numPegs,numColors,guessLimit,puzzleID)
if (numColors^numPegs < 5e4) % 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
[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().
if numPegs-lsr==2,
finalAnswer(fr)=[cs(1,1) cs(2,1)];
return
end
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,guess,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
guess = ones(1,numPegs); % Our guess
T = 0;
j = 0;
k = 1;
colors_found=logical(zeros(numColors,1));
lsr = 0; %Number of pegs identified?
secondaryColor = 1; %The secondary color we're testing
mc = 0;
for i = 1:numColors-1
guess(fr) = i;
if (secondaryColor <= j)
guess(fr(k)) = cs(secondaryColor,1);
[black,white,numCallsMade] = scoreme(guess,puzzleID);
black = black + white - 1 - lsr;
if white
if (white > 1)
guess(fr(k)) = i;
fr(k) = [];
lsr = lsr + 1;
black = black - 1;
T = T + 1;
else
k = k + 1;
end
else
fr(k)=[];
cs(secondaryColor,2) = cs(secondaryColor,2)-1;
lsr=lsr+1;
if (cs(secondaryColor,2)==0)
mc = cs(secondaryColor,1);
colors_found(secondaryColor)=1;
if sum(cs(:,2))~=0
[buh,secondaryColor]=max(cs(:,2));
else
secondaryColor=secondaryColor+1;
end
k = 1;
end
end
else
[black,white,numCallsMade] = scoreme(guess,puzzleID);
black = black - lsr;
end
if black
j=j+1;
cs(j,1)=i;
cs(j,2)=black;
T=T+black;
else
mc=i;
end
if (numCallsMade >= guessLimit) | (T >= numPegs)
break;
end
end
if (T < numPegs)
j = j+1;
cs(j,1) = numColors;
cs(j,2) = numPegs-T;
end
cs=cs(~colors_found(1:j),:);
if isempty(cs),
lsr = numPegs;
return
elseif size(cs,1) == 1;
guess(fr) = cs(1,1);
lsr = numPegs;
return
end
if (numCallsMade >= guessLimit)
j = 1;
for i = 1:size(cs,1)
guess(fr(j:j+cs(i,2)-1)) = cs(i,1);
j=j+cs(i,2);
end
lsr = numPegs;
return
end
if mc
guess(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);
guess(fr) = c1;
while n2
guess(fr(i)) = c2;
[black,white,numCallsMade]=scoreme(guess,puzzleID);
if (white==0)
fr(i) = [];
n2 = n2-1;
lsr = lsr+1;
elseif (white > 1)
guess(fr(i)) = c1;
fr(i) = [];
cs(1,2) = cs (1,2) - 1;
lsr = lsr+1;
else
guess(fr(i)) = c1;
i = i+1;
end
if (numCallsMade >= guessLimit)
guess(fr(1:n2)) = c2;
fr = fr(n2+1:end);
for i = 3:size(cs,1)
guess(fr(1:cs(i,2))) = cs(i,1);
fr = fr(cs(i,2)+1:end);
end
lsr = numPegs;
return
end
end
guess(fr) = c2;
cs(2,:) = [];
[i,j] = sort(-cs(:,2));
cs = cs([j(end); j(1:end-1)],:);
if (size(cs,1) == 1)
guess(fr) = cs(1,1);
lsr = numPegs;
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [ind,numCallsMade] = ffclp(gs,index,n,cl,b0,guessLimit,puzzleID)
persistent guessesCache
persistent guessesCache answersCache
numCallsMade = 0;
len = length(index);
oneToL=1:len;
if isempty(guessesCache) | length(guessesCache) < len | isempty(guessesCache{len})
twoexp = 1;
guesses = zeros(1, 0);
for i = 1:len % MATLAB knows how to optimize this
guesses = [ ...
guesses zeros(twoexp, 1); ...
guesses ones(twoexp, 1)];
twoexp = twoexp * 2;
end
guessesCache{len} = guesses;
else
guesses = guessesCache{len};
end
answers = guesses(sum(guesses,2) == n,:)';
if isempty(answersCache) | size(answersCache, 1) < len | size(answersCache, 2) < n+1 | isempty(answersCache{len,n+1})
answers = guesses(sum(guesses,2) == n,:)';
answersCache{len, n+1} = answers;
else
answers = answersCache{len, n+1};
end
count = 0;
while (size(answers,2)~= 1) & (numCallsMade<guessLimit)
count = count+1;
if (count == 1)
bestguess = (oneToL)>len/2;
elseif (count == 2)
bestguess = (oneToL <= len/4)+(oneToL > len*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))))';
ind = find(answers(:,ceil(.1602*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)];
end
|
64.25, 
35.75 (78.82 taken)