Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
74 lines (63 sloc) 1.78 KB
from numpy import abs
import itertools
import operator
f = operator.itemgetter(1)
def inv_perm(l):
return([l.index(i)+1 for i in range(1,len(l)+1)])
def prod_perm(p,q):
return([q[p[i-1]-1] for i in range(1,len(p)+1)])
def find_breaks(p):
breakpoints=[]
for i,x in enumerate(p):
if i==0:
if x!=1:
breakpoints.append(0)
continue
if abs(x-p[i-1])>1:
breakpoints.append(i)
continue
if p[-1]!=len(p):
breakpoints.append(len(p))
return(breakpoints)
def rdistance(pl,depth=0):
smaller=[]
small=100
for p in pl:
r=len(p)
z=find_breaks(p)
if len(z)==0:
return(depth)
rr=len(z)
for t,i in enumerate(z):
for j in z[t+1:]:
if j-i>1:
q=p[:]
q[i:j]=reversed(p[i:j])
loss=0
if i==0 and q[0]==1: loss=1
if i>0 and abs(q[i-1]-q[i])==1: loss+=1
if j==r and q[r-1]==len(p): loss+=1
if j<r and abs(q[j-1]-q[j])==1: loss+=1
est=rr-loss
if est==small:
smaller.append(q)
elif est<small:
small=est
smaller=[q]
a=rdistance(smaller,depth+1)
return(a)
f=open("rosalind_rear.txt","rU")
while True:
l=f.readline()
p=map(int,l.split())
l=f.readline()
if len(l)==0:
break
q=map(int,l.split())
c=prod_perm(p,inv_perm(q))
#print c
print rdistance([c]),
l=f.readline()
if len(l)==0:
break
f.close()
You can’t perform that action at this time.