Tuenti Challenge 10: niveles 11-14

Construir el mayor castillo de rollos de papel higiénico o introducirse en una red distribuida para alterar su funcionamiento: estos son algunos de los niveles de este cuarto post de la serie Tuenti Challenge 10.

Los primeros tres primeros niveles son bastante matemáticos. El último, echando un ojo al ranking, es uno de los más complejos de esta edición. En Github he subido todas mis soluciones a estos problemas.

Nivel 11: All the Possibilities

Este es uno de esos posts que esconden cierta complejidad bajo la simpleza de su enunciado: dado un número X entre 1 y 100 y algunos números Ni menores a este, calcular de cuántas formas se puede representar X como suma de enteros que no contengan ningún Ni. En matemáticas, una suma de enteros que da lugar a un número se denomina una partición.

def solve(X, N):
    res = [1] + [0] * X
    for i in range(1, X):  # in how many ways you can use an i...
        if i not in N:
            for j in range(i, X + 1):  # ...to obtain j
                res[j] += res[j - i]
    return res[X]

La solución también parece sencilla aunque esconde cierta complejidad. La mejor forma de entenderlo con un ejemplo: vamos a calcular cuántas formas hay de sumar 5 sin usar el número 3.

Primero, construiremos una array res en la que iremos guardando en cada posición j de cuántas formas se puede sumar dicho número. Como sólo hay una forma de sumar cero, res = [1, 0, 0, 0, 0, 0].

A continuación, iremos viendo cuántas formas hay de sumar el número en posición j usando sólo el número 1 y actualizaremos res sumándole estos valores.

Después, repetiremos la operación para el número dos. Como no podemos usar el 2 para sumar un número menor a sí mismo, empezaremos intentando sumar dos.

Como en este problema no podemos usar el número 3, nos lo saltamos y repetimos esta operación usando el número 4 para sumar 4 o 5.

Al terminar esta operación, tenemos almacenado en el último valor de la array la solución al problema.

Nivel 12: Hackerman Origins

En este problema tenemos dos mensajes en texto plano y sus versiones cifradas usando RSA. Como hemos perdido la clave pública que hemos usado para cifrarlos, debemos encontrarla a partir de ambos pares de mensajes.

Este cifrado tan seguro es la base de nuestra comunicación. La usan bancos, VPNs, navegadores y hasta comunicaciones entre gobiernos. Si pudiéramos romperlo, ¿por qué conformarse con solucionar este problema? Por suerte, no tenemos que llegar tan lejos y basta con recuperar la clave pública, cuyo propósito no es ser especialmente segura.

Una clave pública RSA es un par (e, m). Dado un mensaje sin cifrar P, su cifrado consiste en convertirlo en un entero, elevarlo al exponente e, y aplicarle el módulo m dado. El número resultante es el texto cifrado C. En otras palabras, P e = C (mod m), o lo que es lo mismo P e - C = k m, donde k es algún número entero.

Por tanto, si tenemos dos pares de textos (P1, C1) y (P2, C2) y conocemos el exponente e, podríamos hallar su módulo mediante el máximo común divisor: m = gcd(P1e - C1, P2e - C2). Para encontrar el exponente usar el más habitual: 65537.

Nivel 13: The Great Toilet Paper Fortress

Debido al reciente afán por el acopio de papel higiénico, un supermercado ha decidido construir el mayor castillo de rollos de papel para tranquilizar a los compradores, siguiendo ciertas propiedades.

Ejemplos de torre de papel higiénico

El castillo debe tener una torre central lo más alta posible, rodeada por una muralla con dos rollos menos de altura, rodeada por otra de un rollo más de altura y así sucesivamente. Este proceso termina cuando la siguiente muralla a construir tuviera que tener altura cero. Además, la torre central debe ser cuadrada o rectangular con sólo un rollo de diferencia entre ambas dimensiones.

Si asumimos que la torre central siempre tiene un único rollo en cada planta, podemos usar las propiedades de los sumatorios para calcular el número de rollos necesarios para hacer una torre de h rollos de altura.

def simple_rolls(h):
    return (16 * h**3 - 36 * h**2 - h + 24) // 3

Ahora tenemos que ver cómo añadir rollos a la planta de la torre central. Como sólo puede haber un rollo de diferencia entre ambas dimensiones, la torre central debe ser siempre de 1x1, 1x2, 2x2, 2x3, 3x3, etc. Lo que significa que la suma del ancho y el largo siempre es distinta: 2, 3, 4, 5, 6, etc.

Si de nuevo nos peleamos un poco con las propiedades de los sumatorios mirando muchos ejemplos de castillos (el Excel fue de gran ayuda), podemos escribir una función que calcule cuántos rollos extra, aparte de los calculados por simple_rolls, necesitamos para hacer una torre cuya suma de dimensiones es s.

def extra_rolls(h, s):
    if s == 0: return 0
    return (2 * s) * (h**2 - h) - h + h * (s // 2 - 1 + s % 2) * (s // 2 - 1)

Teniendo estas dos ecuaciones, el problema se vuelve muy sencillo: devolvemos IMPOSSIBLE si nos dan menos de simple_rolls(3) rollos, y en otro caso encontramos el mayor h posible con los rollos que nos dan y vamos aumentando s para encontrar el mayor la mayor torre central.

Nivel 14: Public Safety Bureau

Este fue uno de los problemas más interesantes y complejos del concurso: muchos se lo saltaron, y otros tantos abandonaron en este problema. Es un CTF en el que sólo tenemos una IP y un puerto mediante los que conectarnos a un protocolo de consenso de red conocido como Paxos inspirado en el sistema Sibyl del anime Psycho-Pass.

Sybil System logo

El objetivo de este protocolo es establecer un acuerdo sobre cierto valor v, como podría ocurrir al actualizar el valor de un atributo en una base de datos distribuida. Tenemos una serie de servidores que tienen roles definidos. Los servidores se agrupan en conjuntos llamados quorums de forma solapada. Por ejemplo, un quorum puede estar formado por los servidores 1, 2 y 4; otro por los servidores 2, 3 y 5.

El protocolo va realizando pequeñas tareas una por una, que se realizan en paralelo por todos los servidores del quorum y se ponen en común para garantizar la consistencia. Veamos este proceso paxo a paxo (mis disculpas):

  1. La petición para actualizar un valor v surge de un servidor con el rol proposer, que contacta con todos los servidores de uno de sus quorums mediante un mensaje llamado PREPARE que va acompañado de un identificador numérico n que se va incrementando.
  2. Si los servidores que reciben el mensaje, cuyo rol es acceptor, no han recibido ningún n superior significa que el servidor está al día. En este caso, responden con un mensaje llamado PROMISE, acompañado del último valor v-1 que han visto, y actualizan su valor n.
  3. Cuando el proposer ha recibido una mayoría de promises, escoge el nuevo valor de acuerdo con los v-1 que ha recibido, y se lo envía a todos los servidores mediante un mensaje ACCEPT, que debe entenderse como "acepta este nuevo valor, por favor".
  4. Si este es el mensaje más nuevo que han encontrado, los acceptors enviarán un mensaje ACCEPTED al proposer, y el valor será actualizado en todos ellos.

Tras entender el protocolo, es necesario hacer muchas, muchas pruebas hasta entender cómo funciona su sintaxis en el servidor del problema. Además, este problema tiene una pequeña vuelta de tuerca en uso de este protocolo: el valor sobre el que ponerse de acuerdo no es ningún atributo en una base de datos, es una cadena que contiene la lista de servidores que se están usando y un valor secret_owner: 1 que apunta a un servidor que contiene un secreto.

ROUND 897: 5 -> ACCEPTED {servers: [1,2,3,4,6,7,8,9], secret_owner: 1}

La modificación del secret_owner debe ser aceptada por mayoría. Cada ciclo completo de Paxos nos permite añadir o eliminar un único servidor de la lista de servidores del quorum. Podemos ir eliminando servidores uno por uno para hacernos con el control de la red, pero al llegar a 3 servidores nos encontraremos un problema.

Cluster needs to have at least 3 members alive

No podemos garantizar la mayoría siendo un único servidor. Pero si nos conectamos con 2 o más servidores al mismo tiempo, podemos alcanzar esta mayoría. Así, podemos definir la siguiente estrategia:

Y con esto recibiremos el mensaje secreto, que es una cita de Psycho-Pass. Tras indagar un poco sobre este anime para este problema, he terminado por engancharme. Son capítulos de 20 minutos y está en Netflix, así que si os gustan los futuros distópicos os recomiendo echarle un ojo.

Y esto es todo en esta entrega, nos vemos en la siguiente!

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