2011-04-20 12:00:00 UTC

# Star Crossed 8

Status: Passed
Results: 7127153 (cyc: 32, node: 1852)
CPU Time: 48.174
Score: 17841.9
Submitted at: 2011-04-15 04:03:17 UTC
Scored at: 2011-04-15 04:06:02 UTC

Current Rank: 1098th (Highest: 1st )

Nicholas Howe
15 Apr 2011
So close to #1, how can I not try again?
Code
```function board = starcross8(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&cmult(m{i,1},m{3,i});
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';
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));
end;
board([2 4:end],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;
goodr = ~openr;
goodc = ~openc;
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));
end;
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;
goodc = ~openc;
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));
end;
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);
open = true(1,nword);
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&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;
end;
end
```