Tuenti Challenge 6 (primera parte)

Esta es una explicación de las soluciones que he enviado para la sexta edición del Tuenti Challenge. El código fuente lo podéis encontrar aquí, pero a mí me gusta explicar las soluciones de palabra, para poder discutir todas las opciones.

Challenge 1 – Team Lunch

En este problema introductorio se pedía calcular el mínimo número de mesas necesarias para sentar a un determinado número de comensales. Te dicen que las mesas son cuadradas, que en cada lado de la mesa se puede sentar una sola persona, y que las mesas tienen que distribuirse como una fila. En realidad se puede demostrar que basta con pedir que la distribución de mesas sea conexa, ya que el óptimo es precisamente distribuirlas en fila. Para finalizar el problema son necesarias las siguientes observaciones:

  • La primera mesa permite que se sienten cuatro comensales.
  • Cada mesa adicional permite dos comensales adicionales. Esto es así porque cada mesa tiene cuatro lados, pero al añadir una mesa dos espacios se pierden al juntarla a la anterior.

Por lo tanto es fácil de ver que si el número de mesas es m\geq 1, entonces el número de comensales que pueden sentarse es de 2m + 2. Si el número de mesas es 0, entonces nadie puede sentarse. Si invertimos esta función obtenemos que el número mínimo de mesas necesario para que se sienten c comensales es de \left\lceil {c - 2\over 2}\right\rceil =\left\lfloor {c - 1\over 2}\right\rfloor. Si c es 1 o 2 hace falta una mesa para que se sienten, y si es 0 no hace falta ninguna.

Challenge 2 – The Voynich Manuscript

En este problema se pedía buscar las tres palabras más comunes en determinados fragmentos de un texto. El texto tenía 35.000 palabras, y el número de consultas, determinadas por la posición de la primera y la última palabra del fragmento, es de 5.000. Aquí debo decir que me decanté por el algoritmo trivial. En ese momento estaba pasando unos días de vacaciones y decidí guardarme fuerzas para el día siguiente. El algoritmo consiste, evidentemente, en contar todas las palabras que hay entre dichas posiciones y devolver las tres más repetidas. Este algoritmo tiene un coste de O(N\cdot T), donde N es el número de consultas y T es el tamaño del texto. Esto puede ser demasiado lento, y mi implementación en Python tarda aproximadamente 20 segundos.

Una vez acabado el concurso le he dedicado un poco de tiempo a pensar una solución mejor y se me ha ocurrido un algoritmo que mejora el caso medio, aunque en caso peor no creo que se pueda mejorar mucho. En primer lugar, por cada palabra, guardamos la lista de los índices en los que aparece. Esto se puede hacer en tiempo lineal en el tamaño del texto, y la memoria que ocupa es, también lineal, pero el texto es pequeño. A continuación ordenamos las palabras de más a menos apariciones, y por cada consulta hacemos lo siguiente:

  • Contamos el número de apariciones de dicha palabra en el intervalo buscado. Como por cada palabra tenemos una lista ordenada de apariciones podemos hacerlo en tiempo logarítmico mediante búsqueda binaria. Como cada palabra en el fondo tampoco aparece tantas veces, si recorremos toda la lista buscando el número de apariciones tampoco tardaremos mucho más.
  • Guardamos el número de apariciones de las tres palabras que aparecen más veces de momento.
  • Si la palabra que consideramos aparece en el texto un número menor o igual de veces que la tercera palabra que más ha aparecido hasta ahora, entonces detenemos la búsqueda. Como nos dicen que no puede haber dos palabras empatadas en las tres primeras posiciones sabemos que todas las palabras que vengan a continuación aparecen un número menor de veces.

Mi implementación en Python tarda menos de un segundo en resolver el caso de submit. Se puede encontrar el código en el repositorio, con el nombre de “2alternative.py”.

Challenge 3 – YATM Microservice

En este problema se proporciona la información de una máquina de Turing y se te pide que la simules con un cierto número de valores iniciales de la cinta. No es la primera vez que aparecen máquinas de Turing en problemas del Tuenti Challenge, por lo que si ya estás familiarizado el problema no tiene ninguna dificultad. La única novedad es que la descripción de la máquina se da en formato YAML, pero existen numerosos módulos que leen en ese formato y devuelven una estructura adecuada para trabajar. Yo utilicé el módulo PyYAML de Python, pero también los hay para otros lenguajes como PHP.

Challenge 4 – Hadouken!

Este problema consiste en encontrar el número de casi combos en una secuencia de movimientos llamada sesión. Un combo es también una secuencia de movimientos, y decimos que casi se produce un combo c_1,c_2,\ldots,c_n si la secuencia c_1,c_2,\ldots,c_{n-1} aparece consecutivamente en la sesión, pero el combo no se completa, ya sea porque el siguiente movimiento no es c_n, o porque la sesión finaliza en ese mismo momento. Te dicen que dos combos no pueden finalizar simultáneamente, lo que es equivalente a no considerar un combo c si existe otro combo que es sufijo de c.

Una vez eliminados los combos inválidos, es decir, los que tienen un sufijo en la lista de combos, el problema se reduce a encontrar subsecuencias consecutivas en una secuencia mayor. Como sólo hay tres combos de tamaño tres, probablemente la forma más sencilla, consistente en detectar por cada secuencia de longitud tres si casi se corresponde a uno de los combos, sea más rápida que cualquier solución más compleja, pero como ejercicio vamos a pensar el caso general, con un número arbitrario de combos de tamaño arbitrario.

En mi solución utilizo el algoritmo Aho-Corasick, que es una generalización del algoritmo KMP para un número arbitrario de palabras. Este algoritmo busca el número de ocurrencias de palabras de un determinado conjunto en una cadena más larga, y el coste total es el de la entrada más la salida, es decir, la suma del tamaño de las palabras a buscar, la cadena en la que buscamos, y el número de ocurrencias, que en otros problemas podría ser cuadrático. Para buscar los casi combos ejecuto el algoritmo buscando los combos sin el último movimiento, y al resultado le resto el número total de ocurrencias de los combos completos. El algoritmo puede ser pesado de implementar, pero yo utilicé el módulo ahocorasick de Python, lo que simplificó bastante el código. El tiempo de ejecución es de aproximadamente un segundo.

Sigue aquí