2001-09-21 00:00:00 UTC

# fcol_a_04_x2

Status: Passed
Results:  61.66,  38.33 (80.83 taken)
CPU Time: 44.673
Score: 1297.18
Submitted at: 2001-09-21 16:27:22 UTC
Scored at: 2001-09-21 16:49:50 UTC

Current Rank: 127th
Based on: fcol_a_04_x1 (diff)
Basis for: fcol_a_05 (diff)

Stijn Helsen
21 Sep 2001
test-return removed
Code
```function finalAnswer = solver(numPegs,numColors,guessLimit,puzzleID)

if guessLimit==1 | numColors==1
return
end

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
return
end % ifsmall

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if length(x) == n,
ind = 1:n;
return;
end;
if (length(x)<0) & (n~= 1)
return;
end
i = floor(length(x)/2);
g = gs;
g(x(1:i)) = col;
nv = n-black+b0;
if black>b0,
ind = [1:black-b0,(i+1:i+nv)];
return;
end;
ind = [i1,(i+1:i+nv)];
return;
end
ind = i+1:i+nv;
return;
else
i1 = [];
end
if nv,
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;
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,:);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
persistent guessesCache
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
count = 0;
count = count+1;
if count == 1
bestguess = (oneToL)>l/2;
elseif count == 2
bestguess = (oneToL <= l/4)+(oneToL > l*0.75);
else
bestguess = guesses(bestguessn,:);
end
g = gs; g(index(find(bestguess))) = cl;