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
% STEP V. Additional steps
% 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)));
BadGoodCoef = N.*penalty./GoodWeight;
P = BadGoodCoef > PThresh;
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';
votes = zeros(N);
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));
votes(n,cols) = 2*matches(bm,:)-1;
end
bad = sum(votes)<0;
badword = cwords(bad(1:icross));
open(nonzeros(badword)) = true;
board([2 4:end],bad) = 0;
cwords(bad) = 0;
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;
votes = zeros(N);
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));
votes(rows,c) = 2*matches(bm,:)-1;
end
bad = sum(votes,2) <= -sum(goodc);
badwords = rwords(bad);
open(nonzeros(badwords)) = true;
board(openr,bad) = 0;
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;
votes = zeros(N);
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));
votes(r,cols) = 2*matches(bm,:)-1;
end
bad = sum(votes,2)<= -sum(goodr);
badwords = cwords(bad);
open(nonzeros(badwords)) = true;
board(bad,openc) = 0;
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
|
