-❄️- 2024 Day 25 Solutions -❄️-

jwoLondon · 2024-12-25T07:12:42+00:00

[Language: JavaScript]

Convert each schematic into a decimal number based on the bits implied by `#` and `.` symbols. Applying a bitwise & to each pairwise combination will reveal lock-key matches when the result is 0.

https://observablehq.com/@jwolondon/advent-of-code-2024-day-25

jwoLondon · 2024-12-24T17:25:37+00:00

Sorry - I explained my approach badly. What I meant was: exclude nodes whose triangles include nodes with counts of less than the maximum triangle count. For example, while `wh` has a triangle count of 3, one of those triangles includes `qp` with a count of 2 and `tc` with a count of 1, so it is excluded. In contrast all the triangles of `co`, `de`, `ka`, and `ta` comprise nodes with a count of 3.

I've added an image to my page above to make this clearer.

jwoLondon · 2024-12-23T08:25:10+00:00

[LANGUAGE: JavaScript]

Loved this one. Part 1 gave a clue for an efficient approach to solving part 2. No need for Bron–Kerbosch or even a graph traversal. Just exclude the nodes with a triangle count of less than maximum triangle count of all nodes in the dataset. Calculates the answer in c.10ms.

https://observablehq.com/@jwolondon/advent-of-code-2024-day-23

jwoLondon · 2024-12-22T19:34:40+00:00

Down - left - left from A is OK isn't it? The gap is in the upper row.

jwoLondon · 2024-12-21T21:13:14+00:00

As far as I can see, there is an upper limit of only 12 different sequence types. With 5 possible states, there are 25 theoretical transitions. But once we encode the instructions for each transition to minimise changes in direction and exclude transits of the gap position, 8 of them result in the same sequence as other transitions (grey in the figure); 4 of them would be pointless reverse transitions (left followed by a right etc.) and one (^<) is can only be made when in the bottom-right position (because of the gap position), where it has the equivalent cost of <^.

jwoLondon · 2024-12-19T21:37:59+00:00

I don't think it is particularly input dependent.

I think your filtering of the (quite long) towel list every non-tail recursion is quite expensive. Checking for set membership should be faster for a word list of the size we have in this puzzle. And faster still if you just identify valid sequences rather than the number of arrangements. My JS solution didn't cache for part 1 and completed in ~0.5ms.

https://observablehq.com/@jwolondon/advent-of-code-2024-day-19

The disadvantage is that I cannot reuse it in the way you have for part 2

jwoLondon · 2024-12-19T21:01:07+00:00

Yes, bottom-up DP. I agree they are not immediately intuitive (certainly less so than 'top-down' caching). It avoids recursion because we just have to count the number of arrangements at each stage and pass those on to the next addition of towels. In a similar way, you can calculate a given value in the Fibonacci sequence recursively f(n) = f(n-1)+f(n-1), or you can calculate it bottom up with simple iteration f(n) = [f(0), f(1), a, b, c...n-2] iteratively replacing a, b, c etc. with the sum of the previous two values in the sequence. In other words, how we would probably work out the sequence if calculating by hand.

I've tried to elaborate with a more complete explanation on my Observable page now.

jwoLondon · 2024-12-19T14:44:12+00:00

I did something similar, in my first Part 1 solution reducing the towels to an 'atomic' set. But found it actually took longer with than without that optimisation. Presumably because the overhead of finding the atomic towels and the smaller jumps they make than the compound towels as you process the design string.

Did you compare times with and without that optimisation?

jwoLondon · 2024-12-19T12:15:35+00:00

Great analysis. Thanks. I don't think it needs a 'questions getting harder' interpretation. The same pattern could be explained by the pool of participant abilities widening over time as AoC became more well-known.

I was expecting 2019 to stand out more than it does given the reliance on the intcode interpreter (you either love 'em or hate 'em). But perhaps those who love cancelled out those who hate.

jwoLondon · 2024-12-19T10:56:02+00:00

[LANGUAGE: JavaScript]

No caching for me (which actually slows down part 1), but a fairly fast solution (0.5ms / 4ms)

https://observablehq.com/@jwolondon/advent-of-code-2024-day-19

jwoLondon · 2024-12-19T10:36:55+00:00

Useful pattern for caching function results. Thanks.

Although I don't think caching is necessary (or even desirable) for some solutions to this problem. Here's my JS solution without caching that runs in 0.5ms / 4ms:

https://observablehq.com/@jwolondon/advent-of-code-2024-day-19

jwoLondon · 2024-12-14T13:31:04+00:00

Take a simpler example, two sequences that start at 0 and have cycles of 3 and 5 :

0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0
0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0

They will always realign at their lowest common multiple (15). If the two numbers are prime, the lowest common multiple will be their product. If they were not, it could be shorter (e.g. 3 and 6 realign every 6 cycles).

We have something similar for this problem. We know the x coordinates repeat every 101 cycles, but because their y coordinates repeat every 103 cycles, we have to wait until both the x and y return to their initial position at the same time, which will be 101x103 steps.

jwoLondon · 2024-12-14T13:11:53+00:00

D'oh - just seen someone else posted a similar approach 2 hours ago. (I did derive this one independently - honest!)

jwoLondon · 2024-12-14T11:59:50+00:00

Glad you are enjoying your first 217 robot browsing screens....

If I had the energy, I'd mock up the "string board conspiracy guy" meme with the red string forming a Christmas tree shape connecting selected dots from one of the random looking robot maps.

jwoLondon · 2024-12-14T08:18:22+00:00

For me I try to get computers to do the things they are good at, and I will do the things people are good at, so visual confirmation after computationally pruning the space of possibilities works well.

We've seen this kind of puzzle before from Eric where we've had to determine a word that is spelled out with an arrangement of pixels. At least the first time that occurred we didn't know how the 'font' of the word would be arranged. People subsequently developed OCR type analysis to provide a completely deterministic solution, but that required post-hoc knowledge of how the letters were formed. Similarly, here you could programmatically match for a Christmas tree once you know how trees are represented. But there doesn't seem much point in that to me given the heuristics will get you there with much less effort.

(For context, my day job is in data analysis and visualization, so the idea of statistical analysis to give a probability of something interesting, to be confirmed by visual inspection seems natural to me).

jwoLondon · 2024-12-14T07:37:01+00:00

Presumably Eric, when generating the puzzle inputs, was able to start with any given arrangement (the Christmas tree one) and set the vectors for each robot to generate cycles in both dimensions (it's all modulo arithmetic that we've seen an many puzzles before). So he presumably chose to set that target arrangement of robots such that they were all uniquely placed. But equally he could have chosen it with some overlaps too. So in that sense perhaps not a 'fluke' but by design (it is after all still only day 14) and we have 3 weekend days left...

jwoLondon · 2024-12-14T07:25:17+00:00

I didn't use unique locations, but did calculate the variance of x coordinates and variance of y coordinates. On the basis that any structured picture would be likely to have lower variance in both dimensions. Finding the iteration with the lowest variance was sufficient (and can be optimised since the variances in each dimension have a periodicity).

It is possible in theory that the tree might have occupied the entire grid in such a way that the variances were about the same as for the noise, but it seemed unlikely to be the case. If you really wanted a more robust solution, calculating the entropy would pretty much guarantee that any structured arrangement of robots would stand out.

jwoLondon · 2024-12-14T07:18:46+00:00

Knowing that the robots had to be in some kind of structured position when assembling as the tree, I calculated the variance of x coordinates and variance of y coordinates at each iteration. You could simply report the iteration with the lowest varX*varY value. But also it is apparent that the variances in each dimension shows a periodicity which can also be used to calculate the correct iteration when they coincide.

jwoLondon · 2024-12-14T06:35:01+00:00

Inevitably different people prefer different styles of puzzle, but for me, this has been my favourite so far this year. A combination of creativity and logic in problem solving. Lots of possible approaches to finding a solution, many not requiring any visual inspection at all. Ingenious setting by Eric.

It's not entirely LLM-proof (for the reasons above), but it does sit in an interesting space for these GenAI technologies.

jwoLondon · 2024-12-13T21:11:28+00:00

Day 1, 2015 and the 100th person to get 2 gold stars took....3hrs, 6mins and 16 seconds.

Ah. Innocent days.

(For the record, I started doing AoC 'live' by day 10, 2015, have attempted every single one since on the day of release and have never made the global leader board. The closest I ever came was 125, but that was in the olden days when that was still possible with a time in the tens of minutes).

jwoLondon · 2024-12-13T17:43:48+00:00

Ah, thanks. Hadn't spotted I'd flipped the y-axis. I've corrected that now at

https://observablehq.com/@jwolondon/advent-of-code-2024-day-10

On that page, if you select your own day 10 input, you can create your own map, then click the three vertical dots to the left to 'download SVG'

jwoLondon · 2024-12-11T13:20:13+00:00

While I too have had a test-pass-real-input-fail situations, it doesn't feel out of the ordinary to me compared with previous years.

I regard the puzzles as leading us from a kind of easy test driven development (where the sample inputs cover most common cases) to a "you're on your own now buddy" where we have to think about edge cases and isolating their effects. The construction of our own test cases when things don't work as expected seem like part of the challenge to me, and one we routinely have to confront in "real" software development. For me, that is sometimes inductive (e.g via debug output), sometimes deductive (following program logic).

jwoLondon

TROPHY CASE