function board = solver(words, weights, n, penalty)
% Nick & Alfanso solvers
[board1, score1] = solver_alfonso(words, weights, n, penalty);
[board2, score2] = solver_nick(words, weights, n, penalty);
if score1<score2
board=board1;
else
board=board2;
end
end
function [board, score] = solver_nick(words, weights, n, penalty)
nword = numel(words);
wlen = cellfun(@numel,words);
if (min(wlen) == n)
maxlen = max(wlen);
pwords = cellfun(@(a)[a 0 repmat(-1,1,maxlen-numel(a))],words,'UniformOutput',false);
wmat = cat(1,pwords{:});
wmat = wmat(:,1:end-1);
m = cell(n);
for i = 1:maxlen
m{i,1} = double(sparse(bsxfun(@eq,wmat(:,i),wmat(:,1)')));
m{3,i} = double(sparse(bsxfun(@eq,wmat(:,3),wmat(:,i)')));
end;
rwords = zeros(1,n);
cwords = zeros(1,n);
i = 1;
pm = ones(nword);
ppm = pm&(m{i,1}*m{3,i});
while (i < n) && any(ppm(:))
pm = ppm;
i = i+2;
if (i < n)
ppm = pm&(m{i,1}*m{3,i});
end;
end;
icross = i;
board = zeros(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 i = 1:2:icross
iword = find((m{i,1}(i1,:).*m{3,i}(:,i3)')&open);
if ~isempty(iword)
iword = iword(1);
cwords(i) = iword;
board(1:wlen(iword),i) = 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 i = 5:height
cols = find(board(i,:)~=0);
matches = bsxfun(@eq,wmat(:,cols),board(i,cols))|(wmat(:,cols)<0);
[~,bm] = max(open.*sum(matches,2));
votes(i,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;
i = 5;
while (i <= height)
cols = find(board(i,:)~=0);
row = find(open&all(bsxfun(@eq,wmat(:,cols),board(i,cols))|(wmat(:,cols)<0),2),1);
if ~isempty(row)
open(row) = false;
board(i,1:wlen(row)) = words{row};
rwords(i) = row;
i = i+2;
else
i = i+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;
else
board0 = zeros(n);
s0 = sum(weights);
end;
board = zeros(n);
wcost = weights./(wlen+1);
[~,r] = sort(-wcost);
wlen = wlen(r);
words = words(r);
open = true(1,numel(words));
w = 0;
for i = [1:2:n,2:2:n]
j = 0;
k = find(open&(wlen<=n-j),1);
while ~isempty(k)
open(k) = false;
word = words{k};
board(i,j+1:j+numel(word)) = word;
j = j+numel(word)+1;
w = w+weights(r(k));
k = find(open&(wlen<=n-j),1);
end;
end;
board2 = zeros(n);
w2 = 0;
open = true(1,numel(words));
for i = 1:2:n
j = 0;
k = find(open&(wlen<=n-j),1);
while ~isempty(k)
open(k) = false;
word = words{k};
board2(i,j+1:j+numel(word)) = word;
j = j+numel(word)+1;
w2 = w2+weights(r(k));
k = find(open&(wlen<=n-j),1);
end;
end;
pboard = [board;zeros(1,n)];
cs = cumsum(pboard(:)~=0);
ntrans = sum(diff(cs(pboard==0))>1);
if penalty*ntrans>w-w2
board = board2;
s = sum(weights)-w2;
else
s = sum(weights)-w+penalty*ntrans;
end;
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(r(k));
for i = 2:n
k = find(open&(wlen==targ),1);
board2(i,filled(i)+1:filled(i)+targ) = words{k};
open(k) = false;
w2 = w2+weights(r(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(r(k));
for i = 2:n
idir = ldir*(mod(i,2)==0);
k = find(open&(wlen==targ+idir),1);
board2(i,filled(i)+1:filled(i)+targ+idir) = words{k};
open(k) = false;
w2 = w2+weights(r(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 = repmat(wlen(k0),1,n);
targ(2:2:end) = wlen(k0)+2;
else
targ = repmat(wlen(k0)+2,1,n);
targ(2:2:end) = wlen(k0);
end;
for i = 1:n
k = find(open&(wlen==targ(i)),1);
board2(i,filled(i)+1:filled(i)+targ(i)) = words{k};
open(k) = false;
w2 = w2+weights(r(k));
end;
filled = filled+targ+1;
end;
end;
if (brk&&any(board2(:)))
% finish filling board normally
for i = 1:n
k = find(open&(wlen<=n-filled(i)),1);
while ~isempty(k)
open(k) = false;
word = words{k};
board2(i,filled(i)+1:filled(i)+numel(word)) = word;
filled(i) = filled(i)+numel(word)+1;
w2 = w2+weights(r(k));
k = find(open&(wlen<=n-filled(i)),1);
end;
end;
end;
pboard = [board2;zeros(1,n)];
cs = cumsum(pboard(:)~=0);
ntrans = sum(diff(cs(pboard==0))>1);
if sum(weights)+penalty*ntrans-w2<s
board = board2;
s = sum(weights)+penalty*ntrans-w2;
end;
if (s0 < s)
board = board0;
s = s0;
end;
score = s;
end
function [board,score] = solver_alfonso(words, weights, n, penalty)
board = zeros(n);
nwords=numel(words);
wordlength=zeros(1,nwords);
for nword=1:nwords, wordlength(nword)=numel(words{nword}); end
[wordlength,idxwords]=sort(wordlength);
idxpart=[0,find(diff(wordlength)),nwords];
nwords_=diff(idxpart); % number of words for each wordlength
lwords_=wordlength(idxpart(2:end)); % list of wordlengths
n_=numel(lwords_);
words_=cell(1,n_);
weights_=words_;
weights0_=words_;
for nword_=1:n_,
idx1=idxwords(idxpart(nword_)+1:idxpart(nword_+1));
[w,idx2]=sort(weights(idx1),2,'descend');
weights0_{nword_}=w; % cumulative gains
words_{nword_}=idx1(idx2); % sorted words
weights_{nword_}=cumsum(w); % cumulative gains
end
borders=[1,1,n,n];
while size(borders,1)>0,
border=borders(1,:);
ntwn=sum(prod(border(:,3:4),2),1);
Twn=zeros(1,ntwn);tn=0;twn=0;
for nword_=find(nwords_>0),
t=nwords_(nword_);
Twn(tn+(1:t)*lwords_(nword_))=twn+weights0_{nword_};
tn=tn+t*lwords_(nword_);
if tn>=ntwn,break;end
end
Twn=cumsum(Twn);
Cmax=-inf;
for orientation=1:2,
r=border(3);
c=border(4);
rc=r*c;
for nword_=find(nwords_>0&lwords_<=c),
m=min(r,nwords_(nword_));
C=weights_{nword_}(m) - penalty*lwords_(nword_) + E(rc-min(r,m+1)*(lwords_(nword_)+1),Twn);
if C(1)>0&&sum(C)>Cmax,
Imax=[orientation,1,nword_,m];
Cmax=sum(C);
end
m=min(ceil(r/2),nwords_(nword_));
C=weights_{nword_}(m) + E(rc-min(r,2*m)*(lwords_(nword_)+1),Twn);
if C(1)>0&&sum(C)>Cmax,
Imax=[orientation,2,nword_,m];
Cmax=sum(C);
end
end
border=border([2,1,4,3]);
end
if Cmax>0
if Imax(1)==2, board=board'; borders=borders(:,[2,1,4,3]); end
border=borders(1,:);
switch(Imax(2))
case 1
nword_=Imax(3);
m=Imax(4);
for nw=1:m,
board(border(1)+nw-1,border(2)+(0:lwords_(nword_)-1))=words{words_{nword_}(nw)};
end
words_{nword_}=words_{nword_}(m+1:end);
weights0_{nword_}=weights0_{nword_}(m+1:end);
weights_{nword_}=weights_{nword_}(m+1:end)-weights_{nword_}(m);
nwords_(nword_)=nwords_(nword_)-m;
nwords=nwords-m;
if m<border(3)-1,
borders(1,:)=border+[0,lwords_(nword_)+1,m-border(3),-(lwords_(nword_)+1)];
borders=cat(1,border+[m+1,0,-(m+1),0],borders);
else
borders(1,:)=border+[0,lwords_(nword_)+1,0,-(lwords_(nword_)+1)];
end
case 2
nword_=Imax(3);
m=Imax(4);
for nw=1:m,
board(border(1)+2*nw-2,border(2)+(0:lwords_(nword_)-1))=words{words_{nword_}(nw)};
end
words_{nword_}=words_{nword_}(m+1:end);
weights0_{nword_}=weights0_{nword_}(m+1:end);
weights_{nword_}=weights_{nword_}(m+1:end)-weights_{nword_}(m);
nwords_(nword_)=nwords_(nword_)-m;
nwords=nwords-m;
if 2*m-1<border(3)-1,
borders(1,:)=border+[0,lwords_(nword_)+1,2*m-1-border(3),-(lwords_(nword_)+1)];
borders=cat(1,border+[2*m,0,-2*m,0],borders);
else
borders(1,:)=border+[0,lwords_(nword_)+1,0,-(lwords_(nword_)+1)];
end
case 3
end
if Imax(1)==2, board=board'; borders=borders(:,[2,1,4,3]); end
borders(any(borders(:,3:4)<=0,2),:)=[];
else
borders(1,:)=[];
end
end
[remainInDictionary, ~, bogus] = ...
runSolution(board, n, words, weights);
score = scoresolution(remainInDictionary, bogus, penalty);
end
function c=E(S,Twn)
if S>0
c=[0,Twn(ceil(S/2))];
else
c=[0,0];
end
end
function [remainInDictionary, inPuzzle, bogus] = runSolution(board, boardSize, dictionary, weights)
%runSolution: parses the solution returned by the solver to determine the
% words it contains. Three structures are returned:
%
% * remainInDictionary.words: words that remain in the dictionary
% * remainInDictionary.points: points for each unused dictionary word
% * remainInDictionary.hash: hash value used internally for searching
%
% * inPuzzle.words: valid dictionary words used in the solution
% * inPuzzle.points: points for each valid word
%
% * bogus.words: words in the solution that aren't in the dictionary
% * bogus.locations: linear indices of all letters in each word
% Initialize outputs
remainInDictionary = struct('words',{dictionary}, 'weights',{weights}, ...
'hash', {cellfun(@applyHash, dictionary)});
inPuzzle = struct('words',{{}}, 'weights',{[]});
bogus = struct('words',{{}}, 'locations',{{}});
% Find words going across and down. dir = 1 for across, 2 for down.
for dir = 1:2
for n = 1:boardSize
% Get the current row / column to process
if dir == 1
curLine = board(n,:);
else
curLine = board(:,n).';
end
% Split current line of the board by locations of zeros
zeroLoc = find(curLine == 0);
idx1 = [1, zeroLoc+1];
idx2 = [zeroLoc-1, boardSize];
% Process the words on the current line
for m = 1:numel(idx1)
% Get the linear indices that make up the current word
idxRange = idx1(m):idx2(m);
idxConst = repmat(n, 1, numel(idxRange));
if dir == 1
linearWordIdx = sub2ind([boardSize, boardSize], idxConst, idxRange);
else
linearWordIdx = sub2ind([boardSize, boardSize], idxRange, idxConst);
end
% Current word to process
curWord = board(linearWordIdx);
if isscalar(curWord)
% Get the indices of the adjacent squares - above,
% below, left, and right.
[r, c] = ind2sub([boardSize, boardSize], linearWordIdx);
rows = [r-1, r+1, r, r];
cols = [c, c, c-1, c+1];
outOfRange = (rows < 1) | (rows > boardSize) | ...
(cols < 1) | (cols > boardSize);
rows(outOfRange) = [];
cols(outOfRange) = [];
adjacentIdx = sub2ind([boardSize, boardSize], rows, cols);
% Treat a lone floating letter as invalid both across
% and down. We assume that the dictionary never
% contains any single letter words.
if all(board(adjacentIdx) == 0)
bogus = addBogusWord(bogus, curWord, linearWordIdx);
end
elseif ~isempty(curWord) % Skip empty words - nothing to process
% Determine if the word is in the dictionary
dictionaryLoc = findWord(curWord, remainInDictionary.words, ...
remainInDictionary.hash);
if isempty(dictionaryLoc)
% Bogus word - add to bogus word list
bogus = addBogusWord(bogus, curWord, linearWordIdx);
else
% Legit word - move to inPuzzle list
[remainInDictionary, inPuzzle] = moveValidWord( ...
remainInDictionary, inPuzzle, dictionaryLoc);
end
end
end
end
end
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 idx = findWord(word, dictionary, dictionaryHash)
% findWord: Find word in dictionary using hash table. An empty matrix is
% return if the word does not exist in the dictionary
% Initialize output - assume word won't be found
idx = [];
% Find possible matches
possibleIdx = find(dictionaryHash == applyHash(word));
% Check all possible matches. If none is an actual match, we'll return empty
for n = 1:numel(possibleIdx)
if isequal(dictionary{possibleIdx(n)},word)
idx = possibleIdx(n);
return;
end
end
end
function bogus = addBogusWord(bogus, newWord, wordLoc)
%addBogusWord: add a word to the list of bogus words
bogus.words{end+1} = newWord;
bogus.locations{end+1} = wordLoc;
end
function [inDictionary, inPuzzle] = moveValidWord(inDictionary, inPuzzle, dictionaryLoc)
%moveValidWord: moves a word from the list of unused dictionary words to
% the list of words used in the puzzle solution
% Add word to list of words in the puzzle solution
inPuzzle.words{end+1} = inDictionary.words{dictionaryLoc};
inPuzzle.weights(end+1) = inDictionary.weights(dictionaryLoc);
% Remove word for list of unused dictionary words
inDictionary.words(dictionaryLoc) = [];
inDictionary.weights(dictionaryLoc) = [];
inDictionary.hash(dictionaryLoc) = [];
end
function score = scoresolution(remainInDictionary, bogus, penalty)
% SCORESOLUTION Calculates the score for the solution.
score = sum(remainInDictionary.weights) + penalty * numel(bogus.words);
end
% Amitabh Verma
|
