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

work of the first night

by Alex P.

Status: Passed
Results: 8057024 (cyc: 11, node: 410)
CPU Time: 81.632
Score: 20148.7
Submitted at: 2011-04-13 23:20:18 UTC
Scored at: 2011-04-13 23:24:14 UTC

Current Rank: 1402nd (Highest: 11th )

Comments
Please login or create a profile.
Code
function board = solver(words, weights, bs, penalty)
board = zeros(bs);

nw = numel(words);
sw = sum(weights);

lens = zeros(1,nw);
for k = 1:nw
    lens(k)=numel(words{k});
end

f=3;
if f*min(weights)<max(weights) || min(lens)==max(lens)
    [weights,idx] = sort(weights,2,'descend');
    words = words(idx);
    lens  = lens(idx);
else
    [lens,idx] = sort(lens,2,'ascend');
    words = words(idx);
    weights = weights(idx);
end

remainmin = sw+1;
remain = sw+1e10;
toomuch =0;
delta = 0.001;
limit = 0; max(weights)-min(weights)+max(lens)-min(lens);
while toomuch < limit+remain/10000;
    %2*(remain-remainmin)%
    
    % idx = randperm(nw);
    
    remain = sw;
    lastcol  = zeros(1,bs)-1;
    B = zeros(bs);
    r = 1;
    for kw = 1:nw
        wd = words{kw};
        lastcol(r)=lastcol(r)+1;
        c = max(lastcol(max(1,r-1):min(bs,r+1)))+1;
        %    c = min(lastcol(max(1,r-1):min(bs,r+1)))+2;
        lastcol(r)=lastcol(r)-1;
        if c-1+lens(kw)<=bs
            B(r,c:c-1+lens(kw))= wd;
            lastcol(r) = c-1+lens(kw);
            remain = remain-weights(kw);
        end
        r = r+2;
        if r>bs
            [~,r] = min(lastcol(1:2));
        end
    end
    
    if remain<remainmin
        board = B;
        remainmin=remain;
        fprintf('%d\n',remain)
    else
        toomuch = toomuch +1;
    end
    idx=1:nw;
    for p=1:nw-1
        if rand>delta %lens(p)>lens(p+1)
            a=idx(p);idx(p)=idx(p+1);idx(p+1)=a;
        end
    end
    delta=sqrt(delta);
    words = words(idx);
    lens  = lens(idx);
    weights = weights(idx);
    
end

fprintf('[%d]\n\n',toomuch);

end