TuentiChallenge4: Diario de un developer yonki (3): Ejercicios más chungos y conclusiones

¡OJO!: Esta entrada es la última parte de una saga que empieza en:

TuentiChallenge4: Diario de un developer yonki (1)

Los fuentes Java de mis soluciones están disponibles en Github.

Día 7

Querido diario:

Hoy el día ha sido muy largo. O quizá debería decir la noche. Después del bajón del día de ayer, decidí que lo mejor que podía hacer era descansar muchas horas y dedicar la noche a hacer un ejercicio más, ¡pero hacerlo bien!. Así que dediqué la mayor parte del día a descansar y a la tranquila vida familiar.

A última hora de la tarde, encendí el ordenador y le reté a un duelo de miradas. Esta vez iba a darlo todo.

de vergag.com

Entonces me puse con el ejercicio 14, Train Empire, que propone un juego de trenes con combustible limitado, en el que se incluyen rutas, estaciones y vagones con puntuaciones si consiguen alcanzar una estación de destino. Se trata de obtener la máxima puntuación posible a partir de un estado inicial dado. El ejercicio ha confirmado que estamos ya en fase chunga, y hay que darle bastantes vueltas para resolverlo.

He planteado la resolución en dos fases. En la primera, por cada vagón obtengo todas las posibles combinaciones que llevarían a que ese vagón llegara a su destino, sin tener en cuenta la estación en la que comience el tren. En la segunda, pruebo todas las permutaciones de las posibilidades de cada estación, probando también a cambiar el orden en el que se obtendrá cada vagón. Al hacerlo, recorro antes las posibilidades que exploran primero los vagones con más puntuación, porque así es más fácil obtener rápidamente una solución buena. En cuanto una permutación no sea ya capaz de mejorar la mejor puntuación obtenida hasta el momento, se descarta.

Esta prueba de cada permutación tiene una sutileza con la que hay que tener cuidado: al mover un tren anterior, puede que en parte de su camino no necesite llevar ningún vagón con puntos, por lo que cabe la posibilidad de que el tren esté libre para mover un vagón en su recorrido y dejarlo en alguna estación intermedia. Así que en dicho caso hay que ver cuál de esas estaciones va a ser más adelante la más cercana a su destino, y considerarlo para la situación inicial del siguiente tren. Tengo la impresión de que esta sutileza era la gran dificultad del ejercicio, y que puede hacer que mucha gente no resuelva bien el ejercicio.

En el enunciado se dice que no va a haber más de 2 trenes, por lo que seguramente exista alguna solución más sencilla que la mía que tenga en cuenta esto. La mía es genérica, valdría lo mismo para 2 trenes que para más, aunque por supuesto el rendimiento se resentiría mucho en caso de haber muchos trenes.

Al ejecutarlo crucé los dedos para ver si era lo suficientemente rápido, pensando que el hecho de que solo hubiera 2 trenes debería ser suficiente, y efectivamente ha ejecutado la entrega en 10 segundos. Muy satisfecho con mi solución, a pesar de no ser demasiado elegante, llegó el momento que ya había vivido varias veces estos últimos días: las tantas de la noche, agotado, lo normal sería irse a dormir, aunque eso supusiera ya el final del concurso. Pero ains, volví a caer... me he leído el enunciado del siguiente ejercicio y como buen developer yonki... ¡tenía que hacerlo!.


Y tenía que hacerlo porque el ejercicio 15, Take a corner, es... ¡¡¡un Othello!!!, o sea... ¡¡¡un Reversi!!!. ¡¡¡Me encanta el Reversi!!!. ¡Con mi primer ZX Spectrum, hace ya potorrón de siglos, venía de regalo un juego de Reversi!. Pero es que hay más... ¡YO tengo programado un juego de Reversi!. Lo hice hace un montón de años para JavaME, y lo pasé a Android el año pasado.

Mi Reversi, ¡snif!

En el ejercicio se plantea una solución inicial y se pide qué movimiento hay que hacer para que en N jugadas más, haga lo que haga el contrario, se gane una esquina. Mi juego es malo con ansia, así que no cubría esa posibilidad, pero sí he aprovechado para copiar el código de gestión del tablero de Reversi y que obtiene los posibles movimientos a partir de una situación. Una vez teniendo eso, he hecho una sencilla exploración de todas las posibilidades, considerando que cuando le toca mover al jugador inicial basta conque un movimiento sea exitoso, y cuando le toca mover al contrario tienen que serlos todos.

Estaba tan emocionado ante la posibilidad de reutilizar el mismo código por tercera vez (soy un gran fan de la reutilización) que me recreé especialmente en la solución. ¡Y qué demonios!, ¡¡¡se lo iba a contar a mi amigo el revisor de Tuenti!!!

/**
 * Dear Tuenti Engineer:
 * I've programmed a solution a bit more elegant this time, thinking that this one
 * was going to be the last. I'm not 100% sure, although it's almost 6:00 in the
 * morning and I think this week has been exhausting enough.
 * Thanks for your work and please keep doing things like this.
 * I need a bed. Now!
 * Good night!
 */

Ahora ya sí, con mi consciencia perdiéndose en ovejillas saltando vallas, ¿qué debería haber hecho?: dormir. ¿Qué he hecho?: pffff, está claro... ¡leerme el siguiente ejercicio!

Y así he llegado al ejercicio 16, ÑAPA. Y, ¡ay!... me volví a picar. El ejercicio se trataba de calcular cuántos círculos intersectan entre un mogollón que te dan (potencialmente millones). La solución obvia era... ¡tan obvia!. Recorrerlos todos entre sí y hacer un sencillo cálculo de colisiones, aplicando para ello el teorema de Pitágoras... sí, ese mismo que habría hecho bien en aplicar en el ya lejano ejercicio 3 en lugar de las malditas interpolac... ¡¡¡AGH, NO QUIERO PENSAR EN ESO!!!.

El caso es que... qué demonios, igual no había trampa. Igual en Tuenti querían premiar a la gente que había llegado hasta aquí y ponerles algo facilón. Las ovejas me decían que no había otra solución posible. Y, bueno, me daba tiempo a probar. Los tests iniciales me funcionaban suficientemente rápido. ¿Qué pasaría con la entrega?. Por supuesto, tenía que compartir esto con mi amigo el revisor de Tuenti:

/**
 * Dear Tuenti engineering:
 * 
 * Ouch! I shouldn't have read this challenge... just when I was dreaming on my
 * feet and ready to go to bed, I had the terrible idea of reading it. And...
 * bad idea, really really bad idea, because it's quite easy! Actually, I think it's
 * the easiest challenge!... unless you pretend to process the 8 million points in
 * a reasonable time and there's a hidden trick, but I don't think so (maybe 
 * that's because I'm almost asleep). I'll see it right now. I'm scared. If
 * there's a trick, you are very clever, my friend... hmmm maybe "painting" the
 * points in a grid with the limited 100x100 space, maybe?, and so iterating
 * points in order N -and not N!-, and after that iterating the 100x100 points?...
 * yeeks, I'll better not think on it, it's late!.
 * 
 * I'll try as well to NOT reading the next challenge. Seriously. Promised. Or so.
 * I don't think I have enough time to solve it, anyway...
 * 
 * P.S.: Ooooooooook, I got it! I have and idea, will I correct it in time???
 * 
 * Sincerely,
 * @author andres
 */

Probé y... nada. Se tiraba mogollón de tiempo (ni sé cuánto, pero apuesto a que horas). Como se puede ver al final del comentario, dejé de escuchar a las ovejas y se me ocurrió una solución. Tampoco era demasiado complicado de hacer, aunque el tiempo se me estaba acabando, incluso aunque no durmiera nada.

Se trataría de dividir el espacio, que tiene unos límites definidos (y que no era ni mucho menos 100x100 como pongo en el comentario, prueba inequívoca de que estaba ya en babia), en varias zonas cuadradas. Cada cuadrado se recorre enterito combinando todos los círculos que tenga dentro. Al pasar al siguiente cuadrado, se guardan en un hash las colisiones que se han detectado, porque los mismos dos círculos que colisionan en una zona pueden colisionar también en la siguiente, y no queremos contarla dos veces. Para que el hash no tenga demasiados elementos, calculamos el rectángulo que contiene la intersección de la colisión, y cuando estemos en la zona que contiene la esquina inferior derecha, lo quitamos del conjunto hash. Esto es así porque las zonas las recorría de arriba a abajo y de izquierda a derecha.

Conseguí que la ejecución se hiciera en solo unos segundos, pero al hacerlo el resultado dejó de ser correcto. Creo que la solución que he planteado está muy bien y seguramente sea "la buena", pero he debido hacer algo mal en la implementación. Posiblemente al dividir el espacio en zonas, no sé.

Ya no podía seguir, se me había acabado el tiempo, a pesar de que al final no he dormido nada. Me ha fastidiado no poder entregar correctamente el ejercicio, porque creo que ya casi lo tenía, pero así es la vida...

Conclusiones

El concurso es... mortal. Requiere muchas energías, son demasiados ejercicios, y no son sencillos. Incluso aunque le dediques solo ratos sueltos, si tienes un trabajo exigente y poco tiempo libre, te va a dejar agotado. Mi gran problema, además, es que cuando leía un ejercicio me picaba, independientemente de la hora que fuera. Y si algo he aprendido en este concurso es que cuando llegas a cierto nivel de cansancio y falta de sueño es mejor parar, porque las soluciones que encuentres no van a ser buenas, y te va a costar mucho pensar.

Personalmente preferiría que el concurso tuviera pocos ejercicios y que fueran los más difíciles. Que cada ejercicio que resuelvas tenga su mérito. Solo eso ya es suficiente para hacer un concurso chulo.

Aparte de eso, tengo que decir que el concurso es también muy interesante. Los ejercicios, aparte de algún enunciado ambiguo o no suficientemente definido, están bastante bien, y algunos son realmente divertidos de resolver.

Por otra parte, mi crítica va también a la forma en la que estoy viendo que Tuenti trata el concurso una vez acabado. Mientras estábamos concursando teníamos un ranking con el número de ejercicios que había entregado cada uno, aun sin saber cuántos estaban bien o mal. En cuanto el concurso acabó, el ranking desapareció. Vale que se supone que la puntuación final tiene un componente subjetivo que le dan los revisores de Tuenti a la limpieza de cada solución, pero creo que un simple ranking automático en base al número de ejercicios resueltos por cada uno nos hubiera encantado a todos los participantes. Aunque luego no fuera definitivo y los ganadores no tuvieran por qué ser los primeros puestos de dicho ranking. Creo que basta con dejarlo claro. Es que así es tan... ¡cortarrollos!

Por mi parte, en el ranking provisional de ejercicios entregados sin corregir creo recordar que quedé en el puesto 25. Luego por email me han confirmado que estoy entre los 50 primeros, aunque no haya aún un ranking definitivo (que no tengo muy claro que al final vaya a existir).

No me siento especialmente orgulloso de mi participación, creo que he hecho demasiados ejercicios con demasiado sueño, y quizá debería haberme centrado en hacer menos ejercicios pero con más calma y energías. Pero sí estoy contento con cómo planteé los últimos ejercicios que hice, los que comento en esta tercera parte del mega-artículo. Y oye, quedar entre los 50 primeros está bastante bien.

Pero qué demonios, aun con todo, tengo que decir que lo más importante es que me lo he pasado genial.

de protocoloipv6.blogspot.com