Winner Markus (ones 8)

2007-11-14 12:00:00 UTC

# if at first you don't succeed

Status: Passed
Results: 58970.34 (cyc: 10)
CPU Time: 130.591
Score: 7267.2
Submitted at: 2007-11-11 15:00:27 UTC
Scored at: 2007-11-11 15:04:45 UTC

Current Rank: 1903rd
Based on: always do your best (diff)
Basis for: try again (diff)

11 Nov 2007
Code
```function moves=solver(s,t,budget)
best = inf;
for trynum=1:4
prelimmoves=jacksolver(s,t,budget);
if score<best
moves=prelimmoves;
best=score;
end
end
end

function moves = jacksolver(s,t,budget)

n = length(s);
on = ones(1,n);
trep = t(on,:);
moves = zeros(budget,4);

for b = 1:budget
d = abs(trep - s(on,:)') + std(t)*(budget-b)/125*randn(n);
moves(b,:) = bestmove(d);
if ~moves(b,1)
moves(b:end,:) = [];
return
end
le = moves(b,1);
ai = moves(b,2);
bi = moves(b,3);
if moves(b,4)
if ai>bi
s = s([1:bi-1 ai+le-1:-1:ai bi:ai-1 ai+le:end]);
else
s = s([1:ai-1 ai+le:bi+le-1 ai+le-1:-1:ai bi+le:end]);
end
else
if ai>bi
s = s([1:bi-1 ai:ai+le-1 bi:ai-1 ai+le:end]);
else
s = s([1:ai-1 ai+le:bi+le-1 ai:ai+le-1 bi+le:end]);
end
end
end
end

function m = bestmove(d)
n = size(d,1);
dp = diagcumsum(d);
dm = flipud(diagcumsum(flipud(d)));
cost = 0;
m = zeros(1,4);
for i = 1:n-1
for k = i+2:n+1
old = dp(k,k)-dp(i,i); % orig diag [i,k)
for j = i+1:k-1
if dp(k,i+k-j)-dp(j,i)+dp(j,k)-dp(i,i+k-j)-cost<old || dp(k,i+k-j)-dp(j,i)+dm(i,k)-dm(j,i+k-j)-cost<old || dm(j,i+k-j)-dm(k,i)+dp(j,k)-dp(i,i+k-j)-cost<old
if dp(k,i+k-j)-dp(j,i)+dp(j,k)-dp(i,i+k-j)-cost<old
cost = dp(k,i+k-j)-dp(j,i)+dp(j,k)-dp(i,i+k-j)-old;
m = [k-j j i 0 ];
end
if dp(k,i+k-j)-dp(j,i)+dm(i,k)-dm(j,i+k-j)-cost<old
cost = dp(k,i+k-j)-dp(j,i)+dm(i,k)-dm(j,i+k-j)-old;
m = [j-i i i+k-j 1];
end
if dm(j,i+k-j)-dm(k,i)+dp(j,k)-dp(i,i+k-j)-cost<old
cost = dm(j,i+k-j)-dm(k,i)+dp(j,k)-dp(i,i+k-j)-old;
m = [k-j j i 1 ];
end
end
end
end
end
end

function R = diagcumsum(M)
% cumulative sums along diagonal
n = size(M,1);
R = zeros(n+1);
for c = 2:n+1
for r = 2:n+1
R(r,c) = M(r-1,c-1) + R(r-1,c-1);
end
end
end```