chbp-2.py

    #this one works
    def orient(x):
        if x[0]=='0':
            return x
        else:
            return ''.join([str(1-int(t)) for t in x])
           
    def analyze(group,character):
        if len(group)==1:
            return int(character[group[0]])
        collect=[[],[]]
        for x in group:       
            z=analyze(x,character)
            if z==-1: 
                return -1
            else:
                collect[z].append(x)
        if len(collect[0])==0:
            return 1
        elif len(collect[1])==0:
            return 0
        else:
            group[:]=[]
            group.append(collect[1])
            group.extend(collect[0])     
            return -1
            
    def lists_to_newick(g):
        if len(g)==1:
            return taxon_name[g[0]]
        else:
            s=''
            for x in g:
                s+=lists_to_newick(x)
                s+=','
        return '(%s)'%(s[:-1])
         
    
    start=[[i] for i in range(len(taxa))]
    
    with open("rosalind_chbp.txt","rU") as f:               
        taxa=f.readline().split()
        characters=[orient(x.strip()) for x in f.readlines()]
             
    taxon_name=dict(zip(range(len(taxa)),taxa))
    
    for t in characters:
        analyze(start,t)
    
    print lists_to_newick(start)