The Python Oracle

How to keep looping within a python dictionary to search for values?

--------------------------------------------------
Hire the world's top talent on demand or became one of them at Toptal: https://topt.al/25cXVn
and get $2,000 discount on your first invoice
--------------------------------------------------

Take control of your privacy with Proton's trusted, Swiss-based, secure services.
Choose what you need and safeguard your digital life:
Mail: https://go.getproton.me/SH1CU
VPN: https://go.getproton.me/SH1DI
Password Manager: https://go.getproton.me/SH1DJ
Drive: https://go.getproton.me/SH1CT


Music by Eric Matyas
https://www.soundimage.org
Track title: Flying Over Ancient Lands

--

Chapters
00:00 How To Keep Looping Within A Python Dictionary To Search For Values?
01:36 Answer 1 Score 1
02:01 Answer 2 Score 3
02:27 Answer 3 Score 1
03:07 Accepted Answer Score 1
03:53 Thank you

--

Full question
https://stackoverflow.com/questions/5828...

--

Content licensed under CC BY-SA
https://meta.stackexchange.com/help/lice...

--

Tags
#python #python3x

#avk47



ANSWER 1

Score 3


Here is your answer using recursion:

def is_ancestor(name1, name2, pdict):

    try:
        if pdict[name1] == name2:
            return True
        else:
            return is_ancestor(pdict[name1], name2, pdict)
    except KeyError:
        return False

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.




ANSWER 2

Score 1


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',
}


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

        if name1 == name2:
            return True

    return False


assert is_ancestor('Amy', 'Amy',parent) == False
assert is_ancestor('Amy', 'Ben',parent) == True
assert is_ancestor('Ben', 'Amy',parent) == False
assert is_ancestor('Amy', 'Howard',parent) == True
assert is_ancestor('Howard', 'Amy', parent) == False
assert is_ancestor('Amy', 'George', parent) == True
assert is_ancestor('George', 'Amy', parent) == False



ANSWER 3

Score 1


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:

def is_ancestor(name1,name2,pdict):
    child = name1
    while True:
        if child not in pdict:
            return False
        if pdict[child] == name2:
            return True
        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.




ACCEPTED ANSWER

Score 1


You can use recursion instead of a loop.

def is_ancestor(name1, name2, pdict):
    parent = pdict.get(name2, None)
    if not parent:
        return False
    elif parent == name1:
        return True
    else:
        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.