Tuenti Programming Contest

1ª Competición de Programación Tuenti, Tuenti Programming ContestDurante la semana pasada he participado en la 1ª Competición de Programación Tuenti, con menos tiempo del que me hubiese gustado pero con el propósito único de divertirme y seguir aprendiendo, ya que tenía claro que había gente mucho mejor que yo; de hecho, para cuando empecé a programar el primer problema el martes, ya había gente que la noche anterior había pasado los siete primeros retos. Finalmente fueron sólo diez los que superaron las veinte pruebas.

Stats, Participants per level, Tuenti Programming ContestYo llegué hasta el sexto desafío y puedo estar contento, ya que significa haber hecho más que el 68.38% de los que superaron la primera ronda (un simple nivel de prueba). Aunque si quisiese ver el vaso medio vacío, todavía hay un 29.16% de los participantes que han superado al menos una ronda más que yo..

Esta competición me ha gustado bastante más que la Facebook Hacker Cup que disputé en enero, porque los problemas no han sido tan matemáticos, y la dificultad de entenderlos y diseñar un buen y eficaz algoritmo ha estado mucho más valorada. Además, tanto el sistema de prueba como el de envío estaban mucho mejor montados, mediante scripts que se comunicaban directamente con su servidor.

Soluciones (código)

El Challenge 1 llamado Super hard sum consistía en sumar todos los números de cada línea dada; la mayor dificultad era que los números podían ser muy grandes, así que lo solucioné usando la función bcadd para sumarlos.

En el Challenge 2, llamado Tlang, sube de golpe la dificultad (un 31.5 % de los participantes no lo ha superado) y nos invita a interpretar un extraño lenguaje de programación. Es fácil darse cuenta con los ejemplos que = equivale a sumar, # a multiplicar y @ a restar, mientras que ^ y $ son los paréntesis inicial y final. Así que la dificultad radica en realizar un algoritmo iterativo que va resolviendo cada pequeño bloque hasta obtener el resultado final.

Obtener la suma de todos los Emirps hasta X es el enunciado del Challenge 3. ¿Qué es un emirp? Es un número primo que dado la vuelta sigue siendo primo, exceptuando los números capicúa. Así que una vez comprendido esto, el principal problema es optimizar el algoritmo de obtención de los números primos para que supere el test. Yo lo optimicé evitando comprobar los números pares y dividiendo los impares sólo hasta su raíz cuadrada.

Challenge completed, Tuenti Programming Contest

En el Challenge 4 llamado Task Duration pensaba que me quedaba (otro 20.5 % de la gente atascada) pero al final conseguí resolverlo y aun no sé como, jaja. Lo primero fue leer un archivo de 18 MB comprimido en un zip de 5.72 MB que almacené en dos vectores, uno para las tareas y otro para las dependencias. Luego de forma recursiva analizo todos los caminos del árbol, teniendo en cuenta que las tareas que no tienen dependencias se pueden realizar en paralelo, y finalmente devuelvo el que tarda más tiempo. Una de las cosas que me sorprendió al resolverlo es que se desborda el número de iteraciones (más de 100) y hay que cambiar en el php.ini la opción xdebug.max_nesting_level para poder solucionarlo. Aun así pensaba que no pasaría el test por falta de eficiencia pero parece que no estuvo tan mal.

Y el último que resolví fue The Milkman Problem en el Challenge 5 y en el que hay que optimizar el número de vacas que caben en un camión, de peso limitado, obteniendo la mayor producción posible de leche. Es un problema conocido como Knapsack, así que sólo tuve que buscar un algoritmo que funcionase.

Con el Challenge 6 The Clock ya no me quedaban muchas ganas ni tiempo suficiente, así que esta ha sido mi participación en el concurso. Si alguno quiere consultar mi código PHP y opinar sobre él, lo he subido al repositorio de GitHub. Agradeceré todas las opiniones y sugerencias.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s