Ya estamos de nuevo esperando un vuelo y una vez mas, aburridos. Este viaje está resultando más largo que la vuelta al mundo de Willy Fog. Para pasar el rato, llamamos a los elfos en el Polo norte que resultan estar echando una partida a un juego de memoria basado en números. Sin nada mejor que hacer, nos sumamos a ellos.

Parte 1 y 2 – Generando secuencias

Las reglas del juego son sencillas:

  • Se lee una lista de números iniciales.
  • Una vez terminada comienzan los turnos. En cada turno hay que mirar el último número de la lista y:
    • Si no ha sido dicho anteriormente, decir (añadir a la lista) el 0
    • Si ha sido dicho anteriormente decir la diferencia entre la última y la penúltima vez que apareció en la lista.

Así por ejemplo, para los números iniciales 0,3,6 deberíamos seguir la secuencia con

Turno     : 1  2  3  4  5  6  7  8  9  10
Secuencia : 0, 3, 6, 0, 3, 3, 1, 0, 4, 0 .....

Debemos buscar una manera ágil de almacenar la información que necesitamos para el juego, esto es, necesitamos almacenar la lista de números que ya se han nombrado y en qué turno lo han sido. Para ello voy a utilizar un mapa o diccionario, disponible en Javascript a través del objeto Map, donde la clave será el número y el valor un objeto donde almacenaré la última y penúltima vez que han aparecido en la lista:

/**
 * representa un numero aparecido en el juego.
 */
interface ISpokenNumber {
  /** Última vez dicho */
  lastTurn: number;
  /**Penúltima vez dicho */
  previousTurn?: number;
}

export class SpokenNumbers {
  /**Utilizamos un mapa para guardar los numeros que ya hemos nombrado */
  private spokenNumbers: Map<number, ISpokenNumber> = new Map<
    number,
    ISpokenNumber
  >();

  /** Turno actual */
  public turn = 0;
  /** Último número dicho */
  private lastSpokenNumber = -1;
}

Creo una función en esta clase para calcular el siguiente número de la lista siguiendo las reglas del juego:

  /**
   * Devuelve el siguiente número de la lista. Si el anterior no ha aparecido nunca
   * añade 0 a la lista, si no la diferencia entre las dos ultimas veces que se ha nombrado
   * dicho numero
   */
  public spokeNext = (): number => {
    const prevSpoken = this.spokenNumbers.get(this.lastSpokenNumber);

    const newNumber =
      prevSpoken?.previousTurn != undefined
        ? prevSpoken.lastTurn - prevSpoken.previousTurn
        : 0;
    this.setSpokenNumber(newNumber);

    this.lastSpokenNumber = newNumber;

    return newNumber;
  };

Una vez decidido el número de la lista solo queda actualizar nuestro mapa de números aparecidos, añadiéndolo al diccionario si es la primera vez que aparece o actualizando la información referente a los turnos en los que ha aparecido:

  /**
   * Crea o actualiza una entrada en el mapa de numeros nombrados
   * Avanza el contador de turnos
   * @param number Numero
   */
  private setSpokenNumber(number: number) {
    let spokenNumber = this.spokenNumbers.get(number);

    // Si el numero no ha aparecido hasta el momento en la lista, crear una nueva instancia para él
    if (!spokenNumber) {
      this.spokenNumbers.set(number, { lastTurn: this._turn });
    } else {
      //Si ha sido dicho, actualizar sus turnos de aparición
      spokenNumber.previousTurn = spokenNumber.lastTurn;
      spokenNumber.lastTurn = this.turn;
    }

    this._turn++;
  }

La pregunta de la primera parte nos pide el número de la lista correspondiente al turno 2020, así que simplemente generamos números hasta ese turno:

let spokenNumbers = new SpokenNumbers("./startNumbers.txt");
let spokenNumber: number;
while (spokenNumbers.turn < 2020) spokenNumber = spokenNumbers.spokeNext();
console.log(spokenNumber);

La segunda parte del puzzle nos pide el numero que aparece en la posición 30.000.000. Después de revisar con detenimiento la lista de salida de la parte 1 no doy con ningun ciclo o patrón que me permita establecer una forma de calcularlo directamente, así que opto por utilizar la solución de la primera parte y generar los 30 millones de números. El objeto Map esta optimizado para grandes volúmenes y accesos muy rápidos, por lo que en mi PC no tarda mas de 7 segundos en devolver la respuesta a esta segunda parte, lo que me parece aceptable.

let spokenNumbers = new SpokenNumbers("./startNumbers.txt");
let spokenNumber: number;
while (spokenNumbers.turn < 30000000) spokenNumber = spokenNumbers.spokeNext();
console.log(spokenNumber);
Puedes descargar el código completo de este día desde GitHub: oddbytes.net/adventofcode
Free WordPress Themes, Free Android Games