TLM - Making Crosswords 3

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

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

C  = ones(N,1)*(3*N);
if penalty == 0
    dc = 1;
else
    dc = 2;
end
C(1:dc:N) = 0;

TIPOS = 3;
SCORE = zeros(TIPOS,1);
for t = 1:TIPOS
    SCORE(t)  = estimar_score(Longitud,weights,N,C,t);
end

[~, idx_better] = max(SCORE);

board = colocar(words,Longitud,weights,N,W,C,idx_better);


function idx_sorted = ordena_indices(weights,Longitud,N,C,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    
        [~,idx_sorted] = sort(weights ,'descend');
        idx_ultimo_est = find(cumsum(Longitud(idx_sorted)+1) > sum(C==0)*N,1,'first');
        idx_rnd        = floor(rand(length(idx_ultimo_est),1)*idx_ultimo_est)+1;
        idx_sorted(1:idx_ultimo_est) = idx_sorted(idx_rnd);
    case 5    
        [~,idx_sorted] = sort(Longitud(:) - weights(:)/max(weights(:)),'ascend');
        idx_ultimo_est = find(cumsum(Longitud(idx_sorted)+1) > sum(C==0)*N,1,'first');
        idx_rnd        = floor(rand(length(idx_ultimo_est),1)*idx_ultimo_est)+1;
        idx_sorted(1:idx_ultimo_est) = idx_sorted(idx_rnd);        
end


function score_est  = estimar_score(Longitud,weights,N,C,tipo)

idx_sorted      = ordena_indices(weights,Longitud,N,C,tipo);

idx_ultimo_est  = find(cumsum(Longitud(idx_sorted)+1) > sum(C==0)*N,1,'first');
score_est       = sum(weights(idx_sorted(1:idx_ultimo_est)));



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

board       = zeros(N);
idx_sorted  = ordena_indices(weights,Longitud,N,C,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
            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