Clever Willy II

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

board = zeros(n);

wlen = cellfun(@numel,words);
wcost = weights./(wlen+1);
[~,r] = sort(-wcost);
wlen = wlen(r);
words = words(r);
open = true(1,numel(words));
s = 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;
        s = s+weights(r(k));
        k = find(open&(wlen<=n-j),1);
    end;
end;
board2 = zeros(n);
s2 = 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;
        s2 = s2+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>s-s2
    board = board2;
end;
end