2011-04-20 12:00:00 UTC

# Pack-em13 - unlucky for some

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 )

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
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

% ---------------
[~,i] = sort(word_weights,2,'descend');   % Sort words by weight
word_i = word_i(i);
for w=1:(n*nwc)
unused(word_i(w)) = false;
end
for wc=1:nwc
c = sc+(wc-1)*(wl+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