anansi

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

cost = sum(weights);
board = zeros(n);
lw = numel(words);
lengths = zeros(1, n);
for a=1:lw
    lengths(a) = length(words{a});
end

[~, sortedindices] = sort(weights ./ (lengths + 1), 2, 'descend');

used = false(lw, 1);
c = 1;
row = 1;
col = 1;
while true
    x = c;
    max_length = n - col + 1;
    while x <= lw && (used(x) || length(words{sortedindices(x)}) > max_length)
        x = x + 1;
    end
    
    if x > lw
        while used(c) && c <= lw
            c = c + 1;
        end
        x = c;
        row = row + 2;
        col = 1;
        if row > n
            break
        end
    end

    word = words{sortedindices(x)};
    board(row, col:(col + length(word) - 1)) = word;
    used(x) = true;
    cost = cost - weights(sortedindices(x));
    col = col + length(word) + 1;
    if x == c
        c = c + 1;
    end
end

fprintf('Cost was %8.1f. Used %4d/%4d words.\n', cost, sum(used), lw);