V14

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

board = zeros(n);

firstColFree = 1;
firstRowFree = 1;
for k = 1:size(words,2)
    s(k) = size(words{k},2);
end

wps = weights ./ s;

colsLeft = n;
reduceList = [];

while colsLeft > 2
    blockValue = [];
    blockNum = [];
    firstColFree = n - colsLeft + 1;
    
    %Find best block
    for i = 2:min(colsLeft,max(s))
        
        nw = wps;
        
        ix = s ~= i;
        
        nw(ix) = 0;
        [A wordIx] = sort(nw, 'descend');
        
        if A(n) > 0
            blockValue = [blockValue (sum(wps(wordIx(1:n))) - penalty * i )/ (i+1)] ; 
            blockNum = [blockNum i];
        else
            blockValue = [blockValue 0];
            blockNum = [blockNum i];
        end
    end
    
    % Write block
    is = blockValue == max(blockValue);
    if sum(blockValue) > 0
        compy = blockNum(is);
        compy = compy(1);
        
        nw = wps;
        ix = s == compy;
        ix = ~ix;
        nw(ix) = 0;
        [A wordIx] = sort(nw, 'descend');
        
        for i = 1:n
            board(i,firstColFree:firstColFree+compy-1) = words{wordIx(i)};
        end
        firstRowFree = n;
    else
        % No block found
        break
    end
    
    %     Reduce
    reduceList = wordIx(1:n);
    words(reduceList) = [];
    wps(reduceList) = [];
    s(reduceList) = [];
    
    %     Reduce columns
    colsLeft = colsLeft - compy - 1 ;
end

% Fill inhomogeneous blocks

curLen = 2;
nw = wps;
ix = s ~= curLen;
nw(ix) = 0;
[A wordIx] = sort(nw, 'descend');

reduceList = [];

firstColFree = n - colsLeft + 1;

curCol = firstColFree;
curRow = 1;
while curCol + curLen <= n
    while curRow <= n
        i = wordIx(1);
        if s(i) == curLen
            if curCol + curLen <= n
                board(curRow,curCol:curCol+s(i)-1) = words{i};
                reduceList = [reduceList i];
            else
                break;
            end
            curRow = curRow + 1;
            
            if length(wordIx) > 1
                wordIx = wordIx(2:end);
            end
        else
            curLen = curLen + 1;
            nw = wps;
            ix = s ~= curLen;
            nw(ix) = 0;
            [A wordIx] = sort(nw, 'descend');
            i = wordIx(1);
        end
        firstRowFree = max(firstRowFree,curRow);
    end
    curCol = curCol + curLen + 1;
    curRow = 1;
end

words(reduceList) = [];
wps(reduceList) = [];
s(reduceList) = [];

firstColFree = curCol;



reduceList = [];



%V2 filler for empty Boards
if max(board) == 0
    inc = 1;
    [A wordIx] = sort(wps, 'descend');
    curRow = 1;
    curCol = 1;
    
    b = wordIx(1:n);
    if sum(weights(b(1:ceil(n/2)))) > sum(weights(b(1:n))) - penalty * max(s(b)) + floor(n/2) * penalty
        inc = 2;
    else
        inc = 1;
    end
    
    while curRow <= n
        while curCol < n
            i = wordIx(1);
            if s(i) <= n-curCol+1
                board(curRow,curCol:curCol+s(i)-1) = words{i};
                curCol = curCol + s(i) + 1;
                reduceList = [reduceList i];
                if length(wordIx) > 1
                    wordIx = wordIx(2:end);
                else
                    curCol = n;
                    curRow = n;
                end
            else
                curCol = n;
            end
        end
        curCol = 1;
        curRow = curRow + inc;
    end
end

if ~isempty(reduceList)
    words(reduceList) = [];
    wps(reduceList) = [];
    s(reduceList) = [];
end

reduceList = [];

% if firstRowFree < n/2 & board(firstRowFree, 1) == 0
% 
% [A wordIx] = sort(wps, 'descend');
% curRow = firstRowFree;
% curCol = 1;
% 
% while curRow <= n
%     while curCol < n
%         i = wordIx(1);
%         if s(i) <= n-curCol+1
%             board(curRow,curCol:curCol+s(i)-1) = words{i};
%             curCol = curCol + s(i) + 1;
%             reduceList = [reduceList i];
%             
%             if length(wordIx) > 1
%                 wordIx = wordIx(2:end);
%             else
%                 curCol = n;
%                 curRow = n;
%             end
%         else
%             curCol = n;
%         end
%     end
%     curCol = 1;
%     curRow = curRow + 1;
% end
% 
% 
% if ~isempty(reduceList)
%     words(reduceList) = [];
%     wps(reduceList) = [];
%     s(reduceList) = [];
% end
% reduceList = [];
% end


board = board';

[A wordIx] = sort(wps, 'descend');
curRow = firstColFree;
curCol = 1;

while curRow <= n
    while curCol < n
        i = wordIx(1);
        if s(i) <= n-curCol+1
            board(curRow,curCol:curCol+s(i)-1) = words{i};
            curCol = curCol + s(i) + 1;
            reduceList = [reduceList i];
            
            if length(wordIx) > 1
                wordIx = wordIx(2:end);
            else
                curCol = n;
                curRow = n;
            end
        else
            curCol = n;
        end
    end
    curCol = 1;
    curRow = curRow + 2;
end


if ~isempty(reduceList)
    words(reduceList) = [];
    wps(reduceList) = [];
    s(reduceList) = [];
end
reduceList = [];


% Featuring Andreas
maxv = max(wps);
wlens = cellfun(@(x) numel(x), words);
myf = wlens - wps./(maxv+1);
for i = 1:2;
    
    while ~isempty(words);
        [~,wix] = min(myf);
        nextwsize = wlens(wix);
        p = [0, 1, 0; ones(nextwsize, 3); 0, 1, 0];
        spots = conv2(board, p, 'full')==0;
        spots = spots(nextwsize+1:end-nextwsize, 2:end-1);
        if ~any(spots(:)); break; end
        nextw = words{wix};
        [r c] = find(spots, 1, 'first');
        board(r:r-1+nextwsize,c) = nextw';
        myf(wix)=[];
        words(wix)=[];
        wlens(wix)=[];
    end
    board=board';
end

board = board';

end