A1_5

function board = solver(words, weights, n, penalty)
% ------------------------------------------------------------
% SOLUTION A1_5 : horizontal and vertical filling + special case
% results: 6784922.00
% time: 60.45
% ------------------------------------------------------------
global dist_global; dist_global = repmat((1:n),n,1); dist_global = dist_global+dist_global';
% warning('off','Images:imshow:magnificationMustBeFitForDockedFigure');

L = get_lengths(words);                 % word lengths
wpl = weights'./L;                      % weights per letter
[wpl,idx] = sort(wpl);
words = words(idx);

% special case
if min(L)==n, board = just_rows(words,wpl,n,penalty); return; end

% W = transform_to_matrix(words,max(L));  % matrix of words

board = zeros(n);
hv = zeros(n); % to store whether at board(i,j) is hor(-1) or ver(+1) word
errors = 0;
i=length(words);

while i>=1 && errors<20

    % horizontal placement
    [board_h,placed_h,hv_h,b_h] = placeWord_h(board,words{i},n,hv);
    % vertical placement
    [board_v,placed_v,hv_v,b_v] = placeWord_h(board',words{i},n,-hv');
    board_v = board_v';
    hv_v = -hv_v';
    if placed_h==0 && placed_v==0
        errors = errors+1;
    else
        if b_h>b_v || ( b_h==b_v && rand()>0.5)
            board = board_v;
            hv = hv_v;
        else
            board = board_h;
            hv = hv_h;
        end
    end
    i = i-1;
%     subplot(1,1,1);imshow(board);title(num2str(errors));drawnow;
%     subplot(2,1,2);imshow(uint8(hv*128+128));title(num2str(errors));drawnow;
end

end

function [board,placed,hv,b] = placeWord_h(board,word,n,hv)
global dist_global;
    % horizontal placement
    lw = length(word);
    
    % init
    possible = true(n);
    possible(:,n-lw+2:end) = 0;
    
    % check for actual possible positions
    for i=1:lw
        possible(:,1:n-lw+1) = possible(:,1:n-lw+1) & ((board(:,i:end-lw+i)==0) | (board(:,i:end-lw+i)==word(i)));
    end
    
    % check for space before
    possible(:,2:n-lw+1) = possible(:,2:n-lw+1) & (hv(:,1:n-lw)==0);
    % check for space after
    possible(:,1:n-lw) = possible(:,1:n-lw) & (hv(:,lw+1:end)==0);
    % check for space above
    for i=1:lw
        possible(2:end,1:end-lw+1) = possible(2:end,1:end-lw+1) & (hv(1:end-1,i:end-lw+i)>=0) & (hv(1:end-1,i:end-lw+i)~=3);
    end
    % check for space below
    for i=1:lw
        possible(1:end-1,1:end-lw+1) = possible(1:end-1,1:end-lw+1) & (hv(2:end,i:end-lw+i)>=0) & (hv(2:end,i:end-lw+i)~=2);
    end
    % remove any other horizontal word
    possible = possible & hv>=0;
    
    
    % place to the most top left possible position
    dist = dist_global;
    dist(~possible) = 3*n;
    m = min(min(dist));
    [x,y] = find(dist == m);
    
    if ~isempty(x) && m<3*n
        placed = 1;
        r = ceil(rand()*length(x));
        board(x(r),y(r):y(r)+lw-1) = word;
        hv(x(r),y(r)) = -2; % starting point of the word
        hv(x(r),y(r)+1:y(r)+lw-2) = -1;
        hv(x(r),y(r)+lw-1) = -3; % end point of the word
        b = m;
        return;
    end
    
    placed = 0;
    b = 3*n;
end

function [board,placed] = placeWord(board,word,n)
lw = length(word);
dir = rand()>.5;
if dir, board = board'; end

placed=0;attempt=0;
while ~placed && attempt<=50
    attempt=attempt+1;
    % horizontal placement
    x = ceil(rand()*n);
    y = ceil(rand()*(n-lw+1));
    % check validity
    if empty(board,x,y-1,n) && empty(board,x,y+lw,n)
        valid = 1;
        %above
        for i=y:y+lw-1, if ~empty(board,x-1,i,n), valid=0; end; end
        %below
        for i=y:y+lw-1, if ~empty(board,x+1,i,n), valid=0; end; end
        
        if valid
            curr = board(x,y:y+lw-1);
            if sum((curr==word)+(curr==0)>0)==lw
                board(x,y:y+lw-1) = word;
                placed = 1;
            end
        end
    end
    
end

if dir, board = board'; end

end

function bool = empty(board,x,y,n)
    bool = 1;
    if x<1, return; end
    if y<1, return; end
    if x>n, return; end
    if y>n, return; end
    if board(x,y)==0, return; end
    bool = 0;
end

function W = transform_to_matrix(words,max_length)
    % transform words cell array into matrix
    W = zeros(length(words),max_length);
    for i=1:length(words)
        W(i,1:length(words{i})) = words{i};
    end
end

function L = get_lengths(words)
    % get lengths of the words
    L = zeros(length(words),1);
    for i=1:length(words)
        L(i) = length(words{i});
    end
end

function board = just_rows(words,weights,n,penalty)
    % all words has the length of the board => place only horizontal lines
    board = zeros(n);
    lw = length(words);
    A1 = ceil(n/2);
    if A1>=lw
        for i=1:lw
            board(2*i-1,:) = words{i};
        end
        return;
    end
    B1 = sum(weights(1:A1));
    B2 = sum(weights(1:min(n,lw)))-n*penalty;
    if B2>B1
        for i=1:min(n,lw), board(i,:) = words{i}; end
        return;
    else
        for i=1:A1, board(2*i-1,:) = words{i}; end
        return;
    end
end