Problema Two Crystal Balls

Originalmente publicado en: https://blog.jeankaobando.com/blog/2023/two-crystal-balls/

Tabla de Contenidos

Introducción
Descripción del Problema
Solución Ingenua
Solución Binary Search
Solución Intervalos
Versión generalizada
Aprendizajes y Reflexiones
Conclusión
Recursos

Introducción

Últimamente me he encontrado muy interesado en profundizar mi conocimiento en algoritmos y estructura de datos, además de mejorar mis habilidades en la resolución de problemas de este tipo. Por lo que como parte del curso The Last Algorithms Course You'll Need de FrontEnd Masters me encontré con un interesante problema llamado "Las dos esferas de cristal" o "Two Crystall Balls".

Descripción del Problema

El enunciado del problema es el siguiente:

Nos encontramos en un edificio de n pisos y tenemos dos esferas de cristal. El objetivo es determinar el piso exacto en qué las esferas de cristal se rompen. Se debe buscar la forma más óptima.

Por ejemplo si tenemos un edificio de 128 pisos.

0	1	2	...	67	68	69	...	127	128
false	false	false	...	false	true	true	...	true	true

Para este ejemplo, el piso donde comienzan a romperse las esferas es el 68. Del piso 1 al piso 67 mis esferas se mantienen intactas.

Ahora sí como lo resolvemos!!

Solución Ingenua

Voy a ser muy honesto, al principio no entendía muy bien lo que me pedía el ejercicio y el porqué tenía 2 esferas. Opté por seguir la siguiente estrategia.

Tirar una de las esferas piso por piso
En cada piso verificar si se rompe
Si se rompe retornar el valor de ese piso
Si no se rompe pasar al siguiente hasta llegar al final
Si he llegado al final del edificio y no se rompe, retornar -1 que indica que en ese edificio no se rompen las esferas.

Miremos la implementación en Javascript

const twoCrystalBall = (floors) => {
  for (let i = 0; i < floors.length; i++) {
    if (floors[i]) {
      return i;
    }
  }
  return -1;
}

Sí hacemos un análisis de complejidad de este algoritmo nos percatamos que en el peor escenario vamos a tener que recorrer todo el arreglo. Es decir que nuestro algoritmo necesita tantos pasos como pisos tenga el edificio. Esta es una relación lineal y se la representa como $T=O(n)$ .

Ahora, lo podemos hacer mejor? Si miramos bien la implementación, no se aleja mucho al algoritmo de búsqueda Linear Search. Interesante, existen otros algoritmos de búsqueda más eficientes, entonces pueda que exista una mejor manera de resolverlo. Vamos a la siguiente solución.

Solución Binary Search

Si se percataron bien, en la solución anterior estoy obviando el hecho de que tengo 2 esferas, solo estoy usando una. Algo que he aprendido es que ningún dato en un ejercicio está suelto, tienen una razón de ser.

Dijimos también que la solución anterior se asemejaba a un método de búsqueda. Qué tal si intentamos con otro, mmm vamos con Binary Search, ya les explico el porque.

El algoritmo de búsqueda Binary Search define que dentro de un arreglo de datos ordenados, podemos analizar el elemento de la mitad, si es el elemento que busco retorno su indice, caso contrario verifico si el valor de la mitad es menor al elemento que busco. Si la sentencia es verdadera descarto de mi búsqueda el lado derecho, si es falsa el lado izquierdo de mi arreglo. Y así hasta encontrar mi valor o quedarme sin elementos por analizar. Su complejidad es $O(log n)$ . Mira más información aquí.

Podemos aplicar este algoritmo a nuestro problema, verifiquemos algunas cosas:

Estamos buscando un elemento: Si
Mis datos están ordenados : Sí (Si reemplazamos true y falso por 0 y 1 el arreglo resultante está ordenado [0,0,0,0,1,1]);

Parece que sí, entonces podemos plantearnos la siguiente solución al problema.

Lanzamos la primera esfera desde la mitad del edificio.
Si se rompe, lanzamos la segunda esfera desde el inicio hasta la mitad menos uno, buscando en que piso se rompe
Si no se rompe, lanzamos nuevamente la primera esfera en el intervalo mitad más uno y el final
Repetimos el proceso hasta encontrar piso en qué se rompe, y con la otra esfera recorremos ese intervalo para identificar el piso exacto en que comenzar a romperse las esferas.
En el caso de no encontrar el piso, retornar -1

La implementación en Javascript del problema sería el siguiente:

const twoCrystalBall = (floors) => {
  let startIdx = 0;
  let endIdx = floors.length;

  while (startIdx < endIdx) {
    const midIdx = startIdx + Math.floor((endIdx - startIdx) / 2);

    if (floors[midIdx]) {
      endIdx = midIdx;
      break;
    }
    startIdx = midIdx +1;
  }

  for (let i=startIdx; i < endIdx; i++) {
    if (floors[i]) {
      return i;
    }
  }
  return -1;
}

Cómo podemos notar en la implementación, la solución presenta la combinación de Linear y Binary Search. Procedamos a analizar la complejidad del ejercicio. Si observamos bien podemos identificar que el peor escenario para este algoritmo es cuando la esfera se rompe un piso anterior al piso del medio. Esto se da ya que solo podemos aplicar una vez Binary Search (descartar elementos) y el intervalo para recorrer con la otra esfera es el mas grande que podemos obtener. Traduciendo a notación BigO la complejidad es igual a $1 + ((n/2) -1)$ pasos. Si removemos las constantes el resultado es otra vez $T=O(n)$ .

Parece ser que no hemos mejorado mucho la verdad, si bien de manera practica recorrer la mitad de elementos resulta un avance, si llevamos esto a una cantidad muy grande de datos, la diferencia no es notable.

Nota: Esta solución es la adecuada para muchas empresas o entrevistadores.

Veamos otra solución 🧐

Solución Intervalos

¿Cuál creen que fue el problema con la solución anterior? El intervalo.

El intervalo inicial es muy grande, entonces si rompemos nuestra esfera al primer intento, no aprovechamos las ventajas del Binary Search y el camino a recorrer con la otra esfera es igual a la mitad menos uno de elementos $(n/2) - 1$ . Qué tal si jugamos con otros intervalos, no se tal vez de 10 en 10, o de 5 o 5, como buenos ingeniero le daremos el nombre de $k$ a este intervalo por conocer.

Cuál es el peor escenario ahora? Que la esfera se rompa en el penúltimo piso del edificio. En ese caso vamos a tener que hacer $(n/k) + (k - 1)$ pasos. Que es el número de lanzamientos que hacemos en cada k piso hasta llegar al final con la primera esfera y luego los $k - 1$ pasos que hacemos con la segunda esfera para encontrar el piso exacto. Si minimizamos la función $(n/k) + k -1$ , el resultado es $\sqrt{n}$ . Boom!! Tenemos nuestro intervalo. Procedamos a implementar el código antes de hacer el análisis de complejidad.

const twoCrystalBall = (floors) => {
  let interval = Math.trunc(Math.sqrt(floors.length));
  let endIdx = interval;

  while (endIdx < floors.length ) {
    if (floors[endIdx]) {
      break;
    }
    endIdx = endIdx + interval;
  }

  const startIdx = (endIdx - interval);

  for (let i=startIdx; i < endIdx; i++) {
    if (floors[i]) {
      return i;
    }
  }
  return -1;
}

Como lo habíamos señalado el número de pasos que necesitamos para resolver el problema en el peor escenario es $(n/k) + k -1$ , si reemplazamos $k$ por $\sqrt{n}$ el resultado es $(n/\sqrt{n}) + \sqrt{n} -1$ . Haciendo todas las operaciones y simplificación de la notación BigO el resultado es que la complejidad es $O(\sqrt{n})$ , función que es mucho más eficiente que $O(n)$ .

Versión generalizada

Ahora una pregunta para todos ustedes.

Que tal si llevamos el problema mas allá y ya no tenemos 2 esferas, sino $d$ esferas, como afectaría a nuestro algoritmo?

Bueno si te interesa ahondar en ese caso te invito a revisar la clase del profesor Srini Devadas dónde se aborda la versión generalizada. En el curso The Last Algorithms Course You'll Need, The primeagen solo se señala que el intervalo y la complejidad es $O(\sqrt{n})$ pero no se ahonda en él porque.

Conclusión

Finalmente porque una solución es mejor que las otras. Miremos la siguiente gráfica por un momento.

En la gráfica ustedes pueden observar como el número de pasos para completar la solución crece de manera más lenta en la solución $O(\sqrt{n})$ que en la solución $O(n)$ .

En conclusión la solución optima es lanzar mi primera esfera por intervalos.

Aprendizajes y Reflexiones

Recuerda que cada palabra en un problema, está por algo. En la primera solución no tomamos en cuenta la segunda esfera.
El análisis matemático es importante en las Ciencias de la Computación, es necesario ese conocimiento para llegar a la tercera la solución que como hemos visto es mucho mejor que las otras dos.
No te quedes con la duda. En mi caso no entendía porque se seleccionaba el intervalo $O(\sqrt{n})$ , este hecho me llevo a encontrar la clase del profesor Srini Devadas, la cual me permitió comprender mejor el problema y sus soluciones.