Finish 2011-04-20 12:00:00 UTC

seven seconds

by Alex P.

Status: Passed
Results: 7091100 (cyc: 41, node: 3074)
CPU Time: 51.705
Score: 17762.2
Submitted at: 2011-04-15 23:08:03 UTC
Scored at: 2011-04-15 23:10:43 UTC

Current Rank: 974th (Highest: 1st )
Based on: ten thousand miles away (diff)
Basis for: penalty contre weight (diff)
Basis for: TLM - Just to appear in the leaders (diff)
Basis for: TLM - Slower (diff)

Comments
Please login or create a profile.
Code
function board = nick_fel(words, weights, n, penalty)

[board2, score2] = solver_nick(words, weights, n, penalty);

if penalty < 2
    board=board2;
    return
end
[board1, score1] = solver_fel(words, weights, n, penalty);

if score1 < score2
    board = board1;
else
    board = board2;
end

end


function [board, score] = solver_nick(words, weights, n, penalty)

nword = numel(words);
wlen = cellfun(@numel,words);
if (min(wlen)==n)
    maxlen = max(wlen);
    pwords = cellfun(@(a)[a 0 repmat(-1,1,maxlen-numel(a))],words,'UniformOutput',false);
    wmat = cat(1,pwords{:});
    wmat = wmat(:,1:end-1);
    m = cell(n);
    for i = 1:maxlen
        m{i,1} = double(sparse(bsxfun(@eq,wmat(:,i),wmat(:,1)')));
        m{3,i} = double(sparse(bsxfun(@eq,wmat(:,3),wmat(:,i)')));
    end;
    rwords = zeros(1,n);
    cwords = zeros(1,n);
    
    i = 1;
    pm = ones(nword);
    ppm = pm&(m{i,1}*m{3,i});
    while (i < n) && any(ppm(:))
        pm = ppm;
        i = i+2;
        if (i < n)
            ppm = pm&(m{i,1}*m{3,i});
        end;
    end;
    icross = i;
    board = zeros(n);
    open = true(1,nword);
    [i1,i3] = find(pm);
    i1 = i1(1);
    i3 = i3(1);
    open(i1) = false;
    open(i3) = false;
    board(1,1:wlen(i1)) = words{i1};
    board(3,1:wlen(i3)) = words{i3};
    rwords(1) = i1;
    rwords(3) = i3;
    for i = 1:2:icross
        iword = find((m{i,1}(i1,:).*m{3,i}(:,i3)')&open);
        if ~isempty(iword)
            iword = iword(1);
            cwords(i) = iword;
            board(1:wlen(iword),i) = words{iword}';
            open(iword) = false;
        end;
    end;
    
    % fill in remaining crosses, if possible.
    fcwords = cwords(cwords>0);
    height = max(wlen(fcwords));
    open = open';
    votes = zeros(n);
    for i = 5:height
        cols = find(board(i,:)~=0);
        matches = bsxfun(@eq,wmat(:,cols),board(i,cols))|(wmat(:,cols)<0);
        [~,bm] = max(open.*sum(matches,2));
        votes(i,cols) = 2*matches(bm,:)-1;
    end;
    bad = sum(votes)<0;
    badword = cwords(bad(1:icross));
    open(nonzeros(badword)) = true;
    board([2 4:end],bad) = 0;
    cwords(bad) = 0;
    i = 5;
    while (i <= height)
        cols = find(board(i,:)~=0);
        row = find(open&all(bsxfun(@eq,wmat(:,cols),board(i,cols))|(wmat(:,cols)<0),2),1);
        if ~isempty(row)
            open(row) = false;
            board(i,1:wlen(row)) = words{row};
            rwords(i) = row;
            i = i+2;
        else
            i = i+1;
        end;
    end;
    s0 = sum(weights(open));
    board0 = board;
   
    % now try full fill
    openr = rwords==0;
    openc = cwords==0;
    goodc = ~openc;
    votes = zeros(n);
    for c = find(openc)
        rows = find(board(:,c)~=0);
        matches = bsxfun(@eq,wmat(:,rows),board(rows,c)')|(wmat(:,rows)<0);
        [~,bm] = max(open.*sum(matches,2));
        votes(rows,c) = 2*matches(bm,:)-1;
    end;
    bad = sum(votes,2)<-sum(goodc);
    badwords = rwords(bad);
    open(nonzeros(badwords)) = true;
    board(openr,bad) = 0;
    for c = find(openc)
        rows = find(board(:,c)~=0);
        matches = bsxfun(@eq,wmat(:,rows),board(rows,c)')|(wmat(:,rows)<0);
        wi = find(open&all(matches,2),1);
        if ~isempty(wi)
            open(wi) = false;
            board(1:wlen(wi),c) = words{wi};
            cwords(c) = wi;
        end;
    end;

    openr = rwords==0;
    openc = cwords==0;
    goodr = ~openr;
    votes = zeros(n);
    for r = find(openr)
        cols = find(board(r,:)~=0);
        matches = bsxfun(@eq,wmat(:,cols),board(r,cols))|(wmat(:,cols)<0);
        [~,bm] = max(open.*sum(matches,2));
        votes(r,cols) = 2*matches(bm,:)-1;
    end;
    bad = sum(votes,2)<-sum(goodr);
    badwords = cwords(bad);
    open(nonzeros(badwords)) = true;
    board(bad,openc) = 0;
    for r = find(openr)
        cols = find(board(r,:)~=0);
        matches = bsxfun(@eq,wmat(:,cols),board(r,cols))|(wmat(:,cols)<0);
        wi = find(open&all(matches,2),1);
        if ~isempty(wi)
            open(wi) = false;
            board(r,1:wlen(wi)) = words{wi};
            rwords(r) = wi;
        end;
    end;
    
    board(board==0) = 1;
    s1 = sum(weights(open))+penalty*(sum(rwords==0)+sum(cwords==0));
    if (s1<s0)
        board0 = board;
        s0 = s1;
    end;
else
    board0 = zeros(n);
    s0 = sum(weights);
end;

board = zeros(n);
wcost = weights./(wlen+1);
[~,r] = sort(-wcost);
wlen = wlen(r);
words = words(r);
open = true(1,numel(words));
w = 0;
for i = [1:2:n,2:2:n]
    j = 0;
    k = find(open&(wlen<=n-j),1);
    while ~isempty(k)
        open(k) = false;
        word = words{k};
        board(i,j+1:j+numel(word)) = word;
        j = j+numel(word)+1;
        w = w+weights(r(k));
        k = find(open&(wlen<=n-j),1);
    end;
end;
board2 = zeros(n);
w2 = 0;
open = true(1,numel(words));
for i = 1:2:n
    j = 0;
    k = find(open&(wlen<=n-j),1);
    while ~isempty(k)
        open(k) = false;
        word = words{k};
        board2(i,j+1:j+numel(word)) = word;
        j = j+numel(word)+1;
        w2 = w2+weights(r(k));
        k = find(open&(wlen<=n-j),1);
    end;
end;
pboard = [board;zeros(1,n)];
cs = cumsum(pboard(:)~=0);
ntrans = sum(diff(cs(pboard==0))>1);
if penalty*ntrans>w-w2
    board = board2;
    s = sum(weights)-w2;
else
    s = sum(weights)-w+penalty*ntrans;
end;

board2 = zeros(n);
w2 = 0;
open = true(1,numel(words));
filled = zeros(1,n);
filled(2:2:end) = 1;
brk = false;
while (filled(1)<n)
    wlen2 = wlen.*open;
    wlen2(~open) = 1;
    nlen = (accumarray(wlen2(:),ones(nword,1)));
    k = find(open&(wlen<=n-filled(1)-1)&(nlen(wlen)'>=n),1);
    if isempty(k)
        brk = true;
        break;
    end;
    targ = wlen(k);
    board2(1,filled(1)+1:filled(1)+targ) = words{k};
    open(k) = false;
    w2 = w2+weights(r(k));
    for i = 2:n
        k = find(open&(wlen==targ),1);
        board2(i,filled(i)+1:filled(i)+targ) = words{k};
        open(k) = false;
        w2 = w2+weights(r(k));
    end;
    filled = filled+targ+1;
end;
if (brk)
    % try two half-sets
    brk = false;
    while (filled(1)<n)
        wlen2 = wlen.*open;
        wlen2(~open) = 1;
        nlen = (accumarray(wlen2(:),ones(nword,1)));
        ldir = 2*(filled(1)>filled(2))-1;
        nlen(1) = 0;
        k = find(open&(wlen<=n-filled(1)-1)&(nlen(wlen)'>=ceil(n/2))&(nlen(wlen+ldir)'>=ceil(n/2)),1);
        if isempty(k)
            brk = true;
            break;
        end;
        targ = wlen(k);
        board2(1,filled(1)+1:filled(1)+targ) = words{k};
        open(k) = false;
        w2 = w2+weights(r(k));
        for i = 2:n
            idir = ldir*(mod(i,2)==0);
            k = find(open&(wlen==targ+idir),1);
            board2(i,filled(i)+1:filled(i)+targ+idir) = words{k};
            open(k) = false;
            w2 = w2+weights(r(k));
        end;
        filled = filled+targ+1;
    end;
end;
if (brk)
    % try two half-sets off by 2
    brk = false;
    while (filled(1)<n)
        wlen2 = wlen.*open;
        wlen2(~open) = 1;
        nlen = (accumarray(wlen2(:),ones(nword,1)));
        nlen(1) = 0;
        nlen(end+2) = 0;
        k0 = find(open&(wlen<=n-filled(1)-2)&(nlen(wlen)'>=ceil(n/2))&(nlen(wlen+2)'>=ceil(n/2)),1);
        if isempty(k0)
            brk = true;
            break;
        end;
        if filled(1)>filled(2)
            targ = repmat(wlen(k0),1,n);
            targ(2:2:end) = wlen(k0)+2;
        else
            targ = repmat(wlen(k0)+2,1,n);
            targ(2:2:end) = wlen(k0);
        end;
        for i = 1:n
            k = find(open&(wlen==targ(i)),1);
            board2(i,filled(i)+1:filled(i)+targ(i)) = words{k};
            open(k) = false;
            w2 = w2+weights(r(k));
        end;
        filled = filled+targ+1;
    end;
end;
if (brk&&any(board2(:)))
    % finish filling board normally
    for i = 1:n
        k = find(open&(wlen<=n-filled(i)),1);
        while ~isempty(k)
            open(k) = false;
            word = words{k};
            board2(i,filled(i)+1:filled(i)+numel(word)) = word;
            filled(i) = filled(i)+numel(word)+1;
            w2 = w2+weights(r(k));
            k = find(open&(wlen<=n-filled(i)),1);
        end;
    end;
end;
pboard = [board2;zeros(1,n)];
cs = cumsum(pboard(:)~=0);
ntrans = sum(diff(cs(pboard==0))>1);
if sum(weights)+penalty*ntrans-w2<s
    board = board2;
    s = sum(weights)+penalty*ntrans-w2;
end;

if (s0 < s)
    board = board0;
    s     = s0;
end;

score = s;

end

function [board,score] = solver_fel(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      = 4;

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

end

function idx_sorted = ordena_indices(weights,Longitud,tipo)

switch tipo
    case 1
        [~,idx_sorted] = sort(weights ,'descend');
    case 2
        mean_weights     = mean(weights(:));
        idx_mas_de_media = weights(:) > mean_weights;
        [~,idx_sorted] = sort(Longitud(:) - weights(:)/max(weights(:)) - (idx_mas_de_media)*10500,'ascend');
    case 3
        mean_weights            = mean(weights(:));
        std_weights             = var(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 4
        mean_weights            = mean(weights(:));
        std_weights             = var(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 5
        mean_weights            = mean(weights(:));
        std_weights             = var(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

end

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

score       = 0;
SW          = sum(weights(:));
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

pboard  = [board;zeros(1,N)];
cs      = cumsum(pboard(:)~=0);
ntrans  = sum(diff(cs(pboard==0))>1);
score   = SW - score + penalty*ntrans;

end