function board = solver(words, weights, n, penalty)
%meat_packer v.5
% weight by weight per letter (one for the end too)
% with scoring metric
ii = 0;
ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack2(words, weights, n, penalty); %every other fill
ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack3(words, weights, n, penalty); % 2 interleaved every other fills
ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack4(words, weights, n, penalty); % all lines filled (squeeze & pack)
[m, mi] = min(score);
m = m(1);
mi = mi(1);
% fprintf('Winner %1d scores: %7d %7d %7d \n', mi, score(1), score(2), score(3));
board = boardout{mi};
end
% *********************************
function [board, estim_score] = meat_pack2(words, weights, n, penalty)
%meat_packer v.2
% weight by weight per letter (one for the end too)
board = zeros(n, n+1);
%just pack in, every other line
wordavail = ones(size(weights));
%form length indexing
for ii = 1:length(words),
tmpl = length(words{ii});
% wordsoflen(tmpl) = [words_len(tmpl) ii];
wordlen(ii) = tmpl;
end
%rank the word list
realweights = weights ./ (wordlen + 1);
%sort by realweights
[w_sort, w_sorti] = sort(realweights, 1, 'descend');
done = 0;
row = 1;
while done == 0,
%form a row
tmprow = zeros(1,n+1);
col = 1;
donerow = 0;
colleft = n;
while donerow == 0
%next word
oksize = double(wordlen <= colleft);
[m, ii] = max(realweights .* wordavail .* oksize);
if isempty(m)
%row is done
donerow = 1;
elseif m(1) == 0,
donerow = 1;
else
m = m(1); ii = ii(1);
tmprow(col:col+wordlen(ii)) = [words{ii} 0];
col = col+wordlen(ii)+1;
colleft = n - col + 1;
wordavail(ii) = 0;
if colleft <= 1,
donerow = 1;
end
end
end
board(row,:) = tmprow;
row = row + 2;
if row > n,
done = 1;
end
end
board = board(:, 1:n);
%estimate score:
% assume horiz words ok, vert are bogus
remain_in_dict = sum(weights .* wordavail);
binboard = [zeros(1,n); sign(board)];
diff1 = diff(binboard, 1, 1);
diff2 = diff(diff1, 1, 1);
diff1 = diff1(1:end-1, :);
bi = find(diff1 == 1 & diff2 == -1);
nbogus = numel(bi);
estim_score = remain_in_dict + nbogus * penalty;
% fprintf('Est score: %d remain: %d nbogus %d penalty %d\n', estim_score, remain_in_dict, nbogus, penalty);
end %fn
% *********************************
function [board, estim_score] = meat_pack3(words, weights, n, penalty)
%meat_packer v.3
% weight by weight per letter (one for the end too)
board = zeros(n, n+1);
%just pack in, every other line
wordavail = ones(size(weights));
%form length indexing
for ii = 1:length(words),
tmpl = length(words{ii});
% wordsoflen(tmpl) = [words_len(tmpl) ii];
wordlen(ii) = tmpl;
end
%rank the word list
realweights = weights ./ (wordlen + 1);
%sort by realweights
[w_sort, w_sorti] = sort(realweights, 1, 'descend');
done = 0;
row = 1;
while done == 0,
%form a row
tmprow = zeros(1,n+1);
col = 1;
donerow = 0;
colleft = n;
while donerow == 0
%next word
oksize = double(wordlen <= colleft);
[m, ii] = max(realweights .* wordavail .* oksize);
if isempty(m)
%row is done
donerow = 1;
elseif m(1) == 0,
donerow = 1;
else
m = m(1); ii = ii(1);
tmprow(col:col+wordlen(ii)) = [words{ii} 0];
col = col+wordlen(ii)+1;
colleft = n - col + 1;
wordavail(ii) = 0;
if colleft <= 1,
donerow = 1;
end
end
end
board(row,:) = tmprow;
row = row + 2;
if row > n,
done = 1;
end
end
%part 2:
%
% estimate: if the remaining weight > 2 penalty per word, then fill in
% all rows
w_used = sum(1-wordavail);
wt_used = sum(weights .* (1-wordavail));
if (wt_used / w_used) > 0.9*penalty,
% fprintf('fill 2nd half\n');
done = 0;
row = 2;
while done == 0,
%form a row
tmprow = zeros(1,n+1);
col = 1;
donerow = 0;
colleft = n;
while donerow == 0
%next word
oksize = double(wordlen <= colleft);
[m, ii] = max(realweights .* wordavail .* oksize);
if isempty(m)
%row is done
donerow = 1;
elseif m(1) == 0,
donerow = 1;
else
m = m(1); ii = ii(1);
tmprow(col:col+wordlen(ii)) = [words{ii} 0];
col = col+wordlen(ii)+1;
colleft = n - col + 1;
wordavail(ii) = 0;
if colleft <= 1,
donerow = 1;
end
end
end
board(row,:) = tmprow;
row = row + 2;
if row > n,
done = 1;
end
end
end
board = board(:, 1:n);
%estimate score:
% assume horiz words ok, vert are bogus
remain_in_dict = sum(weights .* wordavail);
binboard = [zeros(1,n); sign(board)];
diff1 = diff(binboard, 1, 1);
diff2 = diff(diff1, 1, 1);
diff1 = diff1(1:end-1, :);
bi = find(diff1 == 1 & diff2 == -1);
nbogus = numel(bi);
estim_score = remain_in_dict + nbogus * penalty;
% fprintf('Est score: %d remain: %d nbogus %d penalty %d\n', estim_score, remain_in_dict, nbogus, penalty);
end
% *********************************
function [board, estim_score] = meat_pack4(words, weights, n, penalty)
board = zeros(n, n+1);
%just pack in, every other line
wordavail = ones(size(weights));
%form length indexing
for ii = 1:length(words),
tmpl = length(words{ii});
% wordsoflen(tmpl) = [words_len(tmpl) ii];
wordlen(ii) = tmpl;
end
%rank the word list
realweights = weights ./ (wordlen + 1);
%sort by realweights
[w_sort, w_sorti] = sort(realweights, 1, 'descend');
done = 0;
row = 1;
while done == 0,
%form a row
tmprow = zeros(1,n+1);
col = 1;
donerow = 0;
colleft = n;
while donerow == 0
%next word
oksize = double(wordlen <= colleft);
[m, ii] = max(realweights .* wordavail .* oksize);
if isempty(m)
%row is done
donerow = 1;
elseif m(1) == 0,
donerow = 1;
else
m = m(1); ii = ii(1);
tmprow(col:col+wordlen(ii)) = [words{ii} 0];
col = col+wordlen(ii)+1;
colleft = n - col + 1;
wordavail(ii) = 0;
if colleft <= 1,
donerow = 1;
end
end
end
board(row,:) = tmprow;
% %%%% debug
% tmprow(tmprow == 0) = 32;
% fprintf('%s\n',char(tmprow(1:n)));
row = row + 2;
if row > n,
done = 1;
end
end
%part 2:
%
% estimate: if the remaining weight > 2 penalty per word, then fill in
% all rows
w_used = sum(1-wordavail);
wt_used = sum(weights .* (1-wordavail));
if (wt_used / w_used) > 0.9*penalty,
% fprintf('fill 2nd half\n');
%first compact 1st half to upper pt of board %v5 - for visual:
%reorder after anyway
for ii = 3:2:n,
board((ii+1)/2,:) = board(ii,:);
board(ii,:) = 0;
end
done = 0;
row = ceil(n/2)+1;
while done == 0,
%form a row
tmprow = zeros(1,n+1);
col = 1;
donerow = 0;
colleft = n;
while donerow == 0
%next word
oksize = double(wordlen <= colleft);
[m, ii] = max(realweights .* wordavail .* oksize);
if isempty(m)
%row is done
donerow = 1;
elseif m(1) == 0,
donerow = 1;
else
m = m(1); ii = ii(1);
tmprow(col:col+wordlen(ii)) = [words{ii} 0];
col = col+wordlen(ii)+1;
colleft = n - col + 1;
wordavail(ii) = 0;
if colleft <= 1,
donerow = 1;
end
end
end
board(row,:) = tmprow;
row = row + 1;
if row > n,
done = 1;
end
end
end
board = board(:, 1:n);
%estimate score:
% assume horiz words ok, vert are bogus
remain_in_dict = sum(weights .* wordavail);
binboard = [zeros(1,n); sign(board)];
diff1 = diff(binboard, 1, 1);
diff2 = diff(diff1, 1, 1);
diff1 = diff1(1:end-1, :);
bi = find(diff1 == 1 & diff2 == -1);
nbogus = numel(bi);
estim_score = remain_in_dict + nbogus * penalty;
% fprintf('Est score: %d remain: %d nbogus %d penalty %d\n',
% estim_score, remain_in_dict, nbogus, penalty);
end
|
