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

won't get better

by Andreas Bonelli

Status: Passed
Results: 7382376 (cyc: 9, node: 754)
CPU Time: 41.444
Score: 18456.7
Submitted at: 2011-04-15 15:10:29 UTC
Scored at: 2011-04-15 15:12:41 UTC

Current Rank: 1253rd (Highest: 36th )

Comments
Please login or create a profile.
Code
function b = solver9(words, weights, n, penalty)
    
    % Exploiting a broken scoring formula.
    % Kudos to Martin F. for stopping me from coding serious algorithms.
    
    holdback = [0,2,6,12];
    pars = [holdback, holdback + 100];
    
    npars = numel(pars);
     
    bs = cell(npars, 1);
    ss = nan(npars, 1);
         
    for i = 1:npars
        [b, s] = mysolver(words, weights, n, penalty, pars(i));
        bs{i} = b;
        ss(i) = s;
%         if isinf(s); break; end;
    end
     
    [~, pick] = max(ss);
    b = bs{pick};
end

function [b,score] = mysolver(words, weights, n, penalty, pars)
    c_score  = 1; %#ok<NASGU>
    c_weight = 2;
    c_len    = 3;
    c_elen   = 4;
    c_w      = 5;
    score = 0;    
    
    nholdback = mod(pars, 100);
    dopack = pars >= 100;
    
    if nholdback > numel(words);
        score = -inf;
        b = zeros(n);
        return;
    end
    
    words = words(:);
    weights = weights(:);
    nwords = numel(words);
    
    wlens = cellfun(@(x) numel(x), words);
    maxwlen = max(wlens);
    ws = zeros(nwords, maxwlen+c_w-1);
    ws(:,c_len) = wlens;
    ws(:,c_elen) = wlens;
    ws(:,c_weight) = weights;
    
    for i = 1:nwords;
        ws(i, c_w:c_w+wlens(i)-1) = words{i};
    end
      
    if nholdback > 0
        ws(:,c_weight) = -ws(:,c_weight);
        ws = sortrows(ws, [c_len, c_weight]);
        holdback = ws(1:nholdback,:);
        ws = ws(nholdback+1:end,:);
        ws(:,c_weight) = -ws(:,c_weight);
    else
        holdback = zeros(0, size(ws, 2));
    end
        
    ws = sortrows(ws, [c_len, c_weight]);
    
    b = zeros(n);
    towers = zeros(ceil(n/3), 2);
    ntowers = 0;
    
    col = 1;
    spaceleft = n;
    while ws(1, c_len) <= spaceleft
        if size(ws, 1) > n;
            blockwidth = ws(n, c_len);
            
            if blockwidth > spaceleft
                picks = find(ws(1:n,c_len) <= spaceleft);
                b(picks,col:col-1+spaceleft) = ws(picks,c_w:c_w-1+spaceleft);
                score = score + sum(ws(picks,c_weight));
                ws = ws(picks(end)+1:end,:);
            else
                % default case
                if dopack && blockwidth > ws(1,c_len);
                    
                    ws(1:n,c_elen) = blockwidth;
                    
                    ws = sortrows(ws, [c_elen, c_weight]);
                    myslice = ws(1:n,:);
                    ws = sortrows(ws(n+1:end, :), [c_len, c_weight]);
                    
                    myslice = sortrows(myslice, c_len);
                else
                    myslice = ws(1:n, :);
                    ws = ws(n+1:end,:);
                end
                b(:,col:col-1+blockwidth) = myslice(:,c_w:c_w-1+blockwidth);
                score = score + sum(myslice(:,c_weight));
%                 ws = ws(n+1:end,:);
            end
            
            ntowers = ntowers + 1;
            towers(ntowers, :) = [col, col-1+blockwidth];
            col = col + blockwidth + 1;
            spaceleft = n-col+1;
        else
            disp('buh');
            break;
        end
    end
    
    filler();
    
    function filler()
        
        for k = 1:2;
            for i = 1:2;
                while ~isempty(ws);
                    nextwsize = ws(1,c_len);
                    p = [0, 1, 0; ones(nextwsize, 3); 0, 1, 0];
                    spots = conv2(b, p, 'full')==0;
                    spots = spots(nextwsize+1:end-nextwsize, 2:end-1);
                    if ~any(spots(:)); break; end
                    nextw = ws(1,c_w:c_w-1+nextwsize);
                    [r c] = find(spots, 1, 'first');
                    b(r:r-1+nextwsize,c) = nextw';
                    ws = ws(2:end,:);
                end
                b=b';
            end
            ws = [holdback; ws];
        end
    end
end