Winner Markus (ones 8)

Finish 2007-11-14 12:00:00 UTC

Ulriks V3

by Ulrik Kjems

Status: Passed
Results: 61054.42 (cyc: 11)
CPU Time: 166.942
Score: 14542.3
Submitted at: 2007-11-14 11:03:46 UTC
Scored at: 2007-11-14 11:49:58 UTC

Current Rank: 2488th

Comments
Ulrik Kjems
14 Nov 2007
add check on no improvement
Please login or create a profile.
Code
function moves = solver(sequence, target, budget)

moves = ones(0,4);

N = length(sequence);

score = sum(abs(sequence-target));
while budget>0 && score>0
    D = abs(repmat(sequence', 1, N)-repmat(target, N, 1));
    D1=D; D2=D;
    for i=2:N
        D1(2:N,i)   = D1(2:N,i)   + D1(1:N-1,i-1);
        D2(1:N-1,i) = D2(1:N-1,i) + D2(2:N,i-1);
    end
    D10=D1-D;
    D20=D2-D;
    scores1 = zeros(N,N,N);
    scores2 = zeros(N,N,N);
    for a1=1:N
        for b1=1:a1-1
            for n=1:N-a1+1
                a2 = a1+n-1;
                b2 = b1+n-1;
                tmp = D1(a1-1,a2)-D10(b1,b2+1) - (D1(a2,a2)-D10(b1,b1));
                scores1(a1,b1,n)=D1(a2,b2)-D10(a1,b1) + tmp;
                scores2(a1,b1,n)=D2(a1,b2)-D20(a2,b1) + tmp;
            end
        end
    end
    for b1=1:N
        for a1=1:b1-1
            for n=1:N-b1+1
                a2 = a1+n-1;
                b2 = b1+n-1;
                tmp = D1(b2,b1-1)-D10(a2+1,a1) - (D1(b2,b2)-D10(a1,a1));
                scores1(a1,b1,n)=D1(a2,b2)-D10(a1,b1) + tmp;
                scores2(a1,b1,n)=D2(a1,b2)-D20(a2,b1) + tmp;
            end
        end
    end
    [ms,ims]=min([scores1 scores2],[],3);
    [y,i]=min(ms(:));
    if y==0
        break
    end
    n = ims(i);
    [a1,b1]=ind2sub(size(ms), i);
    flip=b1>N;
    b1=b1-N*flip;
    moves(end+1,:)=[n, a1, b1, flip];
    sequence = splice(sequence, n, a1, b1, flip);
    budget = budget-1;
end

function b = splice(a, len, ai, bi, flip)

b = zeros(size(a));

aSpan = ai + (1:len) - 1;
bSpan = aSpan - ai + bi;

if flip
    b(bSpan) = fliplr(a(aSpan));
else
    b(bSpan) = a(aSpan);
end
 
a(aSpan) = 0;
b(~b) = a(~~a);