Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
167 lines (130 sloc) 5.51 KB
def tokens(s):
cursor=0
n=''
while cursor<len(s):
if s[cursor]=='(':
cursor+=1
yield 'OPEN_PAREN',cursor,'('
continue
if s[cursor]==')':
cursor+=1
yield 'CLOSE_PAREN',cursor,')'
continue
if s[cursor]==';':
cursor=len(s)
break
if s[cursor]==',':
cursor+=1
yield 'COMMA',cursor,','
continue
n=''
while cursor<len(s) and s[cursor] not in [',',';',')','(']:
n+=s[cursor]
cursor+=1
if len(n.strip())>0:
yield 'LABEL',cursor,n.strip()
def build_tree(s):
tree={}
curnode=0
parent=-1
new_node=1
tree[0]=-1
labels={}
for (kind,cursor,value) in tokens(s):
if kind=='OPEN_PAREN':
parent=curnode
curnode=new_node
tree[curnode]=parent
new_node=new_node+1
continue
if kind=='LABEL':
x=new_node
new_node+=1
labels[value]=x
tree[x]=curnode
continue
if kind=='CLOSE_PAREN':
curnode=parent
parent=tree[curnode]
continue
return tree,labels
def build_tree2(s):
tree={}
curnode=0
parent=-1
new_node=1
tree[0]=-1
labels={}
prior_kind=None
for (kind,cursor,value) in tokens(s):
if kind=='OPEN_PAREN':
parent=curnode
curnode=new_node
tree[curnode]=parent
new_node=new_node+1
prior_kind=kind
continue
if kind=='LABEL':
if prior_kind=='CLOSE_PAREN':
labels[value]=savenode
else:
x=new_node
new_node+=1
labels[value]=x
tree[x]=curnode
prior_kind=kind
continue
if kind=='CLOSE_PAREN':
if prior_kind=='COMMA':
x=new_node
new_node+=1
tree[x]=curnode
savenode=curnode
curnode=parent
parent=tree[curnode]
prior_kind=kind
continue
if kind=='COMMA':
if prior_kind=='COMMA':
x=new_node
new_node+=1
tree[x]=curnode
prior_kind=kind
continue
if parent!=-1:
raise Exception('ParseError')
else:
return tree,labels
s="((((((Agama_ammon,Latastia_lineatus),(Boiga_atthis,Bos_leporosum)),Turdus_laticauda),(Circus_acutus,Dipus_franckii)),(((((Asthenodipsas_caudatus,Passer_novaeguineae),Testudo_quadriocellata),Oedura_kopsteini),(((Basiliscus_rosmarus,(Lepidobatrachus_viridescens,Streptopelia_breitensteini)),((Butastur_hispida,Ciconia_fiber),Lepus_multifasciata)),sibiricus_aegyptia)),Hirundo_fissipes)),((Aix_erythronotus,Uroplatus_garulla),Almo_guttifer),(((((((((((((((((((((((((Alaus_fasciata,Oceanodroma_kingii),(Marmota_vegans,Phrynosoma_amethistina)),Tupinambus_vitticeps),Corallus_baeri),Ciconia_wogura),Budytes_marcianus),Ortigometra_brachydactyla),Phrynosoma_oenanthe),((((Ambystoma_taezanowskyi,Anolis_adspersus),((Monodon_stejnegeri,(Parus_walti,Phrynops_fulva)),Pogona_alterna)),((Chrysopelea_torquatus,Ninox_monachus),Riparia_cambridgei)),Phoca_carbo)),Aythya_stagnalis),Tropidurus_not),Paramesotriton_docilis),Lycaenopsis_hypomelus),Phormictopus_leucophyllata),Petrocincla_oxycephalum),Vipera_arizonensis),((Almo_carnivorus,Nyctaalus_dulkeitiana),Chelodina_dentata)),(((((((((((((Ambystoma_czerskii,(Fulica_stagnalis,(Haplopelma_multituberculatus,Phrynohyas_himalayanus))),Xenochrophis_caninus),Ptychozoon_semipalmatus),Querquedula_graeca),Haliaetus_caniceps),Machetes_laevis),(Litoria_thibetanus,Otis_grandis)),Uroplatus_platyrhinos),Parus_pardalis),(Camptoloma_constrictor,Leuciscus_iguana)),(Lamprophis_fernandi,Sorex_onocrotalus)),((((((((Boiga_gecko,Tropidurus_guentheri),Euspiza_veredus),Net_turtor),Polypedates_krueperi),Notophthalmus_hispida),Ceratophrys_kingii),(Capella_bairdi,(Paraphysa_marmorata,Sus_taxus))),Tropidurus_geyri)),Scincus_semipalmatus)),Thymallus_tristis),(Phyllopneuste_oenanthe,Psammophis_pardus)),Desnana_parahybana),Haplopelma_quadrivirgata),Egretta_insularis),((((Bronchocela_leptochelis,((Circus_mycterizans,(Dasypeltis_orientalis,(Meles_rufina,Pandinus_troglodytes))),Thymallus_alpestris)),Prunella_celer),Ziphius_bifasciatus),(Motacilla_sujfunensis,Neolycaena_yeltoniensis))),Chrttusia_davidiana));"
x,y='Psammophis_pardus', 'Phrynohyas_himalayanus'
def path_to_root(x,tree,labels):
start_node=labels[x]
path=[start_node]
parent=tree[start_node]
while parent!=-1:
path.append(parent)
parent=tree[parent]
return path
def tree_distance(x,y,tree,labels):
xnode=labels[x]
ynode=labels[y]
d=0
while True:
if xnode<ynode:
ynode=tree[ynode]
d+=1
elif ynode<xnode:
xnode=tree[xnode]
d+=1
elif ynode==xnode:
return d
#tree,labels=build_tree2(s)
#print path_to_root(x,tree,labels)
#print path_to_root(y,tree,labels)
f=open("rosalind_nwck.txt","rU")
data=enumerate(f.readlines())
for i,t in data:
tree,labels=build_tree2(t)
(u,v)=data.next()[1].split()
print tree_distance(u,v,tree,labels),
blank=data.next()[1]
You can’t perform that action at this time.