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

fcol_a_07

by Stijn Helsen

Status: Passed
Results:  64.55,  35.45 (78.35 taken)
CPU Time: 129.036
Score: 1252.13
Submitted at: 2001-09-21 16:37:37 UTC
Scored at: 2001-09-21 17:32:03 UTC

Current Rank: 2nd
Based on: fcol_a_06 (diff)

Comments
Stijn Helsen
21 Sep 2001
futher improvements ?
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

if numColors<=1
	finalAnswer=ones(1,numPegs);
	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 [cols,ng,free,answ,lsure]=findcols(np,ncol,guessLim,ID)
free=1:np;
cols=zeros(ncol,1);
answ=ones(1,np);
tot=0;
k=1;
lsure=0;
l=0;
nulcol=0;
for i=1:ncol-1
	answ(free)=i;
	if l
		answ(free(k))=l;
		[b,w,ng]=scoreme(answ,ID);
		b=b+w-1-lsure;
		if w
			if w>1
				answ(free(k))=i;
				free(k)=[];
				lsure=lsure+1;
				b=b-1;
				tot=tot+1;
			else
				k=k+1;
			end
		else
			free(k)=[];
			cols(l)=cols(l)-1;
			lsure=lsure+1;
		end
		if length(free)<cols(l)+k
			answ(free(k:end))=l;
			lsure=lsure+cols(l);
			cols(l)=0;
			free=free(1:k-1);
		end
		if cols(l)==0
			nulcol=l;
			if any(cols)
				[xx,l]=max(cols);
			else
				l=0;
			end
			k=1;
		end
	else
		[b,w,ng]=scoreme(answ,ID);
		b=b-lsure;
	end
	cols(i)=b;
	tot=tot+b;
	if b
		if l==0
			l=i;
		end
	else
		nulcol=i;
	end
	if ng>=guessLim | tot>=np
		break;
	end
end	% for
cols(ncol)=np-tot;

[i,j,cols]=find(cols);
if isempty(cols)
	lsure=np;	%necessary?
	return
elseif length(cols)==1
	answ(free)=cols;
	lsure=np;
	return
end
cols=[i cols];

if ng>=guessLim
	j=1;
	for i=1:size(cols,1)
		answ(free(j:j+cols(i,2)-1))=cols(i,1);
		j=j+cols(i,2);
	end
	lsure=np;
	return;
end
if nulcol
	answ(free)=nulcol;
	l=find(i==l);
	[i,ng]=ffc(answ,free(k:end),cols(l,2),cols(l,1),lsure,guessLim,ID);
	answ(free(i+k-1))=cols(l,1);
	lsure=lsure+cols(l,2);
	free(i+k-1)=[];
	cols(l,:)=[];
	if ng>=guessLim | lsure>=np
		for j=1:size(cols,1)
			answ(free(1:cols(j,2)))=cols(j,1);
			free=free(cols(j,2)+1:end);
		end
		lsure=np;
		return
	end
else
	[i,r1]=max(cols(2:end,2));
	cols=cols([1 r1+1 2:r1 r1+2:end],:);
	n1=cols(1,2);
	n2=cols(2,2);
	c1=cols(1,1);
	c2=cols(2,1);
	answ(free)=c1;
	while n1&n2
		answ(free(k))=c2;
		[b,w,ng]=scoreme(answ,ID);
		if w
			answ(free(k))=c1;
			if w>1
				free(k)=[];
				n1=n1-1;
				lsure=lsure+1;
			else
				k=k+1;
			end
		else
			free(k)=[];
			n2=n2-1;
			lsure=lsure+1;
		end	% no w
		if ng>=guessLim
			j=n1+n2;
			answ(free(n1+1:n1+n2))=c2;
			for i=3:size(cols,1)
				answ(free(j+1:j+cols(i,2)))=cols(i,1);
				j=j+cols(i,2);
			end
			lsure=np;
			return
		end
	end	% while n1
	if n1
		cols(1,2)=n1;
		cols=cols([1 3:end],:);
		answ(free)=c2;
	elseif n2
		cols=cols(2:end,:);
		cols(1,2)=n2;
	else
		cols=cols(3:end,:);
	end
	if size(cols,1)==1
		answ(free)=cols(1,1);
		lsure=np;
		return
	end
end
[i,j]=sort(-cols(:,2));
cols=cols(j,:);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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