function board = solver(words, weights, n, penalty)
%meat_packer v.8
% weight by weight per letter (one for the end too)
% with scoring metric
% with/ without dupl dict entries
%make hash
wordhash = zeros(length(words), 1);
for jj = 1:length(words),
wordhash(jj) = applyHash(words{jj});
end
ii = 0;
% dupl_ok = 0; %y=1/n=0 for dupls
% ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack2(words, weights, n, penalty, wordhash, dupl_ok); %every other fill
% ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack3(words, weights, n, penalty, wordhash, dupl_ok); % 2 interleaved every other fills
% ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack4(words, weights, n, penalty, wordhash, dupl_ok); % all lines filled (squeeze & pack)
% ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack4order(words, weights, n, penalty, wordhash, dupl_ok); % all lines filled (squeeze & pack)
dupl_ok = 1; %y=1/n=0 for dupls
ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack2(words, weights, n, penalty, wordhash, dupl_ok); %every other fill
ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack3(words, weights, n, penalty, wordhash, dupl_ok); % 2 interleaved every other fills
ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack4(words, weights, n, penalty, wordhash, dupl_ok); % all lines filled (squeeze & pack)
ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack4order(words, weights, n, penalty, wordhash, dupl_ok, -1); % all lines filled (squeeze & pack)
ii = ii + 1; [boardout{ii}, score(ii)] = meat_pack4order(words, weights, n, penalty, wordhash, dupl_ok, 1); % all lines filled (squeeze & pack)
[m, mi] = min(score);
m = m(1);
mi = mi(1);
% fprintf('Winner %1d scores: ', mi);
% fprintf('%7d ', score);
% fprintf('\n');
board = boardout{mi};
% board = boardout{4};
end
% *********************************
function [board, estim_score] = meat_pack2(words, weights, n, penalty, wordhash, dupl_ok)
%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));
wordnoignore = 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);
[m0, ii0] = max(realweights .* wordavail .* wordnoignore .*oksize);
if isempty(m0)
%row is done
donerow = 1;
elseif m0(1) == 0,
donerow = 1;
else
m = m0(1); ii = ii0(1);
if dupl_ok == 1,
dupl = 0; %fake out dupl flagging
else
dupl = 0;
thishash = applyHash(words{ii});
simi = find(wordhash == thishash);
for jj = 1:length(simi),
if ~(simi(jj) == ii) & (words{simi(jj)} == words{ii}),
dupl = 1;
break;
end
end
end
if dupl == 1,
% dupl found, ignore
wordnoignore(ii) = 0;
wordnoignore(simi(jj)) = 0;
else
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
end
board(row,:) = tmprow;
row = row + 2;
if row > n,
done = 1;
end
end
board = board(:, 1:n);
estim_score = my_estim_score(words, wordhash, weights, wordavail, board, penalty);
end
% *********************************
function [board, estim_score] = meat_pack3(words, weights, n, penalty, wordhash, dupl_ok)
%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));
wordnoignore = 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);
[m0, ii0] = max(realweights .* wordavail .* wordnoignore .*oksize);
if isempty(m0)
%row is done
donerow = 1;
elseif m0(1) == 0,
donerow = 1;
else
m = m0(1); ii = ii0(1);
if dupl_ok == 1,
dupl = 0; %fake out dupl flagging
else
dupl = 0;
thishash = applyHash(words{ii});
simi = find(wordhash == thishash);
for jj = 1:length(simi),
if ~(simi(jj) == ii) & (words{simi(jj)} == words{ii}),
dupl = 1;
break;
end
end
end
if dupl == 1,
% dupl found, ignore
wordnoignore(ii) = 0;
wordnoignore(simi(jj)) = 0;
else
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
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);
[m0, ii0] = max(realweights .* wordavail .* wordnoignore .*oksize);
if isempty(m0)
%row is done
donerow = 1;
elseif m0(1) == 0,
donerow = 1;
else
m = m0(1); ii = ii0(1);
if dupl_ok == 1,
dupl = 0; %fake out dupl flagging
else
dupl = 0;
thishash = applyHash(words{ii});
simi = find(wordhash == thishash);
for jj = 1:length(simi),
if ~(simi(jj) == ii) & (words{simi(jj)} == words{ii}),
dupl = 1;
break;
end
end
end
if dupl == 1,
% dupl found, ignore
wordnoignore(ii) = 0;
wordnoignore(simi(jj)) = 0;
else
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
end
board(row,:) = tmprow;
row = row + 2;
if row > n,
done = 1;
end
end
end
board = board(:, 1:n);
estim_score = my_estim_score(words, wordhash, weights, wordavail, board, penalty);
end
% *********************************
function [board, estim_score] = meat_pack4(words, weights, n, penalty, wordhash, dupl_ok)
board = zeros(n, n+1);
%just pack in, every other line
wordavail = ones(size(weights));
wordnoignore = 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);
[m0, ii0] = max(realweights .* wordavail .* wordnoignore .*oksize);
if isempty(m0)
%row is done
donerow = 1;
elseif m0(1) == 0,
donerow = 1;
else
m = m0(1); ii = ii0(1);
if dupl_ok == 1,
dupl = 0; %fake out dupl flagging
else
dupl = 0;
thishash = applyHash(words{ii});
simi = find(wordhash == thishash);
for jj = 1:length(simi),
if ~(simi(jj) == ii) & (words{simi(jj)} == words{ii}),
dupl = 1;
break;
end
end
end
if dupl == 1,
% dupl found, ignore
wordnoignore(ii) = 0;
wordnoignore(simi(jj)) = 0;
else
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
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);
[m0, ii0] = max(realweights .* wordavail .* wordnoignore .*oksize);
if isempty(m0)
%row is done
donerow = 1;
elseif m0(1) == 0,
donerow = 1;
else
m = m0(1); ii = ii0(1);
if dupl_ok == 1,
dupl = 0; %fake out dupl flagging
else
dupl = 0;
thishash = applyHash(words{ii});
simi = find(wordhash == thishash);
for jj = 1:length(simi),
if ~(simi(jj) == ii) & (words{simi(jj)} == words{ii}),
dupl = 1;
break;
end
end
end
if dupl == 1,
% dupl found, ignore
wordnoignore(ii) = 0;
wordnoignore(simi(jj)) = 0;
else
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
end
board(row,:) = tmprow;
row = row + 1;
if row > n,
done = 1;
end
end
end
board = board(:, 1:n);
estim_score = my_estim_score(words, wordhash, weights, wordavail, board, penalty);
end
% *********************************
function [board, estim_score] = meat_pack4order(words, weights, n, penalty, wordhash, dupl_ok, orderdir)
board = zeros(n, n+1);
%just pack in, every other line
wordavail = ones(size(weights));
wordnoignore = 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);
[m0, ii0] = max(realweights .* wordavail .* wordnoignore .*oksize);
if isempty(m0)
%row is done
donerow = 1;
elseif m0(1) == 0,
donerow = 1;
else
m = m0(1); ii = ii0(1);
if dupl_ok == 1,
dupl = 0; %fake out dupl flagging
else
dupl = 0;
thishash = applyHash(words{ii});
simi = find(wordhash == thishash);
for jj = 1:length(simi),
if ~(simi(jj) == ii) & (words{simi(jj)} == words{ii}),
dupl = 1;
break;
end
end
end
if dupl == 1,
% dupl found, ignore
wordnoignore(ii) = 0;
wordnoignore(simi(jj)) = 0;
else
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
end
board(row,:) = tmprow;
% %%%% debug
% tmprow(tmprow == 0) = 32;
% fprintf('%s\n',char(tmprow(1:n)));
row = row + 1;
if row > n,
done = 1;
end
end
board = board(:, 1:n);
%reorder the board
wordused = 1-wordavail;
lenused = wordlen(wordused == 1);
done = 0;
board2 = zeros(size(board));
if orderdir == -1,
currlen = max(lenused);
odiff = -1;
else
currlen = min(lenused);
odiff = 1;
end
rr = 1;
cc = 1;
pilewid = 0;
noti = [];
while done == 0,
wi = find(wordlen .* wordused == currlen);
while ~isempty(wi),
thisi = wi(1);
wi = wi(2:end);
if currlen <= n - cc + 1,
board2(rr, cc:cc+currlen) = [words{thisi} 0];
rr = rr + 1;
pilewid = max([pilewid currlen]);
else
noti = [noti thisi];
wordavail(thisi) = 1; %put it back sadly
end
if rr > n,
%new pile
cc = cc + pilewid + 1; %1 for space
rr = 1;
pilewid = 0;
end
% if n - cc < 2,
% %put the remaining unshelved items back
% shelve_rest = 1;
% end
end
%next length
currlen = currlen + odiff;
if orderdir == -1,
if currlen == 0,
done = 1;
end
else
if currlen > max(lenused),
done = 1;
end
end
end
board = board2(1:n,1:n);
estim_score = my_estim_score(words, wordhash, weights, wordavail, board, penalty);
end
function val = applyHash(word)
% applyHash: A rudimentary hashing function to speed up looking for words
% in the dictionary
n = min(5, ceil(numel(word)/2));
m1 = [1e10, 1e9, 1e8, 1e7, 1e6];
m2 = [1e4, 1e3, 1e2, 1e1, 1e0];
val = 1e12*sum(word) + sum(word(1:n).*m1(1:n)) + sum(word(end-n+1:end).*m2(1:n));
end
function estim_score = my_estim_score(words, wordhash, weights, wordavail, board, penalty);
%estimate score:
% assume horiz words ok, vert are bogus
%find each word, check score used
wordused = zeros(size(weights));
wi = find(wordavail == 0);
for ii = 1:length(wi),
thishash = applyHash(words{wi(ii)});
possi = find(wordhash == thishash);
for jj = 1:length(possi),
if isequal(words{wi(ii)}, words{possi(jj)}),
thisi = possi(jj);
break
end
end
wordused(thisi) = 1;
end
% remain_in_dict = sum(weights .* wordavail);
remain_in_dict = sum(weights .* (1-wordused));
n = size(board, 2);
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
|
