CODEWITHSUNDEEP
pythonlistdictionaryrecursion
anotherGatsby
anotherGatsby

Reputation: 1598

How to use recursion in heterogenous list and dict

I was learning about recursion in python and solved some common problems like factorial, iterating through nested lists etc. While solving such problems, I came up with this challenge where you have to use recusion to traverse through a heterogeneous input(an input which contains single str elements, nested lists, dictionary etc).

So the challenge involves traversing through all the values in this input and replace a specified value with another one.

The input used here looks like this:

input = ['a', 'b', {'1':{'o':'a'}}, 'c', 'd', {'T': 'b', 'K': [1, 'a', 3, {'S':{'Z':'t'},'R':{'3':'a'}}, {'key':[66,'a',88]}, ['a', 'c']]}, ['a'], 3, 'r', 'a']

The input is a list which itself contains lists and dicts, and some of these lists and dicts are nested and also have one another in themselves.

And the output that I'm expecting to get is:

# this is the output that should be got at the end, after running the code
['#', 'b', {'1':{'o':'#'}}, 'c', 'd', {'T': 'b', 'K': [1, '#', 3, {'S':{'Z':'t'},'R':{'3':'#'}}, {'key':[66,'#',88]}, ['#', 'c']]}, ['#'], 3, 'r', '#']
# exactly like input but with all 'a' replaced with '#'
# of course we can use treat change the input to string and then use replace() of string module and get the output
# but then this wont be a challenge would it?

correct = ['a', 'b', 'a', 'c', 'd', 'b', 1, 'a', 3, 't', 'a', 66, 'a', 88, 'a', 'c', 'a', 3, 'r', 'a']

The code I wrote is:

remove = 'a'
replace = 'X'

output = []
def recall(input):
    for item in input:
        if isinstance(item, list):
            recall(item)
        elif isinstance(item, dict):
            for entry in item.values():
                recall(entry)
        else:
            if isinstance(input, dict) and item in input.keys():
                if input[item]==remove:
                    input[item]=replace
                    output.append(input[item])
                else:
                    output.append(input[item])
            else:
                if item==remove:
                    item=replace
                    output.append(item)
                else:
                    output.append(item)
            print(item)

recall(input)
print(output)

This produces the output:

['X', 'b', 'X', 'c', 'd', 'b', 1, 'X', 3, 't', 'X', 66, 'X', 88, 'X', 'c', 'X', 3, 'r', 'X']
# a single list with all the 'a' replaced but there are no dicts with their key value pairs in it

I havn't been able to find a way to achieve the desired output. Am I doing something wrong? Or is there any way the desired output can be achieved with recursion?

Upvotes: 0

Views: 59

Answers (1)

Stuart
Stuart

Reputation: 9858

You are appending all the values to a single global output variable regardless of whether they are from a nested dict or list. Instead, you need to get the function to return a value so that the function at the next level up can deal with it appropriately - appending a dict or list in the right position in the nested hierarchy. For example, you could do it this way:

def replace_values(item, replacement):
    if isinstance(item, list):
        return [replace_values(v, replacement) for v in item]
    elif isinstance(item, dict):
        return {k: replace_values(v, replacement) for k, v in item.items()}
        # Alternatively, in case you need the dict keys to be replaced too:
        # return {replacement.get(k, k): replace_values(v, replacement) for k, v in item.items()}
    else:
        return replacement.get(item, item)

input_list = ['a', 'b', {'1':{'o':'a'}}, 'c', 'd', {'T': 'b', 'K': [1, 'a', 3, {'S':{'Z':'t'},'R':{'3':'a'}}, {'key':[66,'a',88]}, ['a', 'c']]}, ['a'], 3, 'r', 'a']
print(replace_values(input_list, {"a": "#"}))

Note that the type (dict, list, or other) and ordering of the elements are the same in the return value as in the input item. This preserves the nested structure of the input.

Upvotes: 1

Related Questions