Hace tiempo de esto, pero ahora en verano es cuando hay tiempo para escribir. Hace varias semanas participé en el First Tuenti Programming Contest. Al principio me pareció algo raro, pero tras leer las bases del concurso vi que no era una idea nueva sino que seguía lo pasos de los grandes como Google ( Google Code Jam) o Facebook (Puzzles, aunque está menos relacionado).
La mecánica del concurso era sencilla: 20 pruebas y 1 semana para realizarlas. Los concursantes empezaban el lunes en la primera prueba y tenían que pasar cuantas más pruebas mejor (ganaba el que más pruebas conseguía pasar de forma correcta). Entonces ¿qué misterio tiene todo esto? La cuestión real eran la dificultad de las pruebas, en teoría incrementaba a medida que avanzabas, por lo que podía darse el caso de no llegar a la última prueba. La forma de evaluar era totalmente automática: al principio del concurso los participantes descargaban las herramientas que ponía a disposición Tuenti. Estas herramientas eran simples scripts que se encargaban de comunicar los servidores de Tuenti con tu programa. Así, para cada prueba realizabas un programa. Este programa lo usabas junto con el script, quien se descargaba de internet los parámetros de entrada y enviaba al servidor la salida de tu programa (y era en el servidor donde se evaluaba). Simple y efectivo.
Según lo que pude ver en la cuenta de Twitter del equipo de ingeniería de Tuenti (TuentiEng), el concurso empezó con mucha fuerza. Mucha gente avanzaba en las primeras pruebas, incluso a horas “intempestivas” de la noche. Pero según el gráfico final que han publicado en su web, muchos de los participantes se fueron quedando en el camino, y sólo 8 personas pudieron con la última prueba.
En general las pruebas fueron de lo más diversas, pero con una raiz común: la programación. Las primeras pruebas fueron clásicos problemas de programación, para “calentar”. En cambio, la cosa empezó a subir de tono con diferentes pruebas, entre las que se podía ver entre líneas cómo pedían soluciones a problemas de optimización multi-objetivo, o algoritmos del camino más corto. Es cierto que todos ellos podían ser resueltos por “fuerza-bruta” (es decir, con muchas sentencias “for” e “if”), pero lo realmente elegante era de la otra forma. aún así, las tres últimas pruebas fueron de lo más duras (y muy discutidas por la gente), ya que en su raiz no eran problemas de programación (eran simples frases o poemas, de los que tenías que descifrar qué era lo que pedían). Mucha gente se ha quejado por este tema, pero en mi opinión, sin ninguna razón… ¿Por qué? Porque el trabajo de programador (y en mi caso el de investigador) siempre tiene una parte de intentar descifrar problemas que no te dicen explícitamente que existen.
Participantes por nivel. Fuente: Tuenti
En cuanto a mi participación, todo fue muy interesante e ilusionante. A pesar de empezar a 3 días del final del concurso (es decir, un viernes) conseguí llegar hasta la prueba 13. Por el camino, mucha programación (si, al final también tuve que usar las horas de la madrugada para poder hacer algo decente…), y mucho buenos ratos. Por una parte, siempre intentando resolver los problemas de forma óptima, aunque lo más eficaz siempre era la “fuerza-bruta” (ya que maximizaba la relación entre resultados y tiempo dedicado.
Lo mejor: el problema 13… Era un problema con un punto “freak”. Trataba del universo Stargate, donde había que llegar desde la Tierra hasta Atlantis, usando los stargates de los planetas existentes, para llegar “lo antes posible”. En esencia era un problema de encontrar el camino óptimo, por lo que se podría pensar en aplicar el Algoritmo de Dijkstra… Nada más lejos de la realidad: este algoritmo sólo potimiza caminos entre nodos cuando no existen pesos negativos en los caminos… y este no era el caso, ya que en ciertos “wormhole” entre stargates se podía ir hacia atrás en el tiempo. Por ello, tuve que estar todo el Domingo pensando en un nuevo algoritmo óptimo (si, lo hice en la playa, pero lo hice).
La idea del algoritmo ideado (y que en principio funcionaba bien) se basaba en un algoritmo de enrutamiento óptimo. Este trta sobre “inundar” todos los nodos, e ir eliminando los caminos que se fuesen cerrando o dejasen de ser óptimos. El resutlado fue bastante decente, con una velocidad de análsis aceptable (digo aceptable, porque en otro problema de cálculo de el coste óptimo lo hice por la fuerza bruta y me tardo 5 minutos en el cálculo, mientras que este lo hizo en unos pocos segundos).
La experiencia fue única, ya que hacía bastante tiempo que no se me planteaban retos de ese calibre. Así que un positivo para Tuenti por la organización de este concurso. Y a ver si el año que viene repetimos (y se puede probar suerte en el Google Code Jam!).
