function board = solver(words, weights, N, penalty)
nws = numel(words);
lengths = zeros(1,nws);
for nw=1:nws,lengths(nw)=numel(words{nw});end
[BOARD{1}, SCORE(1)] = solver_victoria(words, weights, N, penalty, lengths, nws);
[BOARD{2}, SCORE(2)] = solver_nick(words, weights, N, penalty, lengths, nws);
[BOARD{3}, SCORE(3)] = solver_anieto(words, weights, N, penalty, lengths, nws);
[BOARD{4}, SCORE(4)] = solver_fel(words, weights, N, penalty, lengths, nws);
[~, board_idx] = min(SCORE);
board = BOARD{board_idx};
end
function [board, score] = solver_victoria(words, weights, N, penalty, L, QWords)
% Victoria's solver
score = 0;
PThresh = 0.15;
board = zeros(N);
WordsInUse = false(1,QWords);
SpecificWeights = weights./(L + 1);
[~,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
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 [board, score] = solver_nick(words, weights, N, penalty,wlen,nword)
% Nicks's solver
if min(wlen) == N
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;
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 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
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 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(r(k));
k = find(open & (wlen <= N-l),1);
end
end
board2 = zeros(N);
w2 = 0;
open = true(1,numel(words));
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(r(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);
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));
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(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 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(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 = 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(r(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(r(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);
s2 = sum(weights) + penalty*ntrans - w2;
if s2 < s
board = board2;
s = s2;
end
if (s0 < s)
board = board0;
s = s0;
end
score = s;
end
function [board,score] = solver_anieto(words, weights, N, penalty, wordlength, nwords)
% Alfonso's solver
board = zeros(N);
[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
isets_ = find(lwords_(1:end-1)+1==lwords_(2:end));
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
pboard = [board;zeros(1,N)];
cs = cumsum(pboard(:)~=0);
ntrans = sum(diff(cs(pboard==0))>1);
score = penalty*ntrans;
for N = 1:length(weights0_)
score = score + sum(weights0_{N});
end
end
function c=E(S,Twn)
if S>0
c=[0,Twn(ceil(S/2))];
else
c=[0,0];
end
end
function [board,score] = solver_fel(words, weights, N, penalty,Longitud,W)
idx_score_sorted = ordena_indices(weights,Longitud,1);
C = ones(N,1)*(3*N);
if penalty == 0
dc = 1;
elseif sum(Longitud == N) >= N && (N-length(1:2:N))*weights(idx_score_sorted(ceil(N/2+1))) > N*penalty
dc = 1;
elseif (N-length(1:2:N))*mean(weights) > N*penalty
dc = 1;
else
dc = 2;
end
C(1:dc:N) = 0;
% TIPOS = 3;
% SCORE = zeros(TIPOS,1);
% for t = 1:TIPOS
% SCORE(t) = estimar_score(Longitud,weights,N,C,t);
% end
% [~, idx_better] = max(SCORE);
% [board, score] = colocar(words,Longitud,weights,penalty,N,W,C,idx_better);
TIPOS = 5;
TRUE_SCORE = zeros(TIPOS,1);
for t = 1:TIPOS
[BOARDS{t}, TRUE_SCORE(t)] = colocar(words,Longitud,weights,penalty,N,W,C,t);
end
[score, idx_true_better] = min(TRUE_SCORE);
board = BOARDS{idx_true_better};
end
function score_est = estimar_score(Longitud,weights,N,C,tipo)
idx_sorted = ordena_indices(weights,Longitud,tipo);
idx_ultimo_est = find(cumsum(Longitud(idx_sorted)+1) > sum(C==0)*N,1,'first');
score_est = sum(weights(idx_sorted(1:idx_ultimo_est)));
end
function idx_sorted = ordena_indices(weights,Longitud,tipo)
switch tipo
case 1
[~,idx_sorted] = sort(weights ,'descend');
case 2
mean_weights = mean(weights(:));
idx_mas_de_media = weights(:) > mean_weights;
[~,idx_sorted] = sort(Longitud(:) - weights(:)/max(weights(:)) - (idx_mas_de_media)*10000,'ascend');
case 3
mean_weights = mean(weights(:));
std_weights = var(weights(:));
idx_mas_de_media_std = weights(:) > mean_weights + 0.5*std_weights;
idx_menos_de_media = weights(:) < mean_weights - 0.5*std_weights;
idx_penalties = idx_mas_de_media_std - idx_menos_de_media;
[~,idx_sorted] = sort(Longitud(:) - weights(:)/max(weights(:)) - (idx_penalties)*10000,'ascend');
case 4
mean_weights = mean(weights(:));
std_weights = var(weights(:));
idx_mas_de_media_std = weights(:) > mean_weights + 0.6*std_weights;
idx_menos_de_media = weights(:) < mean_weights - 0.6*std_weights;
idx_penalties = idx_mas_de_media_std - idx_menos_de_media;
[~,idx_sorted] = sort(Longitud(:) - weights(:)/max(weights(:)) - (idx_penalties)*10000,'ascend');
case 5
mean_weights = mean(weights(:));
std_weights = var(weights(:));
idx_mas_de_media_std = weights(:) > mean_weights + 0.7*std_weights;
idx_menos_de_media = weights(:) < mean_weights - 0.7*std_weights;
idx_penalties = idx_mas_de_media_std - idx_menos_de_media;
[~,idx_sorted] = sort(Longitud(:) - weights(:)/max(weights(:)) - (idx_penalties)*10000,'ascend');
end
end
function [board, score] = colocar(words,Longitud,weights,penalty,N,W,C,tipo)
score = 0;
SW = sum(weights(:));
board = zeros(N);
idx_sorted = ordena_indices(weights,Longitud,tipo);
for m = 1:W
idx_wm = idx_sorted(m);
WORD = words{idx_wm};
L = Longitud(idx_wm);
N_max = max(N-C);
if N_max < min(Longitud)
break
end
if L <= N_max
idx_f = find(C <= N - L,1,'first');
if isempty(idx_f)
weights(idx_wm) = - weights(idx_wm);
else
score = score + weights(idx_wm);
idx_c = C(idx_f);
board(idx_f,idx_c + (1:L)) = WORD;
weights(idx_wm) = 0;
Longitud(idx_wm) = 100000;
C(idx_f) = C(idx_f) + L + 1;
end
else
weights(idx_wm) = - weights(idx_wm);
end
end
pboard = [board;zeros(1,N)];
cs = cumsum(pboard(:)~=0);
ntrans = sum(diff(cs(pboard==0))>1);
score = SW - score + penalty*ntrans;
end
|
