El día 22 del advent of code 2020 nos lleva a jugar una curiosa partida de cartas con ¡un cangrejo!. Desgraciadamente es el único compañero con el que podemos contar en nuestra balsa, pero da la casualidad de que es un animal muy inteligente que aprende las reglas del juego con facilidad.

Parte 1 – Reglas sencillas

Para resolver la primera parte hay que simular una partida de cartas con reglas sencillas:

  • Cada jugador empieza con un mazo de cartas que contiene el mismo número de cartas que el del oponente.
  • Ambos sacan la carta superior y gana el que tenga la carta mas alta.
  • El ganador se lleva ambas cartas, poniendo la ganadora sobre la del contrario e insertando ambas en la parte inferior de su mazo.

El concepto de coger cartas por la parte superior del mazo e insertarlas por la parte inferior cuadra perfectamente con el funcionamiento de una cola, así que para simular la partida voy a hacer uso de una clase auxiliar Queue:

/**
 * Una cola genérica
 */
export class Queue<T> {
  public items: T[] = [];
  constructor(items?: T[]) {
    if (items) this.items = [...items];
  }

  public push = (item: T): number => this.items.push(item);

  public pop = (): T => this.items.shift();

  public peek = (): T => (this.isEmpty ? null : this.items[0]);

  public get length(): number {
    return this.items.length;
  }
  public get isEmpty(): boolean {
    return this.items.length == 0;
  }

  public toString = (): string => this.items.join();
}

Lo primero es leer el fichero de entrada y crear dos colas, una para simular el mazo de cada jugador:

export class Combat {
  public player1Cards: Queue<number>;
  public player2Cards: Queue<number>;

  constructor(tilesFile: string) {
    const cards = fs.readFileSync(tilesFile, "utf8").split("\r\n\r\n");
    this.player1Cards = new Queue(
      cards[0]
        .split("\r\n")
        .slice(1)
        .map((c) => parseInt(c))
    );
    this.player2Cards = new Queue(
      cards[1]
        .split("\r\n")
        .slice(1)
        .map((c) => parseInt(c))
    );
  }
}

Implementar las reglas del juego es muy sencillo: mientras a algún jugador le queden cartas sacamos de ambas colas e introducimos las dos cartas ordenadas de mayor a menor en la cola del ganador:

  public play = (): Queue<number> => {
    while (!(this.player1Cards.isEmpty || this.player2Cards.isEmpty)) {
      const player1Card = this.player1Cards.pop();
      const player2Card = this.player2Cards.pop();
      const winner =
        player1Card > player2Card ? this.player1Cards : this.player2Cards;
      winner.push(Math.max(player1Card, player2Card));
      winner.push(Math.min(player1Card, player2Card));
    }
    return this.player1Cards.isEmpty ? this.player2Cards : this.player1Cards;
  };

Una vez hemos terminado la función devuelve el mazo del ganador para calcular la puntuación, que es la suma de cada carta multiplicada por la posición que ocupa en la cola empezando por el final:

const combat = new Combat("./cards.txt");
const winningDeck = combat.play();
const cards = winningDeck.items.reverse();

console.log(
  "Answer:",
  cards.reduce((a, b, i) => (a += b * (i + 1)), 0)
);

Parte 2 – Reglas recursivas

Advent of Code no es lo mismo sin recursión, así que para la segunda parte del problema la reglas cambian incluyendo juegos y subjuegos:

  • Si al mostrar las cartas superiores los mazos de los jugadores contienen al menos el numero de cartas indicado en el valor de la levantada, el ganador se decide en un nuevo juego en el que solo se usan tantas cartas del mazo actual como el numero de la mostrada. A la hora de insertar las cartas mostradas de nuevo en el mazo del ganador puede darse el caso de que la mas alta vaya debajo, ya que el resultado se ha dirimido en ese subjuego y no en el juego actual.
  • Si en un juego se repite la misma combinación de cartas en los mazos de los jugadores automáticamente gana el jugador 1 sin importar el estado de los mazos ni el estado de otros juegos. Esta es la condición que pone fin a la recursión.
  • Si no se dan las condiciones anteriores se juega como hasta el momento, la carta más alta gana.

Vamos a empezar por la regla que pone fin a la recursión. Para saber si un estado de mazos determinado se repite necesitamos representar de alguna manera las cartas contenidas en cada mazo en un momento dado. Lo mas directo seria escribir un par de cadenas tipo 1,23,45… con todas las cartas y concatenarlas, pero eso nos daría identificadores de estado muy largos. Voy a optar por tratar de encontrar una formula que nos devuelva un numero diferente para cada combinación. Para ello multiplico cada carta por su posición en la cola, y las del jugador 2 las doblo para que la misma secuencia de mazos pero con los jugadores intercambiados obtenga un numero diferente:

  /**
   * Obtiene un  identificador único para el estado del juego a partir de las posiciones de las cartas de cada jugador
   */
  private getGameState = (
    player1Cards: Queue<number>,
    player2Cards: Queue<number>
  ): number =>
    player1Cards.items.reduce((a, b, i) => (a *= b * (i + 1)), 1) +
    player2Cards.items.reduce((a, b, i) => (a *= b * (i + 1)), 1) * 2;

Ya podemos comenzar a escribir la rutina de que simula una partida determinada. Como va a haber múltiples juegos esta deberá recibir los mazos con los que jugar como parámetros:

 public playRecursive = (
    player1Cards: Queue<number>,
    player2Cards: Queue<number>
  ): number => {
    const gameStates: Set<number> = new Set<number>();

    while (!(player1Cards.isEmpty || player2Cards.isEmpty)) {
      const gameState = this.getGameState(player1Cards, player2Cards);

      if (gameStates.has(gameState)) return 1; //Si el juego ya ha pasado por este estado, el jugador instantaneo es el 1

En cada turno del juego lo primero es comprobar si ese estado de juego ya ha ocurrido, porque en ese caso debemos terminar de inmediato. Para ello vamos a guardar los estados en un set y comprobar si el estado actual está en ese conjunto en cada mano. De no ser así podemos jugar la mano, para la que implemento las reglas en una función separada:

 /**
   * Juega una mano de la partida segun las reglas de la segunda parte
   */
  public playRound = (
    player1Cards: Queue<number>,
    player2Cards: Queue<number>
  ): number => {
    const player1Card = player1Cards.pop();
    const player2Card = player2Cards.pop();

    // si los dos jugadores tienen en su mazo al menos tantas cartas como el numero que ha sacado cada uno
    // el ganador se decide en una subpartida
    if (
      player1Card <= player1Cards.length &&
      player2Card <= player2Cards.length
    ) {
      return this.playRecursive(
        new Queue(player1Cards.items.slice(0, player1Card)),
        new Queue(player2Cards.items.slice(0, player2Card))
      );
    }

    // Si no la mano la gana el que tenga la carta mas alta
    return player1Card > player2Card ? 1 : 2;
  };

Esta función implementa las dos reglas restantes: si ambos jugadores tienen en su mazo cartas suficientes para una subpartida, esta se inicia con una llamada recursiva y en caso contrario se devuelve como ganador al que tiene la carta mostrada más alta.

Ya podemos completar la función que simula la partida:

  public playRecursive = (
    player1Cards: Queue<number>,
    player2Cards: Queue<number>
  ): number => {
    const gameStates: Set<number> = new Set<number>();

    while (!(player1Cards.isEmpty || player2Cards.isEmpty)) {
      const gameState = this.getGameState(player1Cards, player2Cards);

      if (gameStates.has(gameState)) return 1; //Si el juego ya ha pasado por este estado, el jugador instantaneo es el 1

      const player1Card = player1Cards.peek();
      const player2Card = player2Cards.peek();
      const winner = this.playRound(player1Cards, player2Cards);
      const winnerCards = winner == 1 ? player1Cards : player2Cards;
      winnerCards.push(winner == 1 ? player1Card : player2Card);
      winnerCards.push(winner == 1 ? player2Card : player1Card);

      gameStates.add(gameState);
    }
    return player1Cards.isEmpty ? 2 : 1;
  };

Al igual que en la primera parte, mientras uno de los dos jugadores tenga cartas en su mazo jugamos rondas teniendo en cuenta que el estado de los mazos no puede repetirse. Al finalizar devolvemos el jugador que gana la partida (o subpartida). Para invocar el juego y obtener la respuesta final solo nos falta:

const combat = new Combat("./cards.txt");
const winner = combat.playRecursive(combat.player1Cards, combat.player2Cards);

let cards = winner == 1 ? combat.player1Cards.items : combat.player2Cards.items;
cards = cards.reverse();

console.log(
  "Answer:",
  cards.reduce((a, b, i) => (a += b * (i + 1)), 0)
);
Puedes descargar el código completo de este día desde GitHub: oddbytes.net/adventofcode
Free WordPress Themes, Free Android Games