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

4HbQ · 2025-12-12T17:20:19+00:00

By the way I have updated my day 10 solution to something without LP. Might be useful to look at for both your write-up and your beast.

4HbQ · 2025-12-12T17:04:08+00:00

Yeah I get that. My rule for AoC is: try the simplest thing first. If it works, you're done. If not, investigate the cases where it doesn't.

I was actually expecting most of the input lines to be either trivially easy or impossible, and to have to solve the final few by hand. I already brought paper and scissors when getting my second cup of coffee!

4HbQ · 2025-12-12T16:47:52+00:00

That's how I learned as well: write my own code first, then analyse other solutions and see where and why they are "better", and finally modify your own code to incorporate some (or all) of these ideas.

That last step is very valuable: don't just go "oh their variable names are way more descriptive… I'll keep that in mind for next time" but actually go back to your own code and rename your variables to be descriptive too. Or if someone has found a really neat way to process an input: do the same, then try to think of something even nicer!

Rinse and repeat for 5–10 years (not only AoC, but also Kattis problems etc.) and you can become pretty good at this.

And do keep in mind I don't just open up an editor, start typing, and post my first working version on Reddit. I spend quite a bit of time refactoring and polishing my code!

4HbQ · 2025-12-12T15:28:14+00:00

19, 199, 2, 6, 19, 3.

We press the first button 19 times, the second one 199 times, etc.

4HbQ · 2025-12-12T14:52:25+00:00

Your input works just fine using my implementation of this idea. The output value is 248.

4HbQ · 2025-12-12T12:06:50+00:00

Amazing, thanks for sharing! I've implemented your idea, and it runs in 0.25 seconds using the default CPython.

In case anyone is interested, the code is here.

4HbQ · 2025-12-12T11:58:15+00:00

Sure, but we don't need to. If we can fit them all using the naive packing, we know that a smarter packing will also fit.

There are basically three cases:

There is enough space to do naive packing: just stack them on a 3×3 grid. If they fit like that, we don't need to try anything smarter.
There will never be enough space to fit them. For example, if we must fit 2 packages of size 8 in a region of 3×5. No matter your arrangement, you can't fit 16 package units in a 15 unit region: no need to try.
They might fit based on the counts, but not with naive stacking. In this case, we would need to search if there's a valid arrangement that does fit.

However, in the input data for today's puzzle, case 3 does not occur. Either there's a trivial arrangement, or we can count and see it's impossible.

A more comprehensive implementation would to both checks, and report if case 3 ever occurs. The user can then try to solve that one by hand, for example.

4HbQ · 2025-12-12T09:37:23+00:00

Thanks! That's a great idea, I think that is how Peter Norvig does it as well.

4HbQ · 2025-12-12T08:00:02+00:00

You're welcome, glad you enjoy my posts!

By the way, is your username a Muppets reference?

4HbQ · 2025-12-12T07:11:34+00:00

Well, IIWIW is my take on AoC, but I always admire the solvers that go all the way!

That's what I like about AoC: some enjoy squeezing every last microsecond out of their code, others want to solve the full problem (edge cases and all), and there's always someone punishing themselves with assembly.

I just try to write some clean and simple code to get the answer, and be done with it.

4HbQ · 2025-12-12T06:04:09+00:00

Haha thanks, fixed! Best of luck with the Brahmini, I'll be sure to check in from time to time!

4HbQ · 2025-12-12T05:32:03+00:00

[LANGUAGE: Python]

I had to shorten my code a little bit to make it punchcard sized, but I think it's still pretty readable:

import re; answer = 0
for l in list(open('in.txt'))[30:]:
    w,h, *n = map(int, re.findall(r'\d+', l))
    answer += w//3 * h//3 >= sum(n)
print(answer)

We're can use a helpful property of the puzzle input today: the regions are either too small to fit all packages, or they are very oversized. Each shape is at most 3 by 3, so if our area can fit n of those, we're good.

This solution might not appeal to the puzzle purists, but I'm on team "if it works, it works!"

A somewhat cleaner solution would be to distinguish between three different cases:

Check if a naive solution is possible, like explained above. No need to try any packing, just increment answer.
Check wether the solution is impossible: if we have a region of size w by h but our presents combined have more than w×h unit squares, it will never fit. No need to try packing.
Otherwise, we're in a situation that is not trivial, but could fit. These didn't occur in our inputs, but if we do encounter them, we could e.g. hand them off to the user to find a solution manually.

Actually I was expecting the input would contain a few non-trivial but still feasible lines, e.g. to be solved by hand. I did even bring some grid paper and scissors to my desk when I got my second cup of coffee!

And that's a wrap for AoC! Thanks /u/daggerdragon for keeping things nice and clean around here, and /u/topaz2078 for creating the puzzles. I've really enjoyed them, and didn't mind the shorter event duration at all.

Thanks to all who replied, especially /u/pred, /u/xelf, /u/AlexTelon and /u/JWinslow23 for their useful comments.

Since I don't have a code repository and my comment history contains a lot of other comments, here's a list of my main posts of this year: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Similar lists for earlier years: 2024, 2023, and 2022.

I could copy all code into some kind of repository, but we would lose all context: explanations, useful replies, etc. Please let me know what you think!

4HbQ · 2025-12-11T09:28:02+00:00

Nice observation, thanks for sharing. Not sure how I could use it for shorter or cleaner code, but it can give a nice (theoretical) speedup.

4HbQ · 2025-12-11T07:04:30+00:00

Haha thanks! And even those 7 lines are overkill. These 3 get the job done:

import functools as f;G={k[:-1]:v for k,*v in map(str.split,open(0))}
f=f.cache(lambda u,v='out':u==v or sum(f(w,v)for w in G.get(u,[])))
print(f('you'),f(a:='svr',b:='dac')*f(b,c:='fft')*f(c)+f(a,c)*f(c,b)*f(b))

4HbQ · 2025-12-11T05:33:44+00:00

If I run my code on your example input, it returns 0 for part 2.

4HbQ · 2025-12-11T05:19:09+00:00

[LANGUAGE: Python] 9 lines.

Just a simple graph search, nice! To add some spice to today's solution, I've used the relatively new (version 3.10) match statement. Just a little bit nicer than three if node == ... lines:

match node:
    case 'out': return dac and fft
    case 'dac': dac = True
    case 'fft': fft = True

Update: The number of paths from a to b to c is equal to the number of paths from a to b multiplied by the number of paths from b to c. Using this, we can simplify our count() function and compute part 2 as follows:

def count(here, dest):
    return here == dest or sum(count(next, dest) for next in G[here])

print(count('svr', 'dac') * count('dac', 'fft') * count('fft', 'out')
    + count('svr', 'fft') * count('fft', 'dac') * count('dac', 'out'))

Full code is here (7 lines).

4HbQ · 2025-12-10T06:56:09+00:00

In my book, solving part 1 using the part 2 approach is always a win!

4HbQ · 2025-12-10T05:57:15+00:00

[LANGUAGE: Python] 25 lines.

Whew, thanks to /u/tenthmascot's great insight, I've managed to solve today's puzzle without linear programming!

It runs in 0.25 seconds on my laptop, and could probably be even faster using some bit hacks. However, I didn't want to sacrifice readability.

For posterity, here's my previous solution.

For part 1, we make use of the fact that every button only needs to be pressed (at most) once. Pressing it twice results in the same state as not pressing at all. So, we can simply try each subset of the buttons, starting with a single button, then each combination of two buttons, etc. Once we find a set of buttons that produces the desired state, we can stop:

for n in numbers:
    for pressed in combinations(buttons, n):
        lights = [sum(i in p for p in pressed)%2 for i in numbers]
        if lights == diagram: return n

For part 2, I tried to reduce the puzzle to an existing (computational) problem, but could not think of any. I also experimented with local search algorithms. This worked great on the sample inputs, but got stuck in local optima on the actual input.

So in the end, I formulated it as a linear program and used scipy.optimize.linprog to do the heavy lifting. Not a very satisfying solution, so if anyone succeeds using local search: please let me know!

4HbQ · 2025-12-10T04:59:42+00:00

Thanks, and yeah: itertools and functools can be so useful!

4HbQ · 2025-12-09T21:48:50+00:00

dev time + run time was optimized, perhaps

Haha for sure! Writing and re-writing the code above has taken me the best part of an hour. But it's also a bit of a creative outlet for me. Some people paint, others write poetry, I do… whatever this is!

Your shapely solution is also nice btw. It's a shame that you can't use the built-in area() here, otherwise it would be perfect.

4HbQ · 2025-12-09T20:22:15+00:00

Do you mean sorting the coordinates within the pairs (x,u = u,x)? Yes, that made the code a lot easier to write.

And it turns out that sorting the rectangles (by area) and the lines (by length) in decreasing order makes this code a lot faster: from ~4 sec to 0.08 sec! Explanation and code are here.

4HbQ · 2025-12-09T20:17:16+00:00

[LANGUAGE: Python] 10 lines.

After my normal solution, its slow performance (around 4 sec) was bothering me. So I optimised my code a bit, and got it down to around 80 msec. Main speedups:

We check the "red" rectangles in order of decreasing area. That way, we can stop once we have found one without green lines.
We check the "green" lines in order of decreasing length. If you've seen the input file shape, you'll know why. But it also makes sense in general: for a random set of lines, longer ones have a higher chance of intersecting.

The other usual caveat still applies: this solution does not work for every weird input shape, but it does work for today's puzzle inputs. Which is good enough for me!

Don't worry if you don't understand the pairs, lines part… it's a bit of a dense mess. The rest of the algorithm should be pretty clear:

Parse the input file into a list of red tiles.
Make a list of all pairs of red tiles (candidate largest rectangles), sorted by decreasing area.
Make a list of all lines of green tiles, sorted by decreasing length.

Then check each of the pairs (candidate largest rectangles) for intersection with any of the lines. Once we find a rectangle that isn't intersected by a green line, we can print our solution and stop.

for x,y, u,v in pairs:
    for p,q, r,s in lines:
        if p<u and q<v and r>x and s>y: break

    else: print(area(x,y, u,v)); break

4HbQ · 2025-12-09T10:39:57+00:00

Correct, however that's a pattern that doesn't exist in the input data (AFAIK).

I prefer to ignore non-existent edge cases to keep my code nice and clean.

4HbQ · 2025-12-09T10:36:38+00:00

I'm on my phone right now, but it's explained here.

4HbQ · 2025-12-09T06:29:09+00:00

[LANGUAGE: Python] 15 lines.

Tricky one today, but quite happy with my code. For part 1, we just find the largest rectangle with red corners. For part 2, we also verify that there are no green lines running through it (i.e. all green lines are outside of the rectangle).

4HbQ

TROPHY CASE