Por fin hemos llegado al aeropuerto regional, justo a tiempo para coger el siguiente vuelo. De hecho nos sobra tiempo, ya que las salidas de todos los vuelos están retrasadas por problemas en el procesamiento de los equipajes. Y es normal, ya que los cambios recientes en cuestión de seguridad relativos a los contenidos admitidos en cada maleta son una absoluta locura.
Cada maleta, dependiendo de su color, puede contener otras maletas en cantidades específicas, y todos los equipajes deben cumplir con sus reglas, que serán nuestro juego de entrada del puzzle.
Como ejemplo de estas reglas tenemos la siguiente lista:
light red bags contain 1 bright white bag, 2 muted yellow bags. dark orange bags contain 3 bright white bags, 4 muted yellow bags. bright white bags contain 1 shiny gold bag. muted yellow bags contain 2 shiny gold bags, 9 faded blue bags. shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags. dark olive bags contain 3 faded blue bags, 4 dotted black bags. vibrant plum bags contain 5 faded blue bags, 6 dotted black bags. faded blue bags contain no other bags. dotted black bags contain no other bags.
Cada linea nos indica, para un color de maleta, que cantidades de otras maletas puede contener.
Parte 1 – ¿Donde puedo poner mi maleta?
En la primera parte del puzzle de hoy se nos pide resolver cuantas maletas diferentes pueden contener una de color shiny gold. En el ejemplo superior, este color puede estar contenido en una maleta bright white o también en una muted yellow. Pero estas dos, a su vez, pueden estar contenidas en maletas light red o dark orange. Por tanto, la respuesta al problema sería 4.
Para resolver esta cuestión debemos entrar de lleno en un terreno habitual en las diferentes ediciones del advent of code: los grafos. Sin entrar en teoría matemática, podemos representar las reglas como un grafo dirigido en el que los vértices o nodos representan un color de maleta y las aristas de uno a otro indican cual contiene a cual y, adicionalmente, en qué cantidad.
Para poder crear grafo voy a definir dos objetos que permitan representar los vértices (maletas) y las aristas (relación que indica qué maleta contiene a cual y en qué cantidad):
/**
* Representa la relacion entre una maleta y las que contiene, indicando la cantidad (arista)
*/
export interface IContainedBag {
quantity: number;
bag: IBagNode;
}
export class ContainedBag implements IContainedBag {
constructor(public quantity: number, public bag: BagNode) {}
}
/**
* Representa un nodo del grafo de maletas. Almacena su color, las maletas que contiene y
* adicionalmente, para poder recorrerlo, en las que está contenida
*/
export interface IBagNode {
color: string;
contains: IContainedBag[];
containedIn: IBagNode[];
containers: IBagNode[];
}
export class BagNode implements IBagNode {
constructor(
public color: string,
public containedIn: IBagNode[],
public contains: IContainedBag[]
) {}
}
Adicionalmente, para poder recorrer el grafo en cualquier dirección con facilidad incluyo la propiedad containedIn que permite recorrer las aristas en sentido contrario a la indicada por contains.
Una vez listo el soporte de nuestro grafo debemos alimentarlo a partir de la lista de reglas. Mi primera intención era la de utilizar una única expresión regular para parsear cada linea, pero no he sido capaz de hacerla funcionar como quería probablemente por las diferencias de funcionamiento con las expresiones regulares de C# a las que estoy acostumbrado, así que lo haré en dos pasos:
- Partir la regla en dos para separar la maleta contenedora (parte derecha) de las contenidas (parte izquierda)
- Partir la parte izquierda en tantas maletas diferentes y sus cantidades como haya, aplicando ahora si una expresión regular para parsear la cadena de cada una de ellas.
export class RulesFile {
private reContainedBags = /(?:(?<quantity>\d+) (?<color>\w+ \w+)) bags?/;
public read = (file: string): IBagNode[] => {
const rules = fs.readFileSync(file, "utf8").split("\r\n");
const bags: IBagNode[] = [];
for (const rule of rules) {
const parts = rule.split(" bags contain ");
const contained = parts[1].split(", ");
//si ya existe la maleta no creamos un nuevo nodo
const currentBag =
bags.find((bag) => bag.color == parts[0]) ??
new BagNode(parts[0], [], []);
if (contained[0] != "no other bags.") {
// puesto que la maleta cntenedora solo aparece una vez en la parte derecha de las definiciones
// podemos asignar directamente sus hijos
currentBag.contains = contained.map((containedBagDefinition) => {
const containedBagMatch = this.reContainedBags.exec(
containedBagDefinition
);
let containedBag = bags.find(
(b) => b.color == containedBagMatch.groups["color"]
);
if (containedBag) {
//Si esta maleta ya existe no creamos un nodo nuevo
containedBag.containedIn.push(currentBag);
} else {
containedBag = new BagNode(
containedBagMatch.groups["color"],
[currentBag],
[]
);
bags.push(containedBag);
}
return new ContainedBag(
parseInt(containedBagMatch.groups["quantity"]),
containedBag
);
});
bags.push(currentBag);
}
}
return bags;
};
}
Para cada linea del fichero de reglas crearemos nodos, aristas, o ambos:
- Maleta contenedora (parte derecha de la regla): buscamos el nodo de esa maleta o creamos uno si no existe
- Maletas contenidas (parte izquierda de la regla):
- Si no hay maletas contenidas hemos terminado con esta regla.
- Si las hay, para cada una de ellas buscamos el nodo de esa maleta. Si no existe creamos uno nuevo y en cualquier caso creamos una relación desde la maleta contenedora hasta la maleta contenida, guardando la cantidad de maletas en en dicha relación.
- Además, para poder recorrer el grafo fácilmente almacenamos la relación inversa, es decir, de maleta contenida a maleta contenedora
Una vez creado el grafo debemos localizar el vértice correspondiente a la maleta que nos solicitan y después obtener recursívamente las maletas contenedoras del mismo. Para ello voy a crear una propiedad containers en nuestro nodo BagNode:
/**
* Devuelve un array con todos los contenedores de esta maleta
*/
public get containers(): IBagNode[] {
return this.containedIn.flatMap((bag) => [bag].concat(bag.containers));
}
La función devuelve, para cada uno de los nodos guardados en la colección containedIn, tanto ese nodo como todos sus relacionados mediante una llamada recursiva. Para obtener un array plano utilizo la función Array.flatMap.
Ya tenemos todas las maletas que pueden contener la buscada, pero dada la naturaleza del grafo puede que tengamos elementos repetidos, y la pregunta nos solicita los diferentes. Al igual que hicimos el día anterior para eliminar duplicados en un array utilizo un Set. Su longitud será la respuesta buscada:
const origin = bags.find((bag) => bag.color == "shiny gold");
console.log("Answer:", new Set<BagNode>(...[origin.containers]).size);
Parte 2 – ¡¿Que me cuesta CUANTO el sobrepeso?!
Para resolver la segunda parte del puzzle debemos hallar cuantas maletas individuales en total se requieren según el conjunto de reglas, partiendo de nuevo desde nuestra maleta shiny gold. Así, en el ejemplo del principio dentro de la shiny gold deben ir 1 dark olive y 2 vibrant plum. La dark olive a su vez lleva 4 dotted black y 3 faded blue, y cada vibrant plum debe contener 5 faded black y 6 dotted blue. La respuesta es por tanto 1 + 1 * (4+3) + 2 + 2 * (5+6) = 1 + 7 + 2+ 22= 32 maletas.
En nuestro grafo dirigido esto significa recorrerlo desde el vértice origen siguiendo la dirección de las flechas de las aristas y teniendo en cuenta las cantidades asociadas a cada una de ellas. Utilizo de nuevo una función recursiva, esta vez sobre la colección contains, que nos llevará a recorrer todas las aristas hasta llegar a vértices que no tengan flechas salientes, es decir, maletas que no contengan a otras. Esta vez lo haré con la función Array.reduce para ir sumando las cantidades:
/**
* Devuelve el numero de maletas contenidas
*/
public get containedBags(): number {
return this.contains.reduce((acum, containedBag) => {
acum +=
containedBag.quantity +
containedBag.quantity * containedBag.bag.containedBags;
return acum;
}, 0);
}
Y así termina el séptimo día de este advent of code 2020, ¿que te ha parecido el puzzle de hoy?