Crossword_01

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

% 1st strategy: Fill-in-the-blanks

% Initialization
board = zeros(n);

num_words = length(weights);

indices = 1:num_words;

word_length = zeros(size(indices));
for i = 1:num_words
    word_length(i) = length(words{i});
end


% Criteria
[temp ind] = sort(word_length, 2, 'ascend'); % prefer short word

weights     = weights(ind);
indices     = indices(ind);
word_length = word_length(ind);


% Estimate the location of the last word to be used
num_rows = [n floor(n/2)];
possible_sum = n * num_rows(1  + (penalty > 0));

cumulate = 0;
count    = 1;
while( (cumulate < possible_sum) && (count <= num_words) )
    cumulate = cumulate + word_length(count) + 1;
    count    = count + 1;
end
count = count - 1;


% Rearrange according to weight in descending order for a given word length
I = find(word_length == word_length(count));
[temp ind] = sort(weights(I), 2, 'descend');

weights(I)     = weights(I(ind));
indices(I)     = indices(I(ind));
word_length(I) = word_length(I(ind));


% Make them fill in better
weights(1:count)     = weights(count:-1:1);
indices(1:count)     = indices(count:-1:1);
word_length(1:count) = word_length(count:-1:1);


% Pick and place
num_words_left = num_words;
inc = 1 + (penalty > 0);
for row = 1:inc:n
    col_i = 1;
    count = 1;
    while( (col_i < n) && (count <= num_words_left) )
        col_f = col_i + word_length(count) - 1;
        
        if col_f <= n
            board(row, col_i:col_f) = words{indices(count)};

            weights(count)     = -1;
            indices(count)     = -1;
            word_length(count) = -1;
            
            col_i = col_f + 2;
        end
        
        count = count + 1;
    end
    weights     = weights(weights > 0);
    indices     = indices(indices > 0);
    word_length = word_length(word_length > 0);
    
    num_words_left = length(weights);
end

end