La caída de las lámparas… resuelta

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: \mathrm{Cost}(n, l) y \mathrm{FixedTryCost}(t, n, l), donde n es la cantidad de pisos que podrían ser el piso mínimo, l es la cantidad de lámparas disponibles y t es un piso determinado desde donde la próxima lámpara será arrojada. La primera función \mathrm{Cost} nos indica la cantidad máxima de lanzamientos de lámparas requeridos según la estrategia óptima, mientras que \mathrm{FixedTryCost} 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

\mathrm{Cost}(1, l) = 0.

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

\mathrm{Cost}(n, 1) = n.

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 n que son candidatos. Por lo tanto podemos decir que

\displaystyle \mathrm{Cost}(n, l) = \min_{0 \le t < n} \mathrm{FixedTryCost}(t, n, l),

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 t solo podemos tener dos resultados: la lámpara puede romperse o no. En caso de que se rompa examinaremos los t candidatos menores que t, mientras que en caso de que quede intacta haremos lo propio con los n-t-1 candidatos menores que t. Como se realizó un lanzamiento, el costo será

\mathrm{FixedTryCost}(t, n, l) = 1 + \max(\mathrm{Cost}(t, l-1), \mathrm{Cost}(n-t-1, l)).

Con esto tenemos definidas casi por completo a las funciones \mathrm{Cost} y \mathrm{FixedTryCost}, pero quedan pendientes algunas sutilezas que suelen conducir a errores en las definiciones recursivas. En este caso particular, habrá llamadas a \mathrm{Cost}(0, l), que nunca fue definida. Podemos resolver esto haciendo que

\mathrm{Cost}(0, l) = 0,

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 n y l:

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 \mathrm{Cost}(100, 2) = 14. 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.

La caída de las lámparas

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.)

Respuestas pendientes

Un problema de sumas

El problema pedía encontrar un algoritmo subcuadrático para determinar si dos elementos en un vector de enteros con una suma dada. Si confiamos en el caracter O(1) de las tablas hash podemos obtener un algoritmo lineal aun más breve que el cuadrático mostrado anteriormente (y sin recurrir al code golfing 😀 ):

def sum1_n(s, v):
    d = {}
    for x in v:
        if s-x in d:
            return True
        d[x] = True
    return False

Si no confiamos en eso, puede hacerse en tiempo O(n log n) ordenando la secuencia y reemplazando las búsquedas en la tabla por búsquedas binarias (como sugirió Fer) o directamente escanear el vector ordenado con dos punteros desde los extremos (no es difícil determinar las reglas de avance).

Ahora pueden probar su suerte buscando algoritmos subcuadráticos para resolver 3SUM; es solo un poquito más difícil… 😛

Circuitos hamiltonianos

Este otro problema pedía determinar si era posible encontrar circuitos hamiltonianos en grillas cuadradas con una cantidad impar de vértices. Para ver que esto no es posible, dividamos a los vértices de la grilla en dos clases de acuerdo al siguiente esquema:

ham_cycle_parity

División de los nodos del grafo en dos clases, indicadas por el color utilizado para representarlos.

Si recorremos un circuito en el grafo no es difícil convencernos de que en cada paso cambiaremos de clase de vértice. Ahora, en un circuito hamiltoniano la cantidad de pasos será impar, dándonos para el último vértice una clase distinta que para el primero. Como esto es incompatible con el hecho de que se trata de un circuito, es imposible encontrar un circuito hamiltoniano en grillas con una cantidad impar de vértices (no solo cuadradas!).