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

Pack-em13 - unlucky for some

by Martin Rees

Status: Passed
Results: 7283904 (cyc: 7, node: 501)
CPU Time: 16.32
Score: 18210.2
Submitted at: 2011-04-15 11:27:34 UTC
Scored at: 2011-04-15 11:30:26 UTC

Current Rank: 1213th (Highest: 9th )

Comments
Please login or create a profile.
Code
function board = solver(words, weights, n, penalty)

    % Solver - Pack-em13

    board = zeros(n);

    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(word_lengths,2,'ascend');   % Sort words by length
    words = words(i);
    word_lengths = word_lengths(i);
    weights = weights(i);

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

    % Arrays used in indexing
    all_words = 1:num_words;

    % Don't use words with zero weights
    unused(weights==0) = false;
    
    grid_cols_used = 0;
    
    % Loop through the word lengths
    for wl = min(word_lengths(unused)):min(max(word_lengths(unused)),n)
        wlc = sum(word_lengths(unused)==wl);
        if wlc>0
            max_cols = floor((n-grid_cols_used)/(wl+1));
            word_cols = min(floor(wlc/n),max_cols);
            if word_cols>0
                add_word_columns(all_words(unused & word_lengths==wl),weights(unused & word_lengths==wl),wl,grid_cols_used+1,word_cols);
                grid_cols_used = grid_cols_used + word_cols*(wl+1);
            end
        end
        if wl>=(n-grid_cols_used)
            % Cannot fit in any more words
            break;
        end
    end
    if grid_cols_used<n
        % Fill the rows, not bothering with whole columns
        fill_rows
    end

    % ---------------
    function add_word_columns(word_i,word_weights,wl,sc,nwc)
        [~,i] = sort(word_weights,2,'descend');   % Sort words by weight
        word_i = word_i(i);
        words_to_add = zeros(n*nwc,wl);
        for w=1:(n*nwc)
            words_to_add(w,:) = words{word_i(w)};
            unused(word_i(w)) = false;
        end
        for wc=1:nwc
            c = sc+(wc-1)*(wl+1);
            board(1:2:n,c:(c+wl-1)) = words_to_add((1:2:n)+n*(wc-1),:);
            board(2:2:n,1+(c:(c+wl-1))) = words_to_add((2:2:n)+n*(wc-1),:);
        end
    end

    function fill_rows
        grid_col_pos = ones(n,1);
        grid_col_pos(1:2:n) = grid_cols_used;
        grid_col_pos(2:2:n) = grid_cols_used+1;
        last_r = 0;
        for w=all_words(unused)
            word_length = word_lengths(w);
            if word_length<=n
                % Find a row to put it in
                all_rows = 1:n;
                for r=all_rows([(last_r+1):end,1:last_r])
                    space = n-grid_col_pos(r);
                    if space>=word_length;
                        board(r,grid_col_pos(r)+(1:word_length)) = words{w};
                        unused(w) = 0;
                        grid_col_pos(r) = grid_col_pos(r) + word_length + 1; % Allow a gap after the word
                        last_r = r;
                        break
                    end
                end
            end
            if all(grid_col_pos>=n)
                % Grid is full
                break
            end
        end
    end
end