Winner Markus (ones 8)

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

little by little

by Ulf Schwurack

Status: Passed
Results: 159216.54 (cyc: 18)
CPU Time: 0.3615
Score: 15931.7
Submitted at: 2007-11-12 07:23:43 UTC
Scored at: 2007-11-12 07:24:46 UTC

Current Rank: 2546th

Comments
Ulf Schwurack
12 Nov 2007
Another little improvement...
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: Position und L?nge _des_ "Gens", das am weitesten vorne in die
% Sequenz geh?rt

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

posOfCand = 1;

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