Tuenti Challenge 10: introducción

Del 27 al 4 de mayo se ha celebrado la décima edición del reto para programadores que organiza Tuenti todos los años. Suelo participar siempre porque se sale de los esquemas habituales de los concursos de programación y eso lo hace muy divertido.

Logo del Tuenti Challenge 10

En este post voy a describir cómo he resuelto el primer problema y cuál es mi estrategia para resolverlos rápidamente. Podéis encontrar todas mis soluciones en Github. Para echar un vistazo al resto de problemas, puedes consultar los siguientes posts de esta serie:

Estos concursos suelen seguir la estructura que inventó ICPC, que consiste en resolviendo problemas algorítmicos a partir de una descripción y un archivo de entrada. Este archivo contiene muchos casos de prueba que hay que interpretar para generar otro archivo de salida. Otros concursos de este tipo son Google Code Jam o Facebook Hacker Cup.

Otros siguen la estructura CTF, que consiste en encontrar una clave escondida tras un archivo o la IP de un servidor. Al no tener enunciado, es necesario aplicar el pensamiento lateral y tener ciertos conocimientos sobre un tema. Hay muchos CTF sobre seguridad informática al año.

Tuenti Challenge destaca por la variedad de problemas de ambos tipos. En esta edición ha habido niveles tales como una escape room via SSH a un servidor que sólo funciona con emojis, calcular el CRC32 de archivos de 200GB ultra-comprimidos o construir el mayor castillo de papel higiénico posible con los rollos de un supermercado.

Nivel 1: Rock, Paper, Scissors

El primer problema suele ser algo simple para ir calentando, así que voy a aprovechar para explicar cómo proceso la entrada y genero la salida. Suelo resolver todos los problemas usando Python por su cercanía al pseudocódigo que hace tan fácil probar nuevas ideas rápidamente.

Diagrama de piedra, papel o tijera

El problema consiste en averiguar qué figura ganaría en un juego de piedra, papel o tijera. Al ser un problema en formato ICPC, la entrada es un archivo de texto cuya primera línea es el número de casos N (partidas de piedra, papel o tijera) y cada una de las N siguientes líneas se corresponde a un caso.

4
R S
R P
P P
S P

Con una entrada como la anterior, debemos generar un archivo de salida en el que cada línea sea el resultado de uno de los casos siguiendo el formato Case #n: result. Para nuestro ejemplo, la salida esperada es la figura ganadora, o - en caso de empate.

Case #1: R
Case #2: P
Case #3: -
Case #4: S

Primero debemos procesar un archivo de prueba llamado testInput.txt que contiene unos pocos casos pequeños. Cuando lo resolvemos, obtenemos el archivo submitInput.txt en el mismo formato y con muchos más —y casi siempre más complejos— casos de prueba. La idea es usar el test para comprobar que nuestro algoritmo funciona bien, y el submit para que puedan evaluar nuestra solución.

FNAME = 'test'

def load_input():
    with open('%sInput.txt' % FNAME, 'r', encoding='utf-8') as fp:
        problems = int(fp.readline())
        for p in range(problems):
            yield sorted(fp.readline().strip().split(' '))

Esta es la forma en la que suelo cargar el archivo de entrada en estos problemas. Ir iterando línea a línea y usar un generador mediante la sentencia yield hace que estos problemas se procesen de una forma muy natural. En ninguno de ellos he tenido que dedicar demasiado tiempo a adaptar la entrada y eso me permite centrarme en el problema. El único tuning que ha sufrido en este caso es la función sorted, que me asegura que las figuras de la partida lleguen en orden alfabético.

def main():
    output = ''
    for p, problem in enumerate(load_input(), 1):
        print('Solving case #%d' % p)
        output += 'Case #%d: %s\n' % (p, solve(*problem))
    with open('%sOutput.txt' % FNAME, 'w', encoding='utf-8') as fp:
        fp.write(output)

La función main es el punto de entrada de este script, y va leyendo los problemas uno a uno para obtener su solución llamando a la función solve. Al usar el operador * como argumento de solve, esta función recibe como entrada los mismos parámetros que devuelve el generador.

def solve(p1, p2):
    if p1 == 'R' and p2 == 'S':
        return 'R'  # rock beats scissors
    elif p1 == 'P' and p2 == 'R':
        return 'P'  # paper beats rock
    elif p1 == 'P' and p2 == 'S':
        return 'S'  # scissors beats paper
    else:
        return '-'  # it's a draw

Sabiendo que las figuras de ambos jugadores llegan ordenadas, la solución se obtiene de forma muy sencilla. Y con esto podemos resolver el problema de test, descargar el archivo submit y cambiar FNAME para procesarlo de la misma forma.

Y eso es todo en este post introductorio. En los siguientes posts contaré los problemas posteriores sin prestar mucha atención al formato de entrada y salida. Si os ha gustado y no lo conocíais os animo a entrar en la web del concurso y probar a resolver algunos. Los problemas de todas las ediciones siguen estando disponibles.

Sé el primero en comentar

Recibir un mail

🍪 ¿Cookies?

Esta web usa cookies para identificar qué contenido es interesante y escribir más contenido similar. Puedes obtener más información aquí.