AOC Día 9 - Encoding Error
Resolviendo el desafío Advent of Code (AOC) en JavaScript
Publicado: 14/12/2020 · Tiempo de lectura: 4 minutos
Advent of Code (o Advenimiento de Código) es un calendario de advenimiento de pequeños desafíos de programación que pueden ser resueltos en cualquier lenguaje de programación. Cada día y hasta el 25 de diciembre se publican 2 desafíos por https://adventofcode.com/.
Este año he decidido participar y publicar las soluciones a cada desafío con explicaciones a fondo en mi blog.
Puedes ver todos los desafíos resueltos hasta el momento:
- AOC Día 1 - Report Repair
- AOC Día 2 - Password Philosophy
- AOC Día 3 - Toboggan Trajectory
- AOC Día 4 - Passport Processing
- AOC Día 5 - Binary Boarding
- AOC Día 6 - Custom Customs
- AOC Día 7 - Handy Haversacks
- AOC Día 8 - Handheld Halting
- AOC Día 9 - Encoding Error (este mismo artículo☝️)
Día 9 - Encoding Error
Puedes encontrar el enunciado completo del problema aquí.
La primera parte de este desafío consta en verificar la validez de una secuencia de números (nuestra data de entrada). Una secuencia es válida sólo si un número en la posición n + 1
de la lista corresponde a la suma de exactamente dos números de los n
números anteriores.
Consideremos la siguiente data:
35201525474062556595102117150182127219299277309576
Por ejemplo, si n
es igual 5
, el sexto número en la colección debe ser la suma de dos números entre los cinco primeros. En este caso es correcto, porque el sexto número (40
) es la suma del tercer y cuarto número (15
y 25
respectivamente).
Nuetra misión es encontrar el primer número en la secuencia que no cumpla con esta regla.
Nuestra solución quedaría así:
const input =`35201525474062556595102117150182127219299277309576`;// Verifica si el número `n + 1` corresponde a la suma entre dos// números del preámbulo, buscando si la diferencia entre el número// objetivo y alguno de los números del preámbulo se encuentra en esteconst isTargetValid = (preamble, target) =>preamble.some((value, _, arr) => arr.includes(target - value));function findCorruptedNumber(preambleSize, input) {const preamble = input.slice(0, preambleSize);const target = input[preambleSize];// Si el número objetivo es válido, llamamos a la función// nuevamente, esta vez con todos los elementos de la data// de entrada salvo el primero. Así en la siguiente iteración// se chequeará el número siguiente y así sucesivamente hasta// dar con un dígito que no sea válidoreturn isTargetValid(preamble, target)? findCorruptedNumber(preambleSize, input.slice(1)): target;}findCorruptedNumber(5, input.split('\n').map(Number)); // 127
¡Boom! Con eso hemos resuelto la primera parte del problema.
Segunda parte
La segunda parte del desafío consta en encontrar una secuencia de al menos dos números continuos que sumen como total nuestro número corrupto. Debemos retornar la suma entre el número mayor y el número menor de la secuencia.
La forma de resolver este problema es bastante interesante. Comenzaremos sumando los primeros dos número de nuestra secuencia y mientras dicha suma no sea igual al número corrupto, seguiremos sumando números, el tecero, luego el cuarto y así sucesivamente, hasta alcanzar dicho valor.
Si la suma total llegara a superar el valor buscado, lo que haremos será ir restando números del principio de la secuencia. Si nuevamente el valor de la suma de la secuencia pasa a ser menor que el valor buscado, seguiremos sumando números a la derecha, hasta que eventualmente lleguemos al número exacto.
Para esto utilizaremos la siguiente función:
const Ordering = {Eq: 'Eq',Gt: 'Gt',Lt: 'Lt'}const compare = (a, b) => {if (a === b) return Ordering.Eq;if (a < b) return Ordering.Lt;return Ordering.Gt;}function findSequence(target, input) {let bottom = 0; // cota a la izquieralet upper = 1; // cota a la derechalet sum = input[bottom] + input[upper];while (sum !== target) {// Comparamos si el valor de la suma es menor, igual o mayor al objetivoconst ordering = compare(sum, target);// De ser menor, subimos la cota derecha y añadimos dicho número al totalif (ordering === Ordering.Lt) {upper++;sum += input[upper];continue;}// De ser mayor, restamos dicho número del total y subimos la cota izquierdaif (ordering === Ordering.Gt) {sum -= input[bottom]bottom++;continue;}}return input.slice(bottom, upper + 1);}
Nuestra solución final quedaría así:
const input =`35201525474062556595102117150182127219299277309576`;const isTargetValid = (preamble, target) =>preamble.some((value, _, arr) => arr.includes(target - value));const Ordering = {Eq: 'Eq',Gt: 'Gt',Lt: 'Lt'}const compare = (a, b) => {if (a === b) return Ordering.Eq;if (a < b) return Ordering.Lt;return Ordering.Gt;}function findCorruptedNumber(preambleSize, input) {const preamble = input.slice(0, preambleSize);const target = input[preambleSize];return isTargetValid(preamble, target)? findCorruptedNumber(preambleSize, input.slice(1)): target;}function findSequence(target, input) {let bottom = 0; // cota a la izquieralet upper = 1; // cota a la derechalet sum = input[bottom] + input[upper];while (sum !== target) {// Comparamos si el valor de la suma es menor, igual o mayor al objetivoconst ordering = compare(sum, target);// De ser menor, subimos la cota derecha y añadimos dicho número al totalif (ordering === Ordering.Lt) {upper++;sum += input[upper];continue;}// De ser mayor, restamos dicho número del total y subimos la cota izquierdaif (ordering === Ordering.Gt) {sum -= input[bottom]bottom++;continue;}}return input.slice(bottom, upper + 1);}function getEncryptionWeakness(preambleSize, input) {const corruptedNumber = findCorruptedNumber(preambleSize, input);const sequence = findSequence(corruptedNumber, input);const min = Math.min(...sequence);const max = Math.max(...sequence);return min + max;}getEncryptionWeakness(5, input.split('\n').map(Number)); // 62
Y listo, con esto hemos resuelto el desafío del noveno día de #AdventOfCode.
Si te ha gustado el contenido, no te olvides de darle una compartida en Twitter y seguirme por ahí.
Gracias totales y hasta la próxima.