Finish 2011-04-20 12:00:00 UTC

Valles Marinaris

by Nicholas Howe

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 )

Comments
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.
Please login or create a profile.
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';
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