¡Por fin! El día 24 conseguimos llegar a la isla donde vamos a pasar las vacaciones de Navidad para descubrir que la recepción del hotel está en obras y tiene todo el suelo levantado. Los obreros se afanan en colocar baldosas hexagonales blancas y negras formando un dibujo, pero por las discusiones que tienen entre ellos no parece que vaya a ser un proceso rápido. Ante la perspectiva de pasarnos las fiestas entre polvo y cemento nos ponemos el buzo y nos disponemos a ayudar.

Parte 1 – Blanca, negra, negra, blanca…

La primera parte del problema nos propone obtener el numero de baldosas negras que tendremos sí, partiendo de que todas las baldosas son blancas, giramos algunas de ellas según una lista de instrucciones.

direcciones hexagonales

Cada instrucción de la lista nos permitirá identificar la baldosa que debemos girar. Partiendo de una baldosa central debemos ejecutar unos movimientos de manera secuencial hasta que lleguemos a la baldosa que debemos dar la vuelta. Al tratarse de baldosas hexagonales desde cada una de ellas podemos saltar a 6 vecinas, identificadas mediante las direcciones ne, e, se, sw, w y nw.

Por ejemplo, la instrucción nesew nos llevaría desde la baldosa central a la superior derecha, de esa a su inferior derecha y de vuelta a la baldosa central.

Para procesar este problema creo una clase llamada HexaTile en la que utilizaré un Set para almacenar las baldosas negras. En el constructor parseo el fichero de movimientos en una array de objetos de tipo Movement, que contiene a su vez un array con los pasos individuales. Para trocear la cadena de pasos uso una expresión regular sencilla:

type Movements = {
  steps: string[];
};

export class HexaTile {
  public blackTiles: Set<string> = new Set<string>();
  private movements: Movements[];

  constructor(movementsFile: string) {
    const reDir = /s(?:e|w)|e|w|n(?:e|w)/g;

    this.movements = fs
      .readFileSync(movementsFile, "utf8")
      .split("\r\n")
      .map((line) => ({
        steps: Array.from(line.matchAll(reDir)).map((m) => m[0]),
      }));
  }
...

Debemos procesar la lista de movimientos para cada instrucción y para cada uno de ellas calcular las coordenadas de la baldosa final y girarla. Esto significa incluirla en el set de baldosas negras si no estaba o eliminarla del mismo si ya formaba parte de él.

Cada dirección implica desplazarse desde la baldosa actual en el eje x e y. Opto por separar las baldosas horizontalmente en dos posiciones y verticalmente en 1, por lo que la lista de desplazamientos en cada dirección queda así:

  /**
   * Offset de coordenadas de cada dirección
   */
  private offsets: Record<string, number[]> = {
    ne: [1, -1],
    e: [2, 0],
    se: [1, 1],
    sw: [-1, 1],
    w: [-2, 0],
    nw: [-1, -1],
  };

Para obtener las coordenadas finales de una baldosa podemos reducir la lista de movimientos de la instrucción a una posición comenzando desde el punto 0,0 incrementando x e y en los desplazamientos indicados para cada dirección.

Para evitar utilizar el objeto punto como clave del set (recuerda que cuando un objeto se usa como clave se hace por referencia y no por valor), añado un método toString() a la clase Point que devuelva una cadena formada por los valores x,y.

/**
   * Genera el estado inicial girando las baldosas identificadas por los diferentes movimientos a partir de la baldosa (0,0)
   */
  public flipTiles = (): Set<string> => {
    this.movements.forEach((movement) => {
      const tile = movement.steps.reduce((position, step) => {
        position.x += this.offsets[step][0];
        position.y += this.offsets[step][1];
        return position;
      }, new Point(0, 0));

      const tileKey = tile.toString();
      if (this.blackTiles.has(tileKey)) this.blackTiles.delete(tileKey);
      else this.blackTiles.add(tileKey);
    });
    return this.blackTiles;
  };

Solo queda invocar a este método y contar cuantas baldosa negras hay en el set:

const hexaTile = new HexaTile("./movements.txt");
// Contar las baldosas negras tras la inicializacion
console.log("Answer:", hexaTile.flipTiles().size);

Parte 2 – El juego de la vida

La segunda parte nos lleva de nuevo a implementar un juego de la vida como en los días 11 y 17 . En esta ocasión se trata de un espacio infinito en dos dimensiones pero con 6 posibles celdas adyacentes a una dada.

Para saber que parte de ese espacio infinito debo procesar en la función que computa el nuevo estado del espacio añado un par de propiedades a la clase, que inicializo una vez hemos generado el estado inicial:

  //Dimensión más baja del espacio de suelo conocido
  private startDimensions: Point = new Point(0, 0);
  //Dimensión más alta del espacio de suelo conocido
  private endDimensions: Point = new Point(0, 0);
  /**
   * Genera el estado inicial girando las baldosas identificadas por los diferentes movimientos a partir de la baldosa (0,0)
   */
  public flipTiles = (): Set<string> => {
    this.movements.forEach((movement) => {
      const tile = movement.steps.reduce((position, step) => {
        position.x += this.offsets[step][0];
        position.y += this.offsets[step][1];
        return position;
      }, new Point(0, 0));

      if (tile.x < this.startDimensions.x) this.startDimensions.x = tile.x;
      if (tile.x > this.endDimensions.x) this.endDimensions.x = tile.x;

      if (tile.y < this.startDimensions.y) this.startDimensions.y = tile.y;
      if (tile.y > this.endDimensions.y) this.endDimensions.y = tile.y;

      const tileKey = tile.toString();
      if (this.blackTiles.has(tileKey)) this.blackTiles.delete(tileKey);
      else this.blackTiles.add(tileKey);
    });
    return this.blackTiles;
  };

Como en los anterior problemas, necesitamos una función que nos diga cuantas celdas adyacentes a una dada son baldosas negras.. La única novedad de este código respecto a la de días anteriores radica en que, al haber elegido que las celdas estén separadas horizontalmente en dos posiciones hay que tener en cuenta si la coordenada y es par o impar para calcular correctamente las coordenadas de los vecinos:

/**
   * Calcula el numero de baldosas negras adyacentes a una dada
   * @param tile posicion de la baldosa
   */
  private blackAround = (tile: IPoint) => {
    let black = 0;
    for (let y = -1; y < 2; y++)
      for (
        let x = y % 2 == 0 ? -2 : -1; //la coordenada x es par en filas pares e impar en impares
        x < (y % 2 == 0 ? 4 : 2);
        x += 2
      ) {
        if (
          (x != 0 || y != 0) &&
          this.blackTiles.has(new Point(tile.x + x, tile.y + y).toString())
        )
          black++;
      }
    return black;
  };

Dado que el espacio es infinito, en cada bucle puede expandirse el espacio conocido ya que las celdas adyacentes a los bordes actuales entran en juego. En el eje vertical lo puede hacer en una fila por encima y por debajo, mientras en el horizontal lo hará en 2 ya que es la distancia que separa cada celda. Antes de procesar el espacio conocido lo hacemos crecer y después calculamos las baldosas negras adyacentes a cada una de las comprendidas en este espacio, y aplicamos las reglas para calcular el resultante:

/**
   * Ejecuta un ciclo sobre las baldosas, generando un nuevo estado segun las reglas de la parte 2
   */
  public runCycle = (): void => {
    this.startDimensions.x -= 2;
    this.startDimensions.y--;
    this.endDimensions.x += 2;
    this.endDimensions.y++;

    const dayTiles: Set<string> = new Set<string>();

    for (let y = this.startDimensions.y; y <= this.endDimensions.y; y++)
      for (
        let x = this.startDimensions.x + (y % 2 == 0 ? 0 : -1); //la coordenada x es par en las filas pares e impar en las impares
        x <= this.endDimensions.x;
        x += 2
      ) {
        const currentTile = new Point(x, y);

        const blackAround = this.blackAround(currentTile);
        if (this.blackTiles.has(currentTile.toString())) {
          if (blackAround == 2 || blackAround == 1)
            dayTiles.add(currentTile.toString());
        } else if (blackAround == 2) dayTiles.add(currentTile.toString());
      }

    this.blackTiles = dayTiles;
  };

El problema nos pide ejecutar 100 ciclos y contar las baldosas negras que hay al final. Dado que el diseño final será, sin duda artístico, creo una función makeArt que ejecute n veces un ciclo:

 /**
   * Ejecuta el numero de ciclos especificado
   * @param days Numero de ciclos (días ) a simular
   */
  public makeArt = (days: number): Set<string> => {
    while (days-- > 0) {
      this.runCycle();
    }

    return this.blackTiles;
  };

Y ya solo falta ejecutarlo y dar el resultado final:

const hexaTile = new HexaTile("./movements.txt");
// configurar la posicion de inicio
hexaTile.flipTiles();
// ejecutar 100 ciclos
console.log("Answer:", hexaTile.makeArt(100).size);
Puedes descargar el código completo de este día desde GitHub: oddbytes.net/adventofcode
Free WordPress Themes, Free Android Games