Spin Foam

En un comentario del post anterior, Kardo mostraba una solución al problema en 19 intentos:

… Siguiendo este pensamiento, la idea es probar en los pisos múltiplos de N y, en el momento que la lámpara se rompe, probar en los anteriores N-1 pisos para buscar el piso mínimo. De esta forma, si buscamos el mínimo de la función f(100/N+N-1) con 1<N<100, encontramos que ese valor es 19.

Esa es la mejor solución “inteligible” al problema entre las que vi, pero no llega a ser óptima.

El algoritmo

Para buscar la solución óptima, definamos dos funciones: y , donde es la cantidad de pisos que podrían ser el piso mínimo, es la cantidad de lámparas disponibles y es un piso determinado desde donde la próxima lámpara será arrojada. La primera función nos indica la cantidad máxima de lanzamientos de lámparas requeridos según la estrategia óptima, mientras que nos indica esa misma cantidad con la restricción adicional del piso desde donde se arrojará la próxima lámpara.

Si hay un candidato solo restante no hace falta seguir realizando lanzamientos, por lo que

.

Por otro lado, si solo nos queda una lámpara no podemos arriesgarnos a que se rompa quedando pisos sin explorar y tendremos que ir probando piso por piso. Por consiguiente tendremos

.

En los otros casos habrá que efectuar un cierto número de lanzamientos para determinar el piso mínimo. No podemos saber a priori cual será el piso óptimo desde donde realizar el siguiente lanzamiento, pero sabemos que será uno de los que son candidatos. Por lo tanto podemos decir que

,

ya que la estrategia óptima elegirá el piso desde donde lanzar de modo de minimizar el costo.

Pero cuando realizamos un lanzamiento desde el piso solo podemos tener dos resultados: la lámpara puede romperse o no. En caso de que se rompa examinaremos los candidatos menores que , mientras que en caso de que quede intacta haremos lo propio con los candidatos menores que . Como se realizó un lanzamiento, el costo será

.

Con esto tenemos definidas casi por completo a las funciones y , pero quedan pendientes algunas sutilezas que suelen conducir a errores en las definiciones recursivas. En este caso particular, habrá llamadas a , que nunca fue definida. Podemos resolver esto haciendo que

,

que es más simple que separar los casos en que es innecesario buscar.

El algoritmo implementado

La implementación, en este caso en Python, es directa a partir de las definiciones recursivas:

def cost(n, l):
    if n in (0, 1):
        return 0
    elif l == 1:
        return n
    else:
        return min(fixed_try_cost(t, n, l) for t in xrange(0, n))

def fixed_try_cost(t, n, l):
    return 1 + max(cost(t, l-1), cost(n - t - 1, l))

Pero si intentamos ejecutar cost(100, 2), observaremos que la ejecución no termina. Esto es debido a que, al igual que en caso del cálculo recursivo de los números de Fibonacci, se recalculan los mismos valores un gran número de veces. Incluso la ejecución de cost(24, 2) demora decenas de segundos.

El algoritmo utilizando programación dinámica

Una forma común para resolver este problema es aplicar la técnica conocida como programación dinámica, consistente esencialmente en almacenar los resultados previamente calculados de modo de no requerir calcularlos nuevamente. Una forma simple de implementar esto en Python es utilizar un diccionario para almacenar el costo correspondiente a cada valor de y :

costs = {}

def m_fixed_try_cost(t, n, l):
    return 1 + max(m_cost(t, l-1), m_cost(n - t - 1, l))

def m_cost(n, l):
    if (n, l) in costs:
        return costs[(n, l)]
    if n in (0, 1):
        c = 0
    elif l == 1:
        c = n
    else:
        c = min(m_fixed_try_cost(t, n, l) for t in xrange(0, n))
    costs[(n, l)] = c
    return c

Se observa que las únicas diferencias (aparte del prefijo m_) son la consulta del diccionario al inicio de la función m_cost y el grabado del valor calculado antes de devolverlo.

Si se desea obtener mejor performance, puede utilizarse una tabla normal y llenarla mediante iteración en lugar de recursión. Por ejemplo, la misma función podría implementarse en C del siguiente modo:

#define MAX_N 200
#define MAX_L 200

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int cost(int n, int l)
{
	int costs[MAX_N][MAX_L];
	int i, j, k, c;
	for (i = 0; i <= n; i++)
		costs[i][1] = i;
	for (j = 1; j <= l; j++)
		costs[0][j] = costs[1][j] = 0;
	for (i = 2; i <= n; i++)
	{
		for (j = 2; j <= l; j++)
		{
			c = i;
			for (k = 0; k < i; k++)
			{
				c = MIN(c, 1 + MAX(costs[k][j-1],
								   costs[i-k-1][j]));
			}
			costs[i][j] = c;
		}
	}
	return costs[n][l];
}

De todos modos, todas las versiones se ejecutan en forma esencialmente instantánea, dando como resultado . Mediante una simple modificación podría devolverse la secuencia requerida en base a lo que sucede con las lámparas al ser arrojadas, obteniendo así un algoritmo para resolver el problema en la práctica.

We want to figure out how strong our new super-strong light bulbs
are. We know that they will be break when dropped from the top floor
of this building (the 101st). We want to know the exact minimum floor
from which a fall will cause the light bulb to break. You’ll be given
two light bulbs for this task and we want you to do it with the
minimum number of trials.

(Extraído del blog de Louis Brandy.)