2011-04-20 12:00:00 UTC

# lasttry01

Status: Passed
Results: 6846390 (cyc: 103, node: 9918)
CPU Time: 36.78
Score: 17219.9
Submitted at: 2011-04-20 15:52:26 UTC
Scored at: 2011-04-20 19:15:27 UTC

Current Rank: 141st (Highest: 107th )

Alfonso Nieto-Castanon
20 Apr 2011
something weird with the scoring mechanism... not good enough to contest the winner entry anyway
Oli
20 Apr 2011
If you compare with a random entry like 'Resolution' by Volkan, yours is half the cpu time and 30,000 less. However it has 100 cycles (10 for volkan), and more nodes, maybe that compensated the good scores?
Oli
20 Apr 2011
Resolution is 15th
Alfonso Nieto-Castanon
20 Apr 2011
you are right, cyc=100, should have fix that! great contest to all and congrats to Nick!
Alan Chalker
21 Apr 2011
The scoring algorithms incorporates cyc and nodes. I posted it in haiku form on the blog, but here it is in normal form: score = k1*result + k2*e(k3*runtime) + k4*max(complexity-10,0) + k5*nodes

Where:
k1 = 0.0025
k2 = 5/900 (0.000555)
k3 = 1/9 (0.111111)
k4 = 1
k5 = 1/900 (0.0011111)
Oli
21 Apr 2011
impressively fast though!
Franck Dernoncourt
21 Apr 2011
Nice entry!
It would be great most rules (like the scoring function) were properly documented in http://www.mathworks.com/matlabcentral/contest/contests/32/rules
...
Code
```function board = solver(words, weights, n, penalty)

board = zeros(n);
nwords=numel(words);
total=sum(weights);
[weights,idxweights]=sort(weights,'descend');
words=words(idxweights);
wordlength=cellfun('length',words);
[wordlength,idxwords]=sort(wordlength);
idxpart=[0,find(diff(wordlength)),nwords];
nwords_=diff(idxpart);                           % number of words for each wordlength
lwords_=wordlength(idxpart(2:end));              % list of wordlengths
idxinvalid=lwords_>n;
nwords_(idxinvalid)=[];
lwords_(idxinvalid)=[];
isets_=find(lwords_(1:end-1)+1==lwords_(2:end)); % sets of adjacent wordlengths
sn_=numel(isets_);
slwords_=lwords_(isets_+1);

n_=numel(lwords_);
words_=cell(1,n_);
cweights_=words_;
weights_=words_;
%  aw_=zeros(1,n_);
idxn=0;
for nword_=1:n_,
idx1=idxwords(idxpart(nword_)+1:idxpart(nword_+1));
w=weights(idx1);
%      aw_(nword_)=mean(w);
weights_{nword_}=w;             % sorted gains
cweights_{nword_}=cumsum(w);    % cumulative gains
words_{nword_}=idx1;            % sorted words
if lwords_(nword_)==n, idxn=nword_; end
end

%% FULL BOARD METHOD
if idxn&&(n_==1) % || nwords_(idxn)>=n)
nword_=idxn;
Nw=nwords_(nword_);
Np=lwords_(nword_);
X=cat(1,words{words_{nword_}});
W=weights_{nword_};
[uletters,nill,letters]=unique(X);
Y=reshape(letters,size(X));
Nl=numel(uletters);
Iw=(1:Nw)';
Ip=(1:Np);

% STEP I. finds a subset of 'interesting' words
Distw=accumarray([repmat(Iw,[Np,1]),Y(:)],1);                   % letter distribution for each column-word
Distp=accumarray([reshape(Ip(ones(1,Nw),:),[],1),Y(:)],1);      % letter distribution for each letter position within row-words
%Measure=permute(sum(bsxfun(@times,Distp,permute(Distw,[3,2,1])),2),[3,1,2]); % measure of 'interestness' (words by number-of-columns) (loosely related to number of different row combinations compatible with a given word being placed at a given column)
Measure=permute(sum(bsxfun(@times,log(.01+Distp),permute(Distw,[3,2,1])),2),[3,1,2]); % measure of 'interestness' (words by number-of-columns) (loosely related to number of different row combinations compatible with a given word being placed at a given column)
[maxc,idxc]=sort(Measure(:),'descend');
wc=1+rem(idxc-1,Nw);                                            % list of interesting words
ic=1+(idxc-wc)/Nw;                                              % list of columns (column where each interesting word is to be located)
Nint=min(250,numel(wc));                                        % number of interesting word@column combinations to consider
wc=wc(1:Nint);
ic=ic(1:Nint);

% STEP II. estimates compatibility among interesting words
Comp=cell(1,Nint);                                              % compatible rows for each interesting word (Comp{n}(i,j)=true iff word i at row j is compatible with wc(n)-th word being placed at ic(n)-th column)
for n1=1:Nint,tempy=Y(:,ic(n1));tempy(wc(n1))=0;Comp{n1}=sparse(bsxfun(@eq,tempy,Y(wc(n1),:))); end

xt=Y(:,ic)';
CompPairs=zeros(Nint);                                          % compatible column pairs of interesting words (CompPairs(i,j) = approximately number of rows that can be placed compatible with the wc(i)-th word at column ic(i) and the wc(j)-th word at column ic(j) )
for n1=1:Np,
dt=double(sparse(bsxfun(@eq,xt,Y(wc,n1))));
dt(Nint*(wc-1)+(1:Nint)')=0;
CompPairs=CompPairs+((dt*dt')>0);
end
wt=bsxfun(@eq,ic,ic')|bsxfun(@eq,wc,wc');
CompPairs(wt)=0;

% STEP III. clusters compatibility matrix
thr=.9*n; % note: greedy approach, consider column pairs with (possibly) 90% compatible rows
thrCompPairs=CompPairs>=thr;
[p,q,r]=dmperm(thrCompPairs);
SizeCluster=r(2:end)-r(1:end-1);
nC=numel(r)-1;
wC=zeros(1,nC);
for n1=1:nC,
if SizeCluster(n1)>0
idx=p(r(n1):r(n1+1)-1);
wC(n1)=sum(sum(thrCompPairs(idx,idx)));
end
end
[wC,idxC]=sort(wC,'descend');
%     SizeCluster=SizeCluster(idxC);
wcC=cell(1,nC);                                                 % word clusters (cluster of pairly compatible words wc(wcC{n})) (note: not fully connected set, I would hope for a maximal fully connected set, but...)
for n1=1:nC,
wcC{n1}=p(r(idxC(n1)):r(idxC(n1)+1)-1);
end

% STEP IV. greedy search of word placement within-cluster
% (start with each word as seed and grow a fully connected set)
ns=1;
ws=wcC{ns}; % index to interesting words list
ss=numel(ws);
minssn=min(ss,n);
wcs=wc(ws);
ics=ic(ws);

a=CompPairs(ws,ws);
idxselect=zeros(ss,minssn);
nrowselect=idxselect;
%[nill,idxmax]=max(sum(a,2));
for idxfirst=1:ss,
m=inf;
TrueComp=true;
idxmax=idxfirst;

for n1=1:minssn,
TrueComp=TrueComp&Comp{ws(idxmax)};%&sparse(bsxfun(@eq,Y(:,ics(idxmax)),Y(wcs(idxmax),:)));
idxselect(idxfirst,n1)=idxmax;
nrowselect(idxfirst,n1)=sum(any(TrueComp,1),2);
m=min(m,a(idxmax,:));
[nill,idxmax]=max(m);
if ~nill,break; end
end
end
gain=nrowselect+repmat(1:minssn,[ss,1]); % consider the solution with maximal number of rows+columns
[nill,idxmax]=max(gain(:));
idxmax_r=1+rem(idxmax-1,ss);
idxmax_c=1+(idxmax-idxmax_r)/ss;
idxselect=idxselect(idxmax_r,1:idxmax_c);

IC=[];WC=[];IR=[];WR=[];
TrueComp=true;
for n1=1:numel(idxselect),
TrueComp=TrueComp&Comp{ws(idxselect(n1))};
IC=[IC,ic(ws(idxselect(n1)))];
WC=[WC,wc(ws(idxselect(n1)))]; %board(:,ic(ws(idxselect(n1))))=uletters(Y(wc(ws(idxselect(n1))),:))';
end
s1TrueComp=sum(TrueComp,1);
s2TrueComp=sum(TrueComp,2);
[nill,idxsort]=sort(s1TrueComp);
for n1=1:numel(idxsort),
if any(TrueComp(:,idxsort(n1)))
idx=find(TrueComp(:,idxsort(n1)));
[nill,idxmax]=min(s2TrueComp(idx));
IR=[IR,idxsort(n1)];
WR=[WR,idx(idxmax)]; %board(idxsort(n1),:)=uletters(Y(idx(idxmax),:))';
TrueComp(idx(idxmax),:)=false;
end
end

% cleanup: add other columns among uninteresting words if possible
if numel(IC)<n
Valid=ones(Nw,1);
Valid(WR)=0;
Valid(WC)=0;
TrueComp=true;
for n1=1:numel(IR),
tempy=Y(:,IR(n1));tempy(WR(n1))=0;
TrueComp=TrueComp&sparse(bsxfun(@eq,tempy,Y(WR(n1),:)));
end
TrueComp(~Valid,:)=false;
TrueComp(:,IC)=false;
s1TrueComp=sum(TrueComp,1);
s2TrueComp=sum(TrueComp,2);
[nill,idxsort]=sort(s1TrueComp);
for n1=1:numel(idxsort),
if any(TrueComp(:,idxsort(n1)))
idx=find(TrueComp(:,idxsort(n1)));
[nill,idxmax]=min(s2TrueComp(idx));
IC=[IC,idxsort(n1)];
WC=[WC,idx(idxmax)];
%board(:,idxsort(n1))=uletters(Y(idx(idxmax),:))';
TrueComp(idx(idxmax),:)=false;
end
end
end

% cleanup: remove rows/columns iteratively and find maximum score
Nr=numel(IR);
Nc=numel(IC);
[IR,irsort]=sort(IR);
WR=WR(irsort);
[IC,icsort]=sort(IC);
WC=WC(icsort);
PR=[0,find(IR(2:end)-IR(1:end-1)>1),numel(IR)];
NR=numel(PR)-1;
PC=[0,find(IC(2:end)-IC(1:end-1)>1),numel(IC)];
NC=numel(PC)-1;

BLOCKS_R=ones(5,NR);
for n1=1:NR,
w=W(WR(PR(n1)+1:PR(n1+1)));
nw=numel(w);
w1=w(1:2:end);sw1=sum(w1);
w2=w(2:2:end);sw2=sum(w2);
BLOCKS_R(1,n1)=nw;
if nw<=1,       BLOCKS_R(2,n1)=-sum(w); BLOCKS_R(3,n1)=0; BLOCKS_C(4,n1)=1;
elseif sw1>sw2, BLOCKS_R(2,n1)=(nw>1)*penalty*(n-Nc)-sw2; BLOCKS_R(3,n1)=numel(w2); BLOCKS_R(4,n1)=1;
else            BLOCKS_R(2,n1)=(nw>1)*penalty*(n-Nc)-sw1; BLOCKS_R(3,n1)=numel(w1); BLOCKS_R(4,n1)=2; end
end
BLOCKS_C=ones(5,NC);
for n1=1:NC,
w=W(WC(PC(n1)+1:PC(n1+1)));
nw=numel(w);
w1=w(1:2:end);sw1=sum(w1);
w2=w(2:2:end);sw2=sum(w2);
BLOCKS_C(1,n1)=nw;
if nw<=1,       BLOCKS_C(2,n1)=-sum(w); BLOCKS_C(3,n1)=0; BLOCKS_C(4,n1)=1;
elseif sw1>sw2, BLOCKS_C(2,n1)=(nw>1)*penalty*(n-Nr)-sw2; BLOCKS_C(3,n1)=numel(w2); BLOCKS_C(4,n1)=1;
else            BLOCKS_C(2,n1)=(nw>1)*penalty*(n-Nr)-sw1; BLOCKS_C(3,n1)=numel(w1); BLOCKS_C(4,n1)=2; end
end
score=total - (sum(W(WR))+sum(W(WC))-penalty*((n-Nr)*sum(BLOCKS_C(1,:)>1)+(n-Nc)*sum(BLOCKS_R(1,:)>1)));
G=0;
maxG=0;
maxBLOCKS={BLOCKS_R(5,:),BLOCKS_C(5,:)};
while any(BLOCKS_R(5,:))||any(BLOCKS_C(5,:)),
[maxgc,idxmaxgc]=max(BLOCKS_C(2,:));
[maxgr,idxmaxgr]=max(BLOCKS_R(2,:));
maxgc=maxgc-penalty*BLOCKS_C(3,idxmaxgc)*sum(BLOCKS_R(1,:)>1);
maxgr=maxgr-penalty*BLOCKS_R(3,idxmaxgr)*sum(BLOCKS_C(1,:)>1);
if maxgc>maxgr
BLOCKS_R(2,:)=BLOCKS_R(2,:)+penalty*BLOCKS_C(3,idxmaxgc)*(BLOCKS_R(1,:)>1);
BLOCKS_C(5,idxmaxgc)=0;
BLOCKS_C(2,idxmaxgc)=-inf;
G=G+maxgc;
else
BLOCKS_C(2,:)=BLOCKS_C(2,:)+penalty*BLOCKS_R(3,idxmaxgr)*(BLOCKS_C(1,:)>1);
BLOCKS_R(5,idxmaxgr)=0;
BLOCKS_R(2,idxmaxgr)=-inf;
G=G+maxgr;
end
if G>maxG,
maxG=G;
maxBLOCKS={BLOCKS_R(5,:),BLOCKS_C(5,:)};
end
end
maxGfill=penalty*((n-Nr)*(sum(BLOCKS_C(1,:)>1)-1)+(n-Nc)*(sum(BLOCKS_R(1,:)>1)-1));
if maxG<maxGfill
score=score-maxGfill;
board=uletters(end)+ones(n); % fill with random
newIC=IC;newWC=WC;newIR=IR;newWR=WR;
else % remove selected rows/columns
score=score-maxG;
BLOCKS_R(5,:)=maxBLOCKS{1};
BLOCKS_C(5,:)=maxBLOCKS{2};
newIC=[];newWC=[];newIR=[];newWR=[];
for n1=1:NR,
if BLOCKS_R(5,n1)
newIR=[newIR,IR(PR(n1)+1:PR(n1+1))];
newWR=[newWR,WR(PR(n1)+1:PR(n1+1))];
elseif BLOCKS_R(4,n1)==1
newIR=[newIR,IR(PR(n1)+1:2:PR(n1+1))];
newWR=[newWR,WR(PR(n1)+1:2:PR(n1+1))];
elseif BLOCKS_R(4,n1)==2
newIR=[newIR,IR(PR(n1)+2:2:PR(n1+1))];
newWR=[newWR,WR(PR(n1)+2:2:PR(n1+1))];
end
end
for n1=1:NC,
if BLOCKS_C(5,n1)
newIC=[newIC,IC(PC(n1)+1:PC(n1+1))];
newWC=[newWC,WC(PC(n1)+1:PC(n1+1))];
elseif BLOCKS_C(4,n1)==1
newIC=[newIC,IC(PC(n1)+1:2:PC(n1+1))];
newWC=[newWC,WC(PC(n1)+1:2:PC(n1+1))];
elseif BLOCKS_C(5,n1)==2
newIC=[newIC,IC(PC(n1)+2:2:PC(n1+1))];
newWC=[newWC,WC(PC(n1)+2:2:PC(n1+1))];
end
end
end
for n1=1:numel(newIC)
board(:,newIC(n1))=uletters(Y(newWC(n1),:));
end
for n1=1:numel(newIR)
board(newIR(n1),:)=uletters(Y(newWR(n1),:))';
end
scoreFULL=score;
boardFULL=board;
else
scoreFULL=inf;
end

if 1
%% BASE METHOD + 2-LETTER WORDS

if lwords_(1)==2&&nwords_(1)>n,
nword_=1;
Nw=nwords_(nword_);
Np=lwords_(nword_);
X=cat(1,words{words_{nword_}});
W=weights_{nword_};
[uletters,nill,letters]=unique(X);
Y=reshape(letters,size(X));
Nl=numel(uletters);

% Pairwise compatibility between words (2-nd letter in first word matches 1-st letter in second word)
C=double(sparse(bsxfun(@eq,Y(:,1),Y(:,2)')));
C(1:Nw+1:end)=0;

% Grow series of long(~est) paths across words
valid=true(Nw,1);
npath=1;
paths={};
while any(valid)
[nill,Widx]=sort(full(C*valid));%,'descend'); %%%
Cs=C(Widx,Widx);
valids=valid(Widx);
idx=find(valids,1,'first');
if isempty(idx),break;end
path=zeros(Nw,1);
for n1=1:Nw,
path(n1)=idx;
valids(idx)=0;
cs2=valids & Cs(:,idx);
idx2=find(cs2,1,'first');
if isempty(idx2),break; end
idx=idx2;
end
paths{npath}=Widx(path(1:n1));
valid(Widx)=valids;
npath=npath+1;
end
lpaths=cellfun('length',paths);
[lpaths,idx]=sort(lpaths,'descend');
paths=paths(idx);
idx=find(lpaths>0); %%%
paths=paths(idx);
lpaths=lpaths(idx);
npaths=numel(paths);

% fill in diagonals within largest possible square
nwords=[0,   2,   4,   8,  14,  20,  28,  38,  48,  60,  74,  88, 104, 122, 140, 160, 182, 204, 228, 254, 280, 308, 338, 368, 400, 434, 468, 504, 542, 580, 620, 662, 704, 748, 794, 840, 888, 938, 988,1040,1094,1148,1204,1262,1320,1380,1442,1504,1568,1634,1700,1768,1838,1908,1980,2054,2128,2204,2282,2360,2440,2522,2604,2688,2774,2860,2948,3038,3128,3220,3314,3408,3504,3602,3700,3800,3902,4004,4108,4214,4320,4428,4538,4648,4760,4874,4988,5104,5222,5340,5460,5582,5704,5828,5954,6080,6208,6338,6468,6600,6734];
n0=min(n,find(nwords<=sum(lpaths),1,'last')); %%%
Diags=[0:3:n0-2, -2:-3:-(n0-2);
1:3:n0-1,   -3:-3:-(n0-1)];
nDiags=size(Diags,2);
Diags=cat(1,Diags,zeros(3,nDiags));
Diags(3:4,:)=n0-abs(Diags(1:2,:));
Diags(5,:)=2*Diags(4,:);
[nill,idx]=sort(Diags(5,:),'descend');
Diags=Diags(:,idx);

npath=1;
mword=1;
ndiag=1;
mdiag=1;
newdiag=1;
skip=0;
used=false(1,Nw);
while ndiag<=nDiags&&npath<=npaths,
if newdiag
newdiag=0;
x=zeros(1,Diags(3,ndiag)+Diags(4,ndiag));
nx=numel(x);
%mwords=Diags(5,ndiag);
mdiag=1;
skip=0;
end
if skip>0,
skip=skip-1;
else
used(paths{npath}(mword))=true;
x(mdiag:mdiag+1)=X(paths{npath}(mword),:);
mword=mword+1;
if mword>lpaths(npath), % ended path
npath=npath+1;
mword=1;
skip=2;
end
end
mdiag=mdiag+1;
if mdiag>=nx, % ended diagonal
board(1:n0,1:n0)=board(1:n0,1:n0)+diag(x(1:2:end),Diags(1,ndiag))+diag(x(2:2:end),Diags(2,ndiag));
ndiag=ndiag+1;
newdiag=1;
end
end

used0=find(used);
Cmax0=sum(weights_{nword_}(used0));
board0=board;
remove0=words_{nword_}(used0);
score0=Cmax0;
board=zeros(n);
else
Cmax0=-1;
board0=[];
end
borders=[1,1,n,n];
bordertypes=true(1,4);
score=total;

while size(borders,1)>0,
border=borders(1,:);
bordertype=bordertypes(1,:);

snwords_=2*min(nwords_(isets_),nwords_(isets_+1));
ntwn=sum(prod(border(:,3:4),2),1);
Twn=zeros(1,ntwn);tn=0;twn=0;
for nword_=find(nwords_>0),
t=nwords_(nword_);
Twn(tn+(1:t)*lwords_(nword_))=twn+weights_{nword_};
tn=tn+t*lwords_(nword_);
if tn>=ntwn,break;end
end
Twn=cumsum(Twn);                % expected gain by amount of board space left
if Cmax0>0, CCmax0=Cmax0+E(border(3)*border(4),(n0+1)*(n0+1),Twn); end

Cmax=-inf;CCmax=[-inf,-inf];
for orientation=1:2,
r=border(3);
c=border(4);
rc=r*c;
jagged=~bordertype(2);
if jagged, if orientation==1, jagged=1+~board(border(1),border(2)-2); else jagged=1+~board(border(2)-2,border(1)); end; end % jagged=1 (right-left), jagged=2 (left-right)
% dense case
for nword_=find(nwords_>0&lwords_<=c),
m=min(r,nwords_(nword_));
nr=m;
nc=lwords_(nword_);
C=cweights_{nword_}(m) - penalty*(m>1)*nc + E(rc,(nr+1)*(nc+1),Twn);
if C(1)>0&&sum(C)>Cmax,
Imax=[orientation, 1, nword_, m, jagged, nr, nc]; %orientation, case, word_ index, #words, jagged, number-of-rows, number-of-cols
Cmax=sum(C);
CCmax=C;
end
end
if r>1,
% dense case / sets
for snword_=find(snwords_>1&slwords_<=c),
m=min(r,snwords_(snword_));
m1=ceil(m/2);m2=floor(m/2);
nr=m;
nc=slwords_(snword_)-(jagged>0);
if jagged==1,   C=cweights_{isets_(snword_)}(m1) + cweights_{isets_(snword_)+1}(m2) - penalty*(m>1)*nc + E(rc,(nr+1)*(nc+1),Twn);
else            C=cweights_{isets_(snword_)}(m2) + cweights_{isets_(snword_)+1}(m1) - penalty*(m>1)*nc + E(rc,(nr+1)*(nc+1),Twn); end
if C(1)>0&&sum(C)>Cmax,
if jagged==1, Imax=[orientation, 2, snword_, m1, m2, jagged, nr, nc];
else          Imax=[orientation, 2, snword_, m2, m1, jagged, nr, nc]; end
Cmax=sum(C);
CCmax=C;
end
end
% sparse case / (maximal cols if jagged)
if jagged==1, cr=floor(r/2); else cr=ceil(r/2); end
if cr>0
for nword_=find(nwords_>0&lwords_<=c+(jagged>0)),
m=min(cr,nwords_(nword_));
nr=2*m-1+(jagged==1);
nc=lwords_(nword_)-(jagged>0);
C=cweights_{nword_}(m) + E(rc,(nr+1)*(nc+1),Twn);
if C(1)>0&&sum(C)>Cmax,
Imax=[orientation, 3, nword_, m, jagged, nr, nc];
Cmax=sum(C);
CCmax=C;
end
end
end
% sparse case (maximal rows & jagged)
if jagged==1,
for nword_=find(nwords_>0&lwords_==c),
m=min(ceil(r/2),nwords_(nword_));
nr=2*m-1;
nc=lwords_(nword_);
C=cweights_{nword_}(m) + E(rc,(nr+1)*(nc+1),Twn);
if C(1)>0&&sum(C)>Cmax,
Imax=[orientation, 4, nword_, m, jagged, nr, nc];
Cmax=sum(C);
CCmax=C;
end
end
end
end
border=border([2,1,4,3]);
bordertype=bordertype([2,1,4,3]);
end

if Cmax>0||Cmax0>0
if Cmax0>0&&sum(CCmax0)>.9*Cmax
nword_=1;
w=weights_{nword_};
idx1=words_{nword_};
w(used0)=[];
idx1(used0)=[];
weights_{nword_}=w;
cweights_{nword_}=cumsum(w);
words_{nword_}=idx1;
nwords_(nword_)=numel(w);
nwords=nwords-numel(w);

board=board0;
nr=n0;nc=n0;
casetype=1;
score=score-Cmax0;
else
orientation=Imax(1);
casetype=Imax(2);
if casetype==2, snword_=Imax(3); m1=Imax(4); m2=Imax(5); jagged=Imax(6); nr=Imax(7); nc=Imax(8); m=[m1,m2]; nword_=isets_(snword_)+[0,1];
else nword_=Imax(3); m=Imax(4); jagged=Imax(5); nr=Imax(6); nc=Imax(7); end
if orientation==2, board=board'; borders=borders(:,[2,1,4,3]); bordertypes=bordertypes(:,[2,1,4,3]); end
border=borders(1,:);
bordertype=bordertypes(1,:);
switch(casetype)
case 1 % dense case
idxr=border(1)-1;idxc=border(2)+(0:lwords_(nword_)-1)-(jagged==2); for nw=1:2:m, board(idxr+nw,idxc)=words{words_{nword_}(nw)}; end
idxr=border(1)-1;idxc=border(2)+(0:lwords_(nword_)-1)-(jagged==1); for nw=2:2:m, board(idxr+nw,idxc)=words{words_{nword_}(nw)}; end
case 2 % dense case / sets
if jagged==1,nword_=nword_([2,1]); m=m([2,1]); end
idxr=border(1)-2;idxc=border(2)+(0:lwords_(nword_(2))-1)-(jagged==2); for nw=1:m(2), board(idxr+2*nw,idxc)=words{words_{nword_(2)}(nw)}; end
idxr=border(1)-1;idxc=border(2)+(0:lwords_(nword_(1))-1)-(jagged==1); for nw=1:m(1), board(idxr+2*nw,idxc)=words{words_{nword_(1)}(nw)}; end
if jagged==1,nword_=nword_([2,1]); m=m([2,1]); end
case 3 % sparse case / (maximal cols if jagged)
idxr=border(1)-2+(jagged==1);idxc=border(2)+(0:lwords_(nword_)-1)-(jagged>0); for nw=1:m, board(idxr+2*nw,idxc)=words{words_{nword_}(nw)}; end
case 4 % sparse case / (maximal rows & jagged)
idxr=border(1)-2;idxc=border(2)+(0:lwords_(nword_)-1); for nw=1:m, board(idxr+2*nw,idxc)=words{words_{nword_}(nw)}; end
end
for nw=1:numel(m)
words_{nword_(nw)}=words_{nword_(nw)}(m(nw)+1:end);
weights_{nword_(nw)}=weights_{nword_(nw)}(m(nw)+1:end);
cweights_{nword_(nw)}=cweights_{nword_(nw)}(m(nw)+1:end)-cweights_{nword_(nw)}(m(nw));
%idx_{nword_(nw)}=idx_{nword_(nw)}(m(nw)+1:end);
nwords_(nword_(nw))=nwords_(nword_(nw))-m(nw);
nwords=nwords-m(nw);
end
score=score-CCmax(1);
end
if nr<border(3)-1,
borders(1,:)=border+[0,nc+1,nr-border(3),-nc-1];
border2=border+[nr+1,0,-nr-1,0];
bordertypes(1,:)=[bordertype(1),(bordertype(2)&(casetype==1))|(~bordertype(2)&(casetype==2)),true,true];
bordertype2=[true,bordertype(2),true,true];
borders=cat(1,borders,border2);
bordertypes=cat(1,bordertypes,bordertype2);
[nill,idx]=sort(min(borders(:,3),borders(:,4)));
borders=borders(idx,:);
bordertypes=bordertypes(idx,:);
else
borders(1,:)=border+[0,nc+1,0,-nc-1];
bordertypes(1,:)=[bordertype(1),(bordertype(2)&(casetype==1))|(~bordertype(2)&(casetype==2)),true,true];
end

if orientation==2, board=board'; borders=borders(:,[2,1,4,3]); bordertypes=bordertypes(:,[2,1,4,3]); end

idxremove=any(borders(:,3:4)<=0,2);
borders(idxremove,:)=[];
bordertypes(idxremove,:)=[];
Cmax0=-1;
else
borders(1,:)=[];
bordertypes(1,:)=[];
end

end
end

if scoreFULL<score
board=boardFULL;
score=scoreFULL;
end
if score>0
[boardOLI,scoreOLI] = solver_oli(words, weights, n, penalty);
if scoreOLI<score,
board=boardOLI;
score=scoreOLI;
end
end
end

function c=E(S1,S2,Twn)
D=S1-S2;
if D>0
c=[0, Twn(ceil(D/2))];
else
c=[0,0];
end
end

% test 1100
% by Oli
%
% Status: Passed
% Results: 6907992 (cyc: 10, node: 4681)
% CPU Time: 19.999
% Score: 17275.1
% Submitted at: 2011-04-18 00:15:37 UTC
% Scored at: 2011-04-18 00:17:56 UTC
%
function [board,score] = solver_oli(words, weights, N, penalty, skip, skipboard)

words = words(end:-1:1);
weights = weights(end:-1:1);

nws                     = numel(words);
lengths                 = cellfun('length',words);
[nill,idx]                 = sortrows([weights'./lengths'  weights'],[-1 -2]);
words                   = words(idx);
weights                 = weights(idx);
lengths                 = lengths(idx);
board                   = zeros(N);

if nargin>4
[board,score]    = solver_victoria(skipboard, words, weights, N, penalty, lengths, nws, skip);
return
end

if min(lengths) == N && numel(words(weights>0)) < 1100
[BOARD{7}, SCORE(7)]    = solver_nick_1(board, words, weights, N, penalty, lengths, nws);
if SCORE(7)==0
board=BOARD{7};
score=SCORE(7);
return;
end
end

sumw = sum(weights);
[BOARD{1}, SCORE(1)]    = solver_nick_2  (board, words, weights, N, penalty, lengths, nws);
[BOARD{2}, SCORE(2)]    = solver_nick_3  (board, words, weights, N, lengths, nws);
[BOARD{3}, SCORE(3)]    = solver_nick_4  (board, words, weights, N, penalty, lengths, nws);
[BOARD{4}, SCORE(4)]    = solver_james1  (board, words, weights, N, penalty, lengths, nws, sumw);
[BOARD{5}, SCORE(5)]    = solver_james2  (board, words, weights, N, penalty, lengths, nws, sumw);
[BOARD{6}, SCORE(6)]    = solver_victoria(board, words, weights, N, penalty, lengths, nws);

[score, board_idx]          = min(SCORE);
board                   = BOARD{board_idx};

end

function [board, result]               = solver_james1(board, words, weights, n, penalty, wordlengths, nwords, total)

[B,index] = sortrows([wordlengths' weights'],[1 -2]); % index is wordsFromBIndex
last2letterword = find(B(:,1)>2,1)-1;
%words2 = words(index(1:last2letterword));
w2l = index(1:last2letterword)'; % should be row vector for for

isUnplayed = true(1,nwords);
hopeless   = false(1,nwords);

[C,alphaix]=sortrows(cell2mat(words(w2l)')); % so char(C) = char(words{w2l(alphaix)}) % alphaix is WfromC
%wFromC=w2l(alphaix); % gives index in original words

points = 0;
c=1;
r=1;
L = 2; % dim of sq
while r+L-1 <= n,
% try excluding words with letter frequencies of 1
% ordering words by first and second letter would help
sq = zeros(2);
if ~isempty(w2l)
C1 = C(:,1);
[sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C1, alphaix,sq);
end

if ~sq,
break; % no more 2x2s
end
board(r+(0:L-1),c+(0:L-1)) = sq;
c=c+L+1;
if c > n-(L-1),
r =r+L+1;
c=1;
end
end
points = points + sum(weights(~isUnplayed));

% eliminate words that have already been played
[B,index]   = sortrows([wordlengths(isUnplayed)' weights(isUnplayed)'],[1 -2]);
words       = words(isUnplayed);
nwords      = numel(words);
isUnplayed2 = true(1,nwords);
k=1;
% play remaining unused 2 letter words here?

% index of last word to play in current row
stop_index  = min(nwords, n*k-c+1); % check that we haven't run out of words
start_index = 1;

while (r+B(stop_index,1)-1) <= n, % if the new row fits

words_left          = stop_index - start_index + 1;                                 % num words to play in this row
current_row_points  = sum(B(start_index:stop_index,2)) - penalty*B(stop_index-1,1); % use length of next to last word to get number of penalty cols

if current_row_points > 0,
for cc = c:min(n,words_left+c-1),
wi = start_index-c+cc; % word index
board(r:(r+B(wi,1)-1),cc) = words{index(wi)};
isUnplayed2(index(wi))    = false;

end

% the row is unplayed I think it will simply be blank
end

c=1;
points = points + current_row_points;
r=r+B(stop_index,1)+1; % increment row location

k=k+1; % increment row number
start_index=stop_index+1;
stop_index = min(nwords, stop_index+n);

end

result = total - points;

wordlengths2 = wordlengths(isUnplayed);
weights2     = weights(isUnplayed);

[board,result] = james_sub_solver(board,wordlengths2,weights2,isUnplayed2,words,result,n);

end

function [sq, isUnplayed, hopeless]    = press2(words, isUnplayed, hopeless, w2l, C1, alphaix,sq)

ii_valid = w2l(isUnplayed(w2l) & ~hopeless(w2l));

for ii = ii_valid, % w2l must be a row vector here

sq(1,:) = words{ii};
isUnplayed(ii) = false;

% only iterate over reasonable letters
conda = C1 == sq(1,1);
a1 = find(conda,1);
a2 = find(conda,1,'last');
w21jj  = w2l(sort(alphaix(a1:a2)));

condb = C1 == sq(1,2);
b1=find(condb,1);
b2=find(condb,1,'last');

w21kk  = w2l(sort(alphaix(b1:b2)));

for jj = w21jj

% eval order? also checks could be elim
if isUnplayed(jj) && ~hopeless(jj)

sq(2,1) = words{jj}(2);
isUnplayed(jj) = false;

condc = C1 == sq(2,1);

c1=find(condc,1);
c2=find(condc,1,'last');
w21ll = w2l(sort(alphaix(c1:c2)));

for kk = w21kk

if isUnplayed(kk)

sq(2,2)         = words{kk}(2);
isUnplayed(kk)  = false;

for ll =  w21ll

if isUnplayed(ll) && all(sq(2,:) == words{ll})

isUnplayed(ll) = false;

return; % press completed!
end
end
isUnplayed(kk) = true;
end
end
isUnplayed(jj) = true;
end
end
isUnplayed(ii) = true;

% should mark words that didn't work out to avoid retrying them
hopeless(ii) = true; % hopeless in positions 1 or 2

end

sq = zeros(2);

end

function [board, result]               = solver_james2(board, words, weights, n, penalty, wordlengths, nwords, result)

[B,index] = sortrows([wordlengths' weights'],[1 -2]);

k=1;
c=1;
isUnplayed         = true(nwords,1);
current_stop_index = min(nwords, n*k); % check that we haven't run out of words

while (c+B(current_stop_index,1)-1) <= n,
current_col_points = sum(B(((k-1)*n)+1:current_stop_index,2)) - penalty*B(k*n-1,1); % use length of next to last word to get number of penalty cols
if current_col_points > 0,
words_left = current_stop_index - n*(k-1);
for r = 1:min(n,words_left),
board(c:(c+B(r+(k-1)*n,1)-1),r) = words{index(r+(k-1)*n)};
isUnplayed(index(r+(k-1)*n))    = false;
end
end
result = result - current_col_points;
c=c+B(current_stop_index,1)+1;

k=k+1;
current_stop_index = min(nwords, n*k);
end

[board,result] = james_sub_solver(board,wordlengths,weights,isUnplayed,words,result,n);

end

function [board,result]                = james_sub_solver(board, wordlengths,weights,isUnplayed,words,result,n)

wordlengths2 = wordlengths(isUnplayed);
weights2     = weights(isUnplayed);
words        = words(isUnplayed);
[nill,idx_sort] = sort(wordlengths2 - weights2/max(weights2) );

tres_ceros   = board(3:end,1)==0 & board(2:end-1,2)==0 & board(1:end-2,1)==0;
r_ini        = find(tres_ceros) + 1;

if board(n,1)==0 && board(n-1,1)==0
r_ini = [r_ini; n];
end

k = 1;
for p = 1:length(r_ini)

r = r_ini(p);
if board(r-1,1)==0

c = 1;
while c < n && board(r-1,c)==0
word_n = words{idx_sort(k)};
c2     = c + numel(word_n);
if c2-1 <= n && board(r-1,c2-1)==0
board(r,c:c2-1) = word_n;
k = k + 1;
result = result - weights2(idx_sort(k));
end
c = c2 + 1;
end
end
end

end

function [board, score]                = solver_victoria(board, words, weights, N, penalty, L, QWords, skip)
% Victoria's solver
score           = 0;
PThresh         = 0.195;
WordsInUse      = false(1,QWords);
%SpecificWeights = weights./L;
%[nill,IndWS]       = sort(SpecificWeights,'descend');
IndWS=1:length(weights);
SpecLCum        = cumsum(L(IndWS) + 1);
MaxQ            = numel(find(SpecLCum <= N.*(N+1)));
GoodWeight      = sum(weights(IndWS(1:MaxQ)));
L_slots         = P*ceil(N/2) + (1-P)*N; % innovation filter :P
MaxQ            = P*numel(find(SpecLCum <= (N+1).^2/2)) + (1-P)*MaxQ;
slots           = ones(1, L_slots);
if nargin>=8&&skip>0
slots(1:skip)=skip+1;
else
skip=0;
end

LoL             = min(L(IndWS(1:MaxQ)));
HiL             = max(L(IndWS(1:MaxQ)));
IndL            = zeros(MaxQ,1);
l               = 1;
for n = HiL:-1:LoL
idx_long       = find(L(IndWS(1:MaxQ))==n);
l2             = l + numel(idx_long);
IndL(l:l2-1)   = idx_long;
l              = l2;
end
IndWS(1:MaxQ)      = IndWS(IndL);

n       = 1;
seguir  = (min(slots) < N)*(n <= QWords);

while seguir

Space                       = N - L(IndWS(n)) + 1 - slots;
SlotIndex                   = find(~Space,1);

if isempty(SlotIndex)
[Espacio,SlotIndex]     = max(Space);
else
Espacio                 = 1;
end

if Espacio > 0

idx_f                   = (1+P)*SlotIndex-P;
idx_c                   = slots(SlotIndex):slots(SlotIndex) + L(IndWS(n)) - 1;
board(idx_f,idx_c)      = words{IndWS(n)};
slots(SlotIndex)        = slots(SlotIndex) + L(IndWS(n)) + 1;
score                   = score + weights(IndWS(n));
WordsInUse(IndWS(n))    = true;

end

n       = n + 1;
seguir  = (min(slots) < N)*(n <= QWords);

end

QWords = QWords*(P>0);

for n = 1:QWords

CurInd  = IndWS(n);
CurL    = L(CurInd);
word_c  = words{CurInd};

entrar  = (~WordsInUse(CurInd))*(CurL/2 ~= round(CurL/2));

if entrar

[I,J] = find(board(1:N - CurL + 1,:) == word_c(1));

if ~isempty(I)

k = 1;
seguir = (~WordsInUse(CurInd))*(k <= numel(I));
while seguir

if all(word_c(1:2:end) == board(I(k):2:I(k) + CurL - 1,J(k))')

board(I(k):I(k) + CurL - 1,J(k)) = word_c';

score = score + weights(IndWS(n));

WordsInUse(IndWS(n)) = true;

end

k = k + 1;
seguir = (~WordsInUse(CurInd))*(k <= numel(I));
end
end
end
end

if ~skip, [board, score] = victoria_sub_solver(board,words,L,weights,WordsInUse,N,score); end

%--
pboard  = [board;zeros(1,N)];
cs      = cumsum(pboard(:)~=0);
ntrans  = sum(diff(cs(pboard==0))>1) + 1;
score   = sum(weights(:)) - score + penalty*ntrans;

end

function [board, score]                = victoria_sub_solver(board, words,L,weights,WordsInUse,N,score)

L2           = L(~WordsInUse);
weights2     = weights(~WordsInUse);
words        = words(~WordsInUse);
[nill,idx_sort] = sort(L2 - weights2/max(weights2) );

tres_ceros   = board(1,3:end)==0 & board(1,2:end-1)==0 & board(1,1:end-2)==0;
r_ini        = find(tres_ceros) + 1;

if board(1,N)==0 && board(1,N-1)==0
r_ini = [r_ini; N];
end
k = 1;

for p = 1:length(r_ini)

r = r_ini(p);

if board(1,r-1)==0

c = 1;

while c < N && board(c,r-1)==0
word_n = words{idx_sort(k)};
c2     = c + numel(word_n);
if c2-1 <= N && all(board(c:c2-1,r)==0)
board(c:c2-1,r) = word_n;
k = k + 1;
score = score + weights2(idx_sort(k));
end
c = c2 + 1;
end
end
end

end

function [board0, s0]                  = solver_nick_1(board, words, weights, N, penalty, wlen, nword)

% Nicks's solver
global wmat
pwords      = cellfun(@(a)[a 0 -1*ones(1,N-numel(a))],words,'UniformOutput',false);
wmat        = cat(1,pwords{:});
wmat        = wmat(:,1:end-1);
m           = cell(N);

for n = 1:N
m{n,1} = double(sparse(bsxfun(@eq,wmat(:,n),wmat(:,1)')));
m{3,n} = double(sparse(bsxfun(@eq,wmat(:,3),wmat(:,n)')));
end

rwords = zeros(1,N);
cwords = zeros(1,N);

n       = 1;
pm      = ones(nword);
m13     = m{n,1}*m{3,n};
ppm     = pm & m13;

seguir  = (n + 2 < N)*any(ppm(:));
while seguir
pm      = ppm;
m13     = m{n,1}*m{3,n};
ppm     = pm & m13;
n       = n + 2;
seguir  = (n<N)*any(ppm(:));
end

icross              = n;
open                = true(1,nword);
[i1,i3]             = find(pm);
i1                  = i1(1);
i3                  = i3(1);
open(i1)            = false;
open(i3)            = false;
board(1,1:wlen(i1)) = words{i1};
board(3,1:wlen(i3)) = words{i3};
rwords(1)           = i1;
rwords(3)           = i3;

for n = 1:2:icross

iword = find((m{n,1}(i1,:).*m{3,n}(:,i3)') & open);

if ~isempty(iword)
iword                   = iword(1);
cwords(n)               = iword;
board(1:wlen(iword),n)  = words{iword}';
open(iword)             = false;
end
end

% fill in remaining crosses, if possible.
fcwords     = cwords(cwords>0);
height      = max(wlen(fcwords));
open        = open';

for n = 5:height
cols            = find(board(n,:)~=0);
matches         = bsxfun(@eq,wmat(:,cols),board(n,cols))|(wmat(:,cols)<0);
[nill,bm]          = max(open.*sum(matches,2));
end

n = 5;
while (n <= height)
cols    = find(board(n,:)~=0);
row     = find(open & all(bsxfun(@eq,wmat(:,cols),board(n,cols))|(wmat(:,cols)<0),2),1);
if ~isempty(row)
open(row)               = false;
board(n,1:wlen(row))    = words{row};
rwords(n)               = row;
n                       = n + 2;
else
n                       = n + 1;
end
end
% s0      = sum(weights(open));
% board0  = board;
S         = zeros(2,1);
S(1)      = sum(weights(open));
BOARD{1}  = board;

% now try full fill
[board, s1] = solver_nick_1p5(rwords,cwords,N,board,wmat,open,words,weights,wlen,penalty);

S(2)        = s1;
BOARD{2}    = board;

[s0,b_idx] = min(S);
board0     = BOARD{b_idx};

end

function [board, s1]                   = solver_nick_1p5(rwords,cwords,N,board,wmat,open,words,weights,wlen,penalty)

openr   = rwords==0;
openc   = cwords==0;
goodc   = ~openc;

for c = find(openc)
rows            = find(board(:,c)~=0);
matches         = bsxfun(@eq,wmat(:,rows),board(rows,c)')|(wmat(:,rows)<0);
[nill,bm]          = max(open.*sum(matches,2));
end

for c = find(openc)
rows        = find(board(:,c)~=0);
matches     = bsxfun(@eq,wmat(:,rows),board(rows,c)')|(wmat(:,rows)<0);
wi          = find(open & all(matches,2),1);
if ~isempty(wi)
open(wi)            = false;
board(1:wlen(wi),c) = words{wi};
cwords(c)           = wi;
end
end

openr = rwords==0;
openc = cwords==0;
goodr = ~openr;

for r = find(openr)
cols            = find(board(r,:)~=0);
matches         = bsxfun(@eq,wmat(:,cols),board(r,cols))|(wmat(:,cols)<0);
[nill,bm]          = max(open.*sum(matches,2));
end

for r = find(openr)
cols        = find(board(r,:)~=0);
matches     = bsxfun(@eq,wmat(:,cols),board(r,cols))|(wmat(:,cols)<0);
wi          = find(open & all(matches,2),1);
if ~isempty(wi)
open(wi)            = false;
board(r,1:wlen(wi)) = words{wi};
rwords(r)           = wi;
end
end

board(board==0) = 1;
s1              = sum(weights(open)) + penalty*(sum(rwords==0) + sum(cwords==0));

end

function [board , s]                  = solver_nick_2(board, words, weights, N, penalty, wlen, nws)

SW                      = sum(weights);
w       = 0;
open    = true(1,nws);

for n = [1:2:N,2:2:N]
l = 0;
k = find(open & (wlen<=N-l),1);
while ~isempty(k)
open(k)                = false;
word                   = words{k};
L_word                 = numel(word);
board(n,l+1:l+L_word)  = word;
l                      = l + L_word + 1;
w                      = w + weights(k);
k                      = find(open & (wlen <= N-l),1);
end
end

pboard  = [board;zeros(1,N)];
cs      = cumsum(pboard(:)~=0);
ntrans  = sum(diff(cs(pboard==0))>1);
w       = w - penalty*ntrans;
s       = SW - w;

end

function [board2, s]                   = solver_nick_3(board2, words, weights, N, wlen, nws)

SW                      = sum(weights);
w2       = 0;
open     = true(1,nws);
wlen_m_N = wlen <= N;

for n = 1:2:N
l = 0;
k = find(open & wlen_m_N,1);
while ~isempty(k)
open(k)                = false;
word                   = words{k};
L_word                 = numel(word);
board2(n,l+1:l+L_word) = word;
l                      = l+L_word+1;
w2                     = w2 + weights(k);
k                      = find(open & (wlen <= N-l),1);
end
end

s = SW - w2;

end

function [board2, s]                   = solver_nick_4(board2, words, weights, N, penalty, wlen, nword)

SW                      = sum(weights);
w2              = 0;
open            = true(1,numel(words));
filled          = zeros(1,N);
filled(2:2:end) = 1;
brk             = false;

while (filled(1)<N)

wlen2           = wlen.*open;
wlen2(~open)    = 1;
nlen            = accumarray(wlen2(:),ones(nword,1));
k               = find(open & (wlen <= N-filled(1) -1) & (nlen(wlen)' >=N),1);
if isempty(k)
brk         = true;
break
end
targ                                 = wlen(k);
board2(1,filled(1)+1:filled(1)+targ) = words{k};
open(k)                              = false;
w2                                   = w2 + weights(k);
wlen_eq_targ                         = wlen==targ;
for n = 2:N
k                                    = find(open & wlen_eq_targ,1); % DFM SPEED
board2(n,filled(n)+1:filled(n)+targ) = words{k};
open(k)                              = false;
w2                                   = w2 + weights(k);
end
filled = filled + targ + 1;

end

if brk
% try two half-sets
[brk,board2,open,w2,filled] = nick_two_halves(board2,words,weights,wlen,nword,filled,open,N,w2);
end

if brk
% try two half-sets off by 2
[brk,board2,open,w2,filled] = nick_two_halves_off(board2,words,weights,wlen,nword,filled,open,N,w2);

end

if brk && any(board2(:))
% finish filling board normally
for n = 1:N
k = find(open & (wlen<=N-filled(n)),1);
while ~isempty(k)
open(k)                                     = false;
word                                        = words{k};
board2(n,filled(n)+1:filled(n)+numel(word)) = word;
filled(n)                                   = filled(n) + numel(word) + 1;
w2                                          = w2 + weights(k);
k                                           = find(open & (wlen<=N-filled(n)),1);
end
end
end
pboard  = [board2; zeros(1,N)];
cs      = cumsum(pboard(:)~=0);
ntrans  = sum(diff(cs(pboard==0))>1);
w2      = w2 - penalty*ntrans;
s       = SW - w2;

end

function [brk,board2,open,w2,filled]   = nick_two_halves(board2,words,weights,wlen,nword,filled,open,N,w2)

brk = false;
while filled(1) < N
wlen2           = wlen.*open;
wlen2(~open)    = 1;
nlen            = accumarray(wlen2(:),ones(nword,1));
ldir            = 2*(filled(1) > filled(2)) - 1;
nlen(1)         = 0;
k               = find(open & (wlen <= N-filled(1) - 1) & (nlen(wlen)'>=ceil(N/2)) & (nlen(wlen+ldir)'>=ceil(N/2)),1);
if isempty(k)
brk         = true;
break
end
targ                                 = wlen(k);
board2(1,filled(1)+1:filled(1)+targ) = words{k};
open(k)                              = false;
w2                                   = w2 + weights(k);
for n = 2:N
idir                                      = ldir*(mod(n,2)==0);
k                                         = find(open&(wlen==targ+idir),1);
board2(n,filled(n)+1:filled(n)+targ+idir) = words{k};
open(k)                                   = false;
w2                                        = w2 + weights(k);
end;
filled = filled + targ + 1;
end

end

function [brk,board2,open,w2,filled]   = nick_two_halves_off(board2,words,weights,wlen,nword,filled,open,N,w2)

% try two half-sets off by 2
brk = false;
while filled(1) < N
wlen2           = wlen.*open;
wlen2(~open)    = 1;
nlen            = accumarray(wlen2(:),ones(nword,1));
nlen(1)         = 0;
nlen(end+2)     = 0;
k0              = find(open&(wlen<=N-filled(1)-2) & (nlen(wlen)'>=ceil(N/2)) & (nlen(wlen+2)'>=ceil(N/2)),1);
if isempty(k0)
brk = true;
break
end
if filled(1)>filled(2)
targ            = ones(1,N)*wlen(k0);
targ(2:2:end)   = wlen(k0)+2;
else
targ            = ones(1,N)*(wlen(k0)+2);
targ(2:2:end)   = wlen(k0);
end
for n = 1:N
k                                       = find(open&(wlen==targ(n)),1);
board2(n,filled(n)+1:filled(n)+targ(n)) = words{k};
open(k)                                 = false;
w2                                      = w2 + weights(k);
end
filled = filled + targ + 1;
end

end
```