Tuenti Challenge 10: niveles 2-6

En este post, que es la continuación de la introducción al Tuenti Challenge, hablaré de los primeros niveles de esta décima edición. Es más divertido pasarse los niveles que leer sus soluciones, así que he dejado un enlace a cada uno de ellos en el título de su sección.

Nivel 2: The Lucky One

Este nivel en formato ICPC nos da como entrada una lista de partidas de ping-pong y tenemos que averiguar cuál es el mejor jugador. Como el problema asegura que la solución es única y que no es posible el empate, podemos deducir que hay un jugador que nunca ha perdido una partida.

def solve(matches):
    players = set()
    losers = set()
    for p0, p1, p1_loser in matches:
        players.update((p0, p1))
        losers.add(p1 if p1_loser else p0)
    return max(players.difference(losers))

Así, podemos ir recorriendo la lista de partidas creando un conjunto de jugadores que hemos visto y otro de jugadores que han perdido alguna vez. Tras iterar sobre todas las partidas, el mejor jugador es el único del conjunto de jugadores que no aparece en el de perdedores.

Nivel 3: Fortunata and Jacinta

Este nivel es un homenaje al novelista Pérez Galdós en el centenario de su muerte. Dada una versión en txt de su novela magna, tenemos que convertir a minúsculas todo el documento, identificar las palabras como un conjunto de tres o más letras del alfabeto español y ordenarlas por frecuencia siguiendo el orden unicode en caso de empate.

from collections import Counter  # frequency counter
from regex import compile  # unicode-aware regex library

REMOVE_INVALID = compile(r'[^abcdefghijklmnñopqrstuvwxyzáéíóúü]+').sub
SPACE_SPLIT = compile(r'\s+').split

_ctx_by_word = {}
_ctx_by_rank = {}
def load_context():
    global _ctx_by_word, _ctx_by_rank
    text = SPACE_SPLIT(REMOVE_INVALID(' ', text).strip())
    text = [word for word in sorted(text) if len(word) >= 3]
    text = Counter(text).most_common()
    for rank, (word, frequency) in enumerate(text, 1):
        _ctx_by_word[word] = '%d #%d' % (frequency, rank)
        _ctx_by_rank[rank] = '%s %d' % (word, frequency)

Para crear este ranking he usado una expresión regular para reemplazar por espacios todos los caracteres no deseados y otra para separar las palabras. Después, la librería built-in collections nos permite crear un ranking por frecuencia sin esfuerzo, y con él construir los dos rankings que necesitamos para este problema:

def solve(line):
    if line.isnumeric():
        return _ctx_by_rank[int(line)]
    else:
        return _ctx_by_word[line]

Habiendo construido estos rankings al empezar, la resolución del problema es así de simple. Sólo tenemos que ver si la entrada es un número para devolver una salida u otra.

Nivel 4: My Favorite Video Game

Aquí empiezan los problemas que se salen de lo habitual. Este nivel de tipo CTF nos habla de una compañía de videojuegos llamada Steam-Origin (como si Valve y EA no fueran suficientemente grandes por sí solas), que tiene una API para obtener claves de sus juegos.

$ curl steam-origin.contest.tuenti.net:9876/games/free_shoot/get_key
{"game":"Free Shoot","key":"9999-9999-9999"}

La compañía es conocida por sus fallos de seguridad, y la semana que viene va a publicar su nuevo juego, Cat Fight, que quieres conseguir a toda costa. Recientemente han publicado una presentación técnica en Prezi que revela información clave para conseguir el juego antes que nadie.

Prezi con información sobre los entornos de producción y pre-producción

Sus entornos de pre- y producción comparten la base de datos y un balanceador de carga externo, pero al de preproducción sólo se puede acceder desde su VPN en la dirección pre.steam-origin.contest.tuenti.net. Este balanceador de carga no está muy fino:

from requests import get

URL = 'http://steam-origin.contest.tuenti.net:9876/games/cat_fight/get_key'
HEADERS = {'Host': 'pre.steam-origin.contest.tuenti.net:9876'}

data = get(URL, headers=HEADERS).json()
with open('key.txt', 'w') as fp:
    fp.write(data['key'])

La cabecera Host ayuda al servidor a identificar a qué dominio se está enviando cierta petición de entre los alojados en un servidor. Esta cabecera es suficiente para confundir al balanceador de carga, hacerle creer que estamos dentro de la VPN y obtener sin restricciones una clave del juego.

Nivel 5: Tuentistic Numbers

Se define un número "tuentístico" como aquel que pronunciado en inglés contiene la palabra twenty. Por ejemplo, 20, 21 o 120000 son números tuentísticos. Dado un número entre 1 y 262, debemos averiguar cuál es la mayor suma de números tuentísticos que lo representa.

Este es el primer problema en el que los límites empiezan a ser relevantes. Con números tan grandes como 262 no nos podemos plantear probar todas las sumas posibles. En su lugar, debemos buscar una simplificación que nos permita hacer este cálculo rápidamente.

Una posibilidad es usar sólo los números tuentísticos más pequeños; aquellos entre 20 y 29. De esta forma, la menor cantidad de números a sumar será siempre n / 29 y la mayor cantidad será n / 20, redondeando hacia abajo.

def solve(n):
    mn = n // 29 + (1 if n % 29 else 0)
    mx = n // 20
    if mn > mx:
        return 'IMPOSSIBLE'
    else:
        return mx

Y esto es todo lo que debemos hacer, considerando un par de excepciones: si el número no es divisible entre 29, tendremos que añadir un término más a la suma, y si la menor cantidad de números a sumar es mayor que la mayor cantidad, este problema es imposible.

Nivel 6: Knight Labyrinth

De nuevo un nivel de tipo CTF, que me resultó especialmente divertido. Dada una IP para acceder a un laberinto en formato texto que sólo nos muestra las casillas de nuestro alrededor, debemos movernos por ellas mediante el salto del caballo de ajedrez para rescatar a una princesa.

Posiciones del tablero de ajedrez

En esta ocasión he intentado llegar a la solución más rápida posible haciendo algunas optimizaciones:

Representación del laberinto completo

Es una solución bastante larga y la puedes encontrar en mi repositorio de Github del concurso junto al resto de soluciones. En el próximo post hablaré de los niveles intermedios del concurso.

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