Arreglado el problema con los equipajes del día anterior, por fin conseguimos despegar en dirección a nuestro destino. Ya empezamos a ver las vacaciones en el horizonte y a estar relajados cuando el niño del asiento de al lado nos pide ayuda porque su videojuego no se pone en marcha. Y como no es cuestión de que dé el coñazo todo el camino lo mejor será ayudarle y que se quede entretenido.
Al parecer la secuencia de arranque entra en un bucle infinito por alguna razón. Rápidamente desensamblamos el código y nos hacemos con el programa, que solo consta de tres tipos de instrucciones. Y esta vez (lástima) no son IntCode como en el advent of code 2019.
Parte 1 – Localizando el bucle
La primera misión es localizar el punto en el que el programa entra en bucle. La arquitectura es muy sencilla y solo permite las instrucciones nop, acc y jmp, todas ellas seguidas de un parámetro numérico. La primera no hace nada, la segunda incrementa un registro acumulador en la cantidad indicada y la última salta tantas instrucciones desde la actual como se indique en el parámetro.
La respuesta que debemos buscar es el valor del acumulador justo antes de que el programa entre en bucle.
Con un juego de instrucciones tan limitado el problema es sencillo: basta con llevar un registro de las direcciones de las instrucciones ejecutadas y, en el momento en que se trate de ejecutar la instrucción de una de esas direcciones por segunda vez finalizar sin ejecutarla y devolver el acumulador.
Manos a la obra. Implemento nuestro computador en la clase HandheldComputer, que internamente dispondrá del registro acumulador acc y un puntero a la instrucción actual ptr. Las instrucciones las guardaremos en un array que recorreremos con el puntero:
import * as fs from "fs";
export class HandheldComputer {
private ptr = 0;
private acc = 0;
private instructions: string[];
private reInstruction = /(?<op>\w+) (?<p1>[+\-0-9]+)/;
constructor(programFile: string) {
this.instructions = fs.readFileSync(programFile, "utf8").split("\r\n");
}
/**
* Ejecuta la instruccion en la direccion apuntada por ptr
*/
private executeInstruction = () => {
const instruction = this.reInstruction.exec(this.instructions[this.ptr]);
const p1 = parseInt(instruction.groups["p1"]);
switch (instruction.groups["op"]) {
case "acc":
this.acc += p1;
this.ptr++;
break;
case "jmp":
this.ptr += p1;
break;
default:
this.ptr++;
}
};
/**
* Encuentra el valor del acumulador justo antes de que el programa entre en bucle
*/
public findAccBeforeLoop = (): number => {
this.ptr = this.acc = 0;
const executedAddresses: boolean[] = [];
while (!executedAddresses[this.ptr] ) {
executedAddresses[this.ptr] = true;
this.executeInstruction();
}
return this.acc;
};
}
El constructor recibe la ruta al fichero de texto con el programa y lo transforma en un array de lineas.
La función executeInstruction() ejecuta la instrucción apuntada por el puntero ptr, actualizando este y acc como corresponda.
Por último, escribo una función findAccBeforeLoop que lleva registro de las direcciones de las instrucciones que se van ejecutando y que ejecuta el programa hasta que una de ellas trata de ejecutarse más de una vez. En ese momento se devuelve el acumulador.
La solución a la primera parte consiste solo en llamar a esta función:
const computer = new HandheldComputer("./program.txt");
console.log("Answer:", computer.findAccBeforeLoop());
Parte 2 – Arreglando el arranque
Parece ser que el problema es que el programa esta corrupto y una y solo una de las instrucciones nop ha mutado en jmp o viceversa. Debemos encontrar cual es esa instrucción y modificarla para que el programa sea capaz de terminar. La respuesta que debemos dar a esta segunda parte es el valor del acumulador una vez que el programa ha terminado.
Después de darle varias vueltas no se me ocurre ninguna forma de solucionar el problema que no sea mediante prueba-error. Iré probando a modificar una sola instrucción del programa y ejecutarlo para ver si termina, para lo que voy a necesitar un par de funciones auxiliares:
/**
* Devuelve un booleano indicando si el programa ha terminado (End Of Program)
*/
private get EOP() {
return this.ptr >= this.instructions.length;
}
/**
* Cambia nop por jmp y viceversa en la dirección indicada
* @param address Direccion de la instruccion a cambiar
*/
private toggleInstruction = (address: number) => {
this.instructions[address] = this.instructions[address].startsWith("nop")
? this.instructions[address].replace("nop", "jmp")
: this.instructions[address].replace("jmp", "nop");
};
La propiedad EOP nos indica si el programa se ha ejecutado completamente. Esto sucede si el puntero sobrepasa el rango de direcciones de las instrucciones, bien porque se han ejecutado todas, bien porque un jmp lo manda fuera de rango. Como en anteriores ejercicios damos por hecho que el programa de entrada es válido por lo que la única condición contemplada es que el programa termina correctamente y unicamente verificamos que el puntero se haya salido de rango.
La función toggleInstruction simplemente cambia un nop por jmp o viceversa en la dirección del programa que indiquemos.
Puedo reutilizar ademas la función de la primera parte para que ejecute las instrucciones y me devuelva el acumulador. Si después de hacerlo el programa ha terminado (EOP == true) es que habremos dado con la modificación correcta. Pero poder reusarla hay que incluir una pequeña modificación, ya que cuando demos con la solución el programa terminará y esta función no controla esa circunstancia, por lo que trataría de ejecutar instrucciones más allá del final del mismo. Lo resuelvo muy fácilmente incluyendo la condición !this.EOP en el control del bucle de ejecución:
public findAccBeforeLoop = (): number => {
this.ptr = this.acc = 0;
const executedAddresses: boolean[] = [];
while (!executedAddresses[this.ptr] && !this.EOP) {
executedAddresses[this.ptr] = true;
this.executeInstruction();
}
return this.acc;
};
Esta condición no afecta obviamente a la parte 1, ya que en ella el programa nunca termina.
Ya solo queda escribir una función que pruebe a ir modificando instrucciones y ejecutando el programa a ver si finaliza:
/**
* Modifica una instruccion nop o jmp por turno y ejecuta el programa. Si este termina, la funcion finaliza
*/
public findAccAfterFix = (): number => {
//Indices de las instrucciones nop y acc
const corruptedAddresses = this.instructions
.map((instruction, index) => (instruction.startsWith("acc") ? -1 : index))
.filter((address) => address > -1);
let acc = 0;
for (
let instructionIndex = 0;
instructionIndex < corruptedAddresses.length;
instructionIndex++
) {
this.ptr = this.acc = 0; //Inicializar el programa
this.toggleInstruction(corruptedAddresses[instructionIndex]); //Probar con la siguiente instrucción sospechosa
acc = this.findAccBeforeLoop();
if (this.EOP) break; // Si el programa ha finalizado ya hemos localizado la instrucción corrupta
this.toggleInstruction(corruptedAddresses[instructionIndex]); // Dejar el programa como estaba
}
return acc;
};
Obtengo en primer lugar las direcciones de las instrucciones nop y jmp del programa original. Después ejecuto el programa modificando cada vez una de esas instrucciones y llamando a la función de la primera parte. A su vuelta compruebo si se ha ejecutado por completo mediante this.EOP. De ser así hemos dado con la instrucción corrupta.
De nuevo, la solución a la parte 2 consiste únicamente en invocar esta función:
const computer = new HandheldComputer("./program.txt");
console.log("Answer:", computer.findAccAfterFix());