function out = stripper(words, weights, N, penalty)
[out,sux] = solver_volkan(words, weights, N);
if sux;return;end
nws = numel(words);
words = words(end:-1:1);
weights = single(weights(end:-1:1));
lengths = single(cellfun('length',words));
[w1,idx] = sortrows([weights'./lengths' weights'],[-1 -2]);
words = words(idx);
weights = w1(:,2)';
lengths = lengths(idx);
board = zeros(N,'uint8');
SCORE = Inf * ones(1,18);
BOARD=cell(1,18);
if min(lengths) == N
[BOARD{1}, SCORE(1)] = solver_nick_1(board, words, weights, N, penalty, lengths, nws,750,750);
if SCORE(1)==0, board=BOARD{1}; out=double(board); return; end
end
rand('state',789);
mywords=cell(1,5);
myweights=cell(1,5);
mylengths=cell(1,5);
for j=1:5
idx1=randperm(nws);
words1 = words(idx1);
weights1 = weights(idx1);
lengths1 = lengths(idx1);
[w1,idx] = sortrows([weights1'./lengths1' weights1'],[-1 -2]);
mywords{j} = words1(idx);
myweights{j} = w1(:,2)';
mylengths{j} = lengths1(idx);
end
if min(lengths) == N
[BOARD{2}, SCORE(2)] = solver_nick_1(board, mywords{1}, myweights{1}, N, penalty, mylengths{1}, nws,750,750);
else
if (sum(lengths==2)>2*N)
[yboard,yscore,ywordsgood] = solver_yot (board, words, weights, N, penalty, lengths, nws);
else
yboard = board;
yscore = sum(weights);
ywordsgood = true(1,nws);
end;
wordsflip = cellfun(@fliplr,words,'Uniform',false);
sumw = sum(weights);
[BOARD{3}, SCORE(3)] = solver_nick_2 (board, words, weights, N, penalty, lengths, nws, sumw);
[BOARD{4}, SCORE(4)] = solver_nick_3 (board, words, weights, N, lengths, nws, sumw);
[BOARD{5}, SCORE(5)] = solver_nick_4 (board, words, weights, N, penalty, lengths, nws, sumw);
[BOARD{6}, SCORE(6)] = solver_james1 (yboard, yscore, ywordsgood, words, weights, N, penalty, lengths, nws, sumw);
[BOARD{7}, SCORE(7)] = solver_james2 (board, words, weights, N, penalty, lengths, nws);
[BOARD{8}, SCORE(8)] = solver_victoria(board, words, weights, N, penalty, lengths, nws);
[BOARD{9}, SCORE(9)] = solver_james1 (yboard, yscore, ywordsgood, wordsflip, weights, N, penalty, lengths, nws, sumw);
[BOARD{10}, SCORE(10)] = ylattice(yboard,yscore,ywordsgood,words,weights,N,lengths);
%minscore = min(SCORE);
%for j=1:5
% [BOARD{11+j}, SCORE(11+j)] = solver_james1 (yboard, yscore, ywordsgood, mywords{j}, myweights{j}, N, penalty, mylengths{j}, nws, sumw);
%if SCORE(11+j)<minscore
%break ;
%end
% end
end
[~, board_idx] = min(SCORE);
board = BOARD{board_idx};
if (board_idx==9)
board = board(end:-1:1,end:-1:1);
end
out = double(board);
end
function [board, result] = solver_james1(yboard, yscore, isUnplayed, words, weights, n, penalty, wordlengths, nwords, total)
points = total-yscore;
board = yboard;
% 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?
%left = cellfun(@(a)find([1 a]~=0,1,'last'),num2cell(board,2))-1;
%rwid = n+1-left;
c0 = find(any(board>0,1),1,'last')+2;
if isempty(c0)
c0 = 1;
end;
width = n-c0+1;
% index of last word to play in current row
r = 1;
%c0 = max(left)+2;
c = c0;
stop_index = min(nwords, width); % check that we haven't run out of words
start_index = 1;
if (width<=1)
result = yscore;
return;
end;
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=c0;
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+width);
end
result = total - points;
wordlengths2 = wordlengths(isUnplayed);
weights2 = weights(isUnplayed);
[board(c0:end,c0:end),result] = james_sub_solver(board(c0:end,c0:end),wordlengths2,weights2,isUnplayed2,words,result,n-c0+1);
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=sum(weights);
[B,index] = sortrows([wordlengths' weights'],[1 -2]);
k=1;
c=1;
isUnplayed = true(nwords,1);
current_stop_index = min(nwords, n); % 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);
[~,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 [board0, s0] = solver_nick_1(board, words, weights, N, penalty, wlen, nword,maxnwo,maxnwo2)
if numel(words)>maxnwo
rand();
ridx = randperm(numel(words));
ridx = ridx(1:maxnwo2) ;
words=words(ridx);
wlen = wlen(ridx);
weights = weights(ridx);
nword = maxnwo2;
end
wmat = uint8(cat(1,words{:}));
m = cell(N);
for n = 1:N
m{n,1} = sparse(bsxfun(@eq,wmat(:,n),wmat(:,1)'));
m{3,n} = sparse(bsxfun(@eq,wmat(:,3),wmat(:,n)'));
end
rwords = zeros(1,N);
cwords = zeros(1,N);
n = 1;
ppm = true(nword);
seguir = true;
while seguir
pm = ppm;
ppm = pm & double(m{n,1})*double(m{3,n});
n = n + 2;
seguir = (n<N) & any(ppm(:));
end
icross = n;
open = true(1,nword);
[i1,i3] = find(pm,1);
open(i1) = false;
open(i3) = false;
board(1,:) = words{i1};
board(3,:) = words{i3};
rwords(1) = i1;
rwords(3) = i3;
for n = 1:2:icross
iword = find((m{n,1}(i1,:).*m{3,n}(:,i3)') & open,1);
if ~isempty(iword)
cwords(n) = iword;
board(1:wlen(iword),n) = words{iword}';
open(iword) = false;
end
end
% fill in remaining crosses, if possible.
open = open';
votes = zeros(N);
for n = 5:N
cols = find(board(n,:)~=0);
matches = bsxfun(@eq,wmat(:,cols),board(n,cols))|(wmat(:,cols)<0);
[~,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 <= N)
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
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);
[~,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);
[~,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, score] = solver_victoria(board, words, weights, N, penalty, L, QWords)
% Victoria's solver
score = 0;
PThresh = 0.195;
WordsInUse = false(1,QWords);
%SpecificWeights = weights./L;
%[~,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);
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
[board, score] = victoria_sub_solver(board,words,L,weights,WordsInUse,N,score);
%--
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);
[~,idx_sort] = sort(weights2./(L2+1),'descend');
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;
used = false(size(weights2));
if sum(board(:,N)==0 & board(:,N-1)==0)>3
r_ini = [r_ini; N];
end
k=1;
for p = 1:length(r_ini)
r = r_ini(p);
if board(1,r-1)==0 || (r==N && any(all(board(:,r-1:r)==0,2)))
c = 1;
subv
end
end
function subv
while c < N && (board(c,r-1)==0 || r==N)
if board(c,r-1)~=0 || board(c,r)~=0 || board(max(c-1,1),r)~=0
c = c+1;
continue;
end
word_n = words{idx_sort(k)};
c2 = c + numel(word_n);
[c2,word_n] = subv2(c2,word_n);
c = c2 + 1;
end
end
function [c2,word_n] = subv2(c2,word_n)
if c2-1 <= N && all(board(c:c2-1,r)==0) && board(min(c2,N),r)==0
board(c:c2-1,r) = word_n;
k = k + 1;
score = score + weights2(idx_sort(k));
used(idx_sort(k)) = true;
elseif r==N || r==N-1
k=1;
[~,idx_sort] = sort(L2 - weights2/max(weights2)+used*99);
c2 = c+3;
[c2,word_n] = subv3(c2,word_n);
end
end
function [c2,word_n] = subv3(c2,word_n)
while c < N && board(c,r-1)==0 && board(min(c2,N),r)==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
function [board , sumw] = solver_nick_2(board, words, weights, N, penalty, wlen, nws, sumw)
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;
sumw = sumw - 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);
sumw = sumw + penalty*ntrans;
end
function [board2, sumw] = solver_nick_3(board2, words, weights, N, wlen, nws,sumw)
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;
sumw = sumw - weights(k);
k = find(open & (wlen <= N-l),1);
end
end
end
function [board2, s] = solver_nick_4(board2, words, weights, N, penalty, wlen, nword, sumw)
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 = sumw - 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_test = accumarray(wlen2(:),ones(nword,1));
nlen_test(1) = 0;
[row,clone] =size(nlen_test);
nlen =zeros(row+2,clone);
nlen(1:end-2) =nlen_test;
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
function [board,success] = solver_volkan(words, weights, n)
% BEWARE! This solver only tries to find a complete solution, and is a huge
% waste of CPU cycles if none exists
%
% HERE IS THE MAIN IDEA: Say a word contains five 'A's, it cannot be put on
% the first row of the crossword if we do not have five other words that
% begin with the letter 'A'. Expand this idea to all rows and the histogram
% of each word, you get yourself a reduced search space.
board=zeros(n);
success = false;
% look for completely solveable with enough words
solvable = all(cellfun('length',words) == n);
% give up while you can
if ~solvable;return;end
% remove duplicate words (who put them there anyway?)
w = cell2mat(words');
nw = length(w);
% reduce search space
template = sv_reduce();
% get the rows with the least candidates
t_pos = sum(template,1);
[~,id1] = sort(t_pos);
% exit while you can
if prod(t_pos(id1(1:2))) > 5000;return;end
% get two sets of candidates for two different rows
suit1 = find(template(:,id1(1)))';
suit2 = find(template(:,id1(2)))';
% do the work
success = sv_fill();
function template = sv_reduce()
% returns a logical template which shows which word
% can be placed on which row
hist_pos = histc(w,65:90,1);
template = false(nw,n);
for ind = 1:nw
hist_word = histc(w(ind,:),65:90,2)';
hist_word = repmat(hist_word,[1,n]);
locate = (hist_pos >= hist_word);
template(ind,:) = all(locate);
end
end
function done = sv_fill()
% Loops through two sets of row candidates, keeps filling as long as
% there is a single cross match, recursively finishes off if not.
done = false;
for line1 = suit1
if done;break;end
for line2 = suit2
if line1 == line2;continue;end
board(id1(1:2),:) = w([line1 line2],:);
boardcpy = board;
while (1)
[filled,boardcpy] = sv_cross(boardcpy);
if filled
boardcpy = boardcpy';
if all(boardcpy(:))
%check if valid
board = boardcpy;
done = true;
break
end
else
done = false;
break;
end
end
if done;break
else continue;end
end
end
function [filled,outboard] = sv_cross(inboard)
% Places crossovers if there is a single match, calls recursive
% solver if not.
outboard = inboard;
filled = false;
idx = all(outboard,2);
idy = ~all(outboard,1);
full = outboard(idx,idy);
%Xfull = repmat(shiftdim(full,-1),[nw 1 1]);
candi = w(:,idx);
%Xcandi = repmat(candi,[1 1 sum(idy)]);
match = bsxfun(@eq,shiftdim(full,-1),candi);
if isempty(match)
% nasty situation when the board is filled but we did not check
% the last placement
Xboard = repmat(shiftdim(outboard,-1),[nw 1 1]);
Xword = repmat(w,[1 1 n]);
match = Xboard == Xword;
m = squeeze(all(match,2));
mm = squeeze(any(m,1));
mmm = all(mm);
if mmm
filled = true;
return;
else
return;
end
end
m = squeeze(all(match,2));
mm = squeeze(any(m,1));
mmm = all(mm);
if mmm
%find and anchor unique columns
ms = sum(m,1);
%unify duplicate words
doubles = ms==2;
if any(doubles);
duin = m(:,doubles);
in_doubles = find(doubles);
[duinx,~] = find(duin);
for in = 1:(numel(duinx)/2)
first = w(duinx(2*in-1),:);
second = w(duinx(2*in),:);
if all(first==second)
% remove one from template
m(duinx(2*in),in_doubles(in)) = 0;
end
end
ms = sum(m,1);
end
uin = ms==1;
if any(uin) % we have unique columns
muin = m(:,uin);
[uinx,~] = find(muin);
idy(idy) = uin;
outboard(:,idy) = w(uinx,:)';
filled = true;
else
% start diggin
% expand m and ms
tmp = inf(nw,n);
tmp(:,idy) = m;
m = tmp;
ms = sum(m,1);
[outboard,done] = sv_deeper(outboard);
%disp('exited sv_deeper');
filled = done;
end
end
function [dboard,done] = sv_deeper(inboard)
% Recursive solver used to finish off the crossword
done = false;
% get one high probability fit from ms
[~,idm] = sort(ms);
msin = m(:,idm(1));
[usn,~] = find(msin);
% loop candidate words
% ignore duplicates
aw = w(usn,:);
aw = unique(aw,'rows');
if size(aw,1) ~= size(usn,1)
usn = usn(1:size(aw,1));
end
for i = usn'
dboard = inboard;
dboard(:,idm(1)) = w(i,:)';
dboard = dboard';
% see if any matching words appeared
while (1)
[filled,dboard] = sv_cross(dboard);
if filled
dboard = dboard';
if all(dboard(:))
%check if valid
boardcpy = dboard;
done = true;
break
end
else
done = false;
break;
end
end
% check and exit
if done;break
else continue;end
end
end
end
end
end
function [board,score,wordsgood]= solver_yotc(board, words, weights, n, penalty, lengths, nws)
[yboard,yscore,ywordsgood]= solver_yot(board, words, weights, n, penalty, lengths, nws);
[board,score] = ylattice(yboard,yscore,ywordsgood,words,weights,n,lengths);
end
function [board,score,wordsgood]= solver_yot(board, words, weights, n, penalty, lengths, nws)
wordsgood = true(size(words));
wordslen = lengths;
score = weights./(wordslen+6);
[~,idx] = sort(score,'descend');
% [~,idx] = sortrows([score',weights'],[-1 -2]);
words = words(idx);
weights = weights(idx);
wordslen = wordslen(idx);
j=1;
w = find(wordsgood,1);
word = words{w};
wordsgood(w) = false;
wordlen = wordslen(w);
while wordlen < n-2 && any((wordslen < n-wordlen) & wordsgood)
shortw = find(wordslen < n-wordlen & wordsgood,1);
word = [word,0,words{shortw}];
wordlen = length(word);
wordsgood(shortw) = false;
end
board(1:length(word),j) = word;
i = 1;
while i <= n
lenaval = n-j+1;
wfit = find(wordsgood & wordslen<=lenaval);
for w = 1:length(wfit)
if words{wfit(w)}(1)==board(i,j)
board(i,j:wordslen(wfit(w))+j-1) = words{wfit(w)};
wordsgood(wfit(w)) = false;
break;
end
end
if wordsgood(wfit(w)) == false
i = i+2;
else
i = i+1;
end
end
[board,wordsgood] = yot2(j,n,board,words,wordsgood,wordslen,weights);
score = sum(wordsgood.*weights);
wordsgood(idx) = wordsgood;
end
function [board,wordsgood] = yot2(j,n,board,words,wordsgood,wordslen,weights)
jmax = min(n,ceil(1.8*sum(wordslen==2)/n));
while j < jmax
j = j+1;
b02 = board(:,j-1:j)==0;
temp = 2*b02(:,2) + b02(:,1);
spaces = temp==0 | temp==3;
% idx = find([diff(spaces)==0;0]); % start of a space
idx = find([0;diff((spaces==0)*2+(spaces==1))] == -1);
for k=1:length(idx)
lenspace = sum(cumprod(single(spaces(idx(k):end))));
% lenspace = find(spaces(idx(k):end)==0,1)-1;
matchstr = single(board(idx(k):idx(k)+lenspace-1,j));
wfit = find(wordsgood & wordslen==lenspace);
for w = 1:length(wfit)
if all(words{wfit(w)}.*matchstr' == (matchstr').^2)
board(idx(k):idx(k)+lenspace-1,j) = words{wfit(w)};
wordsgood(wfit(w)) = false;
break;
end
end
end
lenaval = jmax-j+1;
if lenaval<2
break;
end
pos = find(board(:,j-1)==0);
[board,wordsgood] = yot3(board,words,pos,n,j,wordsgood,wordslen,lenaval);
end
end
function [board,wordsgood] = yot3(board,words,pos,n,j,wordsgood,wordslen,lenaval)
for k=1:length(pos)
index = [max(pos(k)-1,1):min(pos(k)+1,n)];
if all(board(index([1,end]),j+1)==0) && ...
((length(index)==2 && ismember(sum(board(index,j)==0),[0,2])) || ...
(length(index)==3 && ~ismember(sum((board(index,j)==0).*[1,2,4]'),[2,3,6])))
wfit = find(wordsgood & wordslen<=lenaval);
for w = 1:length(wfit)
if words{wfit(w)}(1)==board(pos(k),j) || board(pos(k),j)==0
board(pos(k),j:wordslen(wfit(w))+j-1) = words{wfit(w)};
wordsgood(wfit(w)) = false;
break;
end
end
end
end
end
function [board,S] = ylattice(yboard,~,wordsgood,words,weights,n,wlen)
wordsgood = wordsgood';
wlen = wlen';
pad = [-1 zeros(1,n)];
pwords = cellfun(@(a)[a pad(1:n-numel(a)+1)],words,'UniformOutput',false);
wmat = cat(1,pwords{:});
maxc = max(wmat(:));
board = repmat(-1,n+2,n+2);
board(2:end-1,2:end-1) = yboard;
%mask = false(n+2);
%mask(2:end-1,2:end-1) = board>0;
mask = board>0;
mask(2:end-1,2:end-1) = mask(2:end-1,1:end-2)|mask(2:end-1,3:end);
mask(board<0) = true;
board(board==0) = -mask(board==0);
top = zeros(1,n+2);
%top = cellfun(@(a)find(a,1,'last'),num2cell(mask(1:end-1,:),1))-1;
%left = zeros(1,n+2);
left = cellfun(@(a)find(a,1,'last'),num2cell(mask(:,1:end-1),2))-1;
left(2:2:end-3) = max(left(2:2:end-3),left(3:2:end-2));
left(4:2:end-1) = max(left(4:2:end-1),left(3:2:end-2));
bottom = repmat(n+1,1,n+2);
right = repmat(n+1,1,n+2);
for i = 1:n
for j = max(1,ceil(i-(n-1)/2)):min(i,(n+1)/2)
ii = 2*i-2*j+2;
jj = 2*j;
%disp([i j ii jj]);
% possible horizontal placements
if (jj > left(ii))
conspos = find(board(ii,jj:right(ii)));
cons = board(ii,jj+conspos-1);
hncon = numel(cons);
if (hncon==0)
hkl = wordsgood&(wlen<=right(ii)-jj+1);
else
hkl = false(numel(wordsgood),1);
tcand = wordsgood&(wlen<=right(ii)-jj+1);
xwmat = wmat(tcand,conspos);
hkl(tcand) = (sum(bsxfun(@eq,xwmat,cons)|xwmat==0,2)==hncon);
%hkl = (wordsgood&(wlen<=right(ii)-jj+1)&(sum(bsxfun(@eq,xwmat,cons)|xwmat==0,2)==hncon));
end;
hk = find(hkl);
else
hk = [];
end;
% possible vertical placements
if (ii > top(jj))
conspos = find(board(ii:bottom(jj),jj))';
cons = board(ii+conspos-1,jj)';
vncon = numel(cons);
if (vncon==0)
vkl = wordsgood&(wlen<=bottom(ii)-ii+1);
else
vkl = false(numel(wordsgood),1);
tcand = wordsgood&(wlen<=bottom(ii)-ii+1);
xwmat = wmat(tcand,conspos);
vkl(tcand) = (sum(bsxfun(@eq,xwmat,cons)|xwmat==0,2)==vncon);
%vkl = (wordsgood&(wlen<=bottom(ii)-ii+1)&(sum(bsxfun(@eq,xwmat,cons)|xwmat==0,2)==vncon));
end;
vk = find(vkl);
else
vk = [];
end;
if isempty(hk)&isempty(vk)
% nothing fits
continue
%vkp = 0;
%hkp = 0;
elseif isempty(hk)
% fill in vertical placement
vkp = vk(1);
hkp = 0;
elseif isempty(vk)
% fill in horizontal placement
hkp = hk(1);
vkp = 0;
else
% possible fits both ways; look for match
vks = wmat(vk,1);
hks = wmat(hk,1);
vksc = accumarray(vks(:),ones(numel(vks,1)),[maxc,1]);
hksc = accumarray(hks(:),ones(numel(hks,1)),[maxc,1]);
okc = (min(vksc,hksc)>=1)&(max(vksc,hksc) >= 2);
if (~any(okc))
% pick direction that satisfies most constraints
if (hncon > vncon)
hkp = hk(1);
vkp = 0;
else
vkp = vk(1);
hkp = 0;
end;
else
okvk = vk(okc(vks));
vkp = okvk(1);
cp = wmat(vkp,1);
okhk = hk(hks==cp);
hkp = okhk(1);
if (vkp==hkp)
if (sum(hks==cp)==1)
okvk = vk(vks==cp);
vkp = okvk(2);
else
okhk = hk(hks==cp);
hkp = okhk(2);
end;
end;
end;
end;
if (vkp>0)
board(ii:ii+wlen(vkp),jj) = wmat(vkp,1:wlen(vkp)+1)';
wordsgood(vkp) = false;
top(jj) = ii+wlen(vkp);
end;
if (hkp>0)
board(ii,jj:jj+wlen(hkp)) = wmat(hkp,1:wlen(hkp)+1);
wordsgood(hkp) = false;
left(ii) = jj+wlen(hkp);
end;
%imagesc(sign(board)); axis image off;
%disp([hkp,vkp]);
%drawnow;
end;
end;
board = board(2:end-1,2:end-1);
board(board<0) = 0;
%wordsgood = wordsgood';
S = sum(wordsgood.*weights');
end
|
