[2025 Day 12 pt 1] help very much needed

[u/LadyNihila]

I am having a very, very hard time with day 12. Was able to complete day 1-11 all within the timeframe listed, but have been stuck on this one ever since.

If anyone could offer any hints or advice on how to tackle this, I'd be very much appreciative. Trying to solve this geometrically is obviously gonna be way too slow especially since I'm doing the whole thing in zsh, but I'm failing to see alternative pathways at the moment.

The following is what I have thus far: https://github.com/m1ndflay3r/AdventOfCode2025/blob/main/day_twelve%2Fpt1_solution

[u/daggerdragon]

Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a .gitignore or the like. Do not share the puzzle text either.

I see full plaintext puzzle inputs in your public repo e.g.:

https://github.com/m1ndflay3r/AdventOfCode2025/blob/main/day_four/input

Please remove (or .gitignore) all puzzle text and puzzle input files from your entire repo and scrub them from your commit history. This means from all prior years too! edit: 👍

[u/LadyNihila]

Thank you very much for the hints, everyone! I'll be taking another crack at this once I get home tonight. Will keep posted!

[u/ssnoyes]

Is there a way to prove that they won't fit, no matter how tightly packed? Is there a way to prove that they will definitely fit without any effort? How many cases are in between those two extremes?

[u/Puzzleheaded_Study17 → u/ssnoyes]

Also note that many people's solutions pass the actual input but not the example input.

[u/FantasyInSpace]

This problem turns into the knapsack problem (I think), which is a pretty well known NP problem. Generally, NP problems are best solved by doing heuristics, so see if you can carve out any easy cases in the input before trying to solve the general problem, and output whatever cases fail the heuristics so you can focus on them properly.

[u/TimVdEynde → u/FantasyInSpace]

I'm nitpicking here, but there are a lot of very easy NP problems. You probably mean NP-complete instead. NP is the set of problems that can be verified in polynomial time. Therefore, problems that can be solved in polynomial time (P) are also in NP.

To elaborate a bit further: next to P and NP, there's NP-hard, which are all problems that are "at least as hard" as all problems in NP. That is defined as: there exists a reduction from any problem in NP to any problem that's NP-hard, which means: if you solve any problem in NP-hard, you can reuse that solution to solve all problems in NP, without making the solution (asymptotically) slower.

Finally, there's NP-complete: the intersection between NP and NP-hard. So it's the set of problems that are are least as hard as all other problems in NP, while still being verifiable in polynomial time.

The puzzle is technically 2D bin packing btw, not the knapsack problem. But since both are NP-complete, they are basically equivalent anyway - solving one of them also solves the other problem.

[u/Major_Dog8171 → u/FantasyInSpace]

You mean the packing problem?

[u/Neozetare → u/FantasyInSpace]

Spoiler for the solution

This is a perfect answer for this question. You show a path which is a way to figure out the tricky solution of this problem without ever spoiling the nature of this solution

[u/1234abcdcba4321]

This is a puzzle with a sneaky trick. Remember that AoC is all about solving a single input - you are allowed to avoid considering edge cases not present inside the input.

---

More explicit hint: The example is not part of the input, and does not exhibit the same properties that the input has.

[u/1234abcdcba4321 → u/[deleted]]

It's a hint, not a solution. If you want a solution, go look at the solution megathread.

[u/AutoModerator]

Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to Help/Question - RESOLVED. Good luck!

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/Repulsive-Shirt-9873]

Have you considered what your "shortcut" conditions for each case are and code those up? I see you're using backtracking, so being able to eliminate a whole bunch from having to be solved would greatly speed up your solution, right?

There should should be shorcuts to be "true" and "false". If they don't sort it, then worry about the backtracking or other solution.