Winner Markus (ones 8)

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

if at first you don't succeed

by Hannes Naudé

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)

Comments
Hannes Naudé
11 Nov 2007
Just keep doing your best.
Please login or create a profile.
Code
function moves=solver(s,t,budget)
best = inf;
for trynum=1:4
    prelimmoves=jacksolver(s,t,budget);
    score = grade(s,t,budget,prelimmoves);
    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