fcol_b_01

function finalAnswer = solver(numPegs,numColors,guessLimit,puzzleID)

if (numColors^numPegs < 9999) % a sieve for small puzzles

    numCallsMade=0;
bestScore=-Inf;

convSol=numColors.^[numPegs-1:-1:0];
posSols=[1:numColors^numPegs];

while numCallsMade<guessLimit
    numSols=length(posSols);
    notok=1;
    while notok,
    guessid=posSols(floor(rand(1)*numSols+1));
    guess=rem(fix(guessid./convSol),numColors)+1;
    if length(unique(guess))>=numColors/2-1, 
        notok=0; 
    end;
end;
    [black,white,numCallsMade]=scoremej(numColors,guess,puzzleID);
    
    ReducedSols=[];
    for i = posSols,
            solj=rem(fix(i./convSol),numColors)+1;
            [btry wtry]=calculatescore(solj,guess);
            if btry==black & wtry==white,
                ReducedSols=[ReducedSols i];
            end;
        end;

    posSols=ReducedSols;
    if size(ReducedSols,2) == 1,
        finalAnswer=rem(fix(ReducedSols(1)./convSol),numColors)+1;
            finalAnswer=numColors+1-finalAnswer;
                return
    else
        finalAnswer=rem(fix(ReducedSols(1)./convSol),numColors)+1;
       end
   end
           finalAnswer=numColors+1-finalAnswer;
   return
end %small

[cs,numCallsMade,fr,finalAnswer,lsr]=findcols(numPegs,numColors,guessLimit,puzzleID);

if (lsr >= numPegs) | (numCallsMade >= guessLimit) | isempty(cs)
            finalAnswer=numColors+1-finalAnswer;
    return 
end

[rows,cols] = size(cs); % to cancel consequentive calls to size().

if numPegs-lsr==2,
   finalAnswer(fr)=[cs(1,1) cs(2,1)]; 
               finalAnswer=numColors+1-finalAnswer;
   return
end

for i = 1:rows
    [ind,numCallsMade]=ffcj(numColors,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 
                    finalAnswer=numColors+1-finalAnswer;
        return 
    end
    lsr = lsr + cs(i,2); 
    if (lsr >= numPegs) 
                    finalAnswer=numColors+1-finalAnswer;
        return
    end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [ind,numCallsMade] = ffcj(numColors,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]  =  ffclpj(numColors,gs,x,n,col,b0,gsLim,puzzleID);
    return
end
i = floor(length(x)/2); 
g = gs; 
g(x(1:i)) = col; 
[black,white,numCallsMade]  =  scoremej(numColors,g,puzzleID);
nv = n-black+b0;
if black>b0, 
    if numCallsMade>= gsLim, 
        ind = [1:black-b0,(i+1:i+nv)]; 
        return 
    end
    [i1,numCallsMade] = ffcj(numColors,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] = ffcj(numColors,gs,x(i+1:end),nv,col,b0,gsLim,puzzleID); 
    i2 = i2+i;
else
    i2 = []; 
end

ind = [i1 i2];

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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] = scoremej(numColors,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] = scoremej(numColors,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]=scoremej(numColors,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] = ffclpj(numColors,gs,index,n,cl,b0,guessLimit,puzzleID)
persistent guessesCache
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,:)';
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] = scoremej(numColors,g,puzzleID);
    answers = answers(:,find(bestguess*answers == black-b0));
end
%ind = find(answers(:,1+floor(rand(1)*size(answers,2))))';
ind = find(answers(:,ceil((.2222+0.02*(2*rand-1))*size(answers,2))))';



%%%%%%%%%%%%

function [b, w] = calculatescore(guess,soln)
%CALCULATESCORE Calcluate the score for a given guess.
% 
% [black,white] = CALCULATESCORE(guess,solution) is the number of black and
% white pegs for this guess given this solution.

% Algorithm by Tom and/or Zhiping.
b=sum(soln==guess);
n=max(max(guess),max(soln));
w=sum(min(sparse(guess,1,1,n,1),sparse(soln,1,1,n,1))) - b;

%%%%%%%%%

function [black,white,numCallsMade] = scoremej(numColors,g,puzzleID);
    g=numColors+1-g;
    [black,white,numCallsMade] = scoreme(g,puzzleID);