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);