La verdad llego tarde a la fiesta que se originó cuando Cesar Soplin publico este slide con un problema que suelen plantear en las entrevistas de trabajo de Google:
Yo recién he visto el problema hoy, hace unas horas, y la verdad, me temo que no lo habia visto nunca. Digo “me temo” porque resulta que el problema es todo un clásico de la optimización via modelos matemáticos y es conocido en los círculos de la Ciencia de la Computación. En el artículo
The Joy of Egg-Dropping in Braunschweig and Hong Kong hay abundante información sobre el problema incluyendo un formulario que muestra la solución para el número de pisos deseado.
Gustavo Picón publicó hace ya varios dias en su blog
una solución al problema, que es absolutamente correcta, pero no explica realmente la lógica que está detrás del algoritmo.
Bueno, resulta que yo también tengo una solución al problema y la pude implementar en menos de 2 minutos en PHP luego de tomarme cerca de cuatro horas en entender realmente lo que el problema pide que uno haga:
Mi código lo tiene en
este link de
pastebin.com. Como ven parece trivial y realmente sería trivial si yo les planteara el problema de esta manera:
Escribe un programa que encuentre el menor número entero positivo que sumado a todos los enteros positivos menores que él de un resultado igual o mayor que cien
Bueno, eso es exactamente lo que hace mi programa y de una manera bastante simple y obvia. La pregunta es ¿Porqué este problema y el problema planteado por Google son equivalentes?
El texto del problema, tal como lo plantea Google dice asi:
Tienes 2 objetos y un edificio de 100 pisos.
Los objetos se rompen si caen desde una altura de N pisos o más
pero quedan intactos si caen de una altura menor de N pisos.
Es decir, un objeto puede caer desde el piso N-1 todo el día y
no se rompería, pero siempre se rompe si se deja caer del piso N.
Diseña un algoritmo que determina el piso N minimizando la caida
de objetos en el peor de los casos.
Al principio puede costar un poco entenderlo pero los dos objetos tienen exactamente el mismo grado de resistencia a romperse si se tiran desde cualquier altura, entonces, si uno encuentre una altura a la que el primer objeto se rompe, necesita ir probando con el segundo objeto con alturas menores hasta encontrar si el piso encontrado con el primero objeto es efectivamente el más bajo desde donde estos se rompen.
Lo que confunde bastante es pensar que uno tiene que dar como respuesta cual es el piso desde donde se rompen los objetos y ese no es el caso. Nunca sabemos desde que piso se rompen los objetos con exactitud.
Lo que nos preguntan realmente es
¿Desde que piso me conviene comenzar a tirar el primer objeto para encontrar el piso más bajo desde donde se rompen haciendo el menor número de intentos?
Lo díficil del problema es entender realmente que significa “minimizando la caida de objetos” por una parte y por otra parte “en el peor de los casos”.
Después de mucho pensarlo creo que encontré una manera mas o menos fácil de explicarlo:
¿Que significa “minimizando la caida de objetos”?
Significa lanzando los objetos el mismo número de veces o incluso menos que si tuviera la suerte de hacer el primer intento justo en el piso más bajo desde donde se rompen y confirmándolo haciendo intentos desde el piso 1 hasta el piso anterior para comprobar que el segundo objeto no se rompe.
¿Que significa “en el peor de los casos”?
Significa el mayor número de intentos por hacer desde la posición de inicio mas óptima, que es justamente, el número de intentos necesarios si logro romper el primero objeto al primer intento, porque si el objeto se rompe en el piso 100 o no se rompe nunca, con la estrategia óptima el número de intentos puede ser incluso menor.
La explicación final comienza por entender que si tengo la suerte de romper el primer objeto justo lanzándolo desde el piso X adecuado y al primer intento solo me faltarían X-1 intentos más, desde el piso 1 hasta el anterior para estar 100% seguro de que ese es el piso buscado.
Entonces la solución optima, rompiendo al menos el primer objeto, se obtiene tirando el objeto desde el piso X haciendo un total de X intentos.
Pero, ¿Qué pasa si en ese primer intento el objeto no se rompe? Solo me quedarían como máximo X-1 intentos más para no superar el número de intentos de la estrategia óptima.
La pregunta entonces es ahora determinar con que piso sigo probando si ya se que en el piso A no se rompe. Como ya se que en A no se rompe, el siguiente piso necesariamente va a estar mas alto, y el valor mas bajo posible sería justamente el piso siguiente, es decir A+1. Sin embargo como solo tengo X-1 intentos, el piso con el que más me conviene seguir probando, es aquel en que, en caso que se rompa el objeto, el número de intentos con el segundo objeto me permitiera llegar al piso inferior, es decir, el piso A+X-1 donde “A” es el primer piso probado (sin éxito) y X es el número optimo de intentos.
Lo interesante es que, aplicando esta técnica, el número de intentos necesarios para llegar al piso 100, nunca supera al número de intentos que hubieran sido necesarios para obtener la confirmación ya sea que uno hubiera logrado romper el primero objeto al primer intento, o al segundo intento, o al tercero, o cuarto, etc.
Entonces, ya llevándolo a un algoritmo basta con calcular la suma de X + (X-1) + (X-2) hasta cero, que no es otra cosa que la suma total de intentos fallidos de romper el primero objeto para todos los valores posibles de X comenzando desde 1 hasta encontrar el primer valor que llegue o supere a 100, el número de pisos del problema.
¿Veamos entonces cuál es la solución?
Efectivamente, 14. Si comienzo lanzando el primer objeto desde el piso 14 y se rompe (sauuu!!!) logro confirmar con el segundo objeto en 13 intentos más que hasta el piso 13 un objeto no se rompe. Sin embargo, si no tengo suerte al primer intento y tampoco en los siguientes, voy a llegar hasta el piso 100 en menos de 13 intentos adicionales, un número de intentos que no es mayor a 14.
Piso 14, quedan 13 intentos
Piso 14 + 13 = 27, quedan 12 intentos
Piso 27 + 12 = 39, quedan 11 intentos
Piso 39 + 11 = 50, quedan 10 intentos
Piso 50 + 10 = 60, quedan 9 intentos
Piso 69 + 9 = 69, quedan 8 intentos
Piso 69 + 8 = 77, quedan 7 intentos
Piso 77 + 7 = 84, quedan 6 intentos
Piso 84 + 6 = 90, quedan 5 intentos
Piso 90 + 5 = 95, quedan 4 intentos
Piso 95 + 4 = 99, quedan 3 intentos
Piso 100, el objeto se rompe y sobraron 2 intentos inclusive.
¿Porqué sobraron dos intentos? Porque si ya probé con el piso 99 y el objeto no se rompió queda demostrado que el piso 100 es el menor piso desde donde los objetos se rompen al soltarlos.
Espero que te sirvan estas notas si estas tratando de comprender el problema. Si lo conoces mejor que yo por favor escribeme y cuéntame al respecto.