Altura Máxima Coincidente: Cilindros y Conjuntos en Python

¿Te imaginas apilando cilindros de diferentes alturas buscando el punto perfecto donde todos coincidan? 🤔 ¡Es un desafío de optimización con sabor a Tetris!

🔮 Enunciado del Problema

El problema que abordamos es el de encontrar la máxima altura común entre múltiples pilas de cilindros, donde cada cilindro tiene el mismo diámetro pero alturas variables dentro de cada pila. Formalmente:

• Parámetros:

  • stacks: Una matriz (o lista de listas) de enteros, stacks[m][n], donde m representa el número de pilas y n la cantidad de cilindros en cada pila. Cada elemento en la matriz representa la altura de un cilindro específico.

• Valor de retorno:

  • Un entero que indica la máxima altura en la que todas las pilas de cilindros coinciden. Si no hay alturas coincidentes, se debe retornar 0.

• Ejemplos:

  equal_height([[1, 1, 1, 1, 1, 1, 2], [2, 2, 2, 1, 3, 5]]) # Retorna 6
  equal_height([[23, 7, 5], [21, 19]]) # Retorna 0
  equal_height([[], [1, 2, 3]]) # Retorna 0

• Notas adicionales:

  • Es crucial considerar que la máxima altura coincidente puede ser 0, lo cual ocurre cuando las pilas no tienen ninguna altura en común.
  • Una pila vacía debe resultar en una altura coincidente de 0, ya que no puede coincidir con ninguna otra pila.

🧩 Resolución Paso a Paso

Para resolver este problema, adoptamos una estrategia basada en conjuntos y sumas acumuladas. Cada pila se transforma en un conjunto de posibles alturas alcanzables, y luego buscamos la intersección de estos conjuntos.

Primero, necesitamos una función que calcule las posibles alturas alcanzables en una pila dada:

def get_sum_stack(stack):
	acc = 0
	sum_stack = set()
	for n in stack:
		acc += n
		sum_stack.add(acc)
	return sum_stack

Este bloque de código itera sobre cada cilindro de la pila, acumulando sus alturas en la variable acc. Por cada altura acumulada, la agregamos al conjunto sum_stack. El conjunto garantiza que no haya alturas duplicadas, lo cual simplifica las operaciones posteriores. La lógica de utilizar un conjunto es que este almacena las alturas posibles de cada una de las pilas, haciendo más eficiente encontrar la intersección entre las alturas de las pilas.

Luego, implementamos la función principal que encuentra la altura coincidente máxima:

def equal_height(stacks):
	"level: medium; points: 5"
	result = get_sum_stack(stacks[0])
	for stack in stacks:
		result &= get_sum_stack(stack)
	return max(result) if len(result) > 0 else 0

Este bloque comienza inicializando result con el conjunto de alturas posibles de la primera pila. Después, itera sobre las pilas restantes, realizando una intersección con result. La intersección (operador &=) mantiene solo las alturas que son comunes a todas las pilas. Finalmente, si el conjunto resultante no está vacío, retorna la altura máxima; de lo contrario, retorna 0.

Solución Completa:

def get_sum_stack(stack):
	acc = 0
	sum_stack = set()
	for n in stack:
		acc += n
		sum_stack.add(acc)
	return sum_stack

def equal_height(stacks):
	"level: medium; points: 5"
	result = get_sum_stack(stacks[0])
	for stack in stacks:
		result &= get_sum_stack(stack)
	return max(result) if len(result) > 0 else 0

🧠 Conceptos Clave

La solución se apoya en varios conceptos clave:

• Conjuntos: Utilizamos conjuntos para representar las posibles alturas alcanzables en cada pila. La principal ventaja de usar conjuntos es su eficiencia al realizar operaciones de intersección, ya que la búsqueda de elementos comunes es mucho más rápida que en una lista.

• Intersección de Conjuntos: La intersección de conjuntos (&=) es fundamental para encontrar las alturas que son comunes a todas las pilas. Esta operación selecciona solo los elementos que están presentes en todos los conjuntos.

• Sumas Acumuladas: Calculamos las sumas acumuladas para determinar todas las posibles alturas alcanzables en cada pila. Cada suma acumulada representa la altura total hasta ese punto en la pila. Este cálculo iterativo es esencial para transformar una pila en un conjunto de alturas potenciales.

• Altura Alcanzable: La idea de “altura alcanzable” encapsula la lógica del problema. Cada suma acumulada representa una altura que se puede lograr apilando los cilindros hasta ese punto. La coincidencia de estas alturas entre las pilas es lo que buscamos.

💫 Reflexiones Finales

Una posible mejora sería optimizar la función get_sum_stack para evitar recalcular las sumas acumuladas en cada iteración de equal_height, aunque el costo en términos de complejidad asintótica es mínimo y el código actual es más legible.

¿Sabías que…? 🤔 La eficiencia de la intersección de conjuntos en Python (implementada en C bajo el capó) hace que esta solución sea sorprendentemente rápida, incluso para grandes cantidades de pilas y cilindros.

¡Espero que este viaje por las alturas coincidentes haya sido revelador! Si te interesa explorar más algoritmos y estructuras de datos, ¡no dudes en seguir leyendo! ¡Te espero en el próximo artículo para seguir expandiendo juntos nuestros horizontes de programación! 🚀