CODEWITHSUNDEEP
pythongraphpath-finding
error_null_pointer
error_null_pointer

Reputation: 455

Merging tuples based of common first and last element

I am not sure why I am having issues getting this to work, I am new to python, but the idea feels like it should be simple.

I have a list of tuples like:

(a,b),(b,c),(b,d),(b,a),(c,l),(d,y),(y,l)

Given a start point, lets say a, and an end point l.

I want to make all the paths. (a,b,c,l) (a,b,d,y,l)

I have made a lot of attempts and they all keep breaking with unhelpful error messages like:

File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths
  File "<stdin>", line 20, in findAllPaths

Each of those methods I think is over complicated. Is there an easy python way of doing it?

EDIT to add some clarity:

My goal is to travel the tuples to find all the different(non circular) paths to an end goal. So in the example I above I wanted to travel from a -> l.

So the program would check all 'a' connections to and make the new tuples above.

So the program will take all the paths it can until it finds l, if it runs out of paths and doesn't find the location it should return an empty list.

Lastly, a->b and b-> a, but that will create a cycle that we ant to ignore.

Upvotes: 0

Views: 61

Answers (2)

Matthias Fripp
Matthias Fripp

Reputation: 18645

Here's a fairly concise way to do it:

def find_paths(segments, start, end):
    full_paths = []
    part_paths = [(start,)]
    while len(part_paths) > 0:
        new_part_paths = []
        for p in part_paths:
            for s in segments:
                if s[0] == p[-1] and s[-1] not in p:
                    # segment s should be added to path p
                    new_path = p + s[1:]
                    if new_path[-1] == end:
                        full_paths += [new_path]
                    else:
                        new_part_paths += [new_path]
        part_paths = new_part_paths
    return full_paths

a = 'a'; b = 'b'; c = 'c'; d = 'd'; l = 'l'; y = 'y'
print find_paths([(a,b),(b,c),(b,d),(b,a),(c,l),(d,y),(y,l)], a, l)

...

[('a', 'b', 'c', 'l'), ('a', 'b', 'd', 'y', 'l')]

Upvotes: 1

Bear
Bear

Reputation: 572

you want to merge 8 lists into 2 lists? or you want to check in those 8 lists what has been repeated more? i didn't understand (a,b,c,l) (a,b,d,y,l) how did you get this?

Edit: okay, wrote it really fast you probably will find some weird name in it, and also it can be more optimize but it do the job and good place to start from.

def check_connection(Connection_DNA_List, Preview=True):
    DNA_Path = []
    for DNA_tuples in Connection_DNA_List:
        DNA_Path = check_DNA_List(newValue=DNA_tuples, Path_list=DNA_Path, Preview=False)

    if Preview:
        print DNA_Path


def check_DNA_List(newValue,Path_list, Preview=False):
    FinalList = []
    if Path_list:
        for eachpath in Path_list:
            newList, newfile = check_DNA(newValue=newValue, DNA_List=eachpath, Preview=False)
            if newfile:
                FinalList.append(eachpath)
            if "A" in newList:
                FinalList.append(newList)
    else:
        newList, newfile = check_DNA(newValue=newValue, DNA_List=Path_list, Preview=False)
        if "A" in newList:
                FinalList.append(newList)
                FinalList.append(newList)

    if Preview:
        print "Current Path List: ", Path_list
        print "New Value: %s %s" %newValue
        print "New Path List: %s" %FinalList
        print "------------------------------------"
    return FinalList

def check_DNA(newValue, DNA_List, Preview=False):
    newDNA = []
    newList = False
    if DNA_List:
        if newValue[0] in DNA_List and newValue[1] in DNA_List:
            newDNA = DNA_List
            newList = False
        elif newValue[0] in DNA_List[-1] and newValue[1] not in DNA_List:
            newDNA = DNA_List
            newDNA.append(newValue[1])
            newList = False
        else:
            newList = True
            newDNA.append(newValue[0])
            newDNA.append(newValue[1])
    else:
        newList = True
        newDNA.append(newValue[0])
        newDNA.append(newValue[1])
    if Preview:
        print "Current List: %s" %DNA_List
        print "New Value: %s %s" %newValue
        print "Created List: %s" %newDNA
        print "Is it a newList? %s" %newList
        print "------------------------------------"
    return newDNA ,newList

a = "A"
b = "B"
c = "C"
d = "D"
y = "Y"
l = "L"

DNAList = [(a,b),(b,c),(b,d),(b,a),(c,l),(d,y),(y,l)]
check_connection(Connection_DNA_List=DNAList)

Note: you find lots of Preview, i usually write them for debugging, it's nice way to know what it is doing, you can turn them off if you don't want to see what them.

Upvotes: 1

Related Questions