2011-04-20 12:00:00 UTC

# Pack-em9b

Status: Passed
Results: 7797499 (cyc: 9, node: 644)
CPU Time: 43.922
Score: 19494.4
Submitted at: 2011-04-14 15:59:25 UTC
Scored at: 2011-04-14 16:39:41 UTC

Current Rank: 1352nd (Highest: 41st )

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

% ---------------
% 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);