function board = solver(words, weights, n, penalty)
%total = sum(weights);
% lb is 3666427
%board = zeros(n); % 9468136
words = words(weights>0);
weights = weights(weights>0);
[board, result] = solver_press(words, weights, n, penalty); % 6494441
[board1, result1] = solver_columns(words, weights, n, penalty); % 7428123
%board=solver_columns2(words, weights, n, penalty); % 6994891
% board=solver_columns2_submit(words, weights, n, penalty); % 6635376
[board3, result3] = solver_columns3(words, weights, n, penalty); % 6635376
% best of columns or columns3 % 6519407
% best of press or columns3 % 6485612
% best of press or columns or columns3 % 6369860
result_vec = [result, result1, result3];
switch find(result_vec == min(result_vec),1),
case 1, ; % do nothing
case 2, board = board1;
case 3, board = board3;
end
end
function [board, result] = solver_press(words, weights, n, penalty)
total = sum(weights);
board = zeros(n);
nwords= numel(words);
for k = 1:nwords,
wordlengths(k)=length(words{k});
end
[B,index] = sortrows([wordlengths' weights'],[1 -2]); % index is wordsFromBIndex
last2letterword = find(B(:,1)>2,1)-1;
%words2 = words(index(1:last2letterword));
w2l = index(1:last2letterword)'; % should be row vector for for
isUnplayed = true(size(words));
hopeless = false(size(words));
[C,alphaix]=sortrows(cell2mat(words(w2l)')); % so char(C) = char(words{w2l(alphaix)}) % alphaix is WfromC
wFromC=w2l(alphaix); % gives index in original words
points = 0;
c=1;
r=1;
L = 2; % dim of sq
while r+L-1 <= n,
[sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C, alphaix);
if ~sq,
break; % no more 2x2s
end
board(r+(0:L-1),c+(0:L-1)) = sq;
c=c+L+1;
if c > n-(L-1),
r =r+L+1;
c=1;
end
end
points = points + sum(weights(~isUnplayed));
result = total-points; % so far...
% eliminate words that have already been played
[B,index] = sortrows([wordlengths(isUnplayed)' weights(isUnplayed)'],[1 -2]);
words = words(isUnplayed);
nwords=numel(words);
isUnplayed = true(size(nwords));
k=1;
% play remaining unused 2 letter words here?
% index of last word to play in current row
stop_index = min(nwords, n*k-c+1); % check that we haven't run out of words
start_index = 1;
while (r+B(stop_index,1)-1) <= n, % if the new row fits
words_left = stop_index - start_index + 1; % num words to play in this row
current_row_points = sum(B(start_index:stop_index,2)) - penalty*B(stop_index-1,1); % use length of next to last word to get number of penalty cols
if current_row_points > 0,
for cc = c:min(n,words_left+c-1),
%fprintf('\n* r=%2i,c=%2i\n',r,c);
wi = start_index-c+cc; % word index
%board(r:(r+B(wi,1)-1),cc)'
%char(words{index(wi)})
board(r:(r+B(wi,1)-1),cc) = words{index(wi)};
end
% the row is unplayed I think it will simply be blank
end
c=1;
points = points + current_row_points;
r=r+B(stop_index,1)+1; % increment row location
k=k+1; % increment row number
start_index=stop_index+1;
stop_index = min(nwords, stop_index+n);
end
result = total - points;
end
% should mark words that didn't work out to avoid retrying them
% hopeless marks words that won't work i positions 1 or 2 (1 across and 1
% down). word 1 is equivalent to word 2, and word 3 is equivalent to word 4
% however, words 1 and 2 are not equivalent to words 3 and 4
function [sq, isUnplayed, hopeless] = press2(words, isUnplayed, hopeless, w2l, C, alphaix)
sq = zeros(2);
% try excluding words with letter frequencies of 1
% ordering words by first and second letter would help
for ii = w2l, % w2l must be a row vector here
%fprintf('ii = %i\n',ii);
if ~isUnplayed(ii) || hopeless(ii),
continue;
end
sq(1,:) = words{ii};
isUnplayed(ii) = false;
% fprintf('letter = %s\n',char(sq(1,:)));
% char(words{w2l(alphaix(a1:a2))})
% only iterate over reasonable letters
a1=find(C(:,1) == sq(1,1),1); a2=find(C(:,1) == sq(1,1),1,'last');
for jj = w2l(sort(alphaix(a1:a2))),
%fprintf(' jj = %i\n',ii,jj);
%assert(sq(1,1) == words{jj}(1));
if isUnplayed(jj) && ~hopeless(jj), % eval order? also checks could be elim
sq(2,1) = words{jj}(2);
isUnplayed(jj) = false;
b1=find(C(:,1) == sq(1,2),1); b2=find(C(:,1) == sq(1,2),1,'last');
c1=find(C(:,1) == sq(2,1),1); c2=find(C(:,1) == sq(2,1),1,'last');
for kk = w2l(sort(alphaix(b1:b2))),
%assert(sq(1,2) == words{kk}(1));
if isUnplayed(kk),
sq(2,2) = words{kk}(2);
isUnplayed(kk) = false;
for ll = w2l(sort(alphaix(c1:c2))),
if isUnplayed(ll) && all(sq(2,:) == words{ll}),
isUnplayed(ll) = false;
%fprintf('1 %s\n2 %s\n3 %s\n4 %s\n\n',char(words{ii}),char(words{jj}),char(words{kk}),char(words{ll}));
%disp(char(sq))
return; % press completed!
end
end
isUnplayed(kk) = true;
end
end
isUnplayed(jj) = true;
end
end
isUnplayed(ii) = true;
% should mark words that didn't work out to avoid retrying them
hopeless(ii) = true; % hopeless in positions 1 or 2
%fprintf('%s (%i) is hopeless\n',char(words{ii}),ii);
end
sq=zeros(2); % no result
end
function [board, result] = solver_columns3(words, weights, n, penalty)
total = sum(weights);
board = zeros(n);
for k = 1:length(words),
wordlengths(k)=length(words{k});
end
nwords= numel(words);
[B,index] = sortrows([wordlengths' weights'],[1 -2]);
points = 0;
k=1;
c=1;
current_stop_index = min(nwords, n*k); % check that we haven't run out of words
while (c+B(current_stop_index,1)-1) <= n,
current_col_points = sum(B(((k-1)*n)+1:current_stop_index,2)) - penalty*B(k*n-1,1); % use length of next to last word to get number of penalty cols
if current_col_points > 0,
r=1;
words_left = current_stop_index - n*(k-1);
for r = 1:min(n,words_left),
board(c:(c+B(r+(k-1)*n,1)-1),r) = words{index(r+(k-1)*n)};
end
end
points = points + current_col_points;
c=c+B(current_stop_index,1)+1;
k=k+1;
current_stop_index = min(nwords, n*k);
end
result = total - points;
end
function [board, result] = solver_columns(words, weights, n, penalty)
% to do:
% use dead space at the bottom of a column more effectively
% use better value for wpl
% consider penalty
total = sum(weights);
board = zeros(n);
for k = 1:length(words),
wordlengths(k)=length(words{k});
end
wpl = weights./(wordlengths); % weight per letter, maybe should also consider blanks; +1 for blank at end of word acutally lowered result?
[s_wpl,ix] = sort(wpl,'descend'); % so now s_wpl = wpl(ix) % possible sign tricks?
points = 0;
w = 1;
for col = 1:2:min(n,length(words)),
r = 1;
while r + wordlengths(ix(w))-1 <= n
board(r:(r-1+wordlengths(ix(w))),col) = words{ix(w)};
points = points + weights(ix(w));
r = r + 1 + wordlengths(ix(w));
w = w + 1;
end
end
result = total - points;
end
|
