viernes, 9 de mayo de 2014

TuentiChallenge4: Diario de un developer yonki (2): la cosa se pone chunga

¡OJO!: Esta entrada es continuación directa de
TuentiChallenge4: Diario de un developer yonki (1)

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

Día 4

Hoy me he puesto otro rato con el concursillo de marras, para no variar.

Primero he empezado con el ejercicio 5, Tribblemaker, que se trata de implementar el Juego de la Vida (aunque no lo decían explícitamente, pero se daban pistas más que obvias), y detectar ciclos en la evolución. El ejercicio resultaba bastante entretenido de programar y daba para hacer código ordenadito, así que me he recreado en eso.

El siguiente, el ejercicio 6, Man in the Middle, me ha encantado. Se trataba de crear un servicio que se metiera en medio de la comunicación encriptada entre un cliente y un servidor, basada en claves que se van intercambiando entre ellos.


Para poder resolverlo, se proporciona el código fuente tanto de la parte cliente como de la parte servidor... en Javascript, o sea, NodeJs. Para alguien con conocimientos de seguridad y que sepa NodeJs imagino que el ejercicio estaba chupado. Para los que no, el ejercicio resultaba realmente divertido. Y mira que yo de criptografía ni flowers, nada de nada.

El ejercicio se podía hacer sin problemas en otros lenguajes, pero teniendo ya los fuentes en Javascript, lo normal es que sea mucho más sencillo resolverlo así. De esta forma, se trata de instalar NodeJs, ver cómo funciona, probarlo, revisar ambos códigos fuentes, hacerte tus esquemas de cómo funciona su intercambio de claves, y finalmente programar la solución, que básicamente se hace mezclando el código del cliente y el del servidor. Podría hacerse incluso sin saber Javascript ni nada de criptografía, que es lo que me parece más genial de este ejercicio. La clave en mi caso para que todo resultara más fácil fue crear un objeto diferenciado para el cliente y otro para el servidor, de forma que todo se hace bastante lógico y comprensible. Crecidito por lo bien que se me estaba dando el día, no he parado ahí.

El siguiente ha sido el ejercicio 7, Yes we scan, en el que se trata de encontrar una relación entre dos elementos a partir de un montón de conexiones. Temía que ya tuviera que ir pensando más en temas de rendimiento y algorítmica. Sin embargo, la verdad es que sólo con usar un par de hashes y tener un poco de cuidado con la forma en la que se obtienen nuevas conexiones indirectas por cada conexión nueva, conseguí que la prueba de entrega se resolviera en solo 10 segundos.


Y entonces me he crecido: ¡leche, en cuanto he dormido un poco qué bien me ha ido todo!. Eran ya las 3 y pico de la mañana, así que llegó ese momento que también conocen los jugadores de poker que están en racha: el momento de retirarse y continuar otro día. Por supuesto... ¡yo no lo hice!.

Así que toma porrazo con el ejercicio 8, Tuenti Reestructuration. Se trata de reorganizar posiciones de personas en mesas, basadas en permutaciones, hasta llegar a una situación final. O sea, segundo momento importante de la noche: ese en el que me doy cuenta de que posiblemente me encuentre ante un ejercicio típico de recorrido de caminos posibles, de esos que en algorítmica tienen tan trillados, pero que yo nunca me entero de cómo lo resuelvo. ¡Ains, ya estoy como siempre!

Lo peor es que el enunciado me ha parecido muy confuso, no deja muy claro cuáles son los movimientos posibles, así que estoy perdiendo muchísimo tiempo sólo para enterarme... y ya se está haciendo de día. ¡Mierda, con lo bueno que era el día! A dormir.


Día 5

Esto de dejarse un ejercicio a medias no mola nada, he estado todo el tiempo dándole vueltas al dichoso ejercicio hasta que me he podido poner con él. Por fin estoy seguro de qué movimientos son los válidos, y le he puesto las heurísticas que se me han ido ocurriendo para que no fuera demasiado lento: probar primero el camino que se acerque más a la solución, control para dejar de recorrer un camino cuando ya tengamos uno mejor, detectar estados ya recorridos... total, que entre unas cosas y otras me he tirado un montón de tiempo con el tema. Al final la entrega se ha tirado varios minutos de ejecución, así que imagino que habrá soluciones mejores, pero para no saber nada de algorítmica creo que ha quedado bastante decente. Eso sí, esto está empezando a complicarse de verdad.

Esto lo confirmó el ejercicio 9, Bendito Caos, que tenía tela. Se trataba de averiguar cuántos coches pueden llegar en una hora desde un punto a otro, calculándolo a partir de las velocidades de los caminos entre cada par de vértices. En este caso estoy aún más seguro de que existen algoritmos que implementan esto sin problema. Pero a mi me iba a tocar hacerlo a lo bruto.

Me ha llevado un rato sacar las reglas de mezcla de las velocidades, para saber cómo se puede calcular la velocidad global entre el vértice de inicio y el de fin, combinando las de todos los caminos posibles. También había que tener cuidado con los bucles. Pero sobre todo no tenía ni idea de cuál sería el rendimiento de mi sencilla solución. En el ejemplo iba rápido, pero el enunciado de este ejercicio no era, la verdad, demasiado bueno. No sólo la explicación era un poco confusa (no tanto como el anterior pero casi), sino que sobre todo, no dejaba claro en ningún momento cuáles eran los límites en número de nodos y de caminos. ¡Tercer WTF del concurso!

Yo, siempre optimista, lo interpreté como que eso sería que no le iban a meter mucha caña. Gran error. Lo puse a ejecutar y eso seguía y seguía y no acababa. ¿Qué pasaría si lo cortaba a medias e intentaba arreglarlo?. Hice la prueba y vi que aparentemente se podía. Hice un cambio en la línea de comando para obtener más información y lo volví a ejecutar. Grandísima cagada. Me equivoqué al poner la línea de comando, así que lo ejecuté de forma incorrecta, pero la entrega se consideró válida.

Por culpa del ejercicio casi llego tarde al cine, donde pude desengrasar un poco mis pobres neuronas viendo a Spider-man pegando tortazos a troche y moche. Mano de santo, oiga, que el dolor de cabeza que se me había quedado hoy era tremendo.

Spidey sí que sabe cómo hay que enfrentarse a los Challenges del Tuenti
¡¡¡A tortazos!!!

Al volver a casa le he echado un vistazo al siguiente ejercicio, con la firme intención de no ponerme con él. Y ha resultado ser un WTF con todas las de la ley. A ver si mañana entiendo algo, porque hoy lo veo realmente negro.


Día 6

El ejercicio 10, Random Password, es tan tan tan WTF, que el enunciado apenas dice: 

It seems to be a random password... how could it be?
Get the key for your input. Start at: http://random.contest.tuenti.net/?input=INPUT

¡¡¡¡¿¿¿Eeeeeeeeeeeeeeeeeeeeeeeeeeeeh???!!!! Espera que lo lea otra vez... sí. Ya veo. Entendido. Entendido que no entiendo nada, quiero decir. Probé a mirar el código fuente del servidor y poco más se me ocurrió. Como ya he dicho, no tengo ni idea sobre seguridad, que es de lo que obviamente trataba esto, así que tras estar un buen rato dándole vueltas, lo descarté.

El ejercicio 11, Pheasant, insiste en la seguridad. ¡Otra vez!. Aunque en este caso parece que algo se puede hacer sin saber nada de encriptación. Se trata de averiguar una clave AES en la que faltan 3 posiciones, a partir de datos conocidos. Lo único que se me ha ocurrido es probar todas las combinaciones en esas 3 posiciones hasta dar con la buena. En lugar de hacerlo con el fichero entero, creo que lo importante es hacerlo solo con los 32 primeros bytes, que he visto que era suficiente en cualquier caso según los límites dados, y que agilizaba muchísimo el proceso. Al hacer la entrega he visto que se ha tirado bastantes minutos, pero sin conocer cómo funciona el AES creo que era imposible hacer nada mejor. También sospecho que la implementación de AES que he usado, que es la que viene por defecto en Java (JCE), debe ser bastante lenta.

El ejercicio 12, Taxi Driver, volvía a ser algorítmico. Es más, en el fondo el problema era muy muy similar al número 8, el de la reestructuración de mesas que tanto tiempo me llevó y que no me quedó demasiado rápido, y que seguro que conociendo los algoritmos típicos se hace en un momentín... ¡¡¡Otra vez el mismo problema de siempre, el que he hecho millones de veces y nunca bien!!!.


He entrado en tal estado de enajenación que he decidido comunicarle mi frustración a un posible corrector. Así que he puesto este comentario en el código, con un par:

/**
 * NOTE
 * ===============
 * 
 * Dear Tuenti Engineer:
 * 
 * Oh, no, the same problem... again! This is almost the same as challenge 8!
 * I'm pretty tired of doing the same problem, and not finding a really GREAT
 * solution to avoid loops in a proper way and find good heuristics (I could
 * swear I've found it also other times in my past... in Google Code Jam, maybe?).
 * 
 * This time, I've decided to program a reusable solution, in the form of this
 * PathFinder class. It's a pity I can't use it for challenge 8 yet, but I'm
 * in the hope that I can find this same problem again. Call it a longshot if
 * you may.
 * 
 * I'm losing some precious minutes in this, but I'm sure you will appreciate
 * it. Enjoy it, my friend.
 * 
 * @author andres
 *
 */

He hecho una preciosa clase PathFinder capaz de resolver todos estos problemas similares. Como ya he dicho, la falta de sueño y el dolor de cabeza que me habían causado los problemillas me han hecho entrar en un grave estado de enajenación. Y tanto, no sabía hasta qué punto...

El caso es que al ejecutar la entrega, sintiéndome en pleno deja vú, veo que eso sigue ejecutando... y sigue ejecutando... y sigue ejecutando... y no para. Mato el proceso, cambio la línea de comando, vuelvo a ejecutar y... adivina.

¡¡¡Sí!!!. ¡¡¡Vuelvo a equivocarme al modificar la línea de comando!!!.

Otra entrega a freír espárragos. Para una vez que me pongo a hacer una clase más genérica, primero la hago demasiado lenta y luego la dejo a medias por pura torpeza... qué grande.

Ejercicio 13, Tuenti Timing Auth.Con los ojos ardiendo en fuego, miro el siguiente ejercicio, con la esperanza de que sirviera para redimirme. ¿Y qué encuentro?.

¡¡¡Otro ejercicio de seguridad, similar al otro que me salté!!!
(en este caso sobre "side channels", tema sobre el que sé lo mismo que el anterior, o sea, nada).

No me lo podía creer.

Tras darle vueltas al tema la correspondiente ración de tiempo inútil, desistí.
¡¡¡¡¡WTF doble, diablos!!!!!

Al rato me levanté, tembloroso, casi sin fuerzas. En la espuma a mis pies yacían dos mundos muertos. Con mi propósito casi olvidado tras el torbellino de violencia, miré estúpidamente a la pantalla. Al poco, recuperé mi raciocinio. Buscaba venganza. ¿Podía aprovechar de alguna forma las circunstancias?...



¡OJO!
: Esta entrada continúa en:





3 comentarios:

  1. "Al hacer la entrega he visto que se ha tirado bastantes minutos, pero sin conocer cómo funciona el AES creo que era imposible hacer nada mejor."

    My solution in python takes a couple of seconds without any knowledge of AES. The trick is to decipher only the users that are needed to return the top N events by using the timestamps: https://github.com/pedrosorio/tuenti_2014/tree/master/prob11

    "y que seguro que conociendo los algoritmos típicos se hace en un momentín... ¡¡¡Otra vez el mismo problema de siempre, el que he hecho millones de veces y nunca bien!!!."

    Truth be told, that is a really easy problem to solve as you say. Graphs (and associated algorithms) are one of computer science's themes that have widest application and if you learn about them you are going to find a lot of places where they can make your life easier.

    In this case, the "algoritmo típico" is a breadth first search (BFS). I don't know of any online source in Spanish, but if you are interested, Sedgewick's Algorithm course (part II) starts with this and it's pretty good: https://www.coursera.org/course/algs4partII
    It also uses Java for the examples which is nice.

    ResponderEliminar
    Respuestas
    1. I should correct the statement above: my solution takes *a few* seconds (around 30) in the submit phase, not just a couple. But well... it's python :)

      Eliminar
    2. Hi, Pedro. Yes, I saw your solution to challenge 6 after I wrote the post, and you're right, very clever! Many times we are obsessed over our lack of knowledge of X and that doesn't allow us to find the right solution... wich doesn't require that knowledge of X. ;-)

      Thanks for your info :-D

      Eliminar

cookie consent