Winner Markus (ones 8)

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

Forget the steps

by Ulf Schwurack

Status: Passed
Results: 164038.15 (cyc: 18)
CPU Time: 0.3603
Score: 16413.9
Submitted at: 2007-11-11 14:31:35 UTC
Scored at: 2007-11-11 14:32:17 UTC

Current Rank: 2557th

Comments
Ulf Schwurack
11 Nov 2007
Still bad, but better...
Please login or create a profile.
Code
function moves = solver( seq, targ, budget )

moves = ones(0,4);
% Problem aufs Sortieren von Indizes reduzieren

% allen Elementen aus seq genau einen Index aus seq zuordnen
% bei denen, die zwar in seq aber nicht in targ vorkommen den Wert
% w?hlen, der am n?chsten dran ist
len = numel( seq );
seqIndexes = zeros( size( seq ) );
for iSeq = 1:len;
    [minm, iMin] = min( abs( targ - seq( iSeq ) ) );
    seqIndexes( iSeq ) = iMin;
    targ( iMin ) = inf;
end

% 1. Finde alle langen absteigenden Teil-Sequenzen (min. 3 Elemente)
%    und drehe sie um (Flip it, baby!). Subtrahiere vom kleinsten Element
%    (ist ein Index!) der Teil-Sequenz 1, finde dieses in der Gesamt-
%    Sequenz und f?ge die Teil-Sequenz hinter diesem ein.  
% 6 >7 5 2< 4 3 1 wird zu
% 6 4 3 1 >2 5 7< 
% >6 4 3 1< 2 5 7 wird zu
% >1 3 4 6< 2 5 7
nMoves = 1;
d = sign( diff( seqIndexes ) );
ma = [d 0] + [0 d];
lenLongSeq = 0;
while ~isempty( find( ma == -2 ) ) && nMoves <= budget
    iCand = find( ma == -2, 1 ) - 1;
    i = iCand;
    curLen = 1;
    while( i < len && seqIndexes( i+1 ) < seqIndexes( i ) )
        curLen = curLen + 1;
        i = i + 1;
    end
    iLongSeq = iCand;
    lenLongSeq = curLen;
    iNew = find( seqIndexes == seqIndexes( iCand + curLen - 1 ) - 1 ) + 1;
    if isempty( iNew )
        iNew = 1;
    end
    if iNew > iCand
        iNew = iNew - curLen;
    end
    moves( nMoves, : ) = [lenLongSeq, iLongSeq, iNew, true];
    seqIndexes = splice( seqIndexes, lenLongSeq, iLongSeq, iNew, true );
    nMoves = nMoves + 1;
    d = sign( diff( seqIndexes ) );
    ma = [d 0] + [0 d];
end

% 2. finde 2-elementige absteigende Sequenzen aufeinanderfolgender
% Elemente, drehen und richtig (hinter dem korrekterma?en vorangehenden
% Element) einf?gen.
iCand = find( diff( seqIndexes ) == -1, 1 );
while ~isempty( iCand ) && nMoves <= budget
    iNew = find( seqIndexes == seqIndexes( iCand + 1 ) - 1 ) + 1;
    if isempty( iNew )
        iNew = 1;
    end
    if iNew > iCand
        iNew = iNew - 2;
    end
    moves( nMoves, : ) = [2, iCand, iNew, true];
    nMoves = nMoves + 1;
    seqIndexes = splice( seqIndexes, 2, iCand, iNew, true );
    iCand = find( diff( seqIndexes ) == -1, 1 );
end

% 3. finde zusammenh?ngende Sequenzen, f?ge sie hinter dem eigentlich
% vorangehenden Element ein.
[pos, l] = findGenes( seqIndexes );
while nMoves <= budget-2 && pos ~= 0
    iNew = find( seqIndexes == seqIndexes( pos ) - 1 ) + 1;
    if isempty( iNew )
        iNew = 1;
    end
    if iNew > pos
        iNew = iNew - l;
    end
    moves( nMoves, : ) = [ l, pos, iNew, false ];
    seqIndexes = splice( seqIndexes, l, pos, iNew, false );
    nMoves = nMoves + 1;
    [pos, l] = findGenes( seqIndexes );
end

% 4. finde zusammenh?ngende Sequenzen und f?ge sie an der richtigen Stelle
% ein
[pos, l] = findGenes( seqIndexes );
while nMoves <= budget && pos ~= 0
    iNew = seqIndexes( pos );
    moves( nMoves, : ) = [ l, pos, iNew, false ];
    seqIndexes = splice( seqIndexes, l, pos, iNew, false );
    nMoves = nMoves + 1;
    [pos, l] = findGenes( seqIndexes );
end

function b = splice(a, len, ai, bi, flip)
%SPLICE  Perform the gene splice
%   b = splice(a, len, ai, bi, flip) where a is the input sequence,
%   len is the length of the extracted fragment, ai is the fragment's
%   starting index in a, bi is the fragment's starting index in b, and
%   flip is a boolean flag (true = flip, false = don't 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);

function [posOfFirst, lFirst] = findGenes( seqIndexes )

% finde alle Sequenzen aufsteigender Elemente in einer Sequenz.
% Ausgabe: Vektor mit den Startpositionen der einzelnen "Gene", wobei das
% das erste ist, das auch am weitesten vorne in der Sequenz sein sollte

len = length( seqIndexes );
g = [];
l = 0;
cGenes = 0;
pos = 0;
i = 1;
posOfFirst = len;
first = len;
lFirst = 0;

while i < len
    if seqIndexes( i+1 ) == seqIndexes( i ) + 1 && seqIndexes( i ) ~= i;
        cGenes = cGenes + 1;
        pos = i;
        i = i + 1;
        while i+1 < len && seqIndexes( i+1 ) == seqIndexes( i ) + 1;
            i = i + 1;
        end
        l( cGenes ) = i - pos + 1;
        g( cGenes ) = pos;
        if first > seqIndexes( pos )
            posOfFirst = pos;
            first = seqIndexes( pos );
        end
        lFirst = i - pos + 1;
    else
        i = i + 1;
    end
end