Advent of Code 2025, part 2
My journey through AoC 2025, days 7-12
14 min read
This blog post is part 2 of the mini-series dedicated to the Advent of Code 2025. The first part can be found in the previous post.
I felt like the difficulty of the puzzles increased a lot the last couple of days š . But letās start with day 7.
Day 7
On this day, we had to trace the beam and practice both BFS and DFS in action š
For the parsing it was incredibly easy - just parse the 2D grid as is:
const START = "S";
const SPLITTER = "^";
type Position = {
row: number;
col: number;
};
type Parsed = {
grid: string[][];
start: Position;
};
function parse(input: string): Parsed {
const grid = input.split("\n").map((line) => line.split(""));
const startCol = grid[0].indexOf(START);
return {
grid,
start: { row: 0, col: startCol },
};
}Thereās one assumption here: that a starting point would always be in the first row. I looked over the example and the actual input and it was the case in both of them. Therefore I simplified the code a little bit š
For the actual first part Iāve decided to go with the BFS because it felt more natural to me - basically, I was simulating the beams just as it was going through the grid.
function countBeamSplits({ grid, start }: Parsed) {
let cnt = 0;
let beams = [start];
for (let i = 1; i < grid.length; ++i) {
const nextBeams: Position[] = [];
for (const { row, col } of beams) {
const nextRow = row + 1;
if (grid[row][col] === SPLITTER) {
nextBeams.push({ row: nextRow, col: col - 1 });
nextBeams.push({ row: nextRow, col: col + 1 });
cnt++;
} else {
nextBeams.push({ row: nextRow, col });
}
}
beams = [];
for (const { row, col } of nextBeams) {
const foundIdx = beams.findIndex((b) => b.row === row && b.col === col);
if (foundIdx === -1) {
beams.push({ row, col });
}
}
}
return cnt;
}
console.log("part 1", countBeamSplits(parse(input)));Thereās something that can be improved here - Iām deduplicating the nextBeams
collection by continuously running findIndex - which is inefficient and leads
to the O(n^2) runtime. But the solution ran pretty quickly even on large input
so Iāve decided to leave it as is.
For the second part we need to count all of the ātimelinesā of all the beams, essentially the number of ways from the start all the way down.
Iāve used DFS this time, but with memoization, because without it, I would need to explore trillions and trillions of paths, and it would take a lot of time.
function countTimelines({ grid, start }: Parsed) {
const counts = new Map<string, number>();
function dfs({ row, col }: Position) {
if (row === grid.length) {
return 1;
}
const key = `${row}-${col}`;
if (counts.has(key)) {
return counts.get(key)!;
}
let result: number;
const nextRow = row + 1;
if (grid[row][col] === SPLITTER) {
result =
dfs({ row: nextRow, col: col - 1 }) +
dfs({ row: nextRow, col: col + 1 });
} else {
result = dfs({ row: nextRow, col });
}
counts.set(key, result);
return result;
}
return dfs(start);
}
console.log("part 2", countTimelines(parse(input)));Day 8
Puzzle for the next day was awesome - and it was even in 3D!, hereās a parsing and type definition for it:
type Position = {
x: number;
y: number;
z: number;
};
function parse(input: string): Position[] {
return input.split("\n").map((line) => {
const [x, y, z] = line.split(",").map(Number);
return { x, y, z };
});
}Figuring out a distance between the points is a little bit involved, but Iāve always struggled with math š
function distance(p: Position, q: Position) {
return Math.sqrt(
Math.pow(p.x - q.x, 2) + Math.pow(p.y - q.y, 2) + Math.pow(p.z - q.z, 2),
);
}And the most difficult part was the solution itself (this time I solved it all in one function). I spent a lot of time figuring out how to represent networks and how to merge them.
function first<K, V>(map: Map<K, V>): V {
return map.values().next().value;
}
function solution(input: string, iterations: number) {
const boxes = parse(input);
const n = boxes.length;
const minDistances: { boxes: [number, number]; distance: number }[] = [];
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; ++j) {
minDistances.push({
boxes: [i, j],
distance: distance(boxes[i], boxes[j]),
});
}
}
minDistances.sort((a, b) => b.distance - a.distance);
let id = 0;
const powered = new Array(n).fill(false);
const networks = new Map<number, Set<number>>();
const boxToNetwork = new Map<number, number>();
let box1 = -1,
box2 = -1;
while (
iterations > 0 ||
networks.size > 1 ||
first(networks).size !== boxes.length
) {
const min = minDistances.pop()!;
[box1, box2] = min.boxes;
if (powered[box1] && powered[box2]) {
const network1 = boxToNetwork.get(box1)!;
const network2 = boxToNetwork.get(box2)!;
if (network1 !== network2) {
for (const pos2 of networks.get(network2)!) {
networks.get(network1)!.add(pos2);
boxToNetwork.set(pos2, network1);
}
networks.delete(network2);
}
} else if (boxToNetwork.has(box1) || boxToNetwork.has(box2)) {
powered[box1] = true;
powered[box2] = true;
const networkId = (boxToNetwork.get(box1) ?? boxToNetwork.get(box2))!;
networks.get(networkId)!.add(box1);
networks.get(networkId)!.add(box2);
boxToNetwork.set(box1, networkId);
boxToNetwork.set(box2, networkId);
} else {
powered[box1] = true;
powered[box2] = true;
const networkId = id++;
networks.set(networkId, new Set([box1, box2]));
boxToNetwork.set(box1, networkId);
boxToNetwork.set(box2, networkId);
}
iterations--;
if (iterations === 0) {
const networksSnapshot = Array.from(networks.values());
networksSnapshot.sort((a, b) => b.size - a.size);
let part1 = 1;
for (let i = 0; i < 3; ++i) {
part1 *= networksSnapshot[i].size;
}
console.log("part 1", part1);
}
}
console.log("part 2", boxes[box1].x * boxes[box2].x);
}
solution(input, iterations);And this solution while not looking pretty, works surprisingly fast, and I started wondering, is there a better approach to this problem? And turns out - there is!
In hindsight, this is essentially Kruskalās algorithm for building a minimum spanning forest - except I reimplemented the āunionā logic manually instead of using DSU.
I actually wrote about it in the Maze Generation Algorithms blog post.
Unfortunately, I couldnāt see that this data structure is perfect for this problem. I think that I come back later to this problem to solve it āproperlyā. Additionally, it will be a great practice implementing this data structure.
Day 9
Day 9 and day 10 were the hardest ones for me - I solved the first part really quickly. But I just couldnāt figure out the second part.
type Point = [number, number];
function parse(input: string): Point[] {
return input.split("\n").map((line) => {
const [x, y] = line.split(",").map(Number);
return [x, y];
});
}
function area([x1, y1]: Point, [x2, y2]: Point): number {
const width = Math.abs(x1 - x2) + 1;
const height = Math.abs(y1 - y2) + 1;
return width * height;
}
function findMaxArea(input: string) {
const points = parse(input);
let maxArea = -Infinity;
for (let i = 0; i < points.length - 1; ++i) {
for (let j = i + 1; j < points.length; ++j) {
maxArea = Math.max(maxArea, area(points[i], points[j]));
}
}
return maxArea;
}
console.log("part 1", findMaxArea(input));In the example above the code is pretty simple - just looking at max areas of all possible pairs of points. But the second part adds a simple condition that makes it so much harder - now we can only look for rectangles (areas between pairs of points) inside of some polygon.
Thanks to my colleague we were able to write a hacky solution based on a lot of math around intersections of lines idea that we had.
By researching later I found that this problem is pretty common in game development, and the simple way to solve it is ray casting. Essentially, when we cast a ray from some point we can count the number of intersections with the polygon, and if itās odd, then the point is inside, if there are no intersections or the number is even - point is outside of the polygon. Well, this is day #2 that I need to come back to later.
Day 10
I liked this day a lot! Iām pretty proud of my solution for the part 1, even though I wasnāt able to solve the part 2 myself.
type LightState = {
lights: number;
presses: number;
};
class Machine {
requiredLights: number;
lightButtons: number[];
constructor(requiredLights: number, lightButtons: number[]) {
this.requiredLights = requiredLights;
this.lightButtons = lightButtons;
}
minLightButtonPresses() {
const best = new Map<number, number>();
const queue = new PriorityQueue<LightState>(
(a, b) => a.presses - b.presses,
[{ lights: 0, presses: 0 }],
);
while (!queue.isEmpty()) {
const { lights, presses } = queue.dequeue()!;
if (lights === this.requiredLights) return presses;
if (best.has(lights) && best.get(lights)! <= presses) continue;
best.set(lights, presses);
for (const button of this.lightButtons) {
queue.enqueue({
lights: lights ^ button,
presses: presses + 1,
});
}
}
return -1;
}
}
function parse(input: string): Machine[] {
const lines = input.split("\n");
const machines: Machine[] = [];
for (const line of lines) {
const parts = line.split(" ");
let requiredLights = 0;
const lightsString = parts[0].substring(1, parts[0].length - 1);
for (let i = 0; i < lightsString.length; ++i) {
if (lightsString[i] === "#") {
requiredLights |= 1 << i;
}
}
const lightButtons: number[] = [];
for (let i = 1; i < parts.length; ++i) {
const part = parts[i];
if (part.startsWith("(") && part.endsWith(")")) {
let lightButton = 0;
part
.substring(1, part.length - 1)
.split(",")
.map(Number)
.forEach((idx) => {
lightButton |= 1 << idx;
});
lightButtons.push(lightButton);
}
}
machines.push(new Machine(requiredLights, lightButtons));
}
return machines;
}
function countMinLightButtonPresses(machines: Machine[]) {
return machines.reduce(
(prev, curr) => prev + curr.minLightButtonPresses(),
0,
);
}
console.log("part 1", countMinLightButtonPresses(parse(input)));Iāve implemented Dijkstraās algorithm here. And Iāve also utilized the bit representation of the lights state here. Adding lights to the requirements became the bit shift and OR. Each button press became XOR and checking for the requirements is just a single comparison. Neat!
I thought that my approach would work for the part 2, but thereās no chance it would have completed in a thousands of years š„²
Turns out this is a math problem: each joltage requirement and button presses becomes a equation. And we need to solve the system of these equations to get an answer. I went on Reddit in the hopes of finding the solution there - and I did. But unfortunately, a lot of folks used python and some library called Z3. And while it gives the correct answer, looks like thereās a lot of ground in math I need to cover in order to understand it.
This makes the day #3 that I need to come back to.
Day 11
Thankfully day 11 was a breeze - Iāve managed to complete it pretty quickly with the help of my trusty DFS once again.
Hereās how I parsed the graph (Iāve added a couple of command-line args for part 2):
const start = argv[3] || "you";
const required1 = argv[4];
const required2 = argv[5];
const input = (await readFile(filename, "utf-8")).trim();
const OUT = "out";
function parse(input: string) {
const graph = new Map<string, string[]>();
for (const line of input.split("\n")) {
const parts = line.split(" ");
graph.set(parts[0].substring(0, parts[0].length - 1), parts.slice(1));
}
return graph;
}The DFS is essentially the same as in Day 7 part 2:
function countPaths(input: string) {
const graph = parse(input);
const memo = new Map<string, number>();
function dfs(curr: string): number {
if (curr === OUT) return 1;
if (memo.has(curr)) {
return memo.get(curr)!;
}
let total = 0;
for (const next of graph.get(curr)!) {
total += dfs(next);
}
memo.set(curr, total);
return total;
}
return dfs(start);
}
console.log("part 1", countPaths(input));But part 2 involves a little trick for caching:
function countPathsWithRequired(input: string) {
const graph = parse(input);
const memo = new Map<string, number>();
function dfs(curr: string, has1: boolean, has2: boolean): number {
if (curr === OUT) {
return Number(has1 && has2);
}
const key = `${curr}|${has1}|${has2}`;
if (memo.has(key)) return memo.get(key)!;
const next1 = has1 || curr === required1;
const next2 = has2 || curr === required2;
let total = 0;
for (const next of graph.get(curr)!) {
total += dfs(next, next1, next2);
}
memo.set(key, total);
return total;
}
return dfs(start, false, false);
}
console.log("part 2", countPathsWithRequired(input));I found out the hard way that trying to remember the whole path is pretty memory-intense. And checking the requirements in this array is inefficient as well - because we need to check every element in the array. Therefore Iām just storing two booleans in the params and memoizing based on them - this drastically improves memory usage and runtime performance.
Day 12
Day 12 was ā¦ something else. When I initially read it I was shocked, I didnāt even know how to approach it. But I did some brainstorming with my friends and just kept on unrolling the problem:
- parsing the elements and the regions
- doing a quick check for the total area needed
- generating rotations and flips of elements for all of the possible positions in a region
- transforming those positions into bitmasks for a quick overlap checks (turns out, you can do bitwise operations on BigInts in JS)
- implementing the core algorithm - backtracking placement of the elements
type Cell = {
row: number;
col: number;
};
type Region = {
width: number;
height: number;
counts: Map<number, number>;
};
function parse(input: string) {
const elements: Cell[][] = [];
const regions: Region[] = [];
const lines = input.split("\n\n");
for (const line of lines) {
if (line.match(/^\d:/)) {
const elementStr = line
.substring(3)
.split("\n")
.map((l) => l.split(""));
const element: Cell[] = [];
for (let row = 0; row < elementStr.length; ++row) {
for (let col = 0; col < elementStr[row].length; ++col) {
if (elementStr[row][col] === "#") {
element.push({ row, col });
}
}
}
elements.push(element);
} else {
for (const regionStr of line.split("\n")) {
const [size, required] = regionStr.split(": ");
const [width, height] = size.split("x").map(Number);
const counts = new Map<number, number>();
const presentCounts = required.split(" ").map(Number);
for (let i = 0; i < presentCounts.length; ++i) {
counts.set(i, presentCounts[i]);
}
regions.push({
width,
height,
counts,
});
}
}
}
return { elements, regions };
}
function rotate(element: Cell[]) {
const maxRow = Math.max(...element.map((c) => c.row));
return element.map(({ row, col }) => ({
row: col,
col: maxRow - row,
}));
}
function flipHorizontal(element: Cell[]) {
const minCol = Math.min(...element.map((c) => c.col));
const maxCol = Math.max(...element.map((c) => c.col));
return element.map(({ row, col }) => ({
row,
col: maxCol - (col - minCol),
}));
}
function generateRotations(element: Cell[]) {
const result: Cell[][] = [];
let current = element;
for (let r = 0; r < 4; ++r) {
result.push(current);
result.push(flipHorizontal(current));
current = rotate(current);
}
return result;
}
function generatePlacements({ width, height }: Region, element: Cell[]) {
const placements: bigint[] = [];
const maxRow = Math.max(...element.map((c) => c.row));
const maxCol = Math.max(...element.map((c) => c.col));
for (let row = 0; row + maxRow < height; ++row) {
for (let col = 0; col + maxCol < width; ++col) {
let mask = 0n;
for (const c of element) {
const id = BigInt((row + c.row) * width + (col + c.col));
mask |= 1n << id;
}
placements.push(mask);
}
}
return placements;
}
function isValidRegion(region: Region, elements: Cell[][]) {
console.log("checking: ", region.width + "x" + region.height, region.counts);
const regionSize = region.width * region.height;
let elementsSize = 0;
for (const [elementIdx, elementRequired] of region.counts) {
if (!elementRequired) continue;
const element = elements[elementIdx];
const elementSize = element.length;
elementsSize += elementSize * elementRequired;
}
if (regionSize < elementsSize) {
console.log("valid:", false);
return false;
}
const variants = new Map<number, Set<bigint>>();
for (const [elementIdx, elementRequired] of region.counts) {
if (!elementRequired) continue;
const element = elements[elementIdx];
const rotations = generateRotations(element);
const placements = new Set<bigint>();
for (const rotation of rotations) {
generatePlacements(region, rotation).forEach((placement) => {
placements.add(placement);
});
}
variants.set(elementIdx, placements);
}
const instances: { shape: number }[] = [];
for (const [shape, counts] of region.counts) {
for (let c = 0; c < counts; ++c) {
instances.push({ shape });
}
}
instances.sort((a, b) => elements[b.shape].length - elements[a.shape].length);
function backtrack(idx: number, occupied: bigint) {
if (idx === instances.length) return true;
const shape = instances[idx].shape;
const options = variants.get(shape)!;
for (const mask of options) {
if ((mask & occupied) !== 0n) continue;
if (backtrack(idx + 1, occupied | mask)) {
return true;
}
}
return false;
}
const valid = backtrack(0, 0n);
console.log("valid:", valid);
return valid;
}
function part1(input: string) {
const { elements, regions } = parse(input);
let count = 0;
for (const region of regions) {
if (isValidRegion(region, elements)) {
count++;
}
}
return count;
}
console.log("part 1", part1(input));After all of this code - it just worked first try! I couldnāt believe it!
This was probably the most complicated thing that I wrote in a long time - so many hard concepts crammed into a single practical task, thatās why I love Advent of Code!
I already have at least three days I want to revisit, and Iām sure Iāll learn even more the second time around.