AOC Día 8 - Handheld Halting
Resolviendo el desafío Advent of Code (AOC) en JavaScript
Publicado: 13/12/2020 · Tiempo de lectura: 5 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 (este mismo artículo☝️)
- AOC Día 9 - Encoding Error
Día 8 - Handheld Halting
Puedes encontrar el enunciado completo del problema aquí.
Para este desafío tenemos un listado de instrucciones como data de entrada. Las instrucciones describen la ejecución de un programa y están compuestas de dos partes: la primera parte indica un tipo de comando y la segunda data asociada a ese comando. La ejecución del programa parte en la primera línea y termina cuando llegamos a la última instrucción del listado.
Desafortunadamente una de las instrucciones del programa está mala, por lo que caemos en un loop infinito.
Consideremos el siguiente programa de ejemplo:
nop +0acc +1jmp +4acc +3jmp -3acc -99acc +1jmp -4acc +6
Existen 3 tipos de instrucciones:
nop
hace absolutamente nada, solo mueve la ejecución del programa a la siguiente línea.acc
le añade la data asociada a un acumulador (que parte en 0) y mueve la ejecución del programa a la siguiente instrucción.- Finalmente
jmp
no modifica el acumulador, pero mueve la ejecución del programa según lo indicado en la data asociada.
Para nuestra data de entrada, la ejecución del programa sería algo así:
Initpointer : 0accumulator : 0-> nop +0pointer : 1accumulator : 0-> acc +1pointer : 2accumulator : 1-> jmp +4pointer : 6accumulator : 1-> acc +1pointer : 7accumulator : 2-> jmp -4pointer : 3accumulator : 2-> acc +3pointer : 4accumulator : 5 <-- Resultado-> jmp -3pointer : 1 ### Duplicadoaccumulator : 5
En la primera parte del desafío debemos encontrar el valor del contador inmediatamente antes de que se ejecute una instrucción duplicada. Para la data de prueba el valor es 5
.
En orden de hacer esto de forma programática, vamos a utilizar –redoble de tambores, prrrrr 🥁🥁🥁– generadores.
Si quieres aprender sobre generadores puedes hacerlo aquí.
Esta es definitivamente la primera vez en la vida que encuentro un uso práctico para utilizar generadores 🎉
Crearemos un generador que se encargará de recorrer el listado de instrucciones.
const input =`nop +0acc +1jmp +4acc +3jmp -3acc -99acc +1jmp -4acc +6`;// Para declarar un generador debemos usar un asteriscofunction *traverser(instructions) {let accumulator = 0;let pointer = 0;while (instructions.length !== pointer) {const [ command, input ] = instructions[pointer].split(' ');accumulator = command === 'acc'? accumulator + Number(input): accumulator;pointer = command === 'jmp'? pointer + Number(input): pointer + 1;yield { accumulator, pointer };}}// Cuando llamamos a un generador obtenemos de vuelta un iteradorconst traverse = traverser(input.split('\n'));traverse.next(); // { done: false, value: { pointer: 1, accumulator: 0 } }traverse.next(); // { done: false, value: { pointer: 2, accumulator: 1 } }traverse.next(); // { done: false, value: { pointer: 6, accumulator: 1 } }
Podemos utilizar nuestro generador para ejecutar las instrucciones del programa y llevar un registro sobre qué instrucciones ya se han ejecutado (utilizando pointer
). Cuando nos encontremos con una instrucción duplicada, retornaremos el valor del acumulador anterior.
Nuestra solución se vería así:
const input =`nop +0acc +1jmp +4acc +3jmp -3acc -99acc +1jmp -4acc +6`;function *traverser(instructions) {let accumulator = 0;let pointer = 0;while (instructions.length !== pointer) {const [ command, input ] = instructions[pointer].split(' ');accumulator = command === 'acc'? accumulator + Number(input): accumulator;pointer = command === 'jmp'? pointer + Number(input): pointer + 1;yield { accumulator, pointer };}}function getAccumulator(input) {const visited = new Set();let accumulator = null;// Como los generadores retornan iterables, podemos utilzar `for of`// para producir los valores sin llamar a .next() manualmentefor (let value of traverser(input)) {if (visited.has(value.pointer)) {break;}accumulator = value.accumulator;visited.add(value.pointer);}return accumulator;}getAccumulator(input.split('\n')); // 5
¡Perfecto! Para la data de entrada provista hemos llegado al resultado esperado.
Segunda parte
Uno de los comandos en una de las instrucciones de nuestra data está corrupta. Si la reemplazamos por el commando correcto, nuestro programa puede finalizar exitosamente. Solo los comandos nop
y jmp
pueden estar corruptos. En otras palabras, en la data hay un nop
que debería ser un jmp
o un jmp
que debería ser un nop
.
Nuestra misión es encontrar dicho comando, reemplazarlo, correr el programa exitosamente y obetener el valor del acumulador final.
Para esto podemos utilizar algo de fuerza bruta y probar reemplazando, una por una, las instrucciones que pueden estar corruptas. Cuando una secuencia caiga en un loop infinito, simplemente probaremos reemplazando la instrucción siguiente.
Nuestra solución se vería así:
const input =`nop +0acc +1jmp +4acc +3jmp -3acc -99acc +1jmp -4acc +6`;function *traverser(instructions) {let accumulator = 0;let pointer = 0;while (instructions.length !== pointer) {const [ command, input ] = instructions[pointer].split(' ');accumulator = command === 'acc'? accumulator + Number(input): accumulator;pointer = command === 'jmp'? pointer + Number(input): pointer + 1;yield { accumulator, pointer };}}function getAccumulator(input) {const visited = new Set();let accumulator = null;for (let value of traverser(input)) {if (visited.has(value.pointer)) {// En vez de terminar el loop, retornamos nullreturn null;}accumulator = value.accumulator;visited.add(value.pointer);}return accumulator;}// Cambia una instrucción de `jmp` a `nop` y visceversafunction swap(instruction) {const [ command, input ] = instruction.split(' ');if (command === 'acc') return instruction;return `${command === 'nop' ? 'jmp' : 'nop'} ${input}`;}// Obtenemos los índices de las instrucciones que podrían estar corruptasconst findCorruptable = sequence =>sequence.reduce((acc, entry, index) =>(/(jmp|nop)/).test(entry) ? acc.concat(index) : acc,[]);function getUncorruptedAccumulator(sequence) {const corruptable = findCorruptable(sequence);let result = null;while (result === null) {// Obtiene el primer indice en la lista de instrucciones// (mutando la secuencia)let index = corruptable.shift();if (typeof index !== 'undefined') {// Reemplazamos una de las instrucciones por su opuestaconst swapedSeq = [...sequence.slice(0, index),swap(input[index]),...sequence.slice(index + 1)];// `getAccumulator` retorna `null` cuando nos encontramos con// una secuencia corrupta, en ese caso volvemos a iterar.result = getAccumulator(swapedSeq);}}return result;}getUncorruptedAccumulator(input.split('\n')); // 8
Y listo, con esto hemos resuelto el desafío del octavo 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.