Finish 2011-04-20 12:00:00 UTC

Naive no-crossing

by Tristrom Cooke

Status: Passed
Results: 8627441 (cyc: 8, node: 320)
CPU Time: 2.887
Score: 21568.8
Submitted at: 2011-04-14 01:58:55 UTC
Scored at: 2011-04-14 02:01:40 UTC

Current Rank: 1573rd (Highest: 44th )

Comments
Please login or create a profile.
Code
function board = solver(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]=addbestword(x,y,board,newword,used,maxi,len);
  while (maxi > 0) && (used(maxi)==1), maxi=maxi-1; end;
end;

return;

function [x,y,board,used] = addbestword(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;