Challenge 4 – Help Pythagoras Junior

Este fue, probablemente, el problema que más tiempo me llevó resolver y que más fundamento teórico/matemático exigía junto al Challenge 3.

Planteamiento

El cuarto desafío consistía en encontrar, dado una serie de lados (longitudes), los tres que formaran el triángulo con el menor perímetro posible. Una vez encontrados dichos lados, si existieran, la salida del problema es dicho perímetro minimizado.

De nuevo, el formato del fichero de entrada tenía una estructura particular:

2
6 13 9 1 13 17 6
7 110 40 10 1 20 60 3

1ª fila: número de casos a resolver (2 en el ejemplo)
Para cada caso:
- 1er carácter: número de lados L a analizar (6 y 7 para los dos casos del ejemplo)
- Siguientes L caracteres: longitud de los lados (13, 9, 1, 13, 17 y 6 en el primer caso)

Para cada caso había que dar una salida indicando el número de caso y el valor del perímetro mínimo calculado siguiendo el formato siguiente:

Case #1: 27
Case #2: IMPOSSIBLE

Entre los lados del primer caso (13, 9, 1, 13, 17, 6) el triángulo de menor perímetro lo forman los lados 13, 1 y 13, dando un perímetro de 13 + 1 + 13 = 27.

Entre los lados del segundo caso (110, 40, 10, 1, 20, 60, 3) no es posible formar ningún triángulo (explicado más adelante).

Solución

Lo primero que hay que considerar es la posibilidad de formar un triángulo con los lados proporcionados. Del ejemplo se deduce que hay una posibilidad de no poder formar un triángulo con ninguna combinación de 3 lados de entre los L proporcionados. Esto viene explicado por el Teorema de la Desigualdad Triangular:

triangle

La suma de las longitudes de dos lados de un triángulo es mayor que la longitud del lado restante.

Sin entrar en detalle, esta simple inecuación basta para resolver, en principio, el problema planteado.

La codificación de este problema pasaba por analizar, para cada conjunto de lados posibles, todas las combinaciones de lados mediante la función combinations del módulo itertools.

        for case in range(cases):
            sides = [int(i) for i in infile.readline().split()]
            min_perimeter = 0
            del sides[0]
            sides.sort()

            for a, b, c in itertools.combinations(sides, 3):
                if a + b > c and b + c > a and a + c > b:
                    min_perimeter = a + b + c
                    break

            if min_perimeter == 0:
                outfile.write(
                    "Case #" + str(case + 1) + ": " + "IMPOSSIBLE" + "\n")
            else:
                outfile.write("Case #" + str(case + 1) + ": " + str(
                    min_perimeter) + "\n")

Si los lados a, b y c cumplían con la desigualdad triangular, al estar la lista de lados ordenada, bastaba para identificar su perímetro como el mínimo posible. En caso de no haber identificado un nuevo perímetro distinto de 0, la inecuación no se cumpliría nunca y ese caso se declararía IMPOSSIBLE. Es necesario recalcar la importancia de tener la lista ordenada, ya que dado el tamaño de los ficheros de entrega (1000 lados a analizar para 131 casos), se hace imposible analizar todas las combinaciones en un tiempo razonable.

Puedes consultar la implementación completa en Python de este desafío en GitHub y el resumen de mis impresiones de esta edición en esta entrada del blog.

Challenge 3 – Board games

Planteamiento

El tercer desafío del Tuenti Challenge consistía en diseñar un hipotético juego de mesa y hallar el mínimo número de cartas no repretidas necesario para representar todos las puntuaciones posibles desde 1 a P, siendo P la puntuación máxima del juego. Es decir, para una puntuación máxima de P = 10, se deberían poder representar 1, 2, 3, 5, 6, 7, 8, 9 y 10 puntos.

Como en los anteriores problemas, se parte de un fichero de entrada con una estructura semántica concreta:

1ª fila: número de casos a resolver (3 en el ejemplo)
Para cada caso:
- Una sola fila: puntuación máxima a representar o P (1, 6 y 3 en el ejemplo)

Para cada caso había que dar una salida indicando el número de caso y el número de cartas necesarias siguiendo el formato siguiente:

Case #1: 1
Case #2: 3
Case #3: 2

Para representar el 1 nos valdría con 1 carta (1)
Para representar del 1 al 6 nos valdría con 3 cartas (1, 2 y 3)
Para representar del 1 al 3 nos valdría con 2 cartas (1 y 2)

Solución

Normalmente todos los desafíos de este tipo tienen algún tipo de truco o atajo que minimiza tanto el tiempo de ejecución como la codificación en sí. En este caso se podría pensar que había que probar todas las combinaciones posibles de cartas entre 1 y P, pero no era así.

Afortunadamente, existe un sistema de representación que cuadra perfectamente con este problema. Puede representar todos los números mediante la suma de otros componentes, indica ausencia o presencia de dichos componentes y es muy probable que si has llegado hasta aquí estés más o menos familiarizado con este sistema: la representación binaria. Podemos representar todos los números usando potencias de 2.

Por ejemplo, para un P = 17, necesitaríamos 5 cartas potencias de 2 con los valores 1, 2, 4, 8 y 16 respectivamente.

Índices (i)	4	3	2	1	0
Representación binaria	1	0	0	0	1
Valor (2^i)	16	0	0	0	1

En otras palabras, el problema nos está pidiendo el número de bits necesarios para representar la puntuación máxima P del juego.

Una vez llegado hasta aquí la codificación es bastante sencilla. Básicamente estaríamos traduciendo la siguiente fórmula:

formulatuenti2

Dado que en el módulo math de Python Standard Library disponemos de la función logaritmo en la base deseada, el núcleo del algoritmo es básicamente una sola línea.

        for case in range(cases):
            points = int(infile.readline())
            cards = math.ceil(math.log(points, 2))

Para cada caso, extrae el valor de la puntuación máxima en la variable points y calcula el entero superior más cercano a su logaritmo en base dos. Este es el resultado en número de cartas (cards) del Challenge 3 – Board games.

Puedes consultar la implementación completa en Python de este desafío en GitHub y el resumen de mis impresiones de esta edición en esta entrada del blog.

Challenge 1 – Pizza Love

Planteamiento

El primer desafío de esta edición del Tuenti Challenge fue bastante sencillo, pero sirvió para ver cómo iban a ser, en mayor o menor medida, el resto de los challenges. El desafío consistía en encontrar el mínimo número de pizzas para satisfacer a una serie de comensales. El hambre de dichos comensales venía indicada por el número de porciones de pizza que se iban a comer y cada pizza contenía 8 porciones.

El fichero de entrada contenía un número de casos en los que había que resolver el problema descrito anteriormente. El formato de la entrada era el siguiente:

1ª fila: número de casos a resolver (3 en el ejemplo)
Para cada caso:
- 1ª fila: número de comensales (3 en el primer caso, 2 en el segundo…)
- 2ª fila: porciones de pizza deseadas por cada comensal (8, 8 y 8 en el primer caso)

Para cada caso había que dar una salida indicando el número de caso y el número de pizzas necesarias siguiendo el formato siguiente:

Case #1: 3
Case #2: 1
Case #3: 3

Solución

Como cada pizza se divide en 8 porciones, la resolución de este primer desafío consistía en sumar todas las porciones de cada caso y dividir el resultado de dicha suma entre 8. Luego, usando alguna función similar a math.ceil de The Python Standard Library, nos quedaríamos con el entero superior más próximo al resultado de la anterior división. La representación de esta solución sería la siguiente:

formulatuenti1

siendo n el número de comensales en cada caso y hunger el número de porciones de pizza desadas por cada comensal.

Resumen de la implementación

El núcleo de la implementación, omitiendo la mayoría de operaciones con ficheros, es el siguiente.

cases = int(infile.readfile())

for case in range(cases):
    next(infile)
    hunger = list(map(int, (infile.readline().split())))
    slices = sum(hunger)
    pizzas = math.ceil(slices / 8)

Para cada caso, se salta la primera línea correspondiente al número de comensales (dato innecesario) mediante la función next(). En la variable hunger se almacenará una lista con el número de porciones deseadas por cada comensal. Se tiene que mapear a enteros debido a que la lectura devuelve caracteres. En la variable slices se guarda la suma de estas porciones y el resultado se halla dividiendo esta suma entre 8, el número de porciones por pizza. Para asegurar que cada comensal se sacia, el resultado se aproxima al siguiente entero superior y se guarda en la variable pizzas.

Puedes consultar la implementación completa en Python de este desafío en GitHub y el resumen de mis impresiones de esta edición en esta entrada del blog.

Tuenti Challenge 7 – El after 1.0

Resumen

Una vez finalizado el período de evaluación del Tuenti Challenge 7, aprovecho para hacer un pequeño resumen de los problemas planteados y el enfoque y solución que les di a los que pude resolver.

Para el que no lo sepa, el Tuenti Challenge es un concurso de programación anual que se basa en resolver una serie de problemas o challenges que se van presentando de manera secuencial. Es decir, se desvelan a medida que vas superando los anteriores y suele ir incrementando en dificultad. Lo ideal es no saltarse ninguno, pero se da la oportunidad de intentar los siguientes si has pasado más de 24 horas intentando resolver un ejercicio en concreto.

En total pude resolver correctamente* 3 de los 6 desafíos que pude intentar en tiempo de concurso, ya que me incorporé a 2 días de la fecha límite. Después de la fecha límite pude resolver algunos más, ya que muchos estaban prácticamente a punto, pero no entraron a concurso. La mayoría de los problemas sigue una estructura similar:

Leer y parsear un fichero de texto plano con una determinada estructura semántica (lo que significa cada línea).
Resolver el challenge.
Escribir el resultado en otro fichero de texto plano con una estructura determinada.

Una vez hallada una solución, la propia plataforma proporcionaba unos casos de prueba. Si se pasaba el 100% de estos casos, se pasaba a la fase de envío. En la fase de envío los casos de prueba eran mucho más exigentes, por lo que una solución que pasara la fase de prueba no implicaba, necesariamente, pasar la fase de envío.

Impresiones

Como he comentado anteriormente, no participaba con la intención de quedar en una buena posición, pero sí de ver qué tal se me daba este tipo de competiciones y cómo me desenvolvía en un lenguaje que estoy prácticamente aprendiendo a usar (learn by doing que le llaman). También me ha servido para quitarme la espina del Google Haschode 2017 en el que no pude presentar ninguna solución válida y era el primer concurso del estilo en el que participaba.

Una de los aspectos que más me gustó de esta competición fue la variedad de desafíos, lo que exigía cierta formación multidisciplinar. De los que pude resolver o intentar, encontré desafíos que implicaban conocimientos sobre algoritmia general, combinatoria, web scraping, reconocimiento de imágenes, teoría de grafos, estructuras de datos, criptografía y protocolos web. En algunos de estos campos estaba bastante verde o eran totalmente desconocidos para mí, por lo que salgo de Tuenti Challenge 7 con unos cuantos «deberes».

Resultados

El resultado ha sido bastante mediocre, pero satisfactorio respecto a lo esperado, quedando en el puesto 327 de más de 1500 registrados (percentil 78,2%). El rendimiento de las soluciones no fue el mejor, pero la mayoría llegaban a resolver los diferentes desafíos completados correctamente.

Otro de los aspectos que más me interesaba era el de optimizar y mejorar la legibilidad del código para lo cual decidí usar las líneas de código como métrica. Aunque no se trataba de una competición de Code golf, la intención siempre fue reducir el número de líneas innecesarias sin que la legibilidad se viera perjudicada. En una primera versión sin depurar me han salido unas 40 líneas de código medias por challenge, dato que compararé con las medias de todos los envíos cuando Tuenti publique sus estadísticas propias.

descarga — Líneas de código por *challenge.* Elaboración propia.

Para leer más

Le intentaré dedicar una entrada a cada uno de los problemas para poder explicar mi solución con el fin de compartir la idea y de, por qué no, recibir aportaciones para mejorarla aunque fuera de concurso. El código está liberado en este repositorio.

Las entradas respectivas a cada problema son:

Challenge 1 – Pizza Love
Challenge 2 – Bowling
Challenge 3 – Board Games
Challenge 4 – Help Pythagoras Junior
Challenge 5 – Ghost in the HTTP (saltado y pendiente)
Challenge 6 – The Tower (pendiente)
Challenge 7 – Word Soup Challenge (pendiente)
Challenge 8 – Uni code to rule them all (saltado y pendiente)
Challenge 9 – The Supreme Scalextric Architect

*Aparentemente me hice un lío con los ficheros y envié la misma solución para dos problemas distintos, después de pasar la fase de prueba.

Las cinco lecturas de la semana (II)

Esta semana vienen todas las lecturas más bien enfocadas a la estética práctica (visualización de datos y tipografía, principalmente). Aquí van las cinco de esta semana:

Las cinco lecturas de la semana (I)

Inicio esta serie con el objetivo de enlazar publicaciones o artículos que haya leído recientemente (normalmente en la misma semana) y me apetezca compartir sin comentar ni aportar nada propio, simplemente enlazar.

En la mayoría de los casos el propio título es bastante indicativo del contenido, por lo que no haré más que listarlos. Ahí va la primera entrada en esta serie:

Eso es todo. Intentaré que sean lo más variado posible, incluso a veces saliéndose de lo que puede ser la temática de este blog.

Script con argumentos en la consola

Siguiendo con el ejemplo del limpiador de duplicados, aprovecho para añadir la posibilidad de elegir el directorio a «limpiar» sin tener que tocar el código. En este caso, se añade la posibilidad de introducir el directorio como argumento del script al ejecutarlo mediante la consola de comandos.

Para poder acceder a los argumentos, es necesario importar el módulo sys que nos permitirá acceder a su función argv que, como en otros lenguajes de programación como C/C++, devuelve una estructura tipo array cuyas posiciones contienen los argumentos introducidos.

import sys

Por ejemplo, si introducimos la siguiente línea de comandos

$> python ejemplo.py arg1 arg2

en este caso, los contenidos de argv[n] serán:

argv[0] = ejemplo.py
argv[1] = arg1
argv[2] = arg2

Por lo tanto, para acceder al primer argumento, usaremos argv[1]. El objetivo es introducir la siguiente línea de comandos

$> python limpiador.py "C:/Users/Fulanito/pruebas/"

y que el script acceda al directorio indicado y proceda a limpiar los duplicados.

Esto es tan sencillo como cambiar la antigua asignación de la variable ruta por el primer argumento introducido por comando (sin contar el propio nombre del script)

import sys

path = "C:/Users/Fulanito/pruebas/"
path = sys.argv[1]

El resto del código, referente a la funcionalidad de encontrar y eliminar duplicados, es el mismo que el del post anterior y puedes verlo aquí.