Winner Markus (ones 8)

2007-11-14 12:00:00 UTC

Ulriks V3

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

Ulrik Kjems
14 Nov 2007
add check on no improvement
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);
```