Calculate the value of every key in a dictionary recursively-CodePudding

I have a dictionary like below, where every key has a total size that is equal to its first value plus the sizes of its additional keys.

I would like to know the size of every key:

dictionary = {'/': [23352670, ['a', 'd']], 'a': [94269, ['e']], 'e': [584, []], 'd': [24933642, []]}

The solution should look like:

{'/': [48381165], 'a': [94853], 'e': [584], 'd': [24933642]}

I am practicing recursion and I would really like to solve this with recursion. I tried to write a recursive function, and made some progress, but was not able to do it for the full dictionary.

The function I wrote looks like:

def recursion(dictionary, key):

    #base case list is empty
    if not dictionary[key][1]:

        return dictionary[key][0]
    
    else:
        
        size = dictionary[key][0]
        for child in dictionary[key][1]:

            size  = recursion(dictionary, child)

    return dictionary

I know it is completely wrong, but it is the best I could come up with. How do I solve this problem correctly?

CodePudding user response：

Your recursion is very close, you just need to return the sum:

def get_dictionary_sum(d):
    
    def get_key_sum(k):
        # Base case
        if d[k][1] is []:
            return d[k][0]
    
        s = d[k][0]
        for k2 in d[k][1]:
            s  = get_key_sum(k2)
    
        return s
    
    return {k: get_key_sum(k) for k in dictionary}

You can then use dictionary comprehension to calculate the sum for each key:

print(get_dictionary_sum(dictionary))

Outputs:
{'/': 48381165, 'a': 94853, 'e': 584, 'd': 24933642}

An improvement on this is to use a LRU (least-recently-used) cache on the function, so if two keys use the same key in their sums, we only need to calculate the sum for that key once:

from functools import lru_cache

def get_dictionary_sum(d):

    @lru_cache(None)
    def get_key_sum(k):
        # Base case
        if d[k][1] is []:
            return d[k][0]

        s = d[k][0]
        for k2 in d[k][1]:
            s  = get_key_sum(k2)

        return s

    return {k: get_key_sum(k) for k in dictionary}

For example, with the input:

dictionary = {
    'a': [23352670, ['b', 'b', 'b']],
    'b': [94269, ['c']],
    'c': [13213, []]
}

The lru cache will reuse the summation for 'b':

(With a print statement at the start of the get_key_sum function)

Summing a
Summing b
Summing c
{'a': 23675116, 'b': 107482, 'c': 13213}

CodePudding user response：

Try:

dictionary = {
    "/": [23352670, ["a", "d"]],
    "a": [94269, ["e"]],
    "e": [584, []],
    "d": [24933642, []],
}


def compute_sizes(dct):
    def _get_size(val):
        out = 0
        for v in val:
            if isinstance(v, int):
                out  = v
            elif isinstance(v, list):
                out  = _get_size(v)
            elif isinstance(v, str):
                out  = _get_size(dct[v])
        return out

    for k, v in dct.items():
        yield k, [_get_size(v)]


print(dict(compute_sizes(dictionary)))

Prints:

{'/': [48381165], 'a': [94853], 'e': [584], 'd': [24933642]}

CodePudding user response：

Your code is not "completely wrong", the only mistake you make is that your return the dictionary instead of the size. Your function should calculate the total for one item.

def recursion(dictionary, key):
    # if branch isn't necessary
    size = dictionary[key][0]
    for child in dictionary[key][1]:
         size  = recursion(dictionary, child)
    return size # not dictionary

# Test
dictionary = {'/': [23352670, ['a', 'd']], 'a': [94269, ['e']], 'e': [584, []], 'd': [24933642, []]}
print(recursion(dictionary, '/'))

To create a new dictionary, just iterate over your original dictionary and create the new one, using the recursion function:

newdict = {k: recursion(dictionary, k) for k in dictionary}

CodePudding user response：

FWIW here is a non-recursive solution (with apologies: I see now that you want to practice recursion!)

def resolve(d):
    done = {}
    while True:
        new = {
            k: v   sum([done[ki] for ki in tail])
            for k, (v, tail) in d.items()
            if all([ki in done for ki in tail])}
        if not new:
            break
        d = {k: v for k, v in d.items() if k not in new}
        done |= new
    
    return {k: [v] for k, v in done.items()}

Example:

d = {'/': [23352670, ['a', 'd']], 'a': [94269, ['e']],
     'e': [584, []], 'd': [24933642, []]}

>>> resolve(d)
{'e': [584], 'd': [24933642], 'a': [94853], '/': [48381165]}