AoC 2020 – Día 5 – Perdone, ese es mi asiento

Advent of Code 2020 llega al día 5, donde una vez salvado el control de embarque conseguimos acceder a nuestro avión solo para darnos cuenta de que se nos ha caído la tarjeta y no sabemos cual es nuestro asiento. El avión es enorme, con 128 filas y 8 asientos por fila, así que no es cuestión de probar al azar cuando siempre hay una solución mas friki que podemos aplicar. Rápidamente escribimos un programa que escanea las tarjetas de embarque de los demás pasajeros para tratar de hallar nuestro sitio por eliminación.

Parte 1 – Por favor, ocupen sus plazas

La linea aérea utiliza un sistema de particionamiento binario para asignar los asientos. Así, el billete identifica el asiento con una secuencia como FBFBBFFRLR, donde las 7 primeras posiciones indican la fila y las tres ultimas el asiento en esa fila. Debemos averiguar el numero de fila y columna de cada billete para después calcular el identificador del billete, que será el resultado de multiplicar la fila por 8 y sumar la columna o numero de asiento.

Para hallar el numero de fila debemos realizar particiones binarias del total de filas: F significa utilizar la partición inferior y B la superior, sabiendo que hay 128 filas en el avión, hasta encontrar la única fila representada por la secuencia.

Como es habitual voy a utilizar una representación de objetos, para lo que voy a crear la clase BoardingPass:

export class BoardingPass {
  private static rows = 128;
  private static columns = 8;
  constructor(public seat: string) {}

  public get row(): number {
    let start = 0,
      end = BoardingPass.rows - 1;
    for (let index = 0; index < 7; index++) {
      const half = (end + 1 - start) / 2;
      this.seat[index] === "B" ? (start += half) : (end -= half);
    }
    return start;
  }
}

La propiedad row de la clase devolverá el numero de fila a partir de los primeros 7 caracteres del billete. Para calcularla utilizo un simple bucle for en el que, en cada paso ajusto los valores de los limites inferior y superior del conjunto de filas posible. Al comenzar, el limite inferior estará establecido en 0 y el superior en 127. En cada paso, dependiendo de si debemos quedarnos con la mitad superior o inferior de ese conjunto, se moverá hacia arriba el limite inferior o hacia abajo el superior para ocupar la posición que se encuentra en la mitad. Una vez finalizado el bucle ambos limites deben haberse encontrado en la fila correcta.

Para calcular el asiento o columna utilizo exactamente el mismo procedimiento, pero con los tres últimos caracteres del billete y teniendo en cuenta que tenemos 8 asientos por fila:

 public get col(): number {
    let start = 0,
      end = BoardingPass.columns - 1;
    for (let index = 7; index < 10; index++) {
      const half = (end + 1 - start) / 2;
      this.seat[index] === "R" ? (start += half) : (end -= half);
    }
    return start;
  }

Ya solo falta calcular el identificador del asiento, una operación muy simple para la que añado una tercera propiedad a la clase:

 public get id(): number {
    return this.row * 8 + this.col;
  }

Como solución al puzzle se nos pide el id máximo de todos los billetes. Solo tenemos que calcular en nuestro programa principal los ids de todos y devolver el superior utilizando la función Math.max:

const boardingPasses = boardingPassesList.map((seat) => new BoardingPass(seat));
console.log("Answer:", Math.max(...boardingPasses.map((b) => b.id)));

Actualización

Nada mas terminar de escribir el post me he dado cuenta de que las cadenas que identifican el asiento no son mas que números en binario. Por ejemplo, la fila 8 , en binario 0001000, corresponde a la cadena FFFBFF. Por tanto se puede simplificar y acelerar mucho la generación de la fila y la columna si simplemente transformamos a decimal el numero a partir de su representación binaria:

public get row(): number {
    return new Number(
      "0b" + this.seat.substr(0, 7).replace(/F/g, "0").replace(/B/g, "1")
    ).valueOf();
  }

Parte 2 – Abróchense los cinturones

Ahora que ya conocemos los asientos del resto del pasaje, solo nos queda calcular cual es el asiento vacío. Pero para complicarlo un poco mas, resulta que algunos de los asientos en las primeras y últimas filas no existen en este avión, y por ello no están tampoco en la lista de pasajes escaneados.

Sabemos que nuestro asiento no estaba entre esas filas faltantes, y como pista nos indican que los asientos con id+1 e id-1 respecto al nuestro sí están en la lista.

Ya podemos componer una imagen del problema: tenemos un conjunto de 128 filas por 8 columnas, y el id de cada posición coincide con el indice de esa posición , ya que se calcula como 8*fila+columna. De este array hay algunas posiciones al principio y al final que no existen, y la nuestra no puede estar en los extremos ya que nos indican que en la lista existe id+1 e id-1. Puesto que algunas posiciones del inicio no existen, tenemos que tener en cuenta que los índices e ids tendrán una diferencia igual al numero de posiciones faltantes.

Con estos datos, la primera solución que salta a la vista es sencilla y directa: examinar la lista de ids en orden desde la menor a la mayor recorriendo el array de ids con un índice y si el id que ocupa la posición correspondiente al indice no coincide con el propio indice al que hay que sumar el desplazamiento provocado por los asientos faltantes del principio ya habremos hallado nuestro id:

const boardingPasses = boardingPassesList.map((seat) => new BoardingPass(seat));
const ids = boardingPasses.map((b) => b.id);
ids.sort((a, b) => a - b);
const min = ids[0],
  max = ids[ids.length - 1];

for (let index = 0; index < ids.length - 1; index++) {
  if (ids[index] != index + min) {
    console.log("Answer:", index + min);
    break;
  }
}

Dentro de nuestro juego de datos, que tiene una longitud máxima de 128 * 8 = 1024 posiciones, esta podría ser una solución aceptable, pero si el espacio de datos fuese varias magnitudes superior este método de fuerza bruta sería muy poco eficiente.

Por eso vamos a tratar de buscar una solución más elegante. Hay un método sencillo para encontrar un numero faltante dentro de una secuencia de números consecutivos: utilizar la suma de Gauss para totalizar la la secuencia completa, calcular la suma de la secuencia real y hallar la diferencia. Esa diferencia será el numero que falta. Definimos la suma de Gauss en una función que nos dará la suma de los primeros n números naturales:

/**Devuelve la suma de los primeros n numeros naturales segun la formula de Gauss */
const gauss = (n: number) => ((1 + n) / 2) * n;

Puesto que la secuencia no comienza en 1, ya que hay posiciones faltantes al inicio, tendremos que calcular la suma de Gauss para la secuencia [min, max] de nuestros ids. Para ello, calculamos la suma de Gauss desde 1 hasta el id máximo,incluyéndolo, gauss(max) y restamos la suma de Gauss desde 1 hasta el id mínimo, sin incluirlo gauss(min-1).

Por otro lado, vamos a calcular la suma de los ids de nuestra lista, para lo que usaremos la función reduce. La diferencia entre la suma de Gauss y la suma real es nuestro numero faltante:

const boardingPasses = boardingPassesList.map((seat) => new BoardingPass(seat));
const ids = boardingPasses.map((b) => b.id);

ids.sort((a, b) => a - b);
const min = ids[0],
  max = ids[ids.length - 1];

const actualSum = ids.reduce((a, b) => a + b, 0);

console.log("Answer:", gauss(max) - gauss(min-1) - actualSum);

ACTUALIZACIÓN: La versión original calculaba la respuesta como gauss(max) - gauss(min) - actualSum + min. Tal y como indica JCarles Vilaseca en los comentarios, se entiende más fácilmente si no se incluye el límite inferior en la resta y se calcula como gauss(max) - gauss(min-1) - actualSum.