A la hora de atracar el ferry (¿como? ¿pero no estábamos ya en un bus?) resulta que el ordenador de a bordo no es compatible con los sistemas del puerto. raudo a ayudar de nuevo al capitán, nos encontramos con que la autoridad portuaria utiliza un sistema de enmascarado de bits extraño en su rutina de inicialización, que escribe valores en un rango de memoria de 36 bits. Va a ser necesario emularlo para ser capaces de interpretar las instrucciones y poner pie en tierra firme.

Parte 1 – Aplicando máscaras a valores

En la primera parte del problema debemos calcular el sumatorio de los valores de todas las posiciones de la memoria del ordenador después de que hayamos cargado el programa de inicialización.

El programa contiene la lista de valores a guardar en cada posición de memoria y la máscara a aplicar a cada valor. Por ejemplo:

mask = XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
mem[8] = 11
mem[7] = 101
mem[8] = 0

Quiere decir que la máscara a aplicar a los tres siguientes valores es la indicada, donde la X indica que el bit de esa posición se deja como está, mientras que el 0 y el 1 sobreescriben el bit correspondiente del valor. Por tanto, antes de escribir el valor 11 a la posición de memoria 8 (primera instrucción) haya que aplicar la mascara:

valor:     000000000000000000000000000000001011  (decimal 11)
mascara:   XXXXXXXXXXXXXXXXXXXXXXXXXXXXX1XXXX0X
resultado: 000000000000000000000000000001001001  (decimal 73)

Con lo que finalmente guardaremos el valor 73 en la posición 8. En cualquier momento de la lista de instrucciones puede llegar otra instrucción mask = XXX... que cambiará las mascara a aplicar a los valores posteriores.

Voy a empezar por tanto por escribir una función que, dado un valor y una máscara, me devuelva el valor resultante de aplicar dicha mascara a su representación binaria:

/**
 * Aplica la máscara a un valor para obtener el valor final
 * @param unmaskedValue valor (decimal)
 * @param mask mascara a aplicar
 */
const maskValue = (unmaskedValue: number, mask: string): number =>
  new Number(
    "0b" +
      Array.from(unmaskedValue.toString(2).padStart(36, "0"))
        .map((bit, index) => (mask[index] == "X" ? bit : mask[index]))
        .join("")
  ).valueOf();

La función realiza los siguientes pasos:

  1. Convierte el valor decimal pasado en el parámetro unmaskedValue a binario mediante .toString(2)
  2. Completa la cadena hasta los 36 bits de longitud que tienen los números en este sistema, según se indica en las instrucciones, con ceros por la izquierda
  3. Convierte esta cadena de 36 posiciones a un array y a cada letra del mismo le aplica las reglas de enmascaramiento. Si la máscara tiene en esa posición index una X, devuelve el bit del valor original, y si no lo sobreescribe con el bit de la mascara
  4. Une el array resultante de nuevo en una cadena de 36 posiciones
  5. Llama al constructor de la clase Number pasándole el prefijo de numero binario 0b concatenado con el resultado enmascarado, con lo que conseguimos el numero resultante en decimal.

Ahora vamos a necesitar un bucle que lea del fichero cada instrucción y que antes de escribir en memoria haga la transformación del valor en cuestión con la última máscara leída del fichero:

const data = fs.readFileSync("./program.txt", "utf8").split("\r\n");
const mem: number[] = [];
const reInstruction = /(?<op>mask|mem)(\[(?<address>\d+)\])? = (?<value>[X\d]+)/;
let mask = "";

data.forEach((instruction) => {
  const inst = instruction.match(reInstruction);
  if (inst.groups["op"] == "mask") mask = inst.groups["value"];
  else
    mem[parseInt(inst.groups["address"])] = maskValue(
      parseInt(inst.groups["value"]),
      mask
    );
});

Utilizo una expresión regular para parsear cada linea. Si la instrucción es mask, guardo el valor de la máscara en una variable para enmascarar los siguientes valores, mientras que si es mem inserto en el array mem, que representa el espacio de direcciones del ordenador, el valor tras aplicarle la máscara con la función anterior.

Una vez ejecutadas todas las instrucciones del fichero solo queda hacer la suma de los valores de la memoria para tener la solución a esta primera parte:

console.log(
  "Answer:",
  mem.reduce((a, b) => (a += b), 0)
);

Parte 2 – Aplicando máscaras a las direcciones

La segunda parte del problema plantea una interesante variación: la respuesta buscada es la misma, la suma de los valores contenidos en la memoria, pero esta vez las máscaras en vez de aplicarse a los valores deben aplicarse a las direcciones. Y para hacer esta aplicación hay nuevas reglas:

  • Si el bit de la máscara es 0, el bit del valor se mantiene como estuviese
  • Si el bit de la máscara es 1, el bit del valor se sobreescribe con 1
  • Si el bit de la máscara es X, el bit del valor se convierte en un bit flotante. Estos bits son indeterminados y pueden tener ambos valores a la vez, por lo que en la práctica quiere decir que se escribirán todas las direcciones que puedan generarse con la combinación de todos los bits flotantes del la dirección a la que hemos aplicado la máscara. Por ejemplo:
dirección:  000000000000000000000000000000101010  (decimal 42)
máscara:    000000000000000000000000000000X1001X
resultado:  000000000000000000000000000000X1101X
direcciones posibles: 
000000000000000000000000000000011010  (decimal 26)
000000000000000000000000000000011011  (decimal 27)
000000000000000000000000000000111010  (decimal 58)
000000000000000000000000000000111011  (decimal 59)

Tenemos por tanto que ser capaces de :

  1. generar la dirección flotante, aplicando a la dirección original la máscara.
  2. generar a partir de esa dirección flotantes todos las posibles direcciones que pueden generarse con las combinaciones de los bits marcados como X.

El primer punto no tiene ningún misterio, ya que no es necesario más que cambiar la función que ya hemos usado en la primera parte y generar una nueva que enmascare con las nuevas normas:

/**
 * Obtiene la mascara flotante para la direccion indicada aplicando la mascara
 * @param unmaskedValue direccion (decimal)
 * @param mask máscara a aplicar
 */
const maskAddress = (unmaskedValue: number, mask: string): string =>
  Array.from(unmaskedValue.toString(2).padStart(36, "0"))
    .map((bit, index) =>
      mask[index] == "0" ? bit : mask[index] == "1" ? "1" : "X"
    )
    .join("");

Como el funcionamiento de esta función no es más que una parte del de la primera parte no entro en su detalle. Únicamente reseñar que, como la dirección flotante no es un numero (contiene X) la devolvemos como un string.

El segundo punto es donde está la complejidad del día. Debemos generar todos los números posibles combinando los valores binario de las Xs y respetando el resto:

Después de probar sin éxito con un par de ideas, se me ocurre que es posible generar un árbol binario mientras recorremos la mascara flotante de derecha a izquierda la derecha. Por ejemplo para l máscara X0XX:

arbol binario
  1. Para comenzar desde una raíz única comenzamos desde un nodo con valor 0
  2. Leemos la primera posición de la mascara flotante. Si es una X creamos dos hijos al nodo actual, con valores 0 y 1
  3. Si la posición es un 0 o un 1 únicamente añadimos un nodo hijo con ese valor.
  4. Repetimos la operación con la siguiente posición de la máscara flotante en o los nodos que hayamos añadido hasta que no queden más posiciones por recorrer.
  5. Recorremos el árbol en profundidad y para cada nodo final la cifra es la concatenación de los valores de los padres. De izquierda a derecha en la imagen obtendríamos 00000, 00001, 00010, 00011, 01000, etc., que son todas las posibles direcciones a generar con esa máscara.

podemos optimizar este árbol si nos fijamos en que la profundidad de cada nodo corresponde a su posición en la cadena binaria, por lo que podemos sustituir los valores 1 y 0 por sus correspondientes potencias de dos para obtener este otro árbol con valores decimales:

Al hacer el recorrido en profundidad solo tenemos que sumar los valores de todos los nodos hasta un nodo hijo para obtener las combinaciones posibles, que para esta máscara X0XX serían:

0+8+0+0=8
0+8+0+1=9
0+8+2+0=10
0+8+2+1=11
.....
0+0+2+1=3

Para las posiciones de la máscara que sean 0 no es necesario generar nodo en el árbol, ya que este tendría valor 0 y no aporta nada a la suma final, por lo que ahorramos niveles.

Con la teoría en la mano ya puedo escribir una función que a partir de una máscara flotante genere un árbol como el que hemos visto. Para ello voy a hacer uso de una clase auxiliar genérica TreeNode que tengo del Aoc 2019:

export interface ITreeNode<T> {
  data: T;
  parent: ITreeNode<T>;
  children: ITreeNode<T>[];
  /**
   * Devuelve la profundidad del nodo en el árbol. La raiz tiene profundidad=0
   */
  depth: number;
  /**
   * Devuelve un array con los nodos padre de este nodo
   */
  parents: ITreeNode<T>[];
}

La función para generar el árbol recorre recursivamente la cadena de máscara flotante d derecha a izquierda aplicando las reglas comentadas:

/**
 * Genera un arbol binario con los valores decimales correspondientes a las combinaciones posibles de la mascara
 * @param floatingAddress mascara de dirección flotante
 * @param treeNode nodo raíz
 */
const generateTree = (floatingAddress: string, treeNode: ITreeNode<number>) => {
  //Agrega al nodo indicado uno (valores de mascara 1) o dos (valores de mascara X) hijos
  // Si la máscara contiene un 0 no agrega nodo y sigue procesando en el actual

  const pow = Math.pow(2, floatingAddress.length - 1);

  if (floatingAddress[0] != "0") {
    if (floatingAddress[0] == "X")
      treeNode.children.push(new TreeNode<number>(0, null, []));
    treeNode.children.push(new TreeNode<number>(pow, null, []));

    if (floatingAddress.length > 1)
      treeNode.children.forEach((child) =>
        generateTree(floatingAddress.substr(1), child)
      );
  } else if (floatingAddress.length > 1)
    generateTree(floatingAddress.substr(1), treeNode);
};

Una vez generado el árbol necesitamos otra función que lo recorra en profundidad y nos devuelva todas las posibles direcciones generadas:

/**
 * Realiza un recorrido DFS sobre el arbol binario sumando en cada paso el valor del nodo. Al llegar a una hoja
 * añade dicho valor al array de direcciones
 * @param node nodo raiz
 * @param acum acumulado desde la raiz hasta este nodo
 */
const getAddresses = (node: TreeNode<number>, acum = 0):number[] => {
  acum += node.data;
  const addresses: number[] = [];

  if (node.children.length == 0) {
    addresses.push(acum);
  } else {
    node.children.forEach((child) =>
      addresses.push(...getAddresses(child, acum))
    );
  }

  return addresses;
};

de nuevo se trata de una función recursiva que partiendo del nodo raiz y de derecha a izquierda baja a cada nodo final, acumulando por el camino los valores de cada nodo. Al llegar a un nodo hoja añade a un array la suma actual.

Ahora solo falta, como en la parte anterior, procesar las instrucciones del fichero de entrada:

const data = fs.readFileSync("./program.txt", "utf8").split("\r\n");

const mem: number[] = [];
const reInstruction = /(?<op>mask|mem)(\[(?<address>\d+)\])? = (?<value>[X\d]+)/;
let mask = "";
let acum = 0;

data.forEach((instruction) => {
  const inst = instruction.match(reInstruction);
  if (inst.groups["op"] == "mask") mask = inst.groups["value"];
  else {
    const floatingAddress = maskAddress(parseInt(inst.groups["address"]), mask);
    //generamos un árbol de combinaciones para la mascara flotante
    const root = new TreeNode<number>(0, null, []);
    generateTree(floatingAddress, root);
    //obtenemos las direcciones del árbol y para cada una escribimos la memoria
   
    getAddresses(root).forEach((address) => {
      if (mem[address]) acum -= mem[address];
      mem[address] = parseInt(inst.groups["value"]);
      acum += mem[address];
    });
  }
});

console.log("Answer:", acum);

El funcionamiento es el mismo que el de la primera parte pero generando las mascaras flotantes y escribiendo a todas las posibles direcciones representadas por esa máscara.

Como cambio respecto a la primera parte vamos a mantener un acumulador con la suma de los valores escritos en memoria. Esto se debe a que al aplicar máscaras a las direcciones vamos a escribir cientos de millones de ellas (en el caso de mi juego de entrada casi 4200 millones), por lo que recorrer luego la memoria para sumar el resultado sería sumamente lento. Únicamente debemos tener en cuenta que si una posición de memoria que se va a escribir ya existe hay que quitar el valor que contenga del acumulador antes de añadir el nuevo.

Si bien la solución a esta segunda parte la he visto clara bastante pronto, me ha constado implementar las funciones recursivas correctamente. ¿Qué solución has dado tú al problema?

Puedes descargar el código completo de este día desde GitHub: oddbytes.net/adventofcode
Free WordPress Themes, Free Android Games