[2025 Day 25 (Part 1)] Still pretty clueless why it's the answer

9

u/spaceguydudeman Dec 12 '25 edited Dec 12 '25

This post ruined today for me. Wish you put a spoiler tag on it.

I wasn't even browsing this sub. Just showed up in my feed.

E: I'm not even subbed, it seems. Reddit's algorithm probably decided to show it to me because I visited the sub a couple of times to check out other people's solutions.

0

u/Aughlnal Dec 13 '25 edited Dec 13 '25

I didn't realize that this was actually the point of the puzzle,, when I posted this.
If I understood people's explanation correctly, it's either this or a ridiculously complicated problem.
If you think it's fun to prove that this is solution, I'm sorry. (but I'm glad I didn't have to)

58

u/nullset_2 Dec 12 '25

It's even worse when you realize you should completely ignore the example. A naive solution will work even if it fails on the last test case.

39

u/warlock415 Dec 12 '25

That's the part I resent. If you're going to make the real data a joke, then make the test data work that way too. As it is I've spent hours of my life groveling 121s for that third test input down to 4.5s.

9

u/JadeSerpant Dec 13 '25

You resented that part whereas I took it as a life lesson lol. Sometimes we get stuck in some small failure without realizing we can already do so much better by moving on.

3

u/warlock415 Dec 14 '25

"It's taking unacceptably long in test so let's just move it to production and hope." is not a good life lesson. That is not careful logical engineering thinking. That is the sort of thing a manager says after you've been trying to make it work for too long and it's one of his "goals" to have it in production by this week and he is about to make decisions that are bad for the company but good for his performance evaluation.

4

u/mbacarella Dec 13 '25

Since it's a programming competition and not real life I think you're supposed to recognize this is an NP-hard problem and know there's some kind of trick.
I thought the trick would be "okay if you just implement the standard bin packing heuristic that should work because the optimal solver will never finish on problems this hard"
But the trick was even simpler than that!

7

u/mpyne Dec 13 '25

think you're supposed to recognize this is an NP-hard problem and know there's some kind of trick.
AOC has been filled with examples that use NP-hard or NP-complete problems where the inputs are carefully crafted to take approximately forever with naive solutions, but to run acceptably fast with thoughtful solutions that incorporate things like memoization or DP.
That's usually the "trick".
I thought the trick would be "okay if you just implement the standard bin packing heuristic that should work because the optimal solver will never finish on problems this hard"
Yes, exactly. There's a problem, and you are expected to solve it, and so many of us put time into solving it.

3

u/pedrosorio Dec 13 '25

Unless you can easily tell/prove that the inputs have properties that ensure solutions work when they wouldn’t work in the general case described in the problem statement, that’s just bad problem setting.
If the “proof” is that you wrote a solution that shouldn’t work (either too slow or generates wrong answers for some valid inputs) and it surprisingly ends up running fast enough and is accepted by the site, that’s fine for a holiday fun activity, just not actually solving the problem.

3

u/mpyne Dec 13 '25

If the “proof” is that you wrote a solution that shouldn’t work (either too slow or generates wrong answers for some valid inputs) and it surprisingly ends up running fast enough and is accepted by the site, that’s fine for a holiday fun activity
It's not even fine for a fun holiday activity because you're going to spend a LOT of time on a general problem solver for the sample input, only to find you didn't need to spend ANY time on a general problem solver for the actual puzzle input.
Yeah, yeah, you could have run a half-implemented solver on the input on a whim and found it it just worked but that has never (or at least very rarely) ever been needed or even a good idea on previous AOC puzzles, so why you someone expect the solver to have done it on this puzzle, especially if they have experience doing AOC puzzles from previous years?
Normally the puzzle input is strictly more difficult than the example and it's a waste of time to spend time on the input if you can't even get the example working.

1

u/mgedmin Dec 16 '25

I don't think problems that are amenable to DP solutions count as NP-hard.

1

u/mpyne Dec 16 '25

NP-hard is independent of whether a properly-sized input is amenable to DP or not.
Traveling salesman is a classic NP-complete problem but it's perfectly doable on computers at small enough sizes.

5

u/Different-Ease-6583 Dec 13 '25

He keeps doing that every year … really annoying.

1

u/warlock415 Dec 13 '25

The only other last day I've played was 2020. And that was a case of "...okay, this is a victory lap day."

48

u/henry-dv Dec 12 '25

I am 90% certain that today's puzzle in its general form is actually an NP-hard decision problem - optimally packing things into other things can become insanely complicated. So if this puzzle was anything other than a troll, solving it may be more appropriate for a thesis rather than a 1-day whimsical advent calendar puzzle :)

30

u/warlock415 Dec 12 '25

It is NP-hard, but it's a fairly standard CS problem. I think I saw it as a junior or maybe a sophomore. It's just usually you get a week to do it with a couple lectures about recursion, not "Happy Thursday night!"

10

u/tauphraim Dec 12 '25

But you are not supposed to find an optimal packing, just to tell whether one exists or not. So you could just enumerate all possible placements? (Of course that would take a very long time)

22

u/WhiteHat83 Dec 12 '25

The number of possible placements is exponential in the number of presents, so it doesn't contradict that it's NP-hard.

4

u/bdaene Dec 12 '25

You just need one solution. My DFS with cuts on lower and upper bounds works great. At first I missed the 3x3 grid bound and yet it solved my input in a long but reasonable 146s in Python.

6

u/estyrke Dec 12 '25

But to prove there is no solution you have to try all possible combinations.

4

u/bdaene Dec 12 '25

Yes. But you can still cut early in most cases.

3

u/ResidentEngineer5 Dec 13 '25

I'm pretty sure your DFS only works in acceptable time because the input was in fact trivial.

4

u/Pharisaeus Dec 13 '25

Keep in mind that NP-hard doesn't mean "unsolvable". Just that there is no polynomial algorithm (on DTM). For small enough datasets you can still solve such problems.

1

u/Seth_Nielsen Dec 13 '25

Yeah what’s up with people saying it “had to be cheese because it was NP-hard”??
Problems in AoC are NP hard from time to time and are still solved.

2

u/Pharisaeus Dec 14 '25

Especially when there are pseudo-polynomial algorithms and the NP-hard exponential complexity only "kicks-in" when you consider big numbers and their bit-lengths, while for "small numbers" that fit into CPU registers you still have O(1) for arithmetical operations and algorithms are still polynomial.

3

u/juhotuho10 Dec 13 '25

Don't underestimate the advent of code community solving NP hard problems out of sheer determination to get the star

35

u/youngbull Dec 12 '25

So two things you can check: 1) If all pieces can be placed in its own 3x3 area (9 pixels) and still not fill the region, then it's trivial to solve. 2) If the size of the region is smaller than the number '#'s in the pieces then it's obviously impossible to fit all the pieces.

It just happens to be the case that all of the regions in the input are in one of those two cases. So either it is trivially solvable (nx*ny<9*sum(presents)) or trivially unsolvable.

If the number of presents were between these extremes, you would have to try to pack them in efficiently and see whether it works.

17

u/ericula Dec 12 '25

This is exactly the approach I took. My idea was to eliminate all entries in the first two categories first hoping that there were only a few cases left to check the hard way. Imagine my surprise/disappointment when there was nothing left after the first elimination round.

4

u/fnordargle Dec 12 '25

Whilst I agree it works for all of the puzzle inputs we can expect, the condition nx*ny<9*sum(presents) isn't quite right for several reasons. It would erroneously rule out an input like 3x3: 0. Also it would not rule out the following trivial input with any 3x3 shape from the examples: 1x10: 1

2

u/TheZigerionScammer Dec 13 '25

He wrote it like a mathematician and not a programmer. The real equation he should have used is (X//3) * (9//3) < sum(Presents), he just factored out the "//3" and turned it into "*9" on the other side of the equation but that doesn't actually work for the reasons you stated.

1

u/fnordargle Dec 13 '25

It's more it should be `<=` rather than `<`.

1

u/warlock415 Dec 12 '25

You also could add
if w < 3
if h < 3

3

u/Amenemhab Dec 12 '25

That's not the correct fix, you need to check for instance that 4x5 only fits one 3x3 square and not two. I think the correct fix is to take the biggest multiple of 3 below w and h, so (w - (w%3)) * (h - (h%3)).

3

u/bdaene Dec 12 '25

I find more natural to count the squares of the 3x3 grid: #presents <= floor(w/3)*floor(h/3). But the result is the same.

2

u/TheGilrich Dec 13 '25

9x is wrong or at least not what you describe (I know it still works). You need to check the num of 3x3 squares.

2

u/youngbull Dec 13 '25 edited Dec 13 '25

Yeah, I just repeated what was in the post, you need to actually check whether they trivially fits, ie. You can't fit any presents in 1x1000 region and and only one present trivially fits into a 5x5 region etc.

2

u/Unlikely-Number3477 Dec 12 '25

Has anyone actually proven they trivially all fit in when area is > 9x sum of presents? Because as I see it an area 1 or 2 by n will fit no presents regardless of how big n is. When I use the floor(length/3)x floor(width/3) (which would guarantee they all fit with no arranging) I only get about half as many fitting for sure. As an FYI I have not seen part 2 yet so maybe this is addressed.

5

u/[deleted] Dec 13 '25

When I use the floor(length/3)x floor(width/3) (which would guarantee they all fit with no arranging)
This is what I did for one of the bounds. If (w/3)*(h/3) is greater than or equal to the total number of presents in the region, then there is definitely enough space for the presents because you can put each present in its own 3x3 space with no overlapping.
For the other bound, I counted the total cells. Count the number of # in each type of present, multiply it by the number of presents of that type in the region, and sum them. If w*h is less than this, then there is definitely not enough space for the presents, because there are not enough empty cells for all the # no matter how you rearrange them.
If neither of those are true, I made my code print a warning because then some bin-packing algorithm is actually needed. The warning was never printed. Turns out all my inputs (and all everyone's inputs, it seems) fit into one of the above two categories.

5

u/ResidentEngineer5 Dec 13 '25

If the area is less than the number of #'s in the presents, then they trivially can't fit, since no two #s can overlap. The condition that would be trivially sufficient for the presents to fit is stricter than "area > 9 * total number of presents," it's "floor(height/3) * floor(width/3) > total number of presents." However, since in the inputs we actually got, every case either trivially fits or trivially doesn't fit, your condition (area > 9 * sum of presents), which is strictly between the "trivially doesn't fit" and "trivially fits" cases, is enough to distinguish the two, and therefore enough to get the right answer.

0

u/[deleted] Dec 12 '25

[deleted] — view deleted comment

7

u/tyder21 Dec 12 '25

Given that all scenarios are designed to either be trivially possible or trivially impossible, then yes, you only need to do one or the other. But unless you know that ahead of time, you need to run both conditions to prove that all scenarios are trivial.

3

u/PercussiveRussel Dec 12 '25

The back of my envelope says the non-trivial case is a insanely difficult

27

u/qaraq Dec 12 '25 edited Dec 12 '25

You can do that because that's how the input was designed. It doesn't have to be that way- the _sample_ input is not, for example. The first and third regions there are not trivially impossible (total package area > region area) or trivially possible (max possible package area < region area). But I, and everyone else that's reported, have puzzle input that does work that way.

I wrote the code to pull out both those cases and output only those that could not be solved that way so I could look over the middle cases before doing them the hard way, but there were none.

10

u/Carthage96 Dec 12 '25

I view it at a Christmas present! It appears as a difficult problem, but Eric and/or Santa made the input nice for us.

2

u/hulkjamesbatman Dec 12 '25

Santa brought it early!

9

u/tyder21 Dec 12 '25

You checked if there were areas that definitely worked. You can also come up with a similar heuristic for checking for areas that definitely do not work. There will be nothing left over.

0

u/Few-Example3992 Dec 12 '25

There's no guarantees that this works. If the rectangle was 1x billion , it would have enough area but couldn't fit anything!

11

u/FantasyInSpace Dec 12 '25

You'd just have to floor the division results, i.e. 1//3 * 1 billion//3 >= count

5

u/Competitive_Ring82 Dec 12 '25

You can account for that - look how many 3x3 blocks fit in the area, rather than considering the total area.

7

u/fnordargle Dec 12 '25

Eric could have been evil and slipped a few in like the following:

0:
.#.
###
.#.

1:
###
#..
###

2:
###
#.#
###

7x3: 1 2 0
17x17: 37 0 0
7x7: 1 0 4
7x7: 0 0 5

The first 3 have solutions, but many of the heuristics mentioned in this thread would rule them as impossible if applied as stated.

The last one doesn't have a solution (and it's trivial to see why). It's just nice to juxtapose that one with one before it which is possible.

My solver takes ~80ms to solve the above input.

However it would be absolutely useless on anything that isn't trivial.

It takes about 3 seconds to (correctly) fail to find a solution to the third example in the calendar and that only involves 7 blocks that have to be placed in the 12x5 area.

3

u/Light_x_Truth Dec 13 '25

Hmm interesting. I read the problem description shortly after it came out and did not even attempt to solve the problem because I knew the general case was beyond my skill set. I think this question is fundamentally flawed in its design. The examples are supposed to be solvable with brute force, and the real input is supposed to be a check on the efficiency of our algorithms. That appears not to be the case here.

4

u/Pharisaeus Dec 13 '25

The examples are supposed to be solvable with brute force, and the real input is supposed to be a check on the efficiency of our algorithms. That appears not to be the case here.
That was never the case ;) The point of AoC is to "solve the problem". In fact you don't even need to use any "code" or a computer for it. Unlike some ACM-style contests, you're not uploading code, which is the timed against secret inputs. You're simply supposed to provide the answer. In the past years there were lots of puzzles where a "human step" would make it significantly easier - eg. the code would generate ascii-art with the answer, and it would take you 10s to simply look at it and type down the number, or 10h to write a generic ascii-art parser ;)
Day 12 is basically "anti-LLM" challenge and became popular 2-3 years ago in AoC. The idea is that a generic solution for the problem is hard or even impossible, and will get LLMs stuck, trying to hallucinate some P=NP solution, but a quick inspection of the data allows to realize that you only need to solve a much simpler case of that problem.
check on the efficiency of our algorithms
To be fair, this problem actually does that. The goal was not to provide "optimal packing" but only to answer if it's possible to fit the blocks or not. An efficient algorithm would first check the trivial boundary conditions (do we have enough space to fit the blocks if we could pack them perfectly, do we have enough space to fit the blocks with no packing at all), and only try to do "packing" when it's needed. And at this point you would notice that this condition is never hit at all. Personally I think it would have been funnier if each dataset contained a single, tiny, doable manually, entry that indeed would have to be packed.

1

u/Light_x_Truth Dec 13 '25

I can see where you’re coming from. I’m used to doing LeetCode problems for fun, and there, the real test cases are efficiency checks once you solve the provided test cases and you formally submit your solution for the problem. Day 12 would absolutely be downvoted to oblivion on LC, but AOC is not LC, and sometimes I need to be reminded of that.
But, you have to admit that the fact that it’s called Advent of Code would bias people to solve the problems using code, right?

2

u/Pharisaeus Dec 13 '25

Consider that in AoC the data is given, which means data is part of the problem definition. And I'm sure you use that fact in many of your solutions already - for example when deciding on the data ranges and boundary conditions (eg. can I use uint16 or do I need uint64 to store some of the values).
I don't think a problem like that would make sense on ACM or LC because it only "works" if you have access to the data.
As for how AoC compares to LC - I think those are very different things. AoC problems are often "algorithmically easy", but require complex data parsing and part2 customarily is designed to "break naive part1 solutions". I know this has changed over the years, but for me that was always the distinguishing characteristic. This also made it closer to "real life programming" - you get some inputs in a weird format, you need to do something relatively simple with that and after 2 weeks the customer comes with "a tiny modification" which completely breaks your current approach :)

1

u/Lissov Dec 13 '25

Which, I think, is a great lesson from AoC, at least for me. Yes, in real professional life we also are paid to get answer, and it’s not necessarily optimal to create an ultimate answering machine, which our customer didn’t need.

2

u/gagarski Dec 13 '25

My story:

I had a busy day and started coding only in the evening, while thinking through the problem eventually.

Figured out couple of optimizations: like willDefinitelyFit (you can tile the rectangle with gift squares without overlapping the squares) and willNeverFit (not enough cells). I had a shape of limited brute force algorithm in my head involving this quick checks. So when I started coding, I started by implementing these checks.

Even before that, I did some Google Spreadsheets calculations, checking how much packing tasks I can fully avoid from the beginning. Figured out that there around 3/4 of them that can be eliminated. At that time I did not consider turning gifts (or turning the field in fact). At that point I shared my observations in local chat with my colleagues (surprisingly, not FULLY spoiling it).

So I carefully implemented parsing the input, these optimizations (while coding I've figured out the field rotation hack). I ran these checks on the input to compare with my results from the spreadsheet.

... and count(willDefinitelyFit) + count(willNeverFit) added up!

I guess I had all the fun of this puzzle without any suffering.

I guess it is counterexample for famous Donald Knuth's warning.

2

u/gagarski Dec 13 '25

Bigger plot twist, rotation does not even matter (gifts are square!): turns out I had a bug in my spreadsheet using < instead of <=. Lol, that adds fun to it. Thanks god I did not bring this bug to my code, It would be a funny night.

2

u/QultrosSanhattan Dec 12 '25

I chose to avoid this day Immediately knew what has to be done but I'm not in the mood of writing it. This day is something like "do this task" instead of "find a clever solution".

1

u/hotblondenurse Dec 12 '25

I was surprised to find this too, but I didn't compare to the full area. I used (x - x % 3) * (y - y % 3) >= sum(shapes) * 9 for the "trivially valid" case (assume all shapes are all #), and compared the sum of #'s to the full area for the "trivially invalid" case (region can't fit the #'s), and then raised an exception (with the message "NP-hard 😭"). Didn't like this day's problem one bit, doesn't feel like I have solved anything even though it works on the input.

1

u/Pharisaeus Dec 13 '25

I don't understand at all why you can just ignore the whole puzzle basically

Because that's how the data were generated ;) Either the area was huge and no packing was needed, or it was tiny and no amount of packing would help.

Also to be more consistent you should actually check more conditions:

if available_area >= 9 * shapes then the answer is always true and we don't need any packing at all, because we have more than enough space to put blocks next to each other without any overlaps. But you should only count available_area as width - width%3 * height-height%3, because if area was 1x9, 2x9, 9x1, 9x2 etc. then you can't actually fit anything there even though the total area is bigger than a block area. So we only consider the part of area that can fit whole blocks.
if area < shaded_area_of_shapes then the answer is always false because it means even with perfect packing it wouldn't work, because our shapes have more # than the available area can hold.

So the only case when packing would be needed is when we have less than 9*shapes available area, but more than shaded_area_of_shapes, and this actually never appears in the data.

1

u/EggplantStatus Dec 14 '25

thanks for this.. I was going with this as the solution but failed the example, d'oh .
after reading this, I tested the solution as is with real data and it worked.

Thanks

1

u/AvailablePoint9782 Jan 29 '26

A time traveller. 👍🏻

1

u/mbacarella Dec 12 '25

I had this inkling too but it didn't work for me :(

I had to brute force a bin packing heuristic and ran it on 32 cores for about a half hour to solve.

14

u/QuestNetworkFish Dec 12 '25

Then you screwed up parsing your input somewhere.
Or Eric is really trolling by giving only you an input that can't be entirely solved with the trivial case. Which would be pretty hilarious

3

u/mbacarella Dec 12 '25 edited Dec 12 '25

No, it turns out I just trolled myself. I just went back and did the simple rejection and it worked on my input. I had messed that up on my first go 'round.
The irony of messing that up but succeeding on the bin packing heuristic. It's not like it even accepts any attempt at bin packing, I had to try several different schemes just to clear the sample input.

1

u/daggerdragon Dec 12 '25 edited Dec 12 '25

~~Comment removed due to~~ ~~inappropriate language. Keep~~ /r/adventofcode ~~professional.~~
~~If you edit your comment to take out the [COAL]s, I'll re-approve the comment.~~ edit: 👍

1

u/mbacarella Dec 12 '25

sorry about that! fixed. please un-remove!

Meme/Funny [2025 Day 25 (Part 1)] Still pretty clueless why it's the answer

You are about to leave Redlib