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

TLM - Score break through

by Fel

Status: Passed
Results: 7014590 (cyc: 41, node: 4782)
CPU Time: 61.77
Score: 17573.2
Submitted at: 2011-04-16 01:14:11 UTC
Scored at: 2011-04-16 01:17:51 UTC

Current Rank: 945th (Highest: 1st )
Basis for: TLM - Score break through (diff)
Basis for: TLM - Score break through (diff)
Basis for: TLM - Score break through (diff)
...and 2 others.

Comments
Please login or create a profile.
Code
function board = solver(words, weights, N, penalty)
nws     = numel(words);
lengths = zeros(1,nws);
for nw=1:nws,lengths(nw)=numel(words{nw});end
[BOARD{1}, SCORE(1)] = solver_victoria(words, weights, N, penalty, lengths, nws);
[BOARD{2}, SCORE(2)] = solver_nick(words, weights, N, penalty, lengths, nws);
[BOARD{3}, SCORE(3)] = solver_anieto(words, weights, N, penalty, lengths, nws);
[BOARD{4}, SCORE(4)] = solver_fel(words, weights, N, penalty, lengths, nws);
[~, board_idx]       = min(SCORE);
board                = BOARD{board_idx};
end

function [board, score] = solver_victoria(words, weights, N, penalty, L, QWords)

% Victoria's solver
score      = 0;
PThresh    = 0.15;
board      = zeros(N);

WordsInUse = false(1,QWords);

SpecificWeights = weights./(L + 1);
[~,IndWS]       = sort(SpecificWeights,'descend');
SpecLCum        = cumsum(L(IndWS) + 1);
MaxQ            = numel(find(SpecLCum <= N.*(N+1)));
GoodWeight      = sum(weights(IndWS(1:MaxQ)));
BadGoodCoef     = N.*penalty./GoodWeight;

P           = BadGoodCoef > PThresh;
if P
    slots   = ones(1,ceil(N/2));
    MaxQ    = numel(find(SpecLCum <= (N+1).^2/2));
else
    slots   = ones(1,N);
end

LoL         = min(L(IndWS(1:MaxQ)));
HiL         = max(L(IndWS(1:MaxQ)));
IndL        = zeros(MaxQ,1);
l           = 1;
for n = HiL:-1:LoL
    idx_long       = find(L(IndWS(1:MaxQ))==n);
    l2             = l + numel(idx_long);
    IndL(l:l2-1)   = idx_long;
    l              = l2;
end
IndWS(1:MaxQ) = IndWS(IndL);

n = 1;

while min(slots) < N && n <= QWords
    
    Space = N - L(IndWS(n)) + 1 - slots;
    
    SlotIndex = find(~Space,1);
    
    if isempty(SlotIndex)
        [Espacio,SlotIndex] = max(Space);
    else
        Espacio = 1;
    end
    
    if Espacio > 0
        board((1+P)*SlotIndex-P,slots(SlotIndex):slots(SlotIndex) + L(IndWS(n)) - 1) = words{IndWS(n)};
        slots(SlotIndex) = slots(SlotIndex) + L(IndWS(n)) + 1;
        
        score = score + weights(IndWS(n));
        
        WordsInUse(IndWS(n)) = true;
    end
    
    n=n+1;
end

if P
    for n = 1:QWords
        
        CurInd  = IndWS(n);
        CurL    = L(CurInd);
        word_c  = words{CurInd};
        
        if ~WordsInUse(CurInd) && (CurL/2 ~= round(CurL/2))
            
            [I,J] = find(board(1:N - CurL + 1,:) == word_c(1));
            
            if ~isempty(I)
                
                k = 1;
                
                while ~WordsInUse(CurInd) && (k <= numel(I))
                    
                    if all(word_c(1:2:end) == board(I(k):2:I(k) + CurL - 1,J(k))')
                        
                        board(I(k):I(k) + CurL - 1,J(k)) = word_c';
                        
                        score = score + weights(IndWS(n));
                        
                        WordsInUse(IndWS(n)) = true;
                        
                    end
                    
                    k = k + 1;
                    
                end
            end
        end
    end
end

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

end

function [board, score] = solver_nick(words, weights, N, penalty,wlen,nword)

% Nicks's solver
if min(wlen) == N
    
    maxlen      = max(wlen);
    pwords      = cellfun(@(a)[a 0 -1*ones(1,maxlen-numel(a))],words,'UniformOutput',false);
    wmat        = cat(1,pwords{:});
    wmat        = wmat(:,1:end-1);
    m           = cell(N);
    
    for n = 1:maxlen
        m{n,1} = double(sparse(bsxfun(@eq,wmat(:,n),wmat(:,1)')));
        m{3,n} = double(sparse(bsxfun(@eq,wmat(:,3),wmat(:,n)')));
    end
    
    rwords = zeros(1,N);
    cwords = zeros(1,N);
    
    n       = 1;
    pm      = ones(nword);
    m13     = m{n,1}*m{3,n};
    ppm     = pm & m13;
    
    while (n < N) && any(ppm(:))
        pm = ppm;
        n  = n + 2;
        if (n < N)
            m13 = m{n,1}*m{3,n};
            ppm = pm & m13;
        end
    end
    
    icross              = n;
    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 n = 1:2:icross
        
        iword = find((m{n,1}(i1,:).*m{3,n}(:,i3)') & open);
        
        if ~isempty(iword)
            iword                   = iword(1);
            cwords(n)               = iword;
            board(1:wlen(iword),n)  = 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 n = 5:height
        cols            = find(board(n,:)~=0);
        matches         = bsxfun(@eq,wmat(:,cols),board(n,cols))|(wmat(:,cols)<0);
        [~,bm]          = max(open.*sum(matches,2));
        votes(n,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;
    
    n = 5;
    while (n <= height)
        cols    = find(board(n,:)~=0);
        row     = find(open & all(bsxfun(@eq,wmat(:,cols),board(n,cols))|(wmat(:,cols)<0),2),1);
        if ~isempty(row)
            open(row)               = false;
            board(n,1:wlen(row))    = words{row};
            rwords(n)               = row;
            n                       = n+2;
        else
            n                       = n+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 n = [1:2:N,2:2:N]
    l = 0;
    k = find(open & (wlen<=N-l),1);
    while ~isempty(k)
        open(k)                = false;
        word                   = words{k};
        L_word                 = numel(word);
        board(n,l+1:l+L_word)  = word;
        l                      = l + L_word + 1;
        w                      = w + weights(r(k));
        k                      = find(open & (wlen <= N-l),1);
    end
end

board2   = zeros(N);
w2       = 0;
open     = true(1,numel(words));
wlen_m_N = wlen <= N;

for n = 1:2:N
    l = 0;
    k = find(open & wlen_m_N,1);
    while ~isempty(k)
        open(k)                = false;
        word                   = words{k};
        L_word                 = numel(word);
        board2(n,l+1:l+L_word) = word;
        l                      = l+L_word+1;
        w2                     = w2 + weights(r(k));
        k                      = find(open & (wlen <= N-l),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));
    wlen_eq_targ                         = wlen==targ;
    for n = 2:N
        k                                    = find(open & wlen_eq_targ,1); % DFM SPEED
        board2(n,filled(n)+1:filled(n)+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 n = 2:N
            idir                                      = ldir*(mod(n,2)==0);
            k                                         = find(open&(wlen==targ+idir),1);
            board2(n,filled(n)+1:filled(n)+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            = ones(1,N)*wlen(k0);
            targ(2:2:end)   = wlen(k0)+2;
        else
            targ            = ones(1,N)*(wlen(k0)+2);
            targ(2:2:end)   = wlen(k0);
        end
        for n = 1:N
            k                                       = find(open&(wlen==targ(n)),1);
            board2(n,filled(n)+1:filled(n)+targ(n)) = 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 n = 1:N
        k = find(open & (wlen<=N-filled(n)),1);
        while ~isempty(k)
            open(k)                                     = false;
            word                                        = words{k};
            board2(n,filled(n)+1:filled(n)+numel(word)) = word;
            filled(n)                                   = filled(n) + numel(word) + 1;
            w2                                          = w2 + weights(r(k));
            k                                           = find(open & (wlen<=N-filled(n)),1);
        end
    end
end
pboard  = [board2; zeros(1,N)];
cs      = cumsum(pboard(:)~=0);
ntrans  = sum(diff(cs(pboard==0))>1);

s2      = sum(weights) + penalty*ntrans - w2;
if s2 < s
    board   = board2;
    s       = s2;
end

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

score = s;

end

function [board,score] = solver_anieto(words, weights, N, penalty, wordlength, nwords)

% Alfonso's solver
board                 = zeros(N);
[wordlength,idxwords] = sort(wordlength);
idxpart               = [0, find(diff(wordlength)), nwords];
nwords_               = diff(idxpart);                          % number of words for each wordlength
lwords_               = wordlength(idxpart(2:end)); % list of wordlengths
isets_                = find(lwords_(1:end-1)+1==lwords_(2:end));

n_                    = numel(lwords_);
words_                = cell(1,n_);
weights_              = words_;
weights0_             = words_;
for nword_= 1:n_,
    idx1                = idxwords(idxpart(nword_)+1:idxpart(nword_+1));
    [w,idx2]            = sort(weights(idx1),2,'descend');
    weights0_{nword_}   = w;            % cumulative gains
    words_{nword_}      = idx1(idx2);   % sorted words
    weights_{nword_}    = cumsum(w);    % cumulative gains
end

borders = [1,1,N,N];

while size(borders,1)>0,
    border = borders(1,:);
    ntwn   = sum(prod(border(:,3:4),2),1);
    Twn    = zeros(1,ntwn);
    tn     = 0;
    twn    = 0;
    for nword_= find(nwords_>0),
        t     = nwords_(nword_);
        Twn(tn+(1:t)*lwords_(nword_)) = twn + weights0_{nword_};
        tn                            = tn + t*lwords_(nword_);
        if tn>=ntwn,
            break;
        end
    end
    Twn     = cumsum(Twn);
    
    Cmax    = -inf;
    
    for orientation=1:2,
        
        r  = border(3);
        c  = border(4);
        rc = r*c;
        
        for nword_ = find(nwords_>0&lwords_<=c),
            
            m      = min(r,nwords_(nword_));
            C      = weights_{nword_}(m) - penalty*lwords_(nword_) + E(rc-min(r,m+1)*(lwords_(nword_)+1),Twn);
            
            if C(1)>0 && sum(C)>Cmax,
                Imax = [orientation,1,nword_,m];
                Cmax = sum(C);
            end
            
            m = min(ceil(r/2),nwords_(nword_));
            C = weights_{nword_}(m) + E(rc-min(r,2*m)*(lwords_(nword_)+1),Twn);
            
            if C(1)>0 && sum(C)>Cmax,
                Imax = [orientation,2,nword_,m];
                Cmax = sum(C);
            end
        end

        border = border([2,1,4,3]);
    end
    
    if Cmax > 0
        
        if Imax(1)==2,
            board=board';
            borders=borders(:,[2,1,4,3]);
        end
        
        border = borders(1,:);
        
        switch(Imax(2))
            case 1
                nword_ = Imax(3);
                m      = Imax(4);
                for nw = 1:m,
                    board(border(1)+nw-1,border(2)+(0:lwords_(nword_)-1)) = words{words_{nword_}(nw)};
                end
                words_{nword_}      = words_{nword_}(m+1:end);
                weights0_{nword_}   = weights0_{nword_}(m+1:end);
                weights_{nword_}    = weights_{nword_}(m+1:end)-weights_{nword_}(m);
                nwords_(nword_)     = nwords_(nword_)-m;
                nwords              = nwords-m;
                if m < border(3)-1,
                    borders(1,:)    = border + [0,lwords_(nword_)+1,m-border(3),-(lwords_(nword_)+1)];
                    borders         = cat(1,border+[m+1,0,-(m+1),0],borders);
                else
                    borders(1,:)    = border + [0,lwords_(nword_)+1,0,-(lwords_(nword_)+1)];
                end
            case 2
                nword_  = Imax(3);
                m       = Imax(4);
                for nw = 1:m,
                    board(border(1)+2*nw-2,border(2)+(0:lwords_(nword_)-1)) = words{words_{nword_}(nw)};
                end
                words_{nword_}      = words_{nword_}(m+1:end);
                weights0_{nword_}   = weights0_{nword_}(m+1:end);
                weights_{nword_}    = weights_{nword_}(m+1:end)-weights_{nword_}(m);
                nwords_(nword_)     = nwords_(nword_)-m;
                nwords              = nwords-m;
                if 2*m-1<border(3)-1,
                    borders(1,:)    = border + [0,lwords_(nword_)+1,2*m-1-border(3),-(lwords_(nword_)+1)];
                    borders         = cat(1,border+[2*m,0,-2*m,0],borders);
                else
                    borders(1,:)    = border + [0,lwords_(nword_)+1,0,-(lwords_(nword_)+1)];
                end
            case 3
        end
        if Imax(1)==2,
            board   = board';
            borders = borders(:,[2,1,4,3]);
        end
        
        borders(any(borders(:,3:4)<=0,2),:)=[];
    else
        borders(1,:)=[];
    end
    
end

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

for N = 1:length(weights0_)
    score = score + sum(weights0_{N});
end

end

function c=E(S,Twn)
if S>0
    c=[0,Twn(ceil(S/2))];
else
    c=[0,0];
end
end

function [board,score] = solver_fel(words, weights, N, penalty,Longitud,W)

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      = 3;
% SCORE = zeros(TIPOS,1);
% for t = 1:TIPOS
%     SCORE(t)  = estimar_score(Longitud,weights,N,C,t);
% end
% [~, idx_better] = max(SCORE);
% [board, score]  = colocar(words,Longitud,weights,penalty,N,W,C,idx_better);

TIPOS      = 5;
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 score_est  = estimar_score(Longitud,weights,N,C,tipo)

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

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)*10000,'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