function board = nick_fel(words, weights, n, penalty)
[board2, score2] = solver_nick(words, weights, n, penalty);
if penalty < 2
board=board2;
return
end
[board1, score1] = solver_fel(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_fel(words, weights, N, penalty)
W = length(words);
Longitud = zeros(W,1);
for w = 1:W
Longitud(w) = length(words{w});
end
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 = 4;
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 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)*10500,'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
|
