# Diffing "M07" and "last go"

 Title: M07 last go Author: MikeR nathan Submitted: 2007-11-14 11:06:56 UTC 2007-11-14 11:59:01 UTC Status: Passed Passed Score: 5175.12 5179.57 Result: 51253.21 (cyc: 17) 51241.50 (cyc: 18) CPU Time: 61.2678 63.32 Code: ```function moves = solver(sequence,target,budget) last = 2; if budget > last moves = oldconvolutedsolver(sequence,target,budget-last); moves2 = new2solver(doMoves(sequence,moves,length(sequence)),target,budget-size(moves,1)); score2 = findscore(doMoves(sequence,moves,length(sequence)),target,budget-size(moves,1),moves2); moves3 = anothersolver(doMoves(sequence,moves,length(sequence)),target,budget-size(moves,1)); score3 = findscore(doMoves(sequence,moves,length(sequence)),target,budget-size(moves,1),moves3); if score30 Delta = Delta.*(1 + rfac*rand(n)); end [dmin,i1] = min(Delta); [dmin,j1] = min(dmin); i1=i1(j1); ij =[i1 j1]; i1 = min(ij); j1=max(ij); % now see if it pays to include neighbours so that we swap a band i1 to i2 with a band j1 to j2 dcum1 = Delta(i1,j1); i2=i1;j2=j1; % go R (i2>i1) first: keepgoing = (j2=0) + (j2==n) + (i2>=j1-1) ); end % go L (decreasing i1) : keepgoing = (i1>1 )*(i2=0) + (i1==1) + (i2>=j1-1) ); end L = i2-i1+1; moves1 = [L j1 i1 0; L i1+L j1 0]; % now repeat the exercise for a flipped sequence dcum2 = Delta(i1,j1); i2=i1;j2=j1; % go R (increasing i2) first: keepgoing = i2=0) + (i2>=j1-1) ); end % go L (decreasing i1) : keepgoing = (i1>1)*(i2=0) + (i1==1) + (j2==n)); end L = i2-i1+1; moves2 = [L j1 i1 1; L i1+L j1 1]; if dcum1<=dcum2 moves(i:i+1,:) = moves1; else moves(i:i+1,:) = moves2; end L= moves(i,1); j1 = moves(i,2); i1=moves(i,3); % note the affected genes sequence1(1,:) = doMoves(sequence,moves(i,:),n); score1(1) = sum(abs(sequence1(1,:)-target)); sequence1(2,:) = doMoves(sequence1(1,:),moves(i+1,:),n); score1(2) = sum(abs(sequence1(2,:)-target)); sequence1(3,:) = doMoves(sequence,moves(i+1,:),n); score1(3) = sum(abs(sequence1(3,:)-target)); [minscore1,ims] = min(score1); sequence=sequence1(ims,:); runningScore(i:i+1) = score1(1:2); if ims==3 moves(i,:) = moves(i+1,:); runningScore(i) = score1(3); i=i+1; else i=i+ims; end % flag the altered bands in the sequence: altered = false(1,n); altered(i1:i1+L-1) = true; altered(j1:j1+L-1) = true; end if i==budget s = abs(sequence-target); [maxs,imaxs]=max(s); % worst current gene [mins,imins1] = min(abs(target-sequence(imaxs))) ; % best place to put the worst gene move1 = [1 imaxs imins1 false]; seq1 = doMoves(sequence,move1,n); s1= sum(abs(seq1-target)); [mins,imins2] = min(abs(target(imaxs)-sequence)) ; % best gene to put in the worst place move2 = [1 imins2 imaxs false]; seq2 = doMoves(sequence,move2,n); s2= sum(abs(seq2-target)); if s1 0 tempmoves=ukilaccuratesolver(seq3,target,mybudget); seq4=doMoves(seq3,tempmoves,L); score4=sum(abs(seq4-target)); if score4=index2 N=abs(index2-index)+1; c = (1:N)'; w = ones(N,1); tempmoves1 = [c (index+1)-c index2*w w]; N=min([numel(seq2)-index,index2-1])+1; c = (2:N)'; w = ones(N-1,1); tempmoves2 = [c index*w (index2+1)-c w]; N=numel(seq2)-index+1; c = (2:N)'; z = zeros(N-1,1); tempmoves3 = [c index+z index2+z z]; N=index2; c = (2:N)'; z = zeros(N-1,1); tempmoves=[tempmoves1;tempmoves2;tempmoves3;[c (index+1)-c (index2+1)-c z]]; end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function moves = new2solver(sequence, target, budget) swap_counter=2; sequence_ini=sequence; L = length(sequence);cumSumShiftLeftMatrix = zeros(L, L+1); cumSumShiftRightMatrix = cumSumShiftLeftMatrix;cumSumShiftLeftRevMatrix = cumSumShiftLeftMatrix;cumSumShiftRightRevMatrix = cumSumShiftLeftMatrix;moves = zeros(budget,4);moveNr = 1; while moveNr <= budget for k = 1:L index = 2:L-k+2; target1 = target(index-1); target2 = target(k:L); cumSumShiftLeftMatrix(k,index) = sequence(k:L) - target1; cumSumShiftRightMatrix(k,index) = sequence(1:L-k+1) - target2; cumSumShiftLeftRevMatrix(k,index) = sequence(L-k+1:-1:1) - target1; cumSumShiftRightRevMatrix(k,index) = sequence(L:-1:k) - 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 = moveNr/budget; tmpscore = bestscore; curMoveLengthVector = [(33:4:L-1), 32, 29:-1:1]; curMoveLengthVector(curMoveLengthVector >= L) = []; zeroIndex = (abs(sequence - target) < 1e-3)*floor(relMove); blen=1;bkFrom=1;bkTo=1;bFlip=false; for len = curMoveLengthVector cssLm = cumSumShiftLeftMatrix(len+1,:); cssRm = cumSumShiftRightMatrix(len+1,:); kMax = L - len + 1; for kFrom = 1:kMax for kTo = 1:kMax*~zeroIndex(kFrom) if kFrom <= kTo score1 =cumSumFromleft(kFrom) + cssLm(kTo) +cumSumFromRight(kTo+len) - cssLm(kFrom); score0 = cumSumFromleft(kFrom) +cumSumFromRight(kTo+len); score1 = score0 + cssLm(kTo) - cssLm(kFrom); else score1 =cumSumFromleft(kTo) + cssRm(kFrom) + cumSumFromRight(kFrom+len) - cssRm(kTo); score0 = cumSumFromleft(kTo) + cumSumFromRight(kFrom+len); score1 = score0 + cssRm(kFrom) - cssRm(kTo); end if score0= 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 end moves(moveNr,:)=[blen bkFrom bkTo bFlip];sequence = doMove(sequence, blen, bkFrom, bkTo, bFlip, L); swap_counter=swap_counter-1; if swap_counter<=0 % if moveNr>1 for jj = 1:2; rfac = (jj>1)*0.8; seq1 = splice(sequence_ini,moves,moveNr-2); [movesS,score]=swapper(seq1,target,2,rfac); if score < bestscore moves(moveNr-1:moveNr,:) = movesS; bestscore = score; sequence = splice(seq1,movesS,2); swap_counter=2; end end end moveNr = moveNr + 1; if 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)); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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) sequence_ini=sequence; moveLengthVector = [19 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 = 1:L index = 2:L-k+2; target1 = target(index-1); target2 = target(k:L); cumSumShiftLeftMatrix(k,index) = sequence(k:L) - target1; cumSumShiftRightMatrix(k,index) = sequence(1:L-k+1) - target2; cumSumShiftLeftRevMatrix(k,index) = sequence(L-k+1:-1:1) - target1; cumSumShiftRightRevMatrix(k,index) = sequence(L:-1:k) - 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:-2: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); blen=1;bkFrom=1;bkTo=1;bFlip=false; for len = curMoveLengthVector cssLm = cumSumShiftLeftMatrix(len+1,:); cssRm = cumSumShiftRightMatrix(len+1,:); kMax = L - len + 1; for kFrom = 1:kMax for kTo = 1:(kFrom-1)*~zeroIndex(kFrom) score1 =cumSumFromleft(kTo) + cssRm(kFrom) + ... cumSumFromRight(kFrom+len) - cssRm(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 end end end moves(moveNr,:)=[blen bkFrom bkTo bFlip];sequence = doMove(sequence, blen, bkFrom, bkTo, bFlip, L); swap_counter=swap_counter-1; if swap_counter<=0 % if moveNr>1 for jj = 1:2; rfac = (jj>1)*0.8; seq1 = splice(sequence_ini,moves,moveNr-2); [movesS,score]=swapper(seq1,target,2,rfac); if score < bestscore moves(moveNr-1:moveNr,:) = movesS; bestscore = score; sequence = splice(seq1,movesS,2); swap_counter=2; end end end moveNr = moveNr + 1; if 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)); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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) sequence_ini=sequence; moveLengthVector = [19 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 = 1:L index = 2:L-k+2; target1 = target(index-1); target2 = target(k:L); cumSumShiftLeftMatrix(k,index) = sequence(k:L) - target1; cumSumShiftRightMatrix(k,index) = sequence(1:L-k+1) - target2; cumSumShiftLeftRevMatrix(k,index) = sequence(L-k+1:-1:1) - target1; cumSumShiftRightRevMatrix(k,index) = sequence(L:-1:k) - 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:-2: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); blen=1;bkFrom=1;bkTo=1;bFlip=false; for len = curMoveLengthVector cssLm = cumSumShiftLeftMatrix(len+1,:); cssRm = cumSumShiftRightMatrix(len+1,:); kMax = L - len + 1; for kFrom = 1:kMax for kTo = 1:(kFrom-1)*~zeroIndex(kFrom) score1 =cumSumFromleft(kTo) + cssRm(kFrom) + ... cumSumFromRight(kFrom+len) - cssRm(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) + cssLm(kTo) +cumSumFromRight(kTo+len) - cssLm(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, L); % if swap_counter<=0 if moveNr>1 for jj = 1:2 rfac = (jj>1)*0.15; seq1 = splice(sequence_ini,moves,moveNr-2); [movesS,score]=swapper(seq1,target,2,rfac); if score < bestscore moves(moveNr-1:moveNr,:) = movesS; bestscore = score; sequence = splice(seq1,movesS,2); end end end moveNr = moveNr + 1; if tmpscore==bestscore moves = moves(1:moveNr-1,:); return end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function seq = oldsplice(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 = doMove(seq, le, ai, bi, flip, L) if flip if ai>bi seq = seq([1:bi-1 ai+le-1:-1:ai bi:ai-1 ai+le:L]); else seq = seq([1:ai-1 ai+le:bi+le-1 ai+le-1:-1:ai bi+le:L]); end else if ai>bi seq = seq([1:bi-1 ai:ai+le-1 bi:ai-1 ai+le:L]); else seq = seq([1:ai-1 ai+le:bi+le-1 ai:ai+le-1 bi+le:L]); end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function seq = doMoves(seq,moves,L) 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:L]); else seq = seq([1:ai-1 ai+le:bi+le-1 ai+le-1:-1:ai bi+le:L]); end else if ai>bi seq = seq([1:bi-1 ai:ai+le-1 bi:ai-1 ai+le:L]); else seq = seq([1:ai-1 ai+le:bi+le-1 ai:ai+le-1 bi+le:L]); end end end```