TLM - Making Crosswords 7

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

W           = length(words);
Longitud    = zeros(W,1);
for w = 1:W
    Longitud(w) = length(words{w});
end

idx_score_sorted = ordena_indices(weights,Longitud,1);

C  = ones(N,1)*(3*N);
if penalty == 0
    dc = 1;
elseif sum(Longitud == N) >= N && (N-length(1:2:N))*weights(idx_score_sorted(ceil(N/2+1))) > N*penalty
    dc = 1;
elseif (N-length(1:2:N))*mean(weights) > N*penalty
    dc = 1;
else
    dc = 2;
end
C(1:dc:N) = 0;

TIPOS      = 7;

TRUE_SCORE = zeros(TIPOS,1);
for t = 1:TIPOS
    [BOARDS{t}, TRUE_SCORE(t)] = colocar(words,Longitud,weights,N,W,C,t);
end
[~, idx_true_better] = max(TRUE_SCORE);
board = BOARDS{idx_true_better};


function idx_sorted = ordena_indices(weights,Longitud,tipo)

switch tipo
    case 1
        [~,idx_sorted] = sort(weights ,'descend');
    case 2
        [~,idx_sorted] = sort(Longitud,'ascend');
    case 3
        [~,idx_sorted] = sort(Longitud(:) - weights(:)/max(weights(:)),'ascend');
    case 4
        mean_weights     = mean(weights(:));
        idx_mas_de_media = weights(:) > mean_weights;
        [~,idx_sorted] = sort(Longitud(:) - weights(:)/max(weights(:)) - (idx_mas_de_media)*10000,'ascend');
    case 5
        mean_weights            = mean(weights(:));
        std_weights             = std(weights(:));
        idx_mas_de_media_std    = weights(:) > mean_weights + 0.5*std_weights;
        idx_menos_de_media      = weights(:) < mean_weights - 0.5*std_weights;
        idx_penalties           = idx_mas_de_media_std - idx_menos_de_media;
        [~,idx_sorted]   = sort(Longitud(:) - weights(:)/max(weights(:)) - (idx_penalties)*10000,'ascend');
    case 6
        mean_weights            = mean(weights(:));
        std_weights             = std(weights(:));
        idx_mas_de_media_std    = weights(:) > mean_weights + 0.6*std_weights;
        idx_menos_de_media      = weights(:) < mean_weights - 0.6*std_weights;
        idx_penalties           = idx_mas_de_media_std - idx_menos_de_media;
        [~,idx_sorted]   = sort(Longitud(:) - weights(:)/max(weights(:)) - (idx_penalties)*10000,'ascend');
    case 7
        mean_weights            = mean(weights(:));
        std_weights             = std(weights(:));
        idx_mas_de_media_std    = weights(:) > mean_weights + 0.7*std_weights;
        idx_menos_de_media      = weights(:) < mean_weights - 0.7*std_weights;
        idx_penalties           = idx_mas_de_media_std - idx_menos_de_media;
        [~,idx_sorted]   = sort(Longitud(:) - weights(:)/max(weights(:)) - (idx_penalties)*10000,'ascend');        
end

% figure, plot(Longitud(idx_sorted) - mean(Longitud),'b*'), hold on, plot(weights(idx_sorted) - mean(weights),'r*'), grid on


function [board, score]  = colocar(words,Longitud,weights,N,W,C,tipo)

score       = 0;

board       = zeros(N);
idx_sorted  = ordena_indices(weights,Longitud,tipo);

for m = 1:W
    
    idx_wm = idx_sorted(m);
    WORD   = words{idx_wm};
    L      = Longitud(idx_wm);
    
    N_max  = max(N-C);
    
    if N_max < min(Longitud)
        break
    end
    
    if L <= N_max
        
        idx_f = find(C <= N - L,1,'first');
        
        if isempty(idx_f)
            weights(idx_wm)             = - weights(idx_wm);
        else
            
            score = score + weights(idx_wm);
                        
            idx_c                       = C(idx_f);
            board(idx_f,idx_c + (1:L))  = WORD;
            weights(idx_wm)             = 0;
            Longitud(idx_wm)            = 100000;
            C(idx_f)                    = C(idx_f)  + L + 1;
            
        end
        
    else
        weights(idx_wm)                 = - weights(idx_wm);
    end
    
end