Diffing "Sneaker" and "Serious Crosswords 1"

Title: Sneaker Serious Crosswords 1
Author: Amitabh Verma Andreas Bonelli
Submitted: 2011-04-20 15:11:33 UTC 2011-04-20 15:56:42 UTC
Status: Passed Passed
Score: 17201.1 17209.8
Result: 6877358 (cyc: 10, node: 6635) 6872840 (cyc: 19, node: 8163)
CPU Time: 59.466 87.964
Code:
function out = solver(words, weights, N, penalty)
function board = solver(words, weights, n, penalty)
    
    takeown  = true;
    takebest = true;
    
    if takebest;
        [board scorebest] = solverbest(words, weights, n, penalty);
    else
        board = zeros(n);
        scorebest = inf;
    end
    
    if takeown && scorebest > 0;
        [boardmy, scoremy] = mysolver(words, weights, n, penalty, scorebest);
        if scoremy < scorebest;
            board = boardmy;
            if ~isinf(scorebest)
%                 disp(['--------- gained ' num2str(scorebest-scoremy)]);
            end
        end
    end
end

[out,sux] = solver_volkan(words, weights, N);
if sux;return;end

nws                     = numel(words);
function [b, score] = mysolver(words, weights, n, penalty, scoretobeat)
    
%     t = tic();
    
    b = zeros(n);
    score = inf;
    
    if ~isinf(scoretobeat) && scoretobeat > 200000;
        %         disp('skipping - score high');
        return;
    end;
    
    c_score  = 1;
    c_weight = 2;
    c_len    = 3;
    c_elen   = 4;
    c_w      = 5;
    
    words = words(:);
    weights = weights(:);
    
    wlens = cellfun(@(x) length(x), words);
    [maxwlen,~] = max(wlens);
    
    ws = zeros(numel(words), maxwlen+c_w-1);
    ws(:,c_len) = wlens;
    ws(:,c_elen) = wlens;
    ws(:,c_weight) = weights;
    ws(:,c_score) = -(ws(:,c_weight) ./ (ws(:,c_len) + 0.5));
    for i = 1:size(ws, 1); ws(i, c_w:c_w+wlens(i)-1) = words{i}; end
    
    score = sum(ws(:,c_weight));
    basescore = score;
    
    if scoretobeat > basescore/2
        return;
    end
    
    nallwords = size(ws, 1);
    
    mwvpl = sum(ws(:,c_weight)) / sum(ws(:,c_len));
    
    ws(:,c_weight) = -ws(:,c_weight);
    ws = sortrows(ws, [c_len, c_weight]);
    ws(:,c_weight) = -ws(:,c_weight);
    
    
    % CHECKS
    
    ws = ws(ws(:,c_len) < n/2, :);
    
    wlenlimit = max(4,3+(n/16.6666));% round(n/10)+1;
    minwords  = 10*n;
    
    if size(ws, 1) > minwords
        wlenok = ws(:,c_len) <= wlenlimit;
        nwlenok = sum(wlenok);
        
        if nwlenok > minwords
            ws = ws(wlenok, :);
        else
            missing = minwords - nwlenok;
            wsout = ws(~wlenok, :);
            ws = [ws(wlenok, :); wsout(1:missing, :)];
        end
    end
    
    mewv   = sum(ws(:,c_weight)) / size(ws, 1);
    
    if max(ws(:,c_len)) <= 3;
        %         disp('skipping - max wlen <= 3');
        return;
    end
    
    if isempty(ws);
        %         disp('skipping - empty ws');
        return;
    end
    
    bestscore = score-sum(ws(:,c_weight));
    if bestscore > scoretobeat;
        %         disp('skipping - can''t beat score');
        return;
    end
    
    %     if size(ws, 1) > 850;
    %         disp('skipping - too slow :(');
    %         return;
    %     end
    
    wlens = unique(ws(:,c_len));
    
    holdbackvalues = wlens(1:end-1);
    holdbackvalues = holdbackvalues(holdbackvalues <= 5);
    if numel(holdbackvalues) > 2; holdbackvalues = holdbackvalues([2,1]); end;
    
    if ~isempty(holdbackvalues)
        % holdbackvalues = [3 2];
        nholdback = numel(holdbackvalues);
        holdback = cell(nholdback, 1);
        for holdbackix = 1:numel(holdbackvalues)
            hv = holdbackvalues(holdbackix);
            isholdback = ws(:,c_len) == hv;
            holdback{holdbackix} = ws(isholdback, :);
            ws(isholdback,:) = [];
        end
    else
        nholdback = 0;
    end
    
    
    
    % SEED
    
    % todo change seed depending on wordlengths
    
    seeds = round(n ./ 22);
    
    stopme =false;
    for i1 = 1:seeds
        for i2 = 1:seeds
            if isempty(ws); stopme = true; break; end;
            if ws(1,c_len) > (n/seeds)-2; return; end;
            
            x = round(n * (2*i1-1) / (2*seeds));
            y = round(n * (2*i2-1) / (2*seeds));
            
            if xor(mod(i1,2), mod(i2,2))
                x = round(x - ws(1,c_len)/2 + 1/2);
                b(x:x-1+ws(1,c_len), y) = ws(1,c_w:c_w-1+ws(1,c_len));
            else
                y = round(y - ws(1,c_len)/2 + 1/2);
                b(x, y:y-1+ws(1,c_len)) = ws(1,c_w:c_w-1+ws(1,c_len));
            end
            
            score = score - ws(1, c_weight);
            ws(1,:) = [];
        end
        if stopme; break; end;
    end
    
    nn = n*n;
    rawboardindices = (1:nn)';
    
    nwords = 0;
    niters = 0;
    
    lastwlen = 0;
    
    
    fun1();
    function fun1()
        
        for holdbackix = 0:nholdback
            if holdbackix > 0;
                ws = [holdback{holdbackix}; ws]; %#ok<AGROW>
            end
            
            found = true;
            while found
                found = false;
                for loop2 = 1:2 % transpose
                    
                    bzm = b == 0;
                    zbefore = [true(1,n); bzm(1:end-1,:)];
                    zbefore = zbefore(:);
                    
                    bz = bzm(:);
                    bnz = ~bz;
                    lz = [true(n,1);bz(1:end-n)];
                    rz = [bz(n+1:end);true(n,1)];
                    
                    bnok = bz & ((~lz) | (~rz));
                    
                    % brave try:
                    %                 bz = bz & lz & rz;
                    
                    wix = 0;
                    while wix <= size(ws, 1) && niters <= 2500;
                        niters = niters + 1;
                        
                        wix = wix + 1;
                        
                        if wix > size(ws, 1) || wix < 1; break; end
                        
                        found = false;
                        wlen = ws(wix, c_len);
                        w    = ws(wix, c_w:c_w-1+wlen);
                        
                        if wlen ~= lastwlen || wix == 1
                            if wlen ~= lastwlen
                                wlenmap = [true(n-wlen+1,n); false(wlen-1,n)];
                                wlenmap = wlenmap(:);
                                posweights = 1 ./ ((1:wlen).*(wlen:-1:1))';
                                lastwlen = wlen;
                            end
                            
                            zafter = [bzm(wlen+1:end,:); true(wlen,n)];
                            zafter = zafter(:);
                            
                            zlimitsok = zbefore & zafter;
                            
                            bwordok = filter(ones(wlen, 1), 1, bnok) < 1;
                            bwordok = [bwordok(wlen:end);false(wlen-1,1)];
                            
                            zlimitsok = zlimitsok & bwordok;
                            
                            check = zlimitsok & wlenmap;
                            boardindices = rawboardindices(check);
                        end
                        
                        % blow bz up
                        bhits = bz(:, ones(1, wlen)) + 0;
                        
                        % fill in matches
                        % bhits(bnz, :) = 2 * (bsxfun(@(x,y) x == y, b(bnz), w) + 0);
                        
                        for i = 1:wlen
                            wl = w(i);
                            bhits(bnz, i) = 2 .* (b(bnz) == wl);
                        end
                        
                        
                        for i = 2:wlen;
                            bhits(:,i) = [bhits(i:end, i); zeros(i-1, 1)];
                        end
                        
                        checkedhits = bhits(check, :);
                        
                        ok = [prod(checkedhits, 2), boardindices, checkedhits];
                        
                        candidates = ok(ok(:,1) > 1 & ok(:,1) < (2.^wlen), :);
                        
                        candidates(:,1) = candidates(:, 3:end) * posweights;
                        
                        if ~isempty(candidates)
                            [~, cix] = max(candidates(:, 1));
                            o = candidates(cix, 2);
                            myhits = candidates(cix, 3:end)' > 1.5;
                            nwords = nwords + 1;
                            % fprintf('word # %4d | %s\n', nwords, w);
                            [x,y]=ind2sub([n,n], o);
                            b(x:x-1+wlen,y) = w';
                            score = score - ws(wix, c_weight);
                            ws(wix,:) = [];
                            found = true;
                            break;
                        end
                        if found; break; end;
                    end % wix
                    if niters > 2500; return; end;
                    b = b';
                end
            end
        end
    end
    
    fun2();
    function fun2()
        for i = 1:2;
            while ~isempty(ws);
                nextwsize = ws(1,c_len);
                p = [0, 1, 0; ones(nextwsize, 3); 0, 1, 0];
                spots = conv2(b, p, 'full')==0;
                spots = spots(nextwsize+1:end-nextwsize, 2:end-1);
                if ~any(spots(:)); break; end
                nextw = ws(1,c_w:c_w-1+nextwsize);
                [r c] = find(spots, 1, 'first');
                b(r:r-1+nextwsize,c) = nextw';
                score = score - ws(1, c_weight);
                ws = ws(2:end,:);
            end
            b=b';
        end
    end
    
%     t = toc(t);
%     
%     scorebest = scoretobeat;
%     escorebest = (basescore-scoretobeat);
%     escore = basescore - score;
%     
%     rscorebest = escorebest/basescore;
%     qscorebest = escorebest / scorebest;
%     
%     fprintf('          | t %.1f | n %3d | ws-size %d | rscorebest %4g | qscorebest %4g | escorebest %d | %.3g of tobeat | \n', ...
%         t, ...
%         n, ...
%         reportsize, ...
%         rscorebest, ...
%         qscorebest, ...
%         escorebest, ...
%         score./scoretobeat);
    %     fprintf('          | ppf   %g\n', (basescore-score) ./ (n^2));
    %     fprintf('          | robn  %g\n', scoretobeat / bestscore);
    %     fprintf('          | escore-best %g\n', (basescore-scoretobeat));
    %     fprintf('          | escore-my   %g\n', (basescore-score));
    %     fprintf('          | my-rating   %g\n', (basescore-score));
    %     fprintf('          | mwvpl       %g\n', mwvpl );
    %     fprintf('          | my-density  %g\n', sum(b(:)>0) ./ (nn));
    %     fprintf('          | mewv        %g\n', mewv);
    %     fprintf('          | fpw         %g\n', nn/nwords);
    
    
    %         reportn
    %         reportsize
    %     end
end

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,760);
    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
    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  (board, 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  (board, wordsflip, weights, N, penalty, lengths, nws, sumw);
    [BOARD{10}, SCORE(10)]    = solver_dave  (board, words, weights, N, penalty, lengths, nws, sumw);
minscore = min(SCORE);
    for j=1:5
        [BOARD{10+j}, SCORE(10+j)]    = solver_james1  (board, mywords{j}, myweights{j}, N, penalty, mylengths{j}, nws, sumw);
if SCORE(10+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 [out, score]= solverbest(words, weights, N, penalty)
function [out, score] = solverbest(words, weights, N, penalty)
    score = 0;
    [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,760);
        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
        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  (board, 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  (board, wordsflip, weights, N, penalty, lengths, nws, sumw);
        [BOARD{10}, SCORE(10)]    = solver_dave  (board, words, weights, N, penalty, lengths, nws, sumw);
        minscore = min(SCORE);
        for j=1:5
            [BOARD{10+j}, SCORE(10+j)]    = solver_james1  (board, mywords{j}, myweights{j}, N, penalty, mylengths{j}, nws, sumw);
            if SCORE(10+j)<minscore
                break ;
            end
        end
    end
    
    [score, 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(board, words, weights, n, penalty, wordlengths, nwords, total)

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

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

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

points = 0;
c=1;
r=1;
while r+1 <= n,
    % try excluding words with letter frequencies of 1
    % ordering words by first and second letter would help
    sq = zeros(2);
    if ~isempty(w2l)
        C1 = C(:,1);
        [sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C1, alphaix,sq);
    end
    
    if ~sq,
        break; % no more 2x2s
    [B,index] = sortrows([wordlengths' weights'],[1 -2]); % index is wordsFromBIndex
    last2letterword = find(B(:,1)>2,1)-1;
    %words2 = words(index(1:last2letterword));
    w2l = index(1:last2letterword)'; % should be row vector for for
    
    isUnplayed = true(1,nwords);
    hopeless   = false(1,nwords);
    
    [C,alphaix]=sortrows(cell2mat(words(w2l)')); % so char(C) = char(words{w2l(alphaix)}) % alphaix is WfromC
    %wFromC=w2l(alphaix); % gives index in original words
    
    points = 0;
    c=1;
    r=1;
    while r+1 <= n,
        % try excluding words with letter frequencies of 1
        % ordering words by first and second letter would help
        sq = zeros(2);
        if ~isempty(w2l)
            C1 = C(:,1);
            [sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C1, alphaix,sq);
        end
        
        if ~sq,
            break; % no more 2x2s
        end
        board(r+(0:1),c+(0:1)) = sq;
        c=c+3;
        if c > n-1,
            r =r+3;
            c=1;
        end
    end
    board(r+(0:1),c+(0:1)) = sq;
    c=c+3;
    if c > n-1,
        r =r+3;
        c=1;
    end
end
points = points + sum(weights(~isUnplayed));

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

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

while (r+B(stop_index,1)-1) <= n, % if the new row fits
    points = points + sum(weights(~isUnplayed));
    
    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
    % 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);
    % play remaining unused 2 letter words here?
    
    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
    % index of last word to play in current row
    stop_index  = min(nwords, n-c+1); % check that we haven't run out of words
    start_index = 1;
    
    while (r+B(stop_index,1)-1) <= n, % if the new row fits
        
        words_left          = stop_index - start_index + 1;                                 % num words to play in this row
        current_row_points  = sum(B(start_index:stop_index,2)) - penalty*B(stop_index-1,1); % use length of next to last word to get number of penalty cols
        
        if current_row_points > 0,
            for cc = c:min(n,words_left+c-1),
                wi = start_index-c+cc; % word index
                board(r:(r+B(wi,1)-1),cc) = words{index(wi)};
                isUnplayed2(index(wi))    = false;
            end
            % the row is unplayed I think it will simply be blank
        end
        
        c=1;
        points = points + current_row_points;
        r=r+B(stop_index,1)+1; % increment row location
        
        start_index=stop_index+1;
        stop_index = min(nwords, stop_index+n);
        
    end
    
    result = total - points;
    
    wordlengths2 = wordlengths(isUnplayed);
    weights2     = weights(isUnplayed);
    
    [board,result] = james_sub_solver(board,wordlengths2,weights2,isUnplayed2,words,result,n);
    
end

function [sq, isUnplayed, hopeless]    = press2(words, isUnplayed, hopeless, w2l, C1, alphaix,sq)
    
    ii_valid = w2l(isUnplayed(w2l) & ~hopeless(w2l));
    
    for ii = ii_valid, % w2l must be a row vector here
        
        
        sq(1,:) = words{ii};
        isUnplayed(ii) = false;
        
        % only iterate over reasonable letters
        conda = C1 == sq(1,1);
        a1 = find(conda,1);
        a2 = find(conda,1,'last');
        w21jj  = w2l(sort(alphaix(a1:a2)));
        
        condb = C1 == sq(1,2);
        b1=find(condb,1);
        b2=find(condb,1,'last');
        
        w21kk  = w2l(sort(alphaix(b1:b2)));
        
        for jj = w21jj
            
            % eval order? also checks could be elim
            if isUnplayed(jj) && ~hopeless(jj)
                
                sq(2,1) = words{jj}(2);
                isUnplayed(jj) = false;
                
                condc = C1 == sq(2,1);
                
                c1=find(condc,1);
                c2=find(condc,1,'last');
                w21ll = w2l(sort(alphaix(c1:c2)));
                
                for kk = w21kk
                    
                    if isUnplayed(kk)
                        
                        sq(2,2)         = words{kk}(2);
                        isUnplayed(kk)  = false;
                        
                        for ll =  w21ll
                            
                            if isUnplayed(ll) && all(sq(2,:) == words{ll})
                                
                                isUnplayed(ll) = false;
                                
                                return; % press completed!
                            end
                        end
                        isUnplayed(kk) = true;
                    end
                end
                isUnplayed(jj) = true;
            end
        end
        isUnplayed(ii) = true;
        
        % should mark words that didn't work out to avoid retrying them
        hopeless(ii) = true; % hopeless in positions 1 or 2
        
    end
    
    sq = zeros(2);
    
    
end

function [board, result]               = solver_james2(board, words, weights, n, penalty, wordlengths, nwords)
    result=sum(weights);
    [B,index] = sortrows([wordlengths' weights'],[1 -2]);
    
    k=1;
    c=1;
    points = points + current_row_points;
    r=r+B(stop_index,1)+1; % increment row location
    isUnplayed         = true(nwords,1);
    current_stop_index = min(nwords, n); % check that we haven't run out of words
    
    start_index=stop_index+1;
    stop_index = min(nwords, stop_index+n);
    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

result = total - points;

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

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

end

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

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

for ii = ii_valid, % w2l must be a row vector here
    
    
    sq(1,:) = words{ii};
    isUnplayed(ii) = false;
    
    % only iterate over reasonable letters
    conda = C1 == sq(1,1);
    a1 = find(conda,1);
    a2 = find(conda,1,'last');
    w21jj  = w2l(sort(alphaix(a1:a2)));
    
    condb = C1 == sq(1,2);
    b1=find(condb,1);
    b2=find(condb,1,'last');
    
    w21kk  = w2l(sort(alphaix(b1:b2)));
    
    for jj = w21jj
        
        % eval order? also checks could be elim
        if isUnplayed(jj) && ~hopeless(jj)
            
            sq(2,1) = words{jj}(2);
            isUnplayed(jj) = false;
            
            condc = C1 == sq(2,1);
            
            c1=find(condc,1);
            c2=find(condc,1,'last');
            w21ll = w2l(sort(alphaix(c1:c2)));
            
            for kk = w21kk
                
                if isUnplayed(kk)
                    
                    sq(2,2)         = words{kk}(2);
                    isUnplayed(kk)  = false;
                    
                    for ll =  w21ll
                        
                        if isUnplayed(ll) && all(sq(2,:) == words{ll})
                            
                            isUnplayed(ll) = false;
                            
                            return; % press completed!
                        end
                    end
                    isUnplayed(kk) = true;
                end
            end
            isUnplayed(jj) = true;
        end
    end
    isUnplayed(ii) = true;
    
    % should mark words that didn't work out to avoid retrying them
    hopeless(ii) = true; % hopeless in positions 1 or 2
    
end

sq = zeros(2);


end

function [board, result]               = solver_james2(board, words, weights, n, penalty, wordlengths, nwords)
result=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
    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, result] = solver_dave(board,words,weights,n, penalty,wordlengths,nwords,total)
    % integrated my press function with james's solver
    [B,index] = sortrows([wordlengths' weights'],[1 -2]); % index is wordsFromBIndex
    last2letterword = find(B(:,1)>2,1)-1;
    %words2 = words(index(1:last2letterword));
    w2l = index(1:last2letterword)'; % should be row vector for for
    
    isUnplayed = true(1,nwords);
    points = 0;
    
    r = 1;
    c = 1;
    
    if ~isempty(w2l)
        [ sq3  played3] = press2tolerant(words(w2l));
        isUnplayed(w2l(played3)) = false;
        r = 1;
        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;
        for k = 1:size(sq3,3)
            board(r,c:c+1) = sq3(1,:,k);
            board(r+1,c+1:c+2) = sq3(2,:,k);
            c = c + 3;
            if c > n - 1
                c = 1;
                r = r + 3;
            end
        end
    end
    c = c + 1;
    points = points + sum(weights(~isUnplayed));
    
    % eliminate words that have already been played
    [B,index]   = sortrows([wordlengths(isUnplayed)' weights(isUnplayed)'],[1 -2]);
    words       = words(isUnplayed);
    nwords      = numel(words);
    isUnplayed2 = true(1,nwords);
    k=1;
    % play remaining unused 2 letter words here?
    
    
    % index of last word to play in current row
    stop_index  = min(nwords, n*k-c+1); % check that we haven't run out of words
    start_index = 1;
    
    while r+B(stop_index,1)-1 <= n, % if the new row fits
        
        words_left          = stop_index - start_index + 1;                                 % num words to play in this row
        current_row_points  = sum(B(start_index:stop_index,2)) - penalty*B(stop_index-1,1); % use length of next to last word to get number of penalty cols
        
        if current_row_points > 0,
            for cc = c:min(n,words_left+c-1),
                wi = start_index-c+cc; % word index
                board(r:(r+B(wi,1)-1),cc) = words{index(wi)};
                isUnplayed2(index(wi))    = false;
                
            end
            
            % the row is unplayed I think it will simply be blank
        end
        
        c=1;
        points = points + current_row_points;
        r=r+B(stop_index,1)+1; % increment row location
        
        k=k+1; % increment row number
        start_index=stop_index+1;
        stop_index = min(nwords, stop_index+n);
        
    end
    
    n       = n + 1;
    seguir  = (min(slots) < N)*(n <= QWords);
    result = total - points;
    
    wordlengths2 = wordlengths(isUnplayed);
    weights2     = weights(isUnplayed);
    
    [board,result] = james_sub_solver(board,wordlengths2,weights2,isUnplayed2,words,result,n);
    
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, result] = solver_dave(board,words,weights,n, penalty,wordlengths,nwords,total)
% integrated my press function with james's solver
[B,index] = sortrows([wordlengths' weights'],[1 -2]); % index is wordsFromBIndex
last2letterword = find(B(:,1)>2,1)-1;
%words2 = words(index(1:last2letterword));
w2l = index(1:last2letterword)'; % should be row vector for for

isUnplayed = true(1,nwords);
points = 0;

r = 1;
c = 1;

if ~isempty(w2l)
  [ sq3  played3] = press2tolerant(words(w2l));
  isUnplayed(w2l(played3)) = false;  
  r = 1;
  c = 1;

  for k = 1:size(sq3,3)
    board(r,c:c+1) = sq3(1,:,k);
    board(r+1,c+1:c+2) = sq3(2,:,k);
    c = c + 3;
    if c > n - 1
      c = 1;
      r = r + 3;
    end
  end
end
c = c + 1;
points = points + sum(weights(~isUnplayed));

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


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

while r+B(stop_index,1)-1 <= n, % if the new row fits
  
  words_left          = stop_index - start_index + 1;                                 % num words to play in this row
  current_row_points  = sum(B(start_index:stop_index,2)) - penalty*B(stop_index-1,1); % use length of next to last word to get number of penalty cols
  
  if current_row_points > 0,
    for cc = c:min(n,words_left+c-1),
      wi = start_index-c+cc; % word index
      board(r:(r+B(wi,1)-1),cc) = words{index(wi)};
      isUnplayed2(index(wi))    = false;
      
    end
    
    % the row is unplayed I think it will simply be blank
  end
  
  c=1;
  points = points + current_row_points;
  r=r+B(stop_index,1)+1; % increment row location
  
  k=k+1; % increment row number
  start_index=stop_index+1;
  stop_index = min(nwords, stop_index+n);
  
end

result = total - points;

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

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

end


% --------------------------------------------------------------------------


function [ sq3  wasPlayed3] = press2tolerant (words)
words = cell2mat(words');
wordMin = min(words(:));
wordMax = max(words(:));
wordRange = wordMax - wordMin + 1;
words = words - wordMin + 1;
N = size(words,1);
unused = true(N,1);
wasPlayed3 = false(N,1);
    words = cell2mat(words');
    wordMin = min(words(:));
    wordMax = max(words(:));
    wordRange = wordMax - wordMin + 1;
    words = words - wordMin + 1;
    N = size(words,1);
    unused = true(N,1);
    wasPlayed3 = false(N,1);
    
    charIdx = cell(2,1);
    for k = 1:2
        charIdx{k} = arrayfun(@(x) find(words(:,k)==x), 1:wordRange, ...
            'UniformOutput', false);
    end
    
    % take the ones that won't match 4 and try to match 3
    sq3 = [];
    for w1= 1:N
        if unused(w1)
            unused(w1) = false;
            [sqNew unused wasPlayed3] = troll23(words, unused, wasPlayed3, w1, charIdx);
            if any(sqNew)
                sq3 = [sq3 sqNew];
            end
        end
    end
    sq3 = reshape(sq3,2,2,[]) + wordMin - 1;
end

charIdx = cell(2,1);
for k = 1:2
  charIdx{k} = arrayfun(@(x) find(words(:,k)==x), 1:wordRange, ...
    'UniformOutput', false);
end

% take the ones that won't match 4 and try to match 3
sq3 = [];
for w1= 1:N
  if unused(w1)
    unused(w1) = false;
    [sqNew unused wasPlayed3] = troll23(words, unused, wasPlayed3, w1, charIdx);
    if any(sqNew)
      sq3 = [sq3 sqNew];
    end
  end
end
sq3 = reshape(sq3,2,2,[]) + wordMin - 1;
end


function [sq unused played] = troll23 (words, unused, played, w1, charIdx)
sq = [];
c2 = words(w1,2);
matches2 = charIdx{1}{c2};
for w2 = matches2(find(unused(matches2),1))
  if any(unused(w2))
    unused(w2) = false;
    c3 = words(w2,2);
    matches3 = charIdx{1}{c3};
    w3 = matches3(find(unused(matches3),1));
    if any(w3)
      unused(w3) = false;
      sq = [words(w1,:); words(w3,:)];
      played([w1 w2 w3]) = true;
      return;
    sq = [];
    c2 = words(w1,2);
    matches2 = charIdx{1}{c2};
    for w2 = matches2(find(unused(matches2),1))
        if any(unused(w2))
            unused(w2) = false;
            c3 = words(w2,2);
            matches3 = charIdx{1}{c3};
            w3 = matches3(find(unused(matches3),1));
            if any(w3)
                unused(w3) = false;
                sq = [words(w1,:); words(w3,:)];
                played([w1 w2 w3]) = true;
                return;
            end
            unused(w2) = true;
        end
    end
    unused(w2) = true;
  end
end
end