Suma anidada ponderada por profundidad
La misión
Problema
Una lista contiene enteros y otras listas, anidadas a cualquier profundidad. Los elementos de la lista externa están a profundidad 1, los de una lista dentro de ella a profundidad 2, y así sucesivamente. Devuelve la suma de cada entero multiplicado por la profundidad a la que está.
Ejemplos
Input: items = [[1, 1], 2, [1, 1]]
Output: 10
Por qué: cuatro 1 a profundidad 2 dan 8, y el 2 a profundidad 1 da 2
Input: items = [1, [4, [6]]]
Output: 27
Por qué: 1 * 1 + 4 * 2 + 6 * 3
Input: items = [[[]]]
Output: 0
Por qué: caso límite: un anidamiento profundo sin enteros no suma nada
Pistas
0 / 3
Cada entero necesita un dato extra que no está escrito a su lado: cuántas listas lo rodean.
Ese dato se conoce en el camino de bajada, no en el de subida. Un parámetro puede llevarlo de cada llamada a las llamadas que hace.
Escribe una función que reciba una lista y su profundidad. Recorre los elementos: suma un entero multiplicado por la profundidad y, para una lista anidada, suma el resultado de llamar a la función sobre ella con la profundidad más uno. Empieza la llamada externa con profundidad 1.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(d)
Restricciones
- items are integers or lists, nested to any depth
Solución
La profundidad de un entero depende solo del camino desde la lista externa hasta él, así que es información que fluye hacia abajo, y por eso es un parámetro y no un valor de retorno. Cada llamada suma sus propios enteros ponderados por la profundidad que recibió y pasa la profundidad más uno a las listas que contiene, mientras las sumas parciales vuelven hacia arriba como valores de retorno. Una lista vacía simplemente devuelve cero. Cada entero y cada lista se visitan una vez, así que el tiempo es O(n) en el número total de elementos, y la pila de llamadas (call stack) es tan profunda como el anidamiento.
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([[[]]])) # -> 0¿Lo que te frena es la idea y no el código? Devolver arriba o pasar abajo lo explica.