Challenge 2 – Hidden numbers

En el segundo desafío de la edición de 2018 había que descifrar el orden de magnitud de una codificación “en una base arbitraria usando símbolos arbitrarios”.

La entrada es una serie de caracteres alfabéticos que representan un número, del cual no sabemos la base ni qué representa cada uno de sus dígitos. Sólamente sabemos que “todos los dígitos en la base están presentes una vez en cada cadena de entrada”.

Por ejemplo, la cadena ‘bfd’ estaría formado por dígitos en base 3 (0, 1, 2), pero sin ser necesariamente b=0, f=1, d=2.

Mi primer enfoque al problema fue el de buscar todas las posibles combinaciones para luego encontrar el menor (sin empezar por cero) y el mayor, y restarlos. Esto era increíblemente ineficiente, del orden de O(n!).

Con un poco de testeo a papel y lápiz se puede encontrar una cierta similitud entre los mínimos y máximos números de cualquier base:

  • Mínimo: Un 1 seguido de un 0 y luego la secuencia de los números de la base en orden (102, 1023, 10234, etc.)
  • Máximo: Los números de la base en orden descendente (210, 3210, 43210, etc.)

Para encontrar dichos valores, primero debemos hallar la base de la codificación:

def get_base(line):
    line = line[0:len(line) - 1]
    res = range(len(line))
    return res

Con esta base se pueden calcular el máximo y el mínimo de la siguiente manera:

def get_minimum(base):
    minimum = [1, 0]
    for num in base[2:len(base)]:
        minimum.append(num)
    return minimum

def get_maximum(base):
    maximum = []
    for num in reversed(base):
        maximum.append(num)
    return maximum

Ahora sólo faltaría hallar el rango entre estos dos valores en decimal, para lo que usaremos otra función.

def to_decimal(comb):
    base = len(comb)
    res = 0
    for i, num in enumerate(reversed(comb)):
        res += num * pow(base, i)
    return res

minimum = get_minimum(base)
maximum = get_maximum(base)

res = to_decimal(maximum) - to_decimal(minimum)

Challenge 1 – Waffle Love

El primero de los desafíos consistió en calcular el número de agujeros de un gofre, dado el número de líneas horizontales y verticales (n y m) de este.

Probando para unos cuantos casos base de n y m se puede ver que el núemero de agujeros h sigue el patrón siguiente:

h = (n - 1) \times (m - 1)

Por lo tanto, la solución al primero y más sencillo de los problemas del Tuenti Challenge 2018 quedaría de la siguiente manera:

def waffle_holes(n, m):
    return (n - 1) * (m - 1)

Aplicado a cada uno de los casos del fichero de entrada.

 

Tuenti Challenge 8

El año pasado participé por primera vez en una competición de programación, el Tuenti Challenge 7. Entonces, me pilló un poco despistado y por sorpresa, pero me gustó bastante el formato y decidí volver a participar en la edición de este año.

Una vez finalizado el Tuenti Challenge 8, vuelvo a publicar mis soluciones y breve explicación o write-ups para cada uno de los desafíos. Esta vez me centraré únicamente en la implementación algorítmica de la solución, dejando la burocracia (leer, parsear, transformar y escribir en fichero) de lado.

No pude dedicarle todo el tiempo que me hubiera gustado, pero fue una edición bastante entretenida y más difícil, en mi opinión, que la anterior. Terminé en el puesto 213 de 650 (contando sólo participantes que subieron al menos una solución), lo que me sitúa en el percentil ~67. Sólo 4 participantes consiguieron resolver correctamente los 15 problemas de esta edición.

Conforme vaya publicando los write-ups los iré enlazando aquí a modo de índice:

  • Challenge 1 – Waffle Love
  • Challenge 2 – Hidden Numbers
  • Challenge 3 – Scales
  • Challenge 4 – Brave Knight
  • Challenge 5 – DNA Splicer
  • Challenge 6 – Button Hero
  • Challenge 7 – Unknown cartridge
  • Challenge 8 – Security by doorscurity
  • Challenge 9 – Scrambled photo
  • Challenge 10 – Dance
  • Challenge 11 – Lasers
  • Challenge 12 – Victoria’s Secret
  • Challenge 13 – Pieces
  • Challenge 14 – Paranoid Android
  • Challenge 15 – The queue

 

Challenge 9 – The Supreme Scalextric Architect

Planteamiento

La temática de este desafío apuntaba directo a la infancia. Se trataba de determinar el máximo número de secciones de cada tipo necesarios para cerrar un circuito de Scalextric de un lote de secciones dado. Existen 3 tipos de secciones:

  • Recta (S)
  • Curva de 90º (C)
  • Doble recta (D)

Todas ocupan un cuadrado menos la doble recta, que ocupa dos, y no pueden superponerse unas sobre las otras (túneles o puentes).

El formato de la entrada es el siguiente:

3
5 2 7
0 4 0
3 7 1
  • 1ª fila: número de casos (3, en el ejemplo)
  • Para cada caso:
    • 3 caracteres que indican el número de secciones S, C y D (5, 2 y 7 en el primer caso)

El formato de salida indica el número máximo de secciones (agrupadas) que se necesitan para cerrar el circuito correspondiente a cada caso.

Case #1: 0
Case #2: 4
Case #3: 9

Para el primer caso se obtiene un máximo de 0, ya que al tener menos de 4 secciones C es imposible cerrar un circuito.

Para el segundo caso se usan todas las secciones (4 C) que es el mínimo circuito posible.

scalextric_C

Para el tercer caso se usan todas las secciones menos una C y una S.

scalextric

Solución

La resolución de este challenge se basa en identificar y controlar los casos conflictivos. El primero de todos ya se ha comentado anteriormente y hace referencia al mínimo de secciones curvas (C) para completar un circuito. Da igual la forma en que se dispongan las secciones que si no hay mínimo 4 secciones curvas el resultado va a ser siempre 0, por lo que este será el primer caso que se controle, además del más obvio:

if used_c < 4:
    used_c = 0
    used_s = 0
    used_d = 0

El segundo caso se da cuando existen exactamente 4 secciones curvas, el mínimo necesario. Este no es tan obvio como el primero, pero se puede deducir haciendo pruebas con papel y bolígrafo. Para este caso, se coge el número par de rectas simples (S) inferior o igual al disponible (#1) y, si este es superior o igual a 2, deja el número de rectas dobles (D) como el inicial (#2), ya que se podrán combinar bien con las simples. En caso de ser inferior a 2, se cogerá el número par de D inferior o igual al de secciones de este tipo disponibles.

elif used_c == 4:
    used_s = math.trunc(s / 2) * 2  # 1
    if s >= 2:
        used_d = d  # 2
    else:
        used_d = math.trunc(d / 2) * 2

Explorando un poco, se pueden obtener el resto de casos mínimos (12 en total) y deducir que cualquier conjunto de secciones dado contendrá alguno de estos si realmente forman un circuito. El resto de casos siguen una estructura similar a los dos anteriores y se puede ver el código completo aquí.

Challenge 2 – Bowling

Planteamiento

Este fue uno de los problemas que resolví incorrectamente. O mejor dicho, no conseguía que pasara los casos de prueba de la fase de testing.  Pudo deberse en parte a que no tenía ni idea de cómo era el sistema de puntuación de los bolos y que lo hiciera más complicado de lo que en realidad era. Es por esto último que pude pasar de una versión incompleta en concurso con más de 60 líneas de código a una completa, fuera de concurso, en menos de 30 (empezando de cero).

El sistema de puntuación en detalle, la nomenclatura y demás se puede consultar aquí.

El Challenge 4 pedía devolver la puntuación acumulada de cada marco dado una lista de las tiradas (rolls) de un jugador y los bolos derribados y teniendo en cuenta los distintos tipos de tirada (strike, spare o normal). El fichero de entrada tenía la siguiente estructura:

4
20
5 4 1 3 0 7 4 5 3 0 2 5 2 4 5 0 7 1 4 4
19
9 0 4 0 8 0 4 5 7 0 10 4 1 7 1 6 3 5 4
17
10 7 2 9 1 10 10 7 1 8 0 7 0 10 10 4 2
12
10 10 10 10 10 10 10 10 10 10 10 10
  • 1ª fila: número de casos (partidas). 4 en este ejemplo
  • Para cada caso:
    • 1ª fila: número de tiradas (20 en el primer caso)
    • 2ª fila: lista de números que representan los bolos derribados en cada tirada (5, 4, 1, 3… en el primer caso)

Para cada caso se debía producir la siguiente salida:

Case #1: 9 13 20 29 32 39 45 50 58 66
Case #2: 9 13 21 30 37 52 57 65 74 83
Case #3: 19 28 48 75 93 101 109 116 140 156
Case #4: 30 60 90 120 150 180 210 240 270 300

Donde cada número representa la puntuación acumulada en cada marco hasta el final del juego.

Bowling_Scores_Jesus
Ejemplo de juego perfecto como el Case #4 del ejemplo | En Stay on Target

Solución

Existen tres tipos de puntuación que tienen distintas consecuencias o bonus:

  • Strike
    • Se derriban todos los bolos (10) en la primera tirada (rollde un marco (frame)
    • Al marco del strike (10) se le suman las puntuaciones de los dos siguientes roll
  • Spare
    • Se derriban todos los bolos (10) en los dos rolls de un frame. 6 y 4, por ejemplo.
    • Al marco del spare (10) se le suman las puntuaciones del siguiente roll
  • Regular
    • Se derriba un número inferior a 10 de bolos en los dos rolls de un frame.
    • No se suma ningún bonus

Con estas reglas tenemos el núcleo del algoritmo siguiente:

for i in range(10):
    if rolls[frame] == 10:  # STRIKE
        score += 10 + rolls[frame + 1] + rolls[frame + 2]
        frame += 1
    elif rolls[frame] + rolls[frame + 1] == 10:  # SPARE
        score += 10 + rolls[frame + 2]
        frame += 2
    else:  # REGULAR
        score += rolls[frame] + rolls[frame + 1]
        frame += 2

    scores.append(score)

Donde scores es la lista con las puntuaciones acumuladas score que luego se escribirán en el fichero siguiendo la estructura correspondiente.

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 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 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 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:

3
1
6
3
  • 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 = 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:

3
3
8 8 8
2
5 3
4
3 4 5 6
  • 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 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:

  1. Leer y parsear un fichero de texto plano con una determinada estructura semántica (lo que significa cada línea).
  2. Resolver el challenge.
  3. 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:

 


*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.