Python algorithm to search keys and values

Question

Part of an algorithm course I am taking is to use look through a dictionary of keys and values and continue to look for matching keys & values. For example if there is a matching key, use the value to look up the next key and continue down the rabbit hole. If a match if found more than once to prevent an infinite loop return False else it should return the last key found.

Look up a key called "bat", and find a value "pig" then continue
Look up a key called "pig", and find "cat" then continue
Look up a key called "cat", and find "dog" then continue
Look up a key called "dog", and find "ant" then continue
Look up a key called "ant", and find no associated value, and so it would return "ant"

This is the data:

d = {'bat': 'pig', 'pig': 'cat', 'cat': 'dog', 'dog': 'ant', 'cow': 'bee', 'bee': 'elk', 'elk': 'fly', 'ewe': 'cod', 'cod': 'hen', 'hog': 'fox', 'fox': 'jay', 'jay': 'doe', 'rat': 'ram', 'ram': 'rat'}

This is my function below where I am trying learn recursion...and understand why my function doesn't return False when a key saved to MEMORY has a value greater than 2.

def rabbit_hole(dictionry,key,MEMORY={}):
    
    #print(MEMORY)
    
    if key in MEMORY:
        MEMORY[key] += 1
        
    else:
        MEMORY[key] = 1
        

    for val in MEMORY.values():
        #print(val)

        if val == 2:
            return False # <--- why not working?

    for k,v in dictionry.items():
        if k == key:
            
            # recursive call
            rabbit_hole(dictionry,v,MEMORY)

    #print("return last added dict key")
    return list(MEMORY)[-1]

Any tips appreciated not a lot of wisdom here...if I run:

print(rabbit_hole(d, "bat"))
print(rabbit_hole(d, "ewe"))
print(rabbit_hole(d, "jay"))
print(rabbit_hole(d, "yak"))
print(rabbit_hole(d, "rat"))

The code above returns:

ant
hen
doe
yak
ram

But its supposed to return a False on rat like this:

ant
hen
doe
yak
False

`for k,v in dictionry.items(): if k == key: rabbit_hole(dictionry,v,MEMORY)` is a very inefficient way to do `if key in dictionry: rabbit_hole(dictionry, dictionry[key], MEMORY)` — Stef, Sep 13 '22 at 16:12

Tom McLean · Accepted Answer · 2022-09-13T18:59:01.897

You are close, this point can help you:

Your condition to break out of the recursive loop should normally come first, which is if the key is in MEMORY
You need to return the value of the recursive call thanks Abhinav

In addition, some style/optimisation suggestions:

If you want to keep track of what you have seen so far, you can use a set over a dict
Then with a dictionary, you dont need to loop over the keys (that defeats the point of a dictionary). You can just see if a key is in the dictionary, and if it is, get the value.
Replace the default mutable argument dict with None, and then set it as a dictionary (or set) if it is passed in as None. This is because if you re-run the function:

print(rabbit_hole(d, "bat"))
print(rabbit_hole(d, "bat"))

It will reuse the same dictionary/set which will then have preexisting keys, rather than creating a new dictionary

ant
False

I would suggest you try again with these points, but if not here is a solution:


 def rabbit_hole(dictionary, key, seen=None):
    if seen is None:
        seen = set()

    if key in seen:
        return False

    seen.add(key)

    if key in dictionary:
        return rabbit_hole(dictionary, dictionary[key], seen)
    return key

Replacing the default mutable value by `None` and an `if` like you did in the solution is really good, but the OP probably won't know why you did it. I suggest adding an explanation for that. — Stef, Sep 13 '22 at 16:14
Or linking to https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument — Stef, Sep 13 '22 at 16:15
Or linking to the tutorial from the official documentation, which has a warning against mutable default arguments: https://docs.python.org/3/tutorial/controlflow.html#default-argument-values — Stef, Sep 13 '22 at 16:20

score 2 · Answer 2 · answered Sep 13 '22 at 16:11

2

The main issue is, you're not returning the value from the recursive call. As a result, the function returns the last value from the memory list. This simple fix should return the correct value:

    for k,v in dictionry.items():
        if k == key:
            # recursive call
            return rabbit_hole(dictionry,v,MEMORY)

answered Sep 13 '22 at 16:11

Abhinav Mathur

7,791
3
10
24

ah thanks....the learning curve is high here.... – bbartling Sep 13 '22 at 16:13
Ill hit the green check box....still trying to soak in the theory of recursion....that I need the `return` ill probably finally get it after about 100 more practice problems : ) – bbartling Sep 13 '22 at 16:15

Python algorithm to search keys and values

2 Answers2