function board = solver(words, weights, N, penalty)
%words = words(weights>0);
%weights = weights(weights>0);
nws = numel(words);
[weights,idx] = sort(weights,'descend');
words = words(idx);
lengths = cellfun('length',words);
[oli,idx2] = sort(weights./lengths,'descend');
words2 = words(idx2);
lengths2 = cellfun('length',words2);
weights2 = weights(idx2)
if min(lengths) == N
[BOARD{7}, SCORE(7)] = solver_nick_1(words2, weights2, N, penalty, lengths2, nws);
if SCORE(7)==0
board=BOARD{7};
return;
end
end
[BOARD{1}, SCORE(1)] = solver_nick_2 (words2, weights2, N, penalty, lengths2, nws);
[BOARD{2}, SCORE(2)] = solver_nick_3 (words2, weights2, N, penalty, lengths2, nws);
[BOARD{3}, SCORE(3)] = solver_nick_4 (words2, weights2, N, penalty, lengths2, nws);
[BOARD{4}, SCORE(4)] = solver_james1 (words2, weights2, N, penalty, lengths2, nws);
[BOARD{5}, SCORE(5)] = solver_james2 (words2, weights2, N, penalty, lengths2, nws);
[BOARD{6}, SCORE(6)] = solver_victoria(words2, weights2, N, penalty, lengths2, nws);
[~, board_idx] = min(SCORE);
board = BOARD{board_idx};
end
function [board, result] = solver_james1(words, weights, n, penalty, wordlengths, nwords)
board = zeros(n);
total = sum(weights);
[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(1,nwords);
hopeless = false(1,nwords);
[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));
% eliminate words that have already been played
[B,index] = sortrows([wordlengths(isUnplayed)' weights(isUnplayed)'],[1 -2]);
words = words(isUnplayed);
nwords = numel(words);
isUnplayed2 = true(1,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)};
isUnplayed2(index(wi)) = false;
% figure(2), imagesc(board)
% disp('')
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;
wordlengths2 = wordlengths(isUnplayed);
wordlengths3 = wordlengths2(isUnplayed2);
weights2 = weights(isUnplayed);
weights3 = weights2(isUnplayed2);
words = words(isUnplayed2);
[~,idx_sort] = sort(wordlengths3 - weights3/max(weights3) );
tres_ceros = board(3:end,1)==0 & board(2:end-1,1)==0 & board(1:end-2,1)==0;
r_ini = find(tres_ceros) + 1;
if board(n,1)==0 && board(n-1,1)==0
r_ini = [r_ini; n];
end
k = 1;
for p = 1:length(r_ini)
r = r_ini(p);
if board(r-1,1)==0
c = 1;
while c < n && board(r-1,c)==0
word_n = words{idx_sort(k)};
c2 = c + numel(word_n);
if c2-1 <= n && board(r-1,c2-1)==0
board(r,c:c2-1) = word_n;
k = k + 1;
result = result - weights3(idx_sort(k));
end
c = c2 + 1;
end
end
end
end
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
if ~isempty(w2l)
C1 = C(:,1);
end
for ii = w2l, % w2l must be a row vector here
if ~isUnplayed(ii) || hopeless(ii),
continue;
end
sq(1,:) = words{ii};
isUnplayed(ii) = false;
% only iterate over reasonable letters
conda = C1 == sq(1,1);
a1 = find(conda,1);
a2 = find(conda,1,'last');
w21jj = w2l(sort(alphaix(a1:a2)));
condb = C1 == sq(1,2);
b1=find(condb,1);
b2=find(condb,1,'last');
w21kk = w2l(sort(alphaix(b1:b2)));
for jj = w21jj
% eval order? also checks could be elim
if isUnplayed(jj) && ~hopeless(jj)
sq(2,1) = words{jj}(2);
isUnplayed(jj) = false;
% condb = C1 == sq(1,2);
condc = C1 == sq(2,1);
% b1=find(condb,1);
% b2=find(condb,1,'last');
c1=find(condc,1);
c2=find(condc,1,'last');
w21ll = w2l(sort(alphaix(c1:c2)));
for kk = w21kk
if isUnplayed(kk)
sq(2,2) = words{kk}(2);
isUnplayed(kk) = false;
for ll = w21ll
if isUnplayed(ll) && all(sq(2,:) == words{ll})
isUnplayed(ll) = false;
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
end
sq = zeros(2);
end
function [board, result] = solver_james2(words, weights, n, penalty, wordlengths, nwords)
total = sum(weights);
board = zeros(n);
[B,index] = sortrows([wordlengths' weights'],[1 -2]);
points = 0;
k=1;
c=1;
isUnplayed = true(nwords,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,
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)};
isUnplayed(index(r+(k-1)*n)) = false;
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;
% figure(3), imagesc(board)
wordlengths2 = wordlengths(isUnplayed);
weights2 = weights(isUnplayed);
words = words(isUnplayed);
[~,idx_sort] = sort(wordlengths2 - weights2/max(weights2) );
tres_ceros = board(3:end,1)==0 & board(2:end-1,2)==0 & board(1:end-2,1)==0;
r_ini = find(tres_ceros) + 1;
if board(n,1)==0 && board(n-1,1)==0
r_ini = [r_ini; n];
end
k = 1;
for p = 1:length(r_ini)
r = r_ini(p);
if board(r-1,1)==0
c = 1;
while c < n && board(r-1,c)==0
word_n = words{idx_sort(k)};
c2 = c + numel(word_n);
if c2-1 <= n && board(r-1,c2-1)==0
board(r,c:c2-1) = word_n;
k = k + 1;
result = result - weights2(idx_sort(k));
end
c = c2 + 1;
% figure(3), imagesc(board)
end
end
end
end
function [board, score] = solver_victoria(words, weights, N, penalty, L, QWords)
% Victoria's solver
score = 0;
PThresh = 0.19;
board = zeros(N);
WordsInUse = false(1,QWords);
SpecificWeights = weights./L;
[~,IndWS] = sort(SpecificWeights,'descend');
SpecLCum = cumsum(L(IndWS) + 1);
MaxQ = numel(find(SpecLCum <= N.*(N+1)));
GoodWeight = sum(weights(IndWS(1:MaxQ)));
BadGoodCoef = N.*penalty./GoodWeight;
P = BadGoodCoef > PThresh;
if P
slots = ones(1,ceil(N/2));
MaxQ = numel(find(SpecLCum <= (N+1).^2/2));
else
slots = ones(1,N);
end
LoL = min(L(IndWS(1:MaxQ)));
HiL = max(L(IndWS(1:MaxQ)));
IndL = zeros(MaxQ,1);
l = 1;
for n = HiL:-1:LoL
idx_long = find(L(IndWS(1:MaxQ))==n);
l2 = l + numel(idx_long);
IndL(l:l2-1) = idx_long;
l = l2;
end
IndWS(1:MaxQ) = IndWS(IndL);
n = 1;
while min(slots) < N && n <= QWords
Space = N - L(IndWS(n)) + 1 - slots;
SlotIndex = find(~Space,1);
if isempty(SlotIndex)
[Espacio,SlotIndex] = max(Space);
else
Espacio = 1;
end
if Espacio > 0
board((1+P)*SlotIndex-P,slots(SlotIndex):slots(SlotIndex) + L(IndWS(n)) - 1) = words{IndWS(n)};
slots(SlotIndex) = slots(SlotIndex) + L(IndWS(n)) + 1;
score = score + weights(IndWS(n));
WordsInUse(IndWS(n)) = true;
end
n=n+1;
end
if P
for n = 1:QWords
CurInd = IndWS(n);
CurL = L(CurInd);
word_c = words{CurInd};
if ~WordsInUse(CurInd) && (CurL/2 ~= round(CurL/2))
[I,J] = find(board(1:N - CurL + 1,:) == word_c(1));
if ~isempty(I)
k = 1;
while ~WordsInUse(CurInd) && (k <= numel(I))
if all(word_c(1:2:end) == board(I(k):2:I(k) + CurL - 1,J(k))')
board(I(k):I(k) + CurL - 1,J(k)) = word_c';
score = score + weights(IndWS(n));
WordsInUse(IndWS(n)) = true;
end
k = k + 1;
end
end
end
end
end
% figure(4), imagesc(board)
%--
L2 = L(~WordsInUse);
weights2 = weights(~WordsInUse);
words = words(~WordsInUse);
[~,idx_sort] = sort(L2 - weights2/max(weights2) );
tres_ceros = board(1,3:end)==0 & board(1,2:end-1)==0 & board(1,1:end-2)==0;
r_ini = find(tres_ceros) + 1;
if board(1,N)==0 && board(1,N-1)==0
r_ini = [r_ini; N];
end
k = 1;
for p = 1:length(r_ini)
r = r_ini(p);
if board(1,r-1)==0
c = 1;
while c < N && board(c,r-1)==0
word_n = words{idx_sort(k)};
c2 = c + numel(word_n);
if c2-1 <= N && all(board(c:c2-1,r)==0)
board(c:c2-1,r) = word_n;
k = k + 1;
score = score + weights2(idx_sort(k));
end
c = c2 + 1;
% figure(4), imagesc(board)
end
end
end
%--
pboard = [board;zeros(1,N)];
cs = cumsum(pboard(:)~=0);
ntrans = sum(diff(cs(pboard==0))>1) + 1;
score = sum(weights(:)) - score + penalty*ntrans;
end
function [board0, s0] = solver_nick_1(words, weights, N, penalty, wlen, nword)
board = zeros(N);
% Nicks's solver
maxlen = max(wlen);
pwords = cellfun(@(a)[a 0 -1*ones(1,maxlen-numel(a))],words,'UniformOutput',false);
wmat = cat(1,pwords{:});
wmat = wmat(:,1:end-1);
m = cell(N);
for n = 1:maxlen
m{n,1} = double(sparse(bsxfun(@eq,wmat(:,n),wmat(:,1)')));
m{3,n} = double(sparse(bsxfun(@eq,wmat(:,3),wmat(:,n)')));
end
rwords = zeros(1,N);
cwords = zeros(1,N);
n = 1;
pm = ones(nword);
m13 = m{n,1}*m{3,n};
ppm = pm & m13;
while (n < N) && any(ppm(:))
pm = ppm;
n = n + 2;
if (n < N)
m13 = m{n,1}*m{3,n};
ppm = pm & m13;
end
end
icross = n;
open = true(1,nword);
[i1,i3] = find(pm);
i1 = i1(1);
i3 = i3(1);
open(i1) = false;
open(i3) = false;
board(1,1:wlen(i1)) = words{i1};
board(3,1:wlen(i3)) = words{i3};
rwords(1) = i1;
rwords(3) = i3;
for n = 1:2:icross
iword = find((m{n,1}(i1,:).*m{3,n}(:,i3)') & open);
if ~isempty(iword)
iword = iword(1);
cwords(n) = iword;
board(1:wlen(iword),n) = words{iword}';
open(iword) = false;
end
end
% fill in remaining crosses, if possible.
fcwords = cwords(cwords>0);
height = max(wlen(fcwords));
open = open';
votes = zeros(N);
for n = 5:height
cols = find(board(n,:)~=0);
matches = bsxfun(@eq,wmat(:,cols),board(n,cols))|(wmat(:,cols)<0);
[~,bm] = max(open.*sum(matches,2));
votes(n,cols) = 2*matches(bm,:)-1;
end;
bad = sum(votes)<0;
badword = cwords(bad(1:icross));
open(nonzeros(badword)) = true;
board([2 4:end],bad) = 0;
cwords(bad) = 0;
n = 5;
while (n <= height)
cols = find(board(n,:)~=0);
row = find(open & all(bsxfun(@eq,wmat(:,cols),board(n,cols))|(wmat(:,cols)<0),2),1);
if ~isempty(row)
open(row) = false;
board(n,1:wlen(row)) = words{row};
rwords(n) = row;
n = n+2;
else
n = n+1;
end;
end;
s0 = sum(weights(open));
board0 = board;
% now try full fill
openr = rwords==0;
openc = cwords==0;
goodc = ~openc;
votes = zeros(N);
for c = find(openc)
rows = find(board(:,c)~=0);
matches = bsxfun(@eq,wmat(:,rows),board(rows,c)')|(wmat(:,rows)<0);
[~,bm] = max(open.*sum(matches,2));
votes(rows,c) = 2*matches(bm,:)-1;
end
bad = sum(votes,2) < -sum(goodc);
badwords = rwords(bad);
open(nonzeros(badwords)) = true;
board(openr,bad) = 0;
for c = find(openc)
rows = find(board(:,c)~=0);
matches = bsxfun(@eq,wmat(:,rows),board(rows,c)')|(wmat(:,rows)<0);
wi = find(open & all(matches,2),1);
if ~isempty(wi)
open(wi) = false;
board(1:wlen(wi),c) = words{wi};
cwords(c) = wi;
end
end
openr = rwords==0;
openc = cwords==0;
goodr = ~openr;
votes = zeros(N);
for r = find(openr)
cols = find(board(r,:)~=0);
matches = bsxfun(@eq,wmat(:,cols),board(r,cols))|(wmat(:,cols)<0);
[~,bm] = max(open.*sum(matches,2));
votes(r,cols) = 2*matches(bm,:)-1;
end;
bad = sum(votes,2)<-sum(goodr);
badwords = cwords(bad);
open(nonzeros(badwords)) = true;
board(bad,openc) = 0;
for r = find(openr)
cols = find(board(r,:)~=0);
matches = bsxfun(@eq,wmat(:,cols),board(r,cols))|(wmat(:,cols)<0);
wi = find(open & all(matches,2),1);
if ~isempty(wi)
open(wi) = false;
board(r,1:wlen(wi)) = words{wi};
rwords(r) = wi;
end;
end;
board(board==0) = 1;
s1 = sum(weights(open)) + penalty*(sum(rwords==0) + sum(cwords==0));
if s1 < s0
board0 = board;
s0 = s1;
end
end
function [board , s ] = solver_nick_2(words, weights, N, penalty, wlen, nws)
SW = sum(weights);
board = zeros(N);
w = 0;
open = true(1,nws);
for n = [1:2:N,2:2:N]
l = 0;
k = find(open & (wlen<=N-l),1);
while ~isempty(k)
open(k) = false;
word = words{k};
L_word = numel(word);
board(n,l+1:l+L_word) = word;
l = l + L_word + 1;
w = w + weights(k);
k = find(open & (wlen <= N-l),1);
end
end
pboard = [board;zeros(1,N)];
cs = cumsum(pboard(:)~=0);
ntrans = sum(diff(cs(pboard==0))>1);
w = w - penalty*ntrans;
s = SW - w;
end
function [board2, s] = solver_nick_3(words, weights, N, penalty, wlen, nws)
SW = sum(weights);
board2 = zeros(N);
w2 = 0;
open = true(1,nws);
wlen_m_N = wlen <= N;
for n = 1:2:N
l = 0;
k = find(open & wlen_m_N,1);
while ~isempty(k)
open(k) = false;
word = words{k};
L_word = numel(word);
board2(n,l+1:l+L_word) = word;
l = l+L_word+1;
w2 = w2 + weights(k);
k = find(open & (wlen <= N-l),1);
end
end
s = SW - w2;
end
function [board2, s] = solver_nick_4(words, weights, N, penalty, wlen, nword)
SW = sum(weights);
board2 = zeros(N);
w2 = 0;
open = true(1,numel(words));
filled = zeros(1,N);
filled(2:2:end) = 1;
brk = false;
while (filled(1)<N)
wlen2 = wlen.*open;
wlen2(~open) = 1;
nlen = accumarray(wlen2(:),ones(nword,1));
k = find(open & (wlen <= N-filled(1) -1) & (nlen(wlen)' >=N),1);
if isempty(k)
brk = true;
break
end
targ = wlen(k);
board2(1,filled(1)+1:filled(1)+targ) = words{k};
open(k) = false;
w2 = w2 + weights(k);
wlen_eq_targ = wlen==targ;
for n = 2:N
k = find(open & wlen_eq_targ,1); % DFM SPEED
board2(n,filled(n)+1:filled(n)+targ) = words{k};
open(k) = false;
w2 = w2 + weights(k);
end
filled = filled + targ + 1;
end
if brk
% try two half-sets
brk = false;
while filled(1) < N
wlen2 = wlen.*open;
wlen2(~open) = 1;
nlen = accumarray(wlen2(:),ones(nword,1));
ldir = 2*(filled(1) > filled(2)) - 1;
nlen(1) = 0;
k = find(open & (wlen <= N-filled(1) - 1) & (nlen(wlen)'>=ceil(N/2)) & (nlen(wlen+ldir)'>=ceil(N/2)),1);
if isempty(k)
brk = true;
break
end
targ = wlen(k);
board2(1,filled(1)+1:filled(1)+targ) = words{k};
open(k) = false;
w2 = w2 + weights(k);
for n = 2:N
idir = ldir*(mod(n,2)==0);
k = find(open&(wlen==targ+idir),1);
board2(n,filled(n)+1:filled(n)+targ+idir) = words{k};
open(k) = false;
w2 = w2 + weights(k);
end;
filled = filled + targ + 1;
end
end
if brk
% try two half-sets off by 2
brk = false;
while filled(1) < N
wlen2 = wlen.*open;
wlen2(~open) = 1;
nlen = accumarray(wlen2(:),ones(nword,1));
nlen(1) = 0;
nlen(end+2) = 0;
k0 = find(open&(wlen<=N-filled(1)-2) & (nlen(wlen)'>=ceil(N/2)) & (nlen(wlen+2)'>=ceil(N/2)),1);
if isempty(k0)
brk = true;
break
end
if filled(1)>filled(2)
targ = ones(1,N)*wlen(k0);
targ(2:2:end) = wlen(k0)+2;
else
targ = ones(1,N)*(wlen(k0)+2);
targ(2:2:end) = wlen(k0);
end
for n = 1:N
k = find(open&(wlen==targ(n)),1);
board2(n,filled(n)+1:filled(n)+targ(n)) = words{k};
open(k) = false;
w2 = w2 + weights(k);
end;
filled = filled + targ + 1;
end
end
if brk && any(board2(:))
% finish filling board normally
for n = 1:N
k = find(open & (wlen<=N-filled(n)),1);
while ~isempty(k)
open(k) = false;
word = words{k};
board2(n,filled(n)+1:filled(n)+numel(word)) = word;
filled(n) = filled(n) + numel(word) + 1;
w2 = w2 + weights(k);
k = find(open & (wlen<=N-filled(n)),1);
end
end
end
pboard = [board2; zeros(1,N)];
cs = cumsum(pboard(:)~=0);
ntrans = sum(diff(cs(pboard==0))>1);
w2 = w2 - penalty*ntrans;
s = SW - w2;
end
|
