Pack-em9b

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

    % Solver - Pack-em9b

    board = zeros(n+2);
    board_tr = zeros(n+2); % Transpose

    num_words = size(words,2);

    % Find the word lengths
    word_lengths = zeros(1,num_words);
    for w=1:num_words
        word_lengths(w) = size(words{w},2);
    end

    %[~,i] = sort(weights,2,'descend');   % Sort words by weight
    [~,i] = sort(weights./(word_lengths+1),2,'descend');  % Sort words by weight per letter
    words = words(i);
    word_lengths = word_lengths(i);

    unused = true(1,num_words); % Track which words not yet used

    % Arrays used in indexing
    all_words = 1:num_words;

    % Fast-fill rows
    fast_fill_rows;

    remaining_words = all_words(unused);
    if numel(remaining_words)>200
        remaining_words = remaining_words(1:50);
    end
    
    % Loop through the words and add them where possible
    for w=remaining_words
        if add_word_to_column(words{w},word_lengths(w));
            unused(w) = false;
        end
    end
    board = board(2:(end-1),2:(end-1));

    % ---------------
    function fast_fill_rows
        % Loop through the words and add them to the rows
        grid_col_pos = ones(n,1);
        rows = [1:2:n,2:2:n];
        last_fj = 0;
        max_fj = size(rows,2);
        for fi=all_words(unused)
            word_length = word_lengths(fi);
            if word_length<=n
                % Find a row to put it in
                for fj=[(last_fj+1):max_fj, 1:last_fj]
                    fjr = rows(fj);
                    space = n+1-grid_col_pos(fjr);
                    if space>=word_length;
                        board(fjr+1,grid_col_pos(fjr)+(1:word_length)) = words{fi};
                        board_tr(grid_col_pos(fjr)+(1:word_length),fjr+1) = words{fi}';
                        unused(fi) = 0;
                        grid_col_pos(fjr) = grid_col_pos(fjr) + word_length + 1; % Allow a gap after the word
                        if penalty>0
                            if fjr>1
                                grid_col_pos(fjr-1) = max(grid_col_pos(fjr-1),grid_col_pos(fjr)-1);
                            end
                            if fjr<max_fj
                                grid_col_pos(fjr+1) = max(grid_col_pos(fjr+1),grid_col_pos(fjr)-1);
                            end
                        end
                        last_fj = fj;
                        break
                    end
                end
            end
            if all(grid_col_pos>n)
                % Grid is full
                break
            end
        end

    end

    % ---------------
    function success = add_word_to_column(word,word_length)
        % Same as the function above, but works on columns
        success = false;

        % Make a 3D-array of the existing grid
        exisiting = zeros(n,n-word_length+1,word_length+2);
        for offset = -1:word_length
            exisiting(:,:,offset+2) = board_tr(2:(n+1),(2:(n-word_length+2))+offset);
        end
        
        word_array = repmat(reshape(word,1,1,word_length),[n,n-word_length+1,1]);
        match = all((exisiting(:,:,2:(end-1))==word_array) | (exisiting(:,:,2:(end-1))==0), 3) ...
            & (exisiting(:,:,1)==0) & (exisiting(:,:,end)==0);

        if sum(match(:))>0
            s = size(match);
            index = 1:numel(match);
            for ind=index(match(:));
                [match_r,match_c] = ind2sub(s,ind);
                match_r = match_r+1;
                match_c = match_c+1;
                end_c = match_c+word_length-1;
                existing_block = board_tr((match_r-1):(match_r+1),match_c:end_c);
                new_letter_mask = (existing_block(2,:)==0);
                space_above = all(existing_block(1,new_letter_mask)==0);
                space_below = all(existing_block(3,new_letter_mask)==0);
                if space_above && space_below
                    board_tr(match_r,match_c:end_c) = word;
                    board(match_c:end_c,match_r) = word';
                    success = true;
                    break
                end
            end
        end
    end
end