Mientras estamos en vuelo los elfos del Polo Norte nos llaman para solicitar ayuda con una fuente de energía experimental con la que están teniendo problemas. Se trata de una tecnología muy avanzada que consta de una serie de cubos en una dimensión de bolsillo que contiene un espacio infinito 3D. Cada uno de estos cubos puede estar encendido o apagado, y al igual que ocurría en el problema del día 11, se dan una serie de ciclos en los que todos los cubos cambian su estado a la vez basándose en el estado de los adyacentes:
- Si un cubo está apagado y tiene exactamente 3 cubos adyacentes encendidos, se enciende.
- Si un cubo está encendido y tiene 2 o 3 cubos adyacentes encendidos, continua encendido y si no se apaga.
El problema consiste en ejecutar una serie de 6 ciclos e indicar cuantos cubos están encendidos al finalizar.
Parte 1 – Tres dimensiones
Para representar los cubos en un espacio tridimensional voy a echar mano de una clase auxiliar Point3D, que se basa en la clase auxiliar Point que ya usé el día 12 y le añade una coordenada en el eje z:
export interface IPoint3D extends IPoint {
z: number;
}
export class Point3D implements IPoint3D {
constructor(public x: number, public y: number, public z: number) {}
public toString = (): string => `x:${this.x},y:${this.y},z:${this.z}`;
}
Voy a crear una clase ConwayCubesSpace3D para representar el espacio tridimensional conocido, del que al principio solo conocemos el estado inicial (los puntos de un plano que nos dan como entrada). Al tratarse como indican las instrucciones de un espacio infinito tenemos que tener en cuenta que ese espacio se va a ir expandiendo en cada ciclo, pues los cubos adyacentes a los conocidos en todos los ejes entran en juego. Para llevar la cuenta del tamaño de este espacio utilizo dos variables, startDimensions y endDimensions.
/**
* Representa el espacio tridimensional conocido en el que existen los cubos
*/
export class ConwayCubesSpace3D {
public cubes: Map<string, boolean> = new Map<string, boolean>();
//Almacena las coordenadas de inicio del espacio actual
private startDimensions: IPoint3D = new Point3D(0, 0, 0);
//Almacena las coordenadas finales del espacio actual
private endDimensions: IPoint3D;
constructor(initialStateFile: string) {
const lines = fs.readFileSync(initialStateFile, "utf8").split("\r\n");
this.endDimensions = new Point3D(lines[0].length - 1, lines.length - 1, 0);
lines.forEach((line, y) =>
Array.from(line).forEach((cube, x) =>
this.cubes.set(new Point3D(x, y, 0).toString(), cube == "#")
)
);
}
El constructor lee el fichero de entrada y genera un mapa de con los cubos en cada una de sus posiciones, ademas de actualizar las dimensiones finales del espacio conocido. Como verás, la clave del mapa no es el objeto punto sino su representación en cadena. Esto se debe a que el acceso al mapa por clave es por referencia cuando la clave es un objeto. Es decir, si pasamos dos objetos diferentes, aunque tengan los mismos valores, serían diferentes claves. Para evitar esto deberíamos llevar una lista de claves y buscar en ella cada vez que quisiéramos acceder al mapa, lo que sería más lento.
Como en el día 12, lo primero que necesitamos es una función que nos de el numero de cubos encendidos adyacentes a uno dado en cualquier dirección. Sencillamente voy a utilizar la función de ese día añadiéndole el nuevo eje z y teniendo en cuenta los limites del espacio 3D conocido:
/**
* Calcula el numero de cubos encendidos adyacentes a uno dado
* @param seat posicion del cubo
*/
private onAround = (cube: IPoint3D) => {
let on = 0;
for (let z = -1; z < 2; z++)
for (let y = -1; y < 2; y++)
for (let x = -1; x < 2; x++) {
if (x != 0 || y != 0 || z != 0) {
const adjacentCube = new Point3D(
cube.x + x,
cube.y + y,
cube.z + z
);
if (
this.cubes.has(adjacentCube.toString()) && //si no existe debe estar fuera del mapa o apagado
adjacentCube.x >= this.startDimensions.x &&
adjacentCube.y >= this.startDimensions.y &&
adjacentCube.z >= this.startDimensions.z &&
adjacentCube.x <= this.endDimensions.x &&
adjacentCube.y <= this.endDimensions.y &&
adjacentCube.z <= this.endDimensions.z &&
this.cubes.get(adjacentCube.toString())
)
on++;
}
}
return on;
};
Ahora, de nuevo igual que el día 12, debemos calcular el nuevo estado de los cubos en cada ciclo con la diferencia de que nuestro espacio conocido va a crecer ya que el enunciado dice que este es infinito. En el anterior problema los asientos eran fijos y no podían crecer. Por tanto hacemos expandirse el espacio añadiendo una posición por el inicio y por el final en cada eje y calculamos los estados de los cubos en este nuevo espacio:
/**
* Ejecuta un ciclo de inicializacion
* Añade dos posiciones en cada eje a las dimensiones y los recorre estableciendo los estados de cada cubo
*/
public runCycle = (): void => {
Object.keys(this.startDimensions).forEach(
(key) => (this.startDimensions[key] -= 1)
);
Object.keys(this.endDimensions).forEach(
(key) => (this.endDimensions[key] += 1)
);
const cycleCubes: Map<string, boolean> = new Map<string, boolean>();
for (let z = this.startDimensions.z; z <= this.endDimensions.z; z++)
for (let y = this.startDimensions.y; y <= this.endDimensions.y; y++)
for (let x = this.startDimensions.x; x <= this.endDimensions.x; x++) {
const currentCube = new Point3D(x, y, z);
if (!cycleCubes.has(currentCube.toString()))
cycleCubes.set(currentCube.toString(), false);
const onAround = this.onAround(currentCube);
if (this.cubes.get(currentCube.toString())) {
cycleCubes.set(
currentCube.toString(),
onAround > 1 && onAround < 4
);
} else cycleCubes.set(currentCube.toString(), onAround == 3);
}
this.cubes = cycleCubes;
};
Solo nos falta invocar a esta clase para generar los 6 ciclos y contar los cubos encendidos después:
const space = new ConwayCubesSpace3D("./initialState.txt");
for (let cycle = 0; cycle < 6; cycle++) {
space.runCycle();
}
console.log(
"Answer:",
Array.from(space.cubes.values()).filter((state) => state).length
);
Parte 2 – La cuarta dimensión
La segunda parte del problema nos propone utilizar las mismas reglas pero en un espacio de cuatro dimensiones. No soy capaz de hacerme una imagen mental de la representación de este espacio, pero intuyo que sería suficiente añadir esta cuarta dimensión a nuestros cálculos, al igual que hemos añadido una tercera al problema del día 12 para resolver la primera parte, por lo que creo una nueva clase auxiliar Point4D y una nueva clase ConwayCubesSpace4D con un nuevo eje w:
export interface IPoint4D extends IPoint3D {
w: number;
}
export class Point4D implements IPoint4D {
constructor(
public x: number,
public y: number,
public z: number,
public w: number
) {}
public toString = (): string =>
`x:${this.x},y:${this.y},z:${this.z},w:${this.w}`;
}
export class ConwayCubesSpace4D {
public cubes: Map<string, boolean> = new Map<string, boolean>();
//Almacena las coordenadas de inicio del espacio actual
private startDimensions: IPoint4D = new Point4D(0, 0, 0, 0);
//Almacena las coordenadas finales del espacio actual
private endDimensions: IPoint4D;
constructor(initialStateFile: string) {
const lines = fs.readFileSync(initialStateFile, "utf8").split("\r\n");
this.endDimensions = new Point4D(
lines[0].length - 1,
lines.length - 1,
0,
0
);
lines.forEach((line, y) =>
Array.from(line).forEach((cube, x) =>
this.cubes.set(new Point4D(x, y, 0, 0).toString(), cube == "#")
)
);
}
/**
* Calcula el numero de cubos encendidos adyacentes a uno dado
* @param seat posicion del asiento
*/
private occupiedAround = (cube: IPoint4D) => {
let on = 0;
for (let w = -1; w < 2; w++)
for (let z = -1; z < 2; z++)
for (let y = -1; y < 2; y++)
for (let x = -1; x < 2; x++) {
if (x != 0 || y != 0 || z != 0 || w != 0) {
const adjacentCube = new Point4D(
cube.x + x,
cube.y + y,
cube.z + z,
cube.w + w
);
if (
this.cubes.has(adjacentCube.toString()) && //si no existe esta fuera del mapa o apagado
adjacentCube.x >= this.startDimensions.x &&
adjacentCube.y >= this.startDimensions.y &&
adjacentCube.z >= this.startDimensions.z &&
adjacentCube.w >= this.startDimensions.w &&
adjacentCube.x <= this.endDimensions.x &&
adjacentCube.y <= this.endDimensions.y &&
adjacentCube.z <= this.endDimensions.z &&
adjacentCube.w <= this.endDimensions.w &&
this.cubes.get(adjacentCube.toString())
)
on++;
}
}
return on;
};
/**
* Ejecuta un ciclo de inicializacion
* Añade dos posiciones en cada eje a las dimensiones y los recorre estableciendo los estados de cada cubo
*/
public runCycle = (): void => {
Object.keys(this.startDimensions).forEach(
(key) => (this.startDimensions[key] -= 1)
);
Object.keys(this.endDimensions).forEach(
(key) => (this.endDimensions[key] += 1)
);
//public cubes:
const cycleCubes: Map<string, boolean> = new Map<string, boolean>();
for (let w = this.startDimensions.w; w <= this.endDimensions.z; w++)
for (let z = this.startDimensions.z; z <= this.endDimensions.z; z++)
for (let y = this.startDimensions.y; y <= this.endDimensions.y; y++)
for (let x = this.startDimensions.x; x <= this.endDimensions.x; x++) {
const currentCube = new Point4D(x, y, z, w);
if (!cycleCubes.has(currentCube.toString()))
cycleCubes.set(currentCube.toString(), false);
const onAround = this.occupiedAround(currentCube);
if (this.cubes.get(currentCube.toString())) {
cycleCubes.set(
currentCube.toString(),
onAround > 1 && onAround < 4
);
} else cycleCubes.set(currentCube.toString(), onAround == 3);
}
this.cubes = cycleCubes;
};
}
La intuición se confirma y las funciones devuelven el resultado esperado al invocarlas:
const space = new ConwayCubesSpace4D("./initialState.txt");
for (let cycle = 0; cycle < 6; cycle++) {
space.runCycle();
// console.log(space.renderSpace());
}
console.log(
"Answer:",
Array.from(space.cubes.values()).filter((state) => state).length
);
Sin embargo no quedo satisfecho con los tiempos de ejecución. La segunda parte tarda unos 7 segundos en mi portátil, por lo que creo que seguiré dándole una vuelta y actualizaré si logro una mejora aceptable.
Actualización
He mejorado el código utilizando Sets en vez de Maps, que realmente no tenían mucho sentido. La segunda parte se ejecuta ahora en 1.7 segundos, pero aún creo que se puede mejorar.