2011-04-20 12:00:00 UTC

Valles Marinaris

Status: Passed
Results: 6830338 (cyc: 17, node: 7614)
CPU Time: 62.99
Score: 17091.8
Submitted at: 2011-04-20 15:44:57 UTC
Scored at: 2011-04-20 18:16:01 UTC

Current Rank: 2nd (Highest: 1st )

Nicholas Howe
20 Apr 2011
I think this is my best entry score-wise. It breaks 6M on the sample test suite, barely. We'll see how it does when the queue clears!
Nicholas Howe
20 Apr 2011
Misspelled the name of Valles Marineris. How embarrassing! Good thing this one didn't win.
Code
```% from 63233 & grandcanyon2
function out = valles(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';

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));
end

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;

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));
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);
[~,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, 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)));
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';
wmat = cat(1,pwords{:});
maxc = max(wmat(:));
board = repmat(-1,n+2,n+2);
board(2:end-1,2:end-1) = yboard;
top = zeros(1,n+2);
%left = zeros(1,n+2);
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
```