Crossing Over N

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)
  [x,y,board,used,maxj]=addbestword(x,y,board,newword,used,maxi,len,smat);

  % 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)
  [x,y,board,used]=addbestwordf(x,y,board,newword,used,maxi,len);
  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;