Depth Weighted Nested Sum
Problem
A list holds integers and further lists, nested to any depth. Items in the outer list sit at depth 1, items in a list inside it at depth 2, and so on. Return the sum of every integer multiplied by the depth it sits at.
Examples
Input: items = [[1, 1], 2, [1, 1]]
Output: 10
Why: four 1s at depth 2 give 8, and the 2 at depth 1 gives 2Input: items = [1, [4, [6]]]
Output: 27
Why: 1 * 1 + 4 * 2 + 6 * 3Input: items = [[[]]]
Output: 0
Why: edge case, deep nesting with no integers adds nothingHints
0 / 3
Every integer needs one extra fact that is not written next to it: how many lists surround it.
That fact is known on the way down, not on the way back up. A parameter can carry it from each call to the calls it makes.
Write a function that takes a list and its depth. Loop over the items: add an integer times the depth, and for a nested list add the result of calling the function on it with the depth plus one. Start the outer call at depth 1.
Solution
The depth of an integer is decided entirely by the path from the outer list down to it, so it is information that flows downwards, which makes it a parameter rather than a return value. Each call adds its own integers weighted by the depth it was handed and passes depth plus one to the lists inside it, while the partial sums flow back up as return values. An empty list simply returns zero. Every integer and every list is visited once, so time is O(n) in the total number of items, and the call stack is as deep as the nesting.
def weighted_sum(items, depth=1):
total = 0
for item in items:
if isinstance(item, list):
total += weighted_sum(item, depth + 1) # depth travels down
else:
total += item * depth # sums travel back up
return total
print(weighted_sum([[1, 1], 2, [1, 1]])) # -> 10
print(weighted_sum([1, [4, [6]]])) # -> 27
print(weighted_sum([[[]]])) # -> 0Stuck on the idea rather than the code? Return Up or Pass Down covers it.