2011-04-20 12:00:00 UTC

# Crossing Over N

Status: Passed
Results: 8119677 (cyc: 27, node: 1446)
CPU Time: 120.907
Score: 20697.1
Submitted at: 2011-04-15 02:02:13 UTC
Scored at: 2011-04-15 02:07:26 UTC

Current Rank: 1460th (Highest: 95th )

Code
```function board = solver(words, weights, n, penalty)

pf = 0.95;   % Horizontal packing factor
pf2 = 1.0;   % Packing factor for vertical

board = zeros(n);
if (n>80)
board = fastsolver(words, weights, n, penalty);
return;
end;

len  = zeros(1,length(words));
for ii=1:length(words)
len(ii)=length(words{ii});
end;
score = weights./(len+1);      % Score per letter placed for each word

% Estimated minimum number of letters that can be placed horizontally

lest = round(pf*floor((n+1)/2)*n);
vest = round(pf2*floor((n+1)/2)*n)+lest;

% Sort all of the words by score per letter (highest first)

[score,idx]=sort(score,'descend');
len=len(idx); maxi=0; tmp=0;
for ii=1:length(words)
newword{ii}=words{idx(ii)};
tmp=tmp+len(ii)+1;

if (tmp < lest), maxi=ii; end;
if (tmp > vest), break; end;   % Don't even consider the worst words
end;
score=score(1:length(newword));
len=len(1:length(newword));

if (1==0)
% Play around with the order that the words are sorted.

idx=[maxi+1:length(newword), maxi:-1:1];
for jj=1:length(idx), n2{jj}=newword{idx(jj)}; end; newword=n2;
len=len(idx); score=score(idx);

end;

% Create an alternative, data structure for newword

nw=zeros(length(newword),max(len));
for ii=1:length(newword)
nw(ii,1:length(newword{ii}))=newword{ii};
end;

% Miscellaneous initialisation

used = zeros(1,length(newword));
x=1; y=1;

minp=1; pword{1}=repmat(len <= n,n,1);
smat=getscore(newword,minp,pword,y,weights,n);

while (y < n)

% Start of a new row

if (x==1)
y=y-2;

% Process vertical words

for ii=minp:length(pword)

flag=0;
for jj=1:n

% Ensure consistency with newly added row

tmp  = y-ii+1;
tmp2 = (board(y,jj)==0) && (jj>1) && (board(y,jj-1)==0);

if ~tmp2
idx=find(pword{ii}(jj,:)~=0);
idx=idx(used(idx)==0);

idx1=idx(tmp <= len(idx));

if ~isempty(idx1)
idx1=idx1(nw(idx1,tmp)~=board(y,jj));
pword{ii}(jj,idx1)=0;
end;

if board(y,jj)~=0
pword{ii}(jj,idx(tmp > len(idx)))=0;
end;

end;

% Try to add vertical words if possible

idx=find(pword{ii}(jj,:)~=0);
idx=idx(used(idx)==0);
if ~isempty(idx), flag=1; end;

idx=idx(tmp >= len(idx));
if ~isempty(idx)
kk=idx(1);
board(ii:ii+len(kk)-1,jj)=newword{kk}';

%if (y==25)
%  y
%  imagesc(board);
%  keyboard;
%end;

used(kk)=1;

% Remove words on either side

for ll=minp:length(pword)
pword{ll}(jj,:)=0;
if (jj>1), pword{ll}(jj-1,:)=0; end;
if (jj<n), pword{ll}(jj+1,:)=0; end;
end;
end;
end;

if (flag==0), minp=minp+1; end;
end;

% Start off new words

pword{y+1}=repmat(len <= (n-y),n,1);
pword{y+2}=repmat(len <= (n-y-1),n,1);
pword{y+1}(board(y,:)~=0,:)=0;
pword{y+2}(board(y+1,:)~=0,:)=0;

y=y+2;
%smat=getscore(newword,minp,pword,y,weights,n);
end;

while (maxi > 0) && (used(maxi)==1), maxi=maxi-1; end;
if (maxi==0), maxi=length(newword); end;
end;

return;

%---------
% Score for adding each letter on each row

function smat=getscore(newword,minp,pword,y,weights,n)

smat=zeros(27,n);

if (1==1)

% For each letter needed, the probability of completing the word
% decreases

e=0.8;

for ii=minp:length(pword)
for jj=1:n
idx=find(pword{ii}(jj,:)~=0);
for kk=idx
if (y-ii+1<=0) || (y-ii+1 > length(newword{kk}))
tmp=27;
else
tmp=newword{kk}(y-ii+1)-64;
end;
if (tmp<=0) || (tmp > 27), tmp=27; end;

tmp2=e^(length(newword{kk})+ii-1-y);

smat(tmp,jj) = smat(tmp,jj) + tmp2 * weights(kk);
%smat(tmp,jj) = max(smat(tmp,jj) , tmp2 * weights(kk));

end;
end;
end;

end;

return;

%---------
% Add the best single horizontal word in a greedy fashion

function [x,y,board,used,maxj] = addbestword(x,y,board,newword,used,maxi,len,smat)

n=size(board,1);

flag=0; bscore=-1; maxj=0;
for ii=maxi:-1:1
if (used(ii)==0) && (len(ii) <= n-x+1)

tmp = newword{ii}-64;
tmp(tmp<0)=27; tmp(tmp>27)=27;
if (len(ii)+x <= n), tmp=[tmp 27]; end;

score=sum(smat(tmp+27*(x-1+(0:length(tmp)-1))));
if (score > bscore), bscore=score; maxj=ii; flag=1; end;

end;
end;

if (flag==0), x=1; y=y+2;  return; end;

board(y,x:x+len(maxj)-1)=newword{maxj};
used(maxj)=1;

x = x+len(maxj)+1; if (x>n-1), x=1; y=y+2; end;

return;

%--------------

function board = fastsolver(words, weights, n, penalty)

pf = 0.95;   % Packing factor

board = zeros(n);

len  = zeros(1,length(words));
for ii=1:length(words)
len(ii)=length(words{ii});
end;
score = weights./(len+1);      % Score per letter placed for each word

% Estimated minimum number of letters that can be placed horizontally

lest = round(pf*floor((n+1)/2)*n);

% Sort all of the words by score per letter (highest first)

[score,idx]=sort(score,'descend');
len=len(idx); maxi=0; tmp=0;
for ii=1:length(words)
newword{ii}=words{idx(ii)};
tmp=tmp+len(ii)+1; if (tmp < lest), maxi=ii; end;
end;

used = zeros(1,length(words));
x=1; y=1;
while (maxi > 1) && (y < n)
while (maxi > 0) && (used(maxi)==1), maxi=maxi-1; end;
end;

return;

function [x,y,board,used] = addbestwordf(x,y,board,newword,used,maxi,len)

n=size(board,1);

flag=0;
for ii=maxi:-1:1
if (used(ii)==0) && (len(ii) <= n-x)
board(y,x:x+len(ii)-1)=newword{ii};
used(ii)=1;

x = x+len(ii)+1; if (x>n-1), x=1; y=y+2; end;
flag=1;
break;
end;
end;

if (flag==0), x=1; y=y+2; end;
return;
```