¡Qué malo es el aburrimiento y más si eres el protagonista de Advent of Code! Con el niño de al lado entretenido con su consola que ya funciona y sin nada que hacer más que mirar el reposacabezas de delante, reparas en un pequeño puerto de datos. A pesar de no ser estándar, con un poco de paciencia y unos clips apañas una conexión a tu ordenador para descubrir que se trata de un puerto serie que escupe inmediatamente datos bajo encriptación eXchange-Masking Addition System (XMAS)
Esta encriptación codifica los datos como enteros sin signo, y utiliza una cabecera o preámbulo de 25 posiciones tras las que cada numero posterior tiene que ser la suma de dos números contenidos entre los 25 anteriores. Es un sistema anticuado que no debería poder ser hackeado fácilmente para poder echar un vistazo a más sistemas del avión. Vamos a ver qué podemos hacer….
Parte 1 – Encontrando la vulnerabilidad
La primera parte del puzzle de hoy consiste en encontrar en la secuencia de números uno que no cumpla con las condición anterior, esto es, que no sea la suma de dos números comprendidos entre los 25 anteriores a él.
Es decir, dado un numero con índice n debemos comprobar si entre las posiciones n-25 y n-1 existen dos cuya suma sea dicho número:
export class XMAS {
private data: number[];
constructor(serialDataFile: string, private preambleLength = 25) {
this.data = fs
.readFileSync(serialDataFile, "utf8")
.split("\r\n")
.map((n) => parseInt(n));
}
/**
* Busca el numero erroneo en la secuencia XMAS
*/
public findChecksumError = (): number => {
for (let index = this.preambleLength; index < this.data.length; index++) {
const ops = this.findSumNumbers(
this.data.slice(index - this.preambleLength, index),
this.data[index]
);
if (ops[0] + ops[1] != this.data[index]) return this.data[index];
}
return -1;
};
/**
* Devuelve los dos numeros del intervalo indicado que sumados den el numero buscado
* @param interval Intervalo de numeros en los que buscar
* @param sum Suma a encontrar
*/
private findSumNumbers = (interval: number[], sum: number): number[] => {
// Ordenamos los numeros
interval = interval.sort((a, b) => a - b); //ojo
let start = 0,
end = interval.length - 1;
// Ajustar los indices teniendo en cuenta la ordenacion
while (interval[start] + interval[end] !== sum && start < end)
if (interval[start] + interval[end] > sum) end--;
else start++;
return [interval[start], interval[end]];
};
}
Para hallar el que no cumple voy a recorrer el array de números a partir de la posición 25 (las primeras 25 son la cabecera o preámbulo) verificando que las anteriores posiciones contienen dos números que den la suma buscada. Curiosamente buscar dos números en un array que den una suma determinada fue la parte 1 del problema del día 1, por lo que voy a reutilizar la función que escribí para resolver aquel problema.
La función findChecksumError comienza a avanzar desde la posición 26, pasando a la función findSumNumbers el trozo de array con las 25 anteriores posiciones a la actual y el número a encontrar. En el momento en esta función devuelva dos números que no sumen la cifra buscada (cosa que ocurre cuando no existen esos dos números en las 25 posiciones anteriores) habremos encontrado nuestra respuesta.
Como mejora se podría evitar pasar la porción de array (que supone una nueva copia de esa porción) en cada invocación a findSumNumbers , sustituyendo this.data.slice por una operacion push y una shift en un array intermedio.
Solo queda invocar a nuestra función:
const xmasProtocol = new XMAS("./serial.txt", 25);
console.log("Answer:", xmasProtocol.findChecksumError());
Parte 2 – Atacando el sistema
Una vez encontrados los datos vulnerables podemos atacar el sistema. Para ello debemos hallar un intervalo consecutivo de números anteriores al vulnerable cuya suma sea igual a este número. Es decir, en vez de hallar dos números entre los 25 anteriores, debemos hallar n números en n posiciones consecutivas entre los existentes en el intervalo de 0 a m-1, siendo m el índice del número buscado.
Como respuesta a la segunda parte debemos dar la suma del máximo y el mínimo de dicho conjunto de números.
Añado una función a nuestra clase XMAS para encontrar ese rango. Manejaré una variable sum para mantener la suma de los números comprendidos en el rango definido por dos punteros al array de datos, start y end. Cada vez que incremente el puntero start restaremos de la suma del conjunto y cada vez que incrementemos el puntero end añadiremos a la suma hasta dar con el resultado buscado:
/**
* Encuentra una intervalo de números en la secuencia de datos que den como suma el parámetro indicado
* @param number Numero a buscar
*/
public findRange = (number: number): number[] => {
// Calcular un intervalo incial
let sum = this.data[0],
start = 0,
end = 0;
const maxIndex = this.data.findIndex((n) => n == number);
while (end < maxIndex && sum <= number) sum += this.data[++end];
//Si no hemos encontrado el rango partiendo de 0, mover los limites inferior y superior
while (sum != number && end < maxIndex) {
//Eliminar números por la parte inferior del rango hasta que la suma sea inferior al número buscado
sum -= this.data[start++];
// Añadir numeros por la parte superior del rango hasta que la suma sea igual o superior al número buscado
while (sum < number && end < maxIndex) {
sum += this.data[++end];
}
}
return this.data.slice(start, end + 1);
};
Como en todos los ejercicios damos por hecho que existe una solución válida al problema, por lo que no incluyo más control de errores. Una vez hayamos salido del último bucle sí o sí debemos tener la respuesta correcta, con los punteros start y end delimitando el rango de números consecutivos cuya suma es igual al número buscado.
Para devolver la respuesta solo queda sumar el máximo y mínimo de dicho rango:
const xmasProtocol = new XMAS("./serial.txt", 25);
const range = xmasProtocol.findRange(xmasProtocol.findChecksumError());
console.log("Answer:", Math.min(...range) + Math.max(...range));
Y así termina el noveno día de este año, que por el momento, está siendo bastante más sencillo que el pasado 2019.