Diffing "code cleanup 9_4" and "code cleanup 9_5"

Title: code cleanup 9_4 code cleanup 9_5
Author: Markus Markus
Submitted: 2007-11-11 17:12:50 UTC 2007-11-11 17:14:35 UTC
Status: Passed Passed
Score: 5958.24 5966.96
Result: 59038.46 (cyc: 14) 59136.46 (cyc: 14)
CPU Time: 64.5337 64.0995
Code:
function moves = solver(sequence,target,budget)

last = 2;
if budget - last > 0
	moves = oldconvolutedsolver(sequence,target,budget-last);
	moves2 = ukilsolver(doMoves(sequence,moves),target,budget-size(moves,1));
	moves = [moves; moves2];
else 
moves = markussolver(sequence,target,budget);

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function moves=oldconvolutedsolver(sequence,target,budget)
seq1=sequence; score1 = 67108864;

L = length(target);
if L < 97
    moves1 = markussolver(sequence, target, budget);
    score1 = findscore(sequence, target, budget, moves1);
    if score1<5
        moves=moves1;
        return
    end
end

moves = ukilsolver(sequence, target, budget);
score2 = findscore(sequence,target,budget,moves);
if score1<score2,
	moves = moves1;
end

nOfMoves = size(moves,1);
runningScore=zeros(nOfMoves,1);
seq2 = seq1;
for i=1:nOfMoves
	seq2=doMove(seq2,moves(i,1),moves(i,2),moves(i,3),moves(i,4));
	runningScore(i)=sum(abs(seq2-target));
end
[Dim, index] = min(runningScore);
%if index < nOfMoves
	moves=moves(1:index, :);
%end

seq3   = doMoves(seq1,moves);
score3 = sum(abs(seq3-target));
mybudget = budget-size(moves,1);
if mybudget > 0
	tempmoves=ukilaccuratesolver(seq3,target,mybudget);
	seq4=doMoves(seq3,tempmoves);
	score4=sum(abs(seq4-target));
	if score4<score3
		moves=[moves;tempmoves];
	end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function moves=ukilaccuratesolver(s,t,budget)
moves = zeros(budget,4);
L = length(s);
for iter=1:budget
	diff=abs(s-t);
	[val,index]=sort(diff,'descend');

	% first do simple
	value = inf(4,5);
	for i=1:2
		diff2 = abs(s(index(i))-t);
		[val2, index2] = sort(diff2);
                for j=1:3
		[localmoves, score] = removefromto(s,t,index(i),index2(j));
		if ~isempty(localmoves)
			value(i,:) = [localmoves score];
		end
                end
	end
	[mv,mi]=min(value(:,5));

	if ~isempty(mi)
		localmoves=value(mi,1:4);
		moves(iter,:) = localmoves;
		s = doMove(s,localmoves(1), localmoves(2), localmoves(3), localmoves(4));
	else
		moves = moves(1:iter-1,:);
		return
	end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function moves = ukilsolver(sequence,target,budget)
seq2=sequence;
tar2=target;
A6=seq2;
L = length(target);
%tscore1=sum(abs(seq2-tar2));
moves = new2solver(seq2, tar2, budget);
O4=doMoves(seq2,moves);
tscore2=sum(abs(O4-tar2));
moves2 = anothersolver(seq2, tar2, budget);
O4=doMoves(seq2,moves2);
tscore3=sum(abs(O4-tar2));
if tscore2>tscore3
	moves = moves2;
end
nOfMoves = size(moves,1);
Q5=zeros(nOfMoves,L);
N7=A6;
for i=1:nOfMoves
	N7=doMove(N7,moves(i,1),moves(i,2),moves(i,3),moves(i,4));
	Q5(i,:)=N7-tar2;
end
Q5=sum(abs(Q5),2);
[val,index]=min(Q5);
if index<nOfMoves
	moves=moves(1:index,:);
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function moves=anothersolver(seq2,MC2,budget)
moves=zeros(budget,4);
L = length(seq2);
for i=1:budget
	diff=abs(seq2-MC2);
	[Dim,index]=max(diff);
	diff2=abs(seq2(index)-MC2);[N0T,J_m]=min(diff2);
	newmoves=removefromto(seq2,MC2,index,J_m);
	if ~isempty(newmoves)
		moves(i,:) = newmoves;
		seq2=doMoves(seq2,newmoves);
	end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [moves,INITIAL]=removefromto(seq2,tar2,index,index2)
L = length(seq2);
INITIAL=sum(abs(seq2-tar2));
tempmoves=removefromtosub1(seq2,index,index2);
if isempty(tempmoves)
	moves=ones(0,4);
else
	n1 = size(tempmoves,1);
	sn1=zeros(n1,L);
	tscore1=zeros(n1,L);
	for i=1:n1
		sn1(i,:)=doMove(seq2,tempmoves(i,1),tempmoves(i,2),tempmoves(i,3),tempmoves(i,4));
		tscore1(i,:)=sn1(i,:)-tar2;
	end
		tscore1=sum(abs(tscore1),2);
	[minval,minindex1]=min(tscore1);
	moves=tempmoves(minindex1,:);
	INITIAL=minval;
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function tempmoves=removefromtosub1(seq2,index,index2)
if index<index2
	N=abs(index2-index)+1;
	tempmoves = zeros(N,4);
	for i=1:N
		tempmoves(i,:)=[i index index2-i+1 1];
	end
	N=min([index-1,numel(seq2)-index2])+1;
	tempmoves2 = zeros(N-1,4);
	for i=2:N
		tempmoves2(i-1,:)=[i index-i+1 index2 1];
	end
	N=index;
	tempmoves3 = zeros(N-1,4);
	for i=2:N
		tempmoves3(i-1,:)=[i index-i+1 index2-i+1 0];
	end
	N=numel(seq2)-index2+1;
	tempmoves4 = zeros(N-1,4);
	for i=2:N
		tempmoves4(i-1,:)=[i index index2 0];
	end
elseif index>=index2
	N=abs(index2-index)+1;
	tempmoves = zeros(N,4);
	for i=1:N
		tempmoves(i,:)=[i index-i+1 index2 1];
	end
	N=min([numel(seq2)-index,index2-1])+1;
	tempmoves2 = zeros(N-1,4);
	for i=2:N
		tempmoves2(i-1,:)=[i index index2-i+1 1];
	end
	N=numel(seq2)-index+1;
	tempmoves3 = zeros(N-1,4);
	for i=2:N
		tempmoves3(i-1,:)=[i index index2 0];
	end
	N=index2;
	tempmoves4 = zeros(N-1,4);
	for i=2:N
		tempmoves4(i-1,:)=[i index-i+1 index2-i+1 0];
	end
end
tempmoves=[tempmoves;tempmoves2;tempmoves3;tempmoves4];

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function moves = new2solver(sequence, target, budget)
L = length(sequence);cumSumShiftLeftMatrix = zeros(L, L+1);
cumSumShiftRightMatrix = cumSumShiftLeftMatrix;cumSumShiftLeftRevMatrix = cumSumShiftLeftMatrix;cumSumShiftRightRevMatrix = cumSumShiftLeftMatrix;moves = zeros(budget,4);moveNr = 1;
while 1
	for k = 0:L-1
		index = 2:L-k+1;target1 = target(index-1);
		target2 = target(k+1:L);
        cumSumShiftLeftMatrix (k+1,index) = sequence(k+1:L) - target1;
		cumSumShiftRightMatrix (k+1,index) = sequence(1:L-k) - target2;
		cumSumShiftLeftRevMatrix (k+1,index) = sequence(L-k:-1:1) - target1;
		cumSumShiftRightRevMatrix(k+1,index) = sequence(L:-1:k+1) - target2;
    end
    cumSumShiftLeftMatrix=cumsum(abs(cumSumShiftLeftMatrix),2);
    cumSumShiftRightMatrix=cumsum(abs(cumSumShiftRightMatrix),2);
    cumSumShiftLeftRevMatrix=cumsum(abs(cumSumShiftLeftRevMatrix),2);
    cumSumShiftRightRevMatrix=cumsum(abs(cumSumShiftRightRevMatrix),2);
	cumSumFromleft = cumSumShiftLeftMatrix(1,:);cumSumFromRight = cumSumFromleft(L+1) - cumSumFromleft;
	bestscore = cumSumFromleft(L+1);relMove = 1 - moveNr / budget;
    tmpscore = bestscore;
	%   curMoveLengthVector = L:-1:1;
	curMoveLengthVector = [(33:4:L-1), 32, 29:-1:1]; %new
	curMoveLengthVector(curMoveLengthVector >= L) = [];
	%    zeroIndex = (abs(sequence - target) < 1e-3)*round(relMove-0.3);
	zeroIndex = (abs(sequence - target) < 1e-3)*floor(relMove-0.3);
	blen=1;bkFrom=1;bkTo=1;bFlip=false;

	for len = curMoveLengthVector
		kMax = L - len + 1;
		for kFrom = 1:kMax
			for kTo = 1:kMax*~zeroIndex(kFrom)

				if kFrom <= kTo
					score1 =cumSumFromleft(kFrom) + cumSumShiftLeftMatrix(len+1,kTo) +cumSumFromRight(kTo+len) - cumSumShiftLeftMatrix(len+1,kFrom);
				else
					score1 =cumSumFromleft(kTo) + cumSumShiftRightMatrix(len+1,kFrom) + cumSumFromRight(kFrom+len) - cumSumShiftRightMatrix(len+1,kTo);
                end

				if len ~= 1 
					seqRevIndex = L-kFrom-len+2;
					if kTo >= seqRevIndex
						curScore = score1 +cumSumShiftRightRevMatrix(kTo - seqRevIndex + 1, seqRevIndex+len) - ...
							cumSumShiftRightRevMatrix(kTo - seqRevIndex + 1, seqRevIndex);
					else
						curScore = score1 + ...
							cumSumShiftLeftRevMatrix(seqRevIndex - kTo + 1, kTo+len) -cumSumShiftLeftRevMatrix(seqRevIndex - kTo + 1, kTo);
					end
					if curScore < bestscore
						bestscore = curScore;blen=len;bkFrom=kFrom;bkTo=kTo;
						bFlip=true;
					end
                end

                if len<=L/2
                    if kFrom <= kTo
                        curScore = score1 +cumSumShiftRightMatrix(kTo-kFrom+1, kFrom+len) -cumSumShiftRightMatrix(kTo-kFrom+1, kFrom);
                    else
                        curScore = score1 + cumSumShiftLeftMatrix(kFrom-kTo+1, kTo+len) -cumSumShiftLeftMatrix(kFrom-kTo+1, kTo);
                    end
                    if curScore < bestscore
                        bestscore = curScore;blen=len;bkFrom=kFrom;bkTo=kTo;
                        bFlip=false;
                    end
                end
			end
		end
	end
	moves(moveNr,:)=[blen bkFrom bkTo bFlip];sequence = doMove(sequence, blen, bkFrom, bkTo, bFlip);
	moveNr = moveNr + 1;
	if (moveNr > budget)+(tmpscore==bestscore)
        moves = moves(1:moveNr-1,:);
		return
	end
end


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function scorecheck = findscore(sequence,target,budget,moves)
seq = splice(sequence,moves,budget);
scorecheck = sum(abs(seq-target));


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
function seq = splice(seq,moves,budget)
if size(moves,1)>budget
	moves = moves(1:budget,:);
end
Z65 = numel(seq);moves(:,1) = max(1,min(Z65,moves(:,1)));
moves(:,2) = max(1,min(Z65-moves(:,1)+1,moves(:,2)));
moves(:,3) = max(1,min(Z65-moves(:,1)+1,moves(:,3)));
moves(:,4) = moves(:,4) ~= 0;
for i =1:size(moves,1)
	le = moves(i,1);ai = moves(i,2);bi = moves(i,3);
	flip = moves(i,4);
	if flip
		if ai>bi
			seq = seq([1:bi-1 ai+le-1:-1:ai bi:ai-1 ai+le:end]);
		else
			seq = seq([1:ai-1 ai+le:bi+le-1 ai+le-1:-1:ai bi+le:end]);
		end
	else
		if ai>bi
			seq = seq([1:bi-1 ai:ai+le-1 bi:ai-1 ai+le:end]);
		else
			seq = seq([1:ai-1 ai+le:bi+le-1 ai:ai+le-1 bi+le:end]);
		end
	end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function moves = markussolver(sequence, target, budget)
moveLengthVector = [14 12 9 8 7];
moveLengthThresh = [0.9 0.6 0.3 0.1 -1];
L = length(sequence);
index = moveLengthVector > L;
moveLengthVector(index) = [];
moveLengthThresh(index) = [];
cumSumShiftLeftMatrix = zeros(L, L+1);
cumSumShiftRightMatrix = cumSumShiftLeftMatrix;
cumSumShiftLeftRevMatrix = cumSumShiftLeftMatrix;
cumSumShiftRightRevMatrix = cumSumShiftLeftMatrix;
moves = zeros(budget,4);
moveNr = 1;
while moveNr <= budget
	for k = 0:L-1
		index = 2:L-k+1;
		target1 = target(index-1);
		target2 = target(k+1:L);
        cumSumShiftLeftMatrix (k+1,index) = sequence(k+1:L) - target1;
		cumSumShiftRightMatrix (k+1,index) = sequence(1:L-k) - target2;
		cumSumShiftLeftRevMatrix (k+1,index) = sequence(L-k:-1:1) - target1;
		cumSumShiftRightRevMatrix(k+1,index) = sequence(L:-1:k+1) - target2;
    end
    cumSumShiftLeftMatrix=cumsum(abs(cumSumShiftLeftMatrix),2);
    cumSumShiftRightMatrix=cumsum(abs(cumSumShiftRightMatrix),2);
    cumSumShiftLeftRevMatrix=cumsum(abs(cumSumShiftLeftRevMatrix),2);
    cumSumShiftRightRevMatrix=cumsum(abs(cumSumShiftRightRevMatrix),2);
	cumSumFromleft = cumSumShiftLeftMatrix(1,:);
	cumSumFromRight = cumSumFromleft(L+1) - cumSumFromleft;
	bestscore = cumSumFromleft(L+1);
    tmpscore=bestscore;
	relMove = 1 - moveNr / budget;
	moveLengthIndex = find(relMove >= moveLengthThresh, 1, 'first');
	curLen = moveLengthVector(moveLengthIndex);
	curMoveLengthVector = [31 27 21 curLen+4 curLen+3 curLen+2 curLen 6 5 4 3 2 1];
	curMoveLengthVector(curMoveLengthVector >= L) = [];
	curMoveLengthVector = fliplr(unique(curMoveLengthVector));
	zeroIndex = (abs(sequence - target) < 1e-3)*round(relMove-0.3);
	%   zeroIndex = (abs(sequence - target) < 1e-3)*floor(relMove-0.3);
	blen=1;bkFrom=1;bkTo=1;bFlip=false;
	for len = curMoveLengthVector
		kMax = L - len + 1;
		for kFrom = 1:kMax
			for kTo = 1:(kFrom-1)*~zeroIndex(kFrom)
				score1 =cumSumFromleft(kTo) + cumSumShiftRightMatrix(len+1,kFrom) + ...
					cumSumFromRight(kFrom+len) - cumSumShiftRightMatrix(len+1,kTo);
				if len == 1
					curScore=score1+cumSumShiftLeftMatrix(kFrom-kTo+1, kTo+len) -cumSumShiftLeftMatrix(kFrom-kTo+1, kTo);
				else
					seqRevIndex = L-kFrom-len+2;
					if kTo >= seqRevIndex
						curScore = score1 +cumSumShiftRightRevMatrix(kTo - seqRevIndex + 1, seqRevIndex+len) - ...
							cumSumShiftRightRevMatrix(kTo - seqRevIndex + 1, seqRevIndex);
					else
						curScore = score1 + ...
							cumSumShiftLeftRevMatrix(seqRevIndex - kTo + 1, kTo+len) -cumSumShiftLeftRevMatrix(seqRevIndex - kTo + 1, kTo);
					end
				end
				if curScore < bestscore
					bestscore = curScore;
					blen=len;
					bkFrom=kFrom;
					bkTo=kTo;
					bFlip=true;
				end
			end
			for kTo = kFrom:kMax
				score1 =cumSumFromleft(kFrom) + cumSumShiftLeftMatrix(len+1,kTo) +cumSumFromRight(kTo+len) - cumSumShiftLeftMatrix(len+1,kFrom);
				if len == 1
					curScore = score1 +cumSumShiftRightMatrix(kTo-kFrom+1, kFrom+len) -cumSumShiftRightMatrix(kTo-kFrom+1, kFrom);
				else
					seqRevIndex = L-kFrom-len+2;
					if kTo >= seqRevIndex
						curScore = score1 +cumSumShiftRightRevMatrix(kTo - seqRevIndex + 1, seqRevIndex+len) - ...
							cumSumShiftRightRevMatrix(kTo - seqRevIndex + 1, seqRevIndex);
					else
						curScore = score1 + ...
							cumSumShiftLeftRevMatrix(seqRevIndex - kTo + 1, kTo+len) -cumSumShiftLeftRevMatrix(seqRevIndex - kTo + 1, kTo);
					end
				end
				if curScore < bestscore
					bestscore = curScore;blen=len;bkFrom=kFrom;bkTo=kTo;
					bFlip=true;
				end
			end
		end
	end
	moves(moveNr,:)=[blen bkFrom bkTo bFlip];sequence = doMove(sequence, blen, bkFrom, bkTo, bFlip);
	moveNr = moveNr + 1;
	if (moveNr > budget)+(tmpscore==bestscore)
        moves = moves(1:moveNr-1,:);
		return
	end
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function seq = doMove(seq, le, ai, bi, flip)
	if flip
		if ai>bi
			seq = seq([1:bi-1 ai+le-1:-1:ai bi:ai-1 ai+le:end]);
		else
			seq = seq([1:ai-1 ai+le:bi+le-1 ai+le-1:-1:ai bi+le:end]);
		end
	else
		if ai>bi
			seq = seq([1:bi-1 ai:ai+le-1 bi:ai-1 ai+le:end]);
		else
			seq = seq([1:ai-1 ai+le:bi+le-1 ai:ai+le-1 bi+le:end]);
		end
	end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function seq = doMoves(seq,moves)

for i =1:size(moves,1)
	le = moves(i,1);
	ai = moves(i,2);
	bi = moves(i,3);
	if moves(i,4)
		if ai>bi
			seq = seq([1:bi-1 ai+le-1:-1:ai bi:ai-1 ai+le:end]);
		else
			seq = seq([1:ai-1 ai+le:bi+le-1 ai+le-1:-1:ai bi+le:end]);
		end
	else
		if ai>bi
			seq = seq([1:bi-1 ai:ai+le-1 bi:ai-1 ai+le:end]);
		else
			seq = seq([1:ai-1 ai+le:bi+le-1 ai:ai+le-1 bi+le:end]);
		end
	end
end