Finish 2001-09-21 00:00:00 UTC

MORE BLACKS

by Johannes Schneider

Status: Passed
Results:  64.25,  35.75 (78.78 taken)
CPU Time: 127.353
Score: 1256.29
Submitted at: 2001-09-21 16:58:03 UTC
Scored at: 2001-09-21 18:24:36 UTC

Current Rank: 5th
Based on: infinite_tunning_06 (diff)

Comments
Johannes Schneider
21 Sep 2001
winning
Please login or create a profile.
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;
         if cs(1,2) == 0
            cs(1,:) = [c2 n2];
            c2 = c1;
            break
         end
      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
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] = 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((.2222+0.02*(2*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)];
   end