Tails

function board = solver(words, weights, n, penalty)

% Victoria's solver

PThresh = 0.15;
board = zeros(n);

QWords = numel(words);
WordsInUse = false(1,QWords);

L = zeros(1,QWords);
for i=1:QWords;
    L(i)=numel(words{i});
end

SpecificWeights = weights./(L + 1);
[~,IndWS] = sort(SpecificWeights,'descend');

SpecLCum = zeros(1,QWords);
SpecLCum(1) = L(IndWS(1)) + 1;
for i=2:QWords;
    SpecLCum(i) = SpecLCum(i-1) + L(IndWS(i)) + 1;
end

MaxQ = numel(find(SpecLCum <= n.*(n+1)));
GoodWeight = sum(weights(IndWS(1:MaxQ)));
BadGoodCoef = n.*penalty./GoodWeight;

P = BadGoodCoef > PThresh;
if P
    slots = ones(1,ceil(n/2));
else
    slots = ones(1,n);
end

i = 1;
while min(slots) < n && i <= QWords

    Space = n - L(IndWS(i)) + 1 - slots;
    if any(Space == 0)
        SlotIndex = find(Space == 0,1);
    else
        if any(Space > 0)
            [~,SlotIndex] = max(Space);
        else
            SlotIndex = [];
        end
    end
    
    if ~isempty(SlotIndex)
        board(RowIndex(SlotIndex),slots(SlotIndex):slots(SlotIndex) + ...
            L(IndWS(i)) - 1) = words{IndWS(i)};
        slots(SlotIndex) = slots(SlotIndex) + L(IndWS(i)) + 1;
        
        WordsInUse(IndWS(i)) = true;
    end
    
    i=i+1;
end

if P
    for i = 1:QWords
        CurInd = IndWS(i);
        CurL = L(CurInd);
        if ~WordsInUse(CurInd) && (CurL/2 ~= round(CurL/2))
            [I,J] = find(board(1:n - CurL + 1,:) == words{CurInd}(1));
            if ~isempty(I)
                j = 1;
                while ~WordsInUse(CurInd) && (j <= numel(I))
                    if all(words{CurInd}(1:2:end) == ...
                            board(I(j):2:I(j) + CurL - 1,J(j))')
                        board(I(j):I(j) + CurL - 1,J(j)) = words{CurInd}';
                        
                        WordsInUse(IndWS(i)) = true;
                    end
                    j = j + 1;
                end
            end
        end
    end
end

    function Ind = RowIndex(SI)
        if P
            Ind = 2*SI - 1;
        else
            Ind = SI;
        end
    end

end