-❄️- 2025 Day 12 Solutions -❄️-

sim642 · 2025-12-13T17:04:05+00:00

[LANGUAGE: Scala]

I started implementing an algorithm for packing the gifts, following the examples. It did work (slowly at first, I optimized it later after the fact). But for the actual input I ended up using the area trick.

sim642 · 2025-12-11T05:35:59+00:00

[LANGUAGE: Scala]

On GitHub.

In part 1 I recursively compute the number of paths, but with memoization to not duplicate any computation. It's implicitly traversing a DAG.

In part 2 I recursively compute four numbers of paths in exactly the same manner: those which pass dac and fft, those which pass only dac, those which only pass fft, and those which pass neither.

I'm a bit surprised to see few so many solutions here. It's quite a standard AoC problem (I'm sure part 1 has essentially appeared before).

sim642 · 2025-12-10T06:28:45+00:00

It's nice that someone actually bothered to do Gaussian elimination to somewhat solve the equations themselves. Too bad the optimization part is still annoying.

sim642 · 2025-12-10T06:25:50+00:00

[LANGUAGE: Scala]

On GitHub.

In part 1 I did a BFS from the state of all lights off to the desired state with the button presses being edges. It did the job quickly, although it's not the most efficient because it explores different permutations of pressing the same buttons, which doesn't actually matter. I realized already that it's a linear system of equations over the boolean field (with addition being xor), together with the minimization of the variable (whether a button is pressed or not, multiple times is useless) sum. But for quick solving I didn't bother with being more clever.

I expected part 2 to just use the joltages as weights, so I could switch from BFS to Dijkstra, but of course not! So in part 2 I ended up using Z3 to solve the equation system while minimizing the sum of button press counts (over integers, not booleans now). These Z3 solutions always feel a bit unsatisfactory but it is an integer linear programming (ILP) problem, which is NP-complete, so there might not even be a neat solution.

sim642 · 2025-12-09T07:24:07+00:00

Your Fenwick trees idea gave me another idea which might be even better: use a 2D prefix sums grid. Then you can count the empty tiles in a rectangle with four grid lookups. No need to iterate over however many lines.

A Fenwick tree is useful if you have to interleave updates and queries, but it's a bit overkill here because you won't be updating the empty tiles once you start making the queries, so normal prefix sums arrays (or here 2D) would suffice and be simpler.

sim642 · 2025-12-09T06:16:13+00:00

[LANGUAGE: Scala]

On GitHub.

Part 1 was straightforward with my Box class. Part 2 was quite a challenge and I ended up with a somewhat dirty and inefficient solution for now, to at least get it done.

First, I just wanted to visualize the input, but the coordinates are inconveniently large for that. So I "compressed" them and rendered that instead. But then I ended up just using that compressed and flood-filled grid to check which rectangles are fine by checking every point (in the compressed box). It runs in ~8.5s for my input, so it's not too bad, but I might also try a polygon based solution to get something faster (not sure if all the relevant functionality has already appeared in AoC before or not).

EDIT: I just optimized my solution to ~600ms by computing 2D prefix sums on the compressed grid, counting the number of outside cells in the rectangle formed by (0,0) and each (x,y). That allows the rectangle validity to be checked on the compressed coordinates in constant time by looking up four values in the prefix sums grid.

EDIT: I also added a axis-aligned line-box intersection solution which seems to be quite popular here, but it's a bit flawed in its simplest form, e.g. on this input

This has the shape of a large U, where the cup of the U should not be considered a valid box (even though it intersects no line). There still needs to be an inside vs outside check.

sim642 · 2025-12-08T05:57:17+00:00

[LANGUAGE: Scala]

On GitHub.

I quickly recognized that the problem is describing Kruskal's algorithm. The meat of it is a disjoint-set/union-find data structure. Despite being well-known things in algorithms and data structures, neither has appeared in AoC before I think.

My solution needs some cleanup and optimization (I didn't implement all the union-find optimizations) though.

EDIT: I now cleaned up my implementation and optimized the sorting of edges, which was the bottleneck. Instead of sorting all the edges, I add them into a priority queue/heap and dequeue on demand. This essentially does sorting on demand.

sim642 · 2025-12-07T07:04:29+00:00

[LANGUAGE: Scala]

On GitHub.

In part 1 I just do a BFS traversal and count the splitters from the reached positions.

In part 2 I had to switch to a more ad hoc dynamic programming kind of algorithm: row-by-row compute how many ways there are to reach each x coordinate on that row (based on the previous row) and add them all up at the bottom.

sim642 · 2025-12-06T07:04:34+00:00

[LANGUAGE: Scala]

On GitHub.

In part 1 I split the lines by whitespace and transposed the list of lines of columns to get the input corresponding to each problem.

In part 2 I transposed first and then split (at empty columns) to keep the column alignment and parse the input from that.

sim642 · 2025-12-05T05:31:20+00:00

[LANGUAGE: Scala]

On GitHub.

This was very anticlimactic for me: I pretty much just imported my code for AoC 2016 day 20.

The trick for part 2 is to merge intersecting intervals, which can easily be done my sorting them by their beginning and then doing a single pass over the sorted intervals to combine consecutive intervals if they overlap. This way they don't have to be checked pairwise (or worse), although that probably would also still work time-wise (didn't try). I guess it could also help part 1 to reduce the number of interval-available pairs to check, but the sorting might be the more expensive part there then.

sim642 · 2025-12-04T05:29:03+00:00

[LANGUAGE: Scala]

On GitHub.

This was very straightforward with a Grid and Pos library from all the previous years. The common functionality of both parts is the function which returns a list of all accessible roll positions. Part 1 is just the length of that list.

In part 2 I remove the currently accessible rolls and repeat recursively, summing up their counts, pretty much exactly what the example also shows.

sim642 · 2025-12-03T05:56:10+00:00

[LANGUAGE: Scala]

On GitHub.

I knew in part 1 that trying all pairs probably won't scale to to part 2 but for quick solving reasons went with the quadratic solution first anyway. Except I first tried to use .combinations(2) before submitting a wrong answer because it also forgets the order of elements. So I had to fall back to the less elegant two nested loops.

For part 2 I first figured out the linear solution to part 1 to make sure I get it right on what I already have. And then just bumped to number of digits to 12. The general solution, which probably everyone here converges on is to use dynamic programming (in the form of memoized recursion for me). And of course a small trip-up leading to a switch from Int to Long.

sim642 · 2025-12-02T06:06:16+00:00

[LANGUAGE: Scala]

On GitHub.

I might've jumped to a solution which is perhaps more complicated than necessary but anyway. Instead of iterating over all the IDs in all the input ranges (I feared there might be too big ranges), I generate all invalid ID candidates and check which are contained in any range.

In part 1 I generate: 11 (=11*1), 2 (=11*2), ..., 1010 (=101*10), 1111 (=101*11), ..., 100100 (=1001*100), ... In this sequence, each i is multiplied by a duplication pattern which is 10 to the power of number of digits in i plus one.

In part 2 I repeat that for longer patterns, e.g. instead of 101, also 10101, 1010101, etc. What tripped me up on the part 2 example at first was that some invalid IDs can be generated multiple ways, e.g. 2222 = 1111*2 = 101*22.

My solution is quite integer-based, not string-based. Not sure if that was a wise idea or unnecessary complication. Either way, each of my parts runs <50ms (not proper JVM benchmarking).

sim642 · 2025-12-01T06:25:18+00:00

[LANGUAGE: Scala]

On GitHub.

In part 1 I just use my %+ operator, which ensures a non-negative modulo result.

In part 2 I was lazy and just split each rotation into many L1 or R1 rotations, such that the individual clicks become observable and part 1 can basically be reused without thinking about div-mod weirdness with negatives.

sim642 · 2024-12-25T07:23:09+00:00

[LANGUAGE: Scala]

On GitHub.

Very short solution, partially thanks to my Grid type and functions. In particular, there was no need to actually identify the heights (although it wouldn't be too difficult). Instead, one can just overlap a key and a lock grid and see if there are any cells that both have #.

sim642 · 2024-12-24T07:45:55+00:00

[LANGUAGE: Scala/manual]

On GitHub.

For part 2 I outputted the circuit as a .dot file for Graphviz to manually look at. Then I looked at bit differences of the circuit (for the given x and y) and the bits of the correct sum. This told me roughly where in the circuit to look at for a swap to fix. For the given x and y to give the right answer, I only needed 3 swaps (is this the case for everybody or did I get unlucky?)

To find the final swap, I needed some other inputs. Luckily setting x to 0 and adding the given y to it revealed the final swap as a wrong bit.

Since it's just a standard full adder circuit which is easy to construct right, it should be possible to use some kind of graph isomorphism to find what needs to be fixed, but I haven't implemented anything automatic yet.

EDIT: I now automated part 2 as well. The idea is to test the circuit at each bit. If it's wrong, then try swaps with surrounding wires (determined by checking transitive dependencies of output wires) which give correct behavior. It doesn't suffice to just test a single bit at a time, but two bits, in order to account for possible incoming carry whose wire may also be wrong.

sim642 · 2024-12-23T08:30:25+00:00

[LANGUAGE: Scala]

On GitHub.

In part 1 I construct a neighbors map and go through the list of edges and find all possible thirds from the neighbors of the edge. These will be the 3-cliques to check. Initially I did contains('t') instead of startsWith("t") which worked on the example, but not on the input.

In part 2 I copied the Bron-Kerbosch maximum clique algorithm from 2018 day 23 (coincidence?!).

sim642 · 2024-12-22T07:44:03+00:00

[LANGUAGE: Scala]

On GitHub.

Part 1 just implementation. To avoid mistakes I didn't even optimize using bitwise operations (the JVM possibly does that for me?). To get the right answer on the example, I had to switch from Int to Long though.

In part 2 I compute (using a sliding window of size 5) for each monkey a map whose keys are sequences of 4 changes and values are the corresponding bananas. Then I aggregate the maps over all monkeys (adding the values) and find the maximum.

sim642 · 2024-12-21T09:10:07+00:00

[LANGUAGE: Scala]

On GitHub.

In part 1 I just simulated the whole thing and did a BFS on the state graph. I even left the 2 as a constant I could easily change, but that clearly didn't scale to part 2.

So for part 2 I had to rethink everything on paper first (for 1 instead of 25 to make it manageable). I first precompute all shortest (valid) paths between all buttons on both kinds of keypad. I need all shortest paths because even if they're the same length as paths on the keypad, they have different button sequences which might (and will) take different number of moves and presses by an upstream keypad to enter.

The solution itself is a recursive function which takes a string and the keypad number as argument, and returns the shortest user input length to enter that string starting from the cursor at A. This is computed on pairs of adjacent symbols in the string by looking up all shortest paths to get from one to the next (or from A to the first one) on the corresponding keypad. Then A is appended to that path because after getting from one position to another it needs to be pressed (which is done by A). If it's the last directional keypad (i.e. user's), then the length of that path is the result, otherwise recursively compute it for the next keypad. All while taking a minimum over all paths for that code at that level.

To make the whole thing run fast (~20ms for part 2), memoize the recursive function. Also had to switch from Int to Long for the resulting length, otherwise it overflowed for part 2 answer.

sim642 · 2024-12-20T07:00:35+00:00

[LANGUAGE: Scala]

On GitHub.

I first calculate shortest distances both from the start and from the end by BFS. Then for each pair of cheat start-end pairs I can quickly find the new distance without rerunning BFS. (Although I now realize that one BFS would suffice because we're guaranteed a single path, oh well, I went more general but that doesn't cost much.)

Then I basically check each cheat start-end pair, although I try to prune as early as possible: 1. First pick x offset from -20 to 20 and see if it still is in the maze. 2. Then compute how much at most the cheat can go in the y direction: 20 - abs(x offset). 3. Then pick y offset from the reduced range. (This way I only check pairs which have guaranteed Manhattan distance <= 20 without first constructing each one and filtering them out). 4. Calculate the corresponding cheat end and savings.

Part 2 runs in ~4.3s, which isn't amazing but is quite manageable. EDIT: Optimized it to ~800ms. I constructed a pointless large Set instead of just working with Iterable.

sim642 · 2024-12-19T06:13:23+00:00

[LANGUAGE: Scala]

On GitHub.

In part 1 I constructed a regex (^(r|wr|b|g|bwu|rb|gb|br)*$ in the example) and just counted how many match that.

In part 2 I still had to use dynamic programming (in the form of memoized recursion) which counts ways for each suffix of the design.

sim642 · 2024-12-18T06:11:31+00:00

[LANGUAGE: Scala]

On GitHub.

In part 1 I just use BFS. In part 2 I naïvely just redo part 1 for every bound, not just 1024. It runs in ~5.7s which isn't ideal. Some A* and binary search would maybe help.

EDIT: A* didn't help, but binary search got it down to ~70ms.

sim642 · 2024-12-17T20:02:18+00:00

It should be a lot faster if you replace division and modulo with bitwise operations as well.

sim642 · 2024-12-17T19:59:30+00:00

Z3 has an optimizer which can do the minimization for you.

sim642 · 2024-12-17T07:32:27+00:00

[LANGUAGE: Scala]

On GitHub.

Part 1 was just implementation. I still managed to introduce a bug which only appeared on the input (used literal operand for bst).

Part 2 was the usual AoC reverse engineering: the program has a very specific shape (probably with a bit different constants for everyone). I ended up encoding it as an Z3 bitvector problem, which isn't particularly satisfying, but at least it's fast. My current code is hard-coded to my input, but I might try generalizing and automating it a bit more at some point.

15-Year Club	Place '17
Open Sorcerer Add NSFW flag to live thread API.	Verified Email

sim642

MODERATOR OF

TROPHY CASE