Ya estamos dentro de los sistemas del avión y justo cuando estábamos viendo la información meteorológica, en la que se mostraba una enorme tormenta tropical, nos quedamos sin batería. Es imposible seguir el resto del viaje sin saber si esa tormenta va a estropearnos las vacaciones, pero no tenemos un adaptador válido para el avión que nos permita cargar el ordenador porque el enchufe situado en el asiento da un joltage inadecuado.
Ni cortos ni perezosos hacemos una lista de todos los adaptadores que llevamos en el equipaje de mano, a ver si conseguimos usarlos para hacer un cargador que nos permita seguir hackeando (er, consultando) los sistemas del avión.
Cada uno de nuestros adaptadores da una salida de x jolts, y admite una entrada de x-1, x-2 o x-3 jolts. Ademas, el ordenador dispone de su propio adaptador adicional que es 3 jolts superior al mas adaptador con mayor salida de nuestra lista. Partiendo del enchufe del asiento, que da 0 jolts, nos ponemos manos a la obra a conectar todos los transformadores de manera consecutiva para lograr nuestro objetivo.
Parte 1 – Conectando todo en serie
Para resolver la primera parte del problema debemos conectar todos los adaptadores de los que disponemos siguiendo la regla de que no puede haber una diferencia de joltage mayor a 3 con el adaptador anterior. Si un adaptador esta marcado como 16, sólo se puede poner a continuación de uno marcado con 13,14 o 15 jolts de salida. A pesar de lo detallado de la explicación de este punto en la página original, puesto que se deben utilizar todos ellos solo hay una posible configuración: los adaptadores deben ir del de menor al de mayor potencia, es decir, basta con ordenar el array de entrada para tener la secuencia correcta:
const adapters = fs
.readFileSync("./adapters.txt", "utf8")
.split("\r\n")
.map((n) => parseInt(n))
.sort((a, b) => a - b);
Para dar respuesta al problema debemos hallar el numero de diferencias de joltage entre adaptadores iguales a 1 y el número de diferencias de joltage iguales a 3 y multiplicar ambas cifras. Creo una función genérica que cuente el número de diferencias de la magnitud que le indiquemos:
/**
* Devuelve el numero de diferencias de voltaje de la magnitud indicada
* @param gapSize diferencia de joltage
*/
const getNumberOfGaps = (gapSize) =>
adapters.reduce(
(count, adapter, index, adapters) =>
(count +=
(index > 0 && adapter - adapters[index - 1]) == gapSize
? 1
: index == 0
? adapter == gapSize
? 1
: 0
: 0),
0
);
La función reduce al array sobre un acumulador al que se suma un cuando la diferencia entre un elemento y el inmediatamente siguiente es igual a la cifra que pasemos como parametro. Puesto que antes de nuestro lio de transformadores esta el enchufe y debemos contar tambien la diferencia entre este y el primer adaptador, hay que hacer un tratamiento especial para el indice 0.
Ahora utilizo la función para dar la respuesta a esta primera parte:
console.log("Answer:", getNumberOfGaps(1) * (getNumberOfGaps(3) + 1));
Hay que prestar atención al hecho de que, tras nuestra secuencia de adaptadores hay uno más extra en el propio ordenador que, según indica el enunciado, siempre tiene una diferencia de tres jolts con el mas alto (el último) de nuestra lista. Por tanto, sumamos ese adaptador al resultado de getNumberOfGaps(3)
Parte 2 – Vaya lio de cables
La segunda parte del problema consiste en buscar todas las posibles combinaciones de adaptadores válidas que podemos crear con nuestro juego de entrada. Por ejemplo, de la secuencia de adaptadores (0) 1 2 (5) podemos quitar el 1 y la secuencia (0) 2 (5) seguiría siendo válida.
Parece claro que las combinaciones sólo se pueden producir cuando tenemos adaptadores con diferencias de voltaje menor de 3, ya que 3 es el límite que no se puede superar . De la primera parte ya sabemos cuantas secuencias de adaptadores con diferencias de 1 jolt hay, así que miro cuantas hay de 2 en la entrada que me ha tocado solo para descubrir que ¡no hay ninguna!
Luego nuestros adoptadores están conectados o con diferencias de 1 jolt o con diferencias de 3. Y únicamente se pueden producir combinaciones en los grupos de adaptadores consecutivos con diferencias de 1 jolt, ya que eliminar de cualquier sitio un adaptador con un salto de 3 jolts nos llevaría a una combinación inválida.
Por tanto podemos dividir nuestro problema en múltiples problemas más pequeños, partiendo nuestra secuencia de adaptadores cada vez que encontremos un salto de 3 jolts, y ver por cada grupo de adaptadores contiguos diferenciados por un único jolt cuantas combinaciones pueden hacerse. La multiplicación de las combinaciones de todos esas combinaciones nos dará la respuesta.
Vamos a ver cuales son esos grupos. En primer lugar, vamos a obtener un array con la diferencia de jolts entre cada adaptador y el siguiente, partiendo del array ordenado de adaptadores como en la primera parte:
// Obtener los saltos de joltaje entre adaptadores const gaps = adapters.map((adapter, index) => index > 0 ? adapter - adapters[index - 1] : adapter );
Ahora vamos a ver como se agrupan los adaptadores que solo tienen 1 jolt de diferencia. Para ello voy a unir todo el array en una cadena y partirla por las diferencias de 3 jolts, de manera que voy a obtener un array con grupos de adaptadores de 1 jolt. La longitud de cada cadena de ese array son los adaptadores de ese grupo:
//Obtener el numero de adaptadores contiguos que tienen un salto de 1 jolt
const oneJoltAdapterGroups = gaps
.join("")
.split("3")
.filter((group) => group.length > 0)
.map((group) => group.length);
Esto nos devolverá un array del estilo [1,3,4,2,1...] en el que cada posición indica la longitud de un grupo de adaptadores.
Ahora voy a hallar las combinaciones que pueden generarse dependiendo de la longitud de cada grupo. Nada mejor que lápiz y papel, y un rato después veo que dependiendo del numero de adaptadores consecutivos de 1 jolt se pueden hacer estas variaciones:
- 1 adaptador: 1 combinación
- 2 adaptadores: 2 combinaciones
- 3 adaptadores: 4 combinaciones
- 4 adaptadores: 7 combinaciones
Veo en el resultado de la función anterior que no tengo ningún grupo de con más de 4 adaptadores, así que no continúo combinando y creo una función que me devuelva la anterior secuencia. Veo que cada número es igual a la suma del anterior mas la diferencia con el actual, así que una función recursiva me hace la labor:
/**
* Devuelve el numero de combinaciones que pueden hacerse con n adpatadores consecutivos que tengan un salto de 1 jolt
* Se trata realmente de la secuencia tribonacci, pero con la entrada del problema solo tenemos longitudes máximas de 4 funciona igual
* @param groupSize numero de adaptadores consecutivos con un salto de 1 jolt
*/
const adapterCombinations = (groupSize: number) => {
if (groupSize == 1) return 1;
return groupSize - 1 + adapterCombinations(groupSize - 1);
};
Y únicamente queda multiplicar las combinaciones que pueden hacerse con cada grupo por las demás:
//Multiplicamos las combinaciones que produce cada grupo de adaptadores consecutivos console.log( "Answer:", oneJoltAdapterGroups.reduce((a, b) => (a *= adapterCombinations(b)), 1) );
Esta segunda parte me ha llevado un rato más largo del habitual. A pesar de haber visto desde el principio que había que localizar los grupos de adaptadores contiguos con diferencias de 1 jolt y que las combinaciones de cada grupo dependían únicamente de su longitud al no haber diferencias de 2 jolts, me he empeñado en dar con una función que generase correctamente las combinaciones para cualquier número de adaptadores. Y para una longitud 5 las combinaciones son 13, lo que no me cuadraba con ninguna secuencia que conociese. Al final, puesto que la longitud máxima según mi entrada es 4, la función que he implementado es suficiente pero esta solución no funcionaría si hubiese un grupo de 5 adaptadores.
La respuesta la he obtenido de la comunidad de Advent of Code. El número de combinaciones sigue la secuencia tribonacci, donde cada numero es igual a la suma de los tres anteriores: 0 0 1 1 2 4 7 13 24 …., luego sería una solución mas correcta implementar esta función para obtener el número de combinaciones que la que yo he creado. Aunque en esta ocasión eso lo dejo para ti, lector.