How To Keep Looping Within A Python Dictionary To Search For Values?

parent = {'Amy':'Ben', 'May':'Tom', 'Tom':'Ben', 'Ben':'Howard', 'Howard':'George', 'Frank':'Amy', 'Joe':'Bill', 'Bill':'Mary', 'Mary':'Philip', 'Simon':'Bill', 'Zoe':'Mary'} T

Solution 1:

Here is your answer using recursion:

defis_ancestor(name1, name2, pdict):

    try:
        if pdict[name1] == name2:
            returnTrueelse:
            return is_ancestor(pdict[name1], name2, pdict)
    except KeyError:
        returnFalse

First it checks if it has found a direct ancestor, if not, checks the next generation by recursing over the same function. The KeyError exception gets triggered if the ancestor is not found, indicating that name2 is not an ancestor of name1.

Solution 2:

You can use recursion instead of a loop.

defis_ancestor(name1, name2, pdict):
    parent = pdict.get(name2, None)
    ifnot parent:
        returnFalseelif parent == name1:
        returnTrueelse:
        return is_ancestor(name1, parent, pdict)

parents = {'Amy':'Ben', 'May':'Tom', 'Tom':'Ben',
 'Ben':'Howard', 'Howard':'George', 'Frank':'Amy',
 'Joe':'Bill', 'Bill':'Mary', 'Mary':'Philip', 'Simon':'Bill',
 'Zoe':'Mary'}

print(is_ancestor("Amy", "Ben", parents))
print(is_ancestor("Ben", "Amy", parents))
print(is_ancestor("Howard", "Amy", parents))

The function gets the parent of name2. If no parent is found, we've reached the base case and we return False. Otherwise, we check to see if the parent found is the one we're looking for. If it is we return True. If not, we look to see if that person's parent is the ancestor we're looking for. This will keep recursing until we either reach the ancestor we're looking for, or we hit a person with no parent in the dictionary.

Solution 3:

You can do something like this:

parent = {
    'Amy':'Ben', 
    'May':'Tom', 
    'Tom':'Ben', 
    'Ben':'Howard', 
    'Howard':'George', 
    'Frank':'Amy', 
    'Joe':'Bill', 
    'Bill':'Mary', 
    'Mary':'Philip', 
    'Simon':'Bill', 
    'Zoe':'Mary',
}


defis_ancestor(name1, name2, pdict):
    while name1 in pdict:
        name1 = pdict[name1]

        if name1 == name2:
            returnTruereturnFalseassert is_ancestor('Amy', 'Amy',parent) == Falseassert is_ancestor('Amy', 'Ben',parent) == Trueassert is_ancestor('Ben', 'Amy',parent) == Falseassert is_ancestor('Amy', 'Howard',parent) == Trueassert is_ancestor('Howard', 'Amy', parent) == Falseassert is_ancestor('Amy', 'George', parent) == Trueassert is_ancestor('George', 'Amy', parent) == False

Solution 4:

What you got wrong

What happens in your code, is that you're only checking the parent, and not any further. You need to keep traversing the chain up, until you find an ancestor, or run out of names

The solution

Here is a simple approach to the problem:

defis_ancestor(name1,name2,pdict):
    child = name1
    whileTrue:
        if child notin pdict:
            returnFalseif pdict[child] == name2:
            returnTrue
        child = pdict[child]

Explanation

Here you check if the child you're checking has a parent. If not, return False if it does, than check if that parent is the person you're looking for. If it's not, set that child as the parent, and repeat the process.