Conseguimos que el ferry sortee la tormenta y terminamos en una isla en la que no nos queda mas remedio que coger otro avión si queremos llegar a nuestro destino. Antes debemos llegar hasta el aeropuerto por autobús, pero, como no, antes de montarnos debemos resolver un par de problemillas en la estación de autobuses para montarnos en el correcto a la hora mas adecuada.

Parte 1 – Módulos, módulos, módulos

Para la primera parte del puzzle de hoy nos dan dos entradas:

  • El momento más tempranos en el que nos podemos montar en un bus
  • Una lista de buses donde cada uno de sus identificadores coincide con su frecuencia. Así, el autobús 5 sale en el momento 0,5,10,15....

La pregunta a contestar es cual es el primer autobús que podemos coger teniendo en cuenta que no nos podemos montar antes del momento indicado anteriormente.

Lo resuelvo manualmente con un ejemplo. Si nos podemos montar en el autobús desde el momento 38 y los ids que tenemos son 5 y 6, podemos ver que para montar en el autobús 5 tendríamos que esperar dos minutos desde el minuto 38 al 40, mientras que si cogemos el 6 habría que esperar al minuto 42, 4 minutos.

Para calcular la diferencia entre la salida de cualquier bus y el momento en el que podemos montarnos solo tenemos que calcular el resto de la división de ese momento y la frecuencia del bus en cuestion. Así 38 mod 5 =3 y 38 mod 6=2. Ahora solo tenemos que restar esta cifra de la frecuencia y ya tenemos el numero de mintos a esperar a cada bus. 5-3= 2 y 6-2=4.

Generalizándolo para todos los buses:

import * as fs from "fs";

const data = fs.readFileSync("./buses.txt", "utf8").split("\r\n");
const minTime = parseInt(data[0]);
const buses = data[1]
  .split(",")
  .filter((id) => id != "x")
  .map((id) => parseInt(id));

const diffs = buses.map((id) => id - (minTime % id));
console.log(minTime, buses, diffs);
const minDiff = Math.min(...diffs);

const busIndex = diffs.findIndex((diff) => diff == minDiff);

console.log("Answer:", buses[busIndex] * minDiff);

El array buses contiene los identificadores (o frecuencias) de cada autobús. A partir de él, y con la fórmula anterior, creo otro array que me indica los minutos de espera a partir del momento en que puedo coger un autobús que tendría que aguardar a cada uno de ellos.

Como respuesta nos piden la multiplicación del numero de minutos a esperar por el id del bus, por lo que sencillamente busco en el array de autobuses el que ocupa la posición que menos minutos me hace esperar según el array de datos de minutos de espera.

Parte 2 – Primos, primos, primos… y más módulos

La segunda parte del problema me ha resultado mucho mas complicada: se trata de encontrar el primer momento en el que sale el bus con el primer id y se cumple que el resto de buses salen con una diferencia igual al índice que ocupan en los datos de entrada. Así, si tenemos en entrada 7,13,x,x,59,x,31,19 hay que encontrar el momento en el que el sale el autobús 7 y se cumple que el 12 sale un minuto después ,el 59 cuatro minutos más tarde, el 31 seis minutos y el 19 siete minutos después (lo que coincidirá con una nueva salida del 7).

Nada más mirar los datos de entrada o de los ejemplos llama la atención que todos los números son primos, por lo que inmediatamente queda claro que, con total seguridad, hay alguna fórmula matemática relacionada con primos que sirve para resolver este problema.

Pero mis matemáticas están muy oxidadas y no me suena nada al respecto, así que voy a tratar de resolverlo por mis propios medios. Me parece que calcular el momento de la salida, t, para los dos primeros autobuses no debe ser complicado. Debe cumplirse algo así:

7a=t
13b=t+1

Lápiz y papel en mano, calculo que para a=11 y b=6, t0=77 se cumple lo anterior. Es decir, ese es el primer momento en el que sale el primer autobús y se cumple que el segundo sale un minuto después. Pero obviamente esto no cumple con el tercer autobús, que es el 59 y debe salir 4 minutos mas tarde que t0.

Habría que hallar en qué siguiente momento que se cumplen las reglas para el primer y segundo autobús se cumplen también para el tercero. Calculo el siguiente, t1, en que se cumplen las reglas para los dos primeros a ver si hay suerte con el tercero. Esta vez es para a=24, b=13, t1=168. Pero el tercer bus no cumple 59c=t+4. Pruebo con el tercer momento y encuentro a=37, b=20, t2=259. El momento t2 sigue sin cumplir la regla para el tercer bus, pero estoy viendo un patrón en los sucesivos momentos t: del primero al segundo hay una diferencia de 91, igual que del segundo al tercero. Tras pensarlo un poco, parece lógico: a partir del primer momento los siguientes tiene que cumplir que tn sea múltiplo de 7 y tn+1 múltiplo de 13, por lo que deben estar separado por múltiplos del mínimo común múltiplo de ambos. Al tratarse de primos, el mínimo común múltiplo es su multiplicación, 7*13=91.

Hay que seguir sumando 91 a t0 hasta encontrar el caso en que 59c=tn+4, es decir, que tn+4 sea múltiplo de 59. No puedo seguir haciéndolo a mano, es hora de escribir una función que lo calcule:

const nextT = (
  t0: number,
  increment: number,
  nextMultiplier: number,
  nextOffset:number
): number => {
  while ((t0 + nextOffset) % nextMultiplier != 0) {
    t0 += increment;
  }
  return t0;
};

Para calcular t0 de los dos primeros autobuses llamo a la función de esta manera: let t=nextT(0,7,13,1). Es decir, comenzando en 0 y usando incrementos de 7 (el primer bus es el 7), busca el momento tn en que se cumple que tn+1 es múltiplo de 13 (el segundo bus), o lo que es lo mismo, que el resto de dividir tn+1 entre 13 es 0.

El resultado es el que ya conocíamos, t0=77. Ahora, para el siguiente bus la llamada sería t=nextT(77,7*13,59,4). Comenzando en 77 e incrementando cada vez en 91, busca en momento en que tn+4 es múltiplo de 59. El resultado de la función en este caso: t1=350, que cumple t1 mod 7=0, t1+1 mod 13=0 y t1+4 mod 59=0.

Esto tiene buena pinta. Ya puedo implementar la parte 2 del día, esta claro que necesitamos para cada bus su id y el desplazamiento respecto al primero. Creo la definición de una estructura para contenerlos y es lo primero que obtengo leyendo el fichero de entrada:

interface IBus {
  busId: number;
  offset: number;
}
const data = fs.readFileSync("./busesDemo.txt", "utf8").split("\r\n");
// Crear un array con la informacion del id del bus y su offset respecto al primero
const buses: IBus[] = data[1]
  .split(",")
  .map((id, index) => ({ busId: parseInt(id), offset: index }))
  .filter((c) => !isNaN(c.busId));

Ahora puedo automatizar las llamadas a nuestra función de prueba, que redefino usando el interface IBus:

/**
 * Calcula el siguiente timestamp para el que se cumplen las condiciones de los autobuses anteriores y el siguiente
 * @param initialTimestamp timestamp a partir del que empezar a buscar
 * @param increment incremento desde el rimestamp
 * @param nextBus siguiente bus que debe cumplir su condicion en el bloque calculado
 */
const nextTimestamp = (
  initialTimestamp: number,
  increment: number,
  nextBus: IBus
): number => {
  while ((initialTimestamp + nextBus.offset) % nextBus.busId != 0) {
    initialTimestamp += increment;
  }
  return initialTimestamp;
};


let timestamp = 0;
let increment = 1;

for (let bus = 1; bus < buses.length; bus++) {
  increment *= buses[bus - 1].busId;
  timestamp = nextTimestamp(timestamp, increment, buses[bus]);
}
console.log("Answer:",timestamp);

Por cada bus llamo a la función aumentando el incremento que debe aplicarse en el mínimo común múltiplo del incremento anterior y el número del bus. Como ya hemos visto, todos los ids de bus son primos, por lo que podemos sencillamente multiplicar las cifras. Una vez que salgamos del bucle, la variable timestamp contiene el momento en que se cumplen las reglas para todos los buses.

Y así acaba el que ha sido, en mi opinión y hasta el momento, el problema más complicado de este Advent of Code 2020. ¿Tú como lo has resuelto?

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