find common ancestor with a dictation of names-CodePudding

I have this dictionary that has a list of names ([child],[parent]). I need help finding whether two or more names, have a ancestor. If they do, then the function should return the single person that is closely related to everyone in the argument input.

Family_tree = { 
        'Steven': 'Mike',       'Josh': 'Mike', 
        'Mike': 'Jackson',           'Jackson': 'Greg', 
        'Drake': 'Bob',     'Greg': 'Calvin',
        'Bob': 'Greg',         'Nathalie':'Amber',
        'Amber': 'Jodie',          'Jodie': 'Calvin',
        'Erick': 'Vincent', 'Vincent': 'Jodie',
        'Emily': 'Sherri',       'Sherri': 'Jodie',
        'Keagan': 'Sherri'}

This is what I have so far, but I do not know what to do next. Could anyone direct me to a post that is similar to this?

def ancestors(names , Family_tree)
        common = ''
        for itr in range(0,len(Family_tree)):

I am not going to pry for a answer, but If you do decide to give one that would be great! Just please be detailed on what you did, so I can improve.

Also, please tell me if this post doesn't make sense. I'll try to explain it better.

CodePudding user response：

Is this sort of what you were looking for?

def ancestors(family_tree):
    connections = {} # dict that'll house everyone's connections
    for p1 in family_tree:# loops through the index values of the dictionary
        if p1 in connections: # if the 'p1' is already an in connections
            if family_tree[p1] not in connections[p1]: # and its not in the list of the second person
                connections[p1].append(family_tree[p1]) # then it adds them to the list
        else:
            connections[p1] = [family_tree[p1]] # otherwise it creates 'p1' in the connections and puts in the second person

        if family_tree[p1] in connections: # same thing but vis versa for the next lines
            if p1 not in connections[family_tree[p1]]:
                connections[family_tree[p1]].append(p1)
        else:
            connections[family_tree[p1]] = [p1]

    return connections

print(ancestors(family_tree))

CodePudding user response：

There's many ways to skin a cat. Just remember that if you just pick one of the answers here and submit it as your own, you won't really have learned anything, and that may come back to bite you.

Try to truly understand the answer you prefer and then try to rewrite it from scratch to make sure you really do before submitting. Some tests you just have to get through, but if you're being tested for a skill you really need, just passing the test may set you up for future embarrassment.

Here's a fairly clean solution:

from functools import reduce

family_tree = {
    'Steven': 'Mike', 'Josh': 'Mike',
    'Mike': 'Jackson', 'Jackson': 'Greg',
    'Drake': 'Bob', 'Greg': 'Calvin',
    'Bob': 'Greg', 'Nathalie': 'Amber',
    'Amber': 'Jodie', 'Jodie': 'Calvin',
    'Erick': 'Vincent', 'Vincent': 'Jodie',
    'Emily': 'Sherri', 'Sherri': 'Jodie',
    'Keagan': 'Sherri'
}


def ancestors(names, parents):
    ancestors = {
        name: [name] for name in names
    }
    while True:
        # if the intersection of all ancestors.values() is not empty, those are the first shared ancestors
        if shared := reduce(lambda s1, s2: s1.intersection(s2), map(set, ancestors.values())):
            return shared
        # remember how many names in the ancestors values in total
        n = sum(map(len, ancestors.values()))
        for name, related in ancestors.items():
            related.extend([parents[ancestor] for ancestor in related if ancestor in parents])
        # check if the number of names has grown, otherwise a common ancestor cannot be found
        if n == sum(map(len, ancestors.values())):
            return None


print(ancestors(['Vincent', 'Sherri'], family_tree))