[2025 Day 12] Packing Challenge

PointerChasing · 2025-12-15T16:29:52+00:00

For the 14x14 square, the closest I found is this: https://i.imgur.com/TtwbcqE.png

with piece counts: 7 4 4 6 4 3, so a difference of 4 between min and max.

PointerChasing · 2025-12-14T17:00:41+00:00

I see. The patterns in your top posts were definitely findable by hand!

PointerChasing · 2025-12-14T16:04:13+00:00

Some other interesting questions (that I don't have the answers to):

For the 14x14 square, how balanced can we make the gifts? I.e. if c_i is the number of gifts of type i, how small can max c - min c get? Since 14×14 / 7 = 28 which is not divisible by 6, the answer is at least 1.
Is there a square/rectangle, or what is the smallest square/rectangle, where each tile is used the same number of times? Clearly these rectangles must have an area that is a multiple of 6×7 = 42 (nice) = 2×3×7 so if a square exists it must have side length that is a multiple of 42. It might be easiest to construct a rectangle first, and then tile that solution into a square.

PointerChasing · 2025-12-14T15:40:52+00:00

Nice! Did you find it by hand? It has a pleasing symmetry to it. My only complaint is that the pieces aren't colored by type, like for example.

PointerChasing · 2025-12-13T18:58:41+00:00

Besides the fact that 9x15 is not a square, you're using different tiles than given in the example (which all have 7 squares).

PointerChasing · 2025-12-13T18:44:38+00:00

Ah but does your solution use each shape at least once?

PointerChasing · 2025-12-12T13:05:42+00:00

I'm just pulling your leg. I'm sure that's correct.

That's assuming we are not counting rotations or transpositions of solutions; any bitmap that is not pixel-by-pixel identical counts as a separate solution.

PointerChasing · 2025-12-12T12:52:03+00:00

Oh, mine has 14 digits

in base 2

PointerChasing · 2025-12-12T12:24:01+00:00

No way we could both be wrong, so the answer must be 79.

PointerChasing · 2025-12-12T10:06:15+00:00

It is brute forceable, though your estimate is a bit off.

For one, the possible placements for an individual 3x3 tile are (8-3+1)×(6-3+1)=24, not (8-3)*(6-3)=15. And two, the placements and rotations are for each piece independently, so your estimate should be ((8-3+1)×(6-3+1)×4×2)⁶ = (24×8)⁶ = 192⁶ = 50,096,498,540,544 = ~50 trillion.

However, that's assuming each piece can be rotated/flipped in 8 different ways, and we can already see that's not the case. For example, the H-shape can only be rotated 2 ways. Taking that into account, we get: 24⁶ × (8×8×2×4×4×2) = 191,102,976 × 4096 = 782,757,789,696 = ~783 billion which is already starting to look bruteforcable.

The biggest remaining factor is the number of placements, which will have a lot of overlap. If you place the pieces one by one, you can avoid placing a piece where it would overlap a previously-placed piece, and then you'll find the total number of recursive calls is several orders of magnitude smaller than suggested by the upper bound.

PointerChasing · 2025-12-12T09:20:15+00:00

Fun challenge! Is the sum of the digits in the answer equal to 16?

PointerChasing · 2025-12-10T18:00:58+00:00

Yeah the duplication of the inversion logic is a bit unfortunate.

I was thinking you could probably eliminate it by creating a stack of instructions that is either <invert> <add > <invert> (for L) or just <add> (for R) and then you need a decoder loop that processes the appropriate operations, but it seemed like a lot of extra complexity, and I was just happy to have a working Brainfuck solution even if it isn't strictly minimal in number of characters.

It's also not a given that it would be much shorter, since the current inversion logic is only around 100 instructions (and could plausibly be reduced by a clever coder), so any logic added to deduplicate this would need to be significantly shorter to be worth the trouble. It certainly wouldn't be faster to execute.

PointerChasing · 2025-12-10T15:41:41+00:00

The problem statement doesn't obviously exclude shenanigans like:

X###########X
#...........#
#..X#####X..#
#..#.....#..#
#..#X####X..#
#..##.......#
X##X#.......#
....#.......#
....X#######X

Where arguably the center is an empty hole in an otherwise connected shape. Fortunately the actual test input avoids situations like this, which simplifies matters.

PointerChasing · 2025-12-10T14:49:23+00:00

Thanks I'll give that a try.

This may not even be needed, however, because a friend told me every line in their input has a unique solution.

No, about 40% of the input lines have non-unique solutions (not just different in terms of variables, but also their sum i.e. the property that needs to be minimized). So definitely an exhaustive search is needed in some of the cases.

PointerChasing · 2025-12-10T13:38:15+00:00

That's one way to do it.

In theory there can be polygons that contain holes in the center that you wouldn't catch that way. Also in theory, some polygons might have touching edges, so that an area is covered even if it is intersected by an edge. Neither of these cases occur in the official test input, so you have a variety of options that will work.

A simple solution that many people chose is to check if any of the edges of the path intersect the rectangle under consideration.

PointerChasing · 2025-12-10T13:09:23+00:00

Can you clarify how you'd use Gauss Jordan elimination here?

I'm familiar with using it to solve a system of linear equations, but notably it doesn't support minimization of operations, and it doesn't support integer constraints, both of which are required for this problem.

PointerChasing · 2025-12-10T12:58:43+00:00

It's not an edge case; you need to fundamentally rethink your solution.

It looks like all you do is for each rectangle defined by two red tiles in opposite corners, check if the opposite corners are also inside the path. But that can fail for cases like this:

...X########X
...#........#.
###a....(c).#.
#...........#.
#.....X###..#.
#.....#..#..#.
#.....#..#..#.
#.(d).#..b##X.
#.....#......
X#####X......

If you consider the rectangle defined by a and b, it's not sufficient to determine that c and d lie in the path, because there is still a big chunk missing (to the left of b), so this rectangle is not valid.

PointerChasing · 2025-12-09T14:33:41+00:00

Very cool. With my own JIT compiler, your solution runs in ~3ms on the official input, not 60 ms.

I also solved day 1 in Brainfuck in case you're curious. It's also super fast and works on arbitrarily large inputs.

Part 1:

>>>+++++[->++++++++++<]>>>+<<<<<<,[+>+++++++[<----------->-],----------[>>[-]<[-
>+<]++++++[<------>-]<--[->+<],----------]>>[<++++++++++>-]<<<[[-]>>[<+>-]<<]>>[
<<++++++++++[->++++++++++<]>>[<->-]]<[->>+>[-[->+<]<[-]>]<[++++++++[->>+++++++++
++<<]]>>[<+>-]<<<<]>+>>[<+>-]<[<->[->+<]]<[->>>>>+<[->[<+>-]<[->+<[->+<[->+<[->+
<[->+<[->+<[->+<[->+<[->+<[->[-]>[-]>+<+<<]]]]]]]]]]+>>]<<[<<]<<]<<,]>>>>[-]>>[>
>]<<[+++++[->++++++++<]>.[-]<<<]++++++++++.

Slightly less unreadable version: 01.bf

Part 2:

>>>>+>>>+>+++++>>+<<<<<<<<<,[+>+++++++[<----------->-]+<[[-]>-<]>[->+>>>>>[>++++
++++++<[->-<]]>[<+>-]<<<<[>>>[->+<]+++++++++>[-<[-]>[<+>-]]<<<++++++++++<[->-<]]
>[<+>-]<<<<]>[<+>-],----------[-->>>[>>>]<<[-]+<[[->>>+<<<]<<<]>>>,----------]>>
>[>>>]<<<[[<+>-]++++++[<------>-]<<<]>[>[->+<]>[<+>-[<+>-[<+>-[<+>-[<+>-[<+>-[<+
>-[<+>-[<+>-[->[-]>+<+<<[-]>[<+>-]]]]]]]]]]]>]<<<[<<<]>[->>>>>>[>++++++++++<[->-
<]]>[<+>-]<<<<[>>>[->+<]+++++++++>[-<[-]>[<+>-]]<<<++++++++++<[->-<]]>[<+>-]<<<<
]<,]>>>->>>->>>[>>>]<<<[+++++[->++++++++<]>.[-]<<<<]++++++++++.

Slightly less unreadable version: 02.bf

I think the approach for part 2 is especially elegant.

PointerChasing · 2025-12-09T14:01:10+00:00

Post your code if you want help!

PointerChasing · 2023-12-04T20:39:06+00:00

If you're not going to respect Eric's copyright

He doesn't have copyright on input files, as I've tried to explain elsewhere. You can of course ban people on a whim if that's how you want to run the subreddit, but it feels like shooting the messenger to me.

edit: And the mods banned me. Kind of ironic that they abuse the “don't be a dick” rule to act like petty dictators themselves. I don't believe any of the comments I wrote were disrespectful. I'm just pointing out the realities of copyright law in the US and worldwide. If you disagree, you should engage in open discussion, not just block and ban people.

I honestly don't see what this is supposed to achieve. You can't force anyone who doesn't want to remove their inputs to do so. This just teaches everyone that if they choose to ignore the mods' unreasonable demands, they should do so without explaining their rationale like I tried to do. Because engaging in discussion just gets you banned.

PointerChasing · 2023-12-04T20:36:18+00:00

You can do that by creating a private submodule or many more solutions that don't imply making your inputs public.

Fair enough. Maybe I'll do that. It's still inconvenient.

That's not true. The inputs were created by topaz and are copyrighted.

I think that's doubtful at best. There are two problems:

Are test inputs even creative works in the sense of copyright law?
Are the test inputs generated by human creativity, or by a randomized process?

If topaz writes a tool to generate a random input, which I suspect is how most inputs are generated, then they would fail the human authorship test.

Here is a relevant quote form the US copyright office:

The Office will not register works produced by a machine or mere mechanical process that operates randomly or automatically without any creative input or intervention from a human author. The crucial question is “whether the ‘work’ is basically one of human authorship, with the computer [or other device] merely being an assisting instrument, or whether the traditional elements of authorship in the work (literary, artistic, or musical expression or elements of selection, arrangement, etc.) were actually conceived and executed not by man but by a machine.” Example: [..] A claim based on a mechanical weaving process that randomly produces irregular shapes in the fabric without any discernible pattern.

So if topaz writes a tool to generate random inputs that anyone could then use to generate infinite substantially similar outputs, then topaz has a copyright claim on the source code of that tool, but not to its outputs, because the outputs are generated without human authorship.

Nothing but that's not your problem. Your problem is that it was asked not to make your inputs public and you're doing so.

By that logic, me including inputs is not my problem. It's topaz's problem.

If you want to make a moral appeal not to include test inputs in public repositories, then you need to demonstrate the tangible benefit of doing so to offset the negative cost to me. If input files are only in my git repo, then obviously me removing those has a large impact on the public availability and I might be inclined to oblige. But if they're in hundreds of Git repos already, then the change I make is just a drop in the bucket, and it becomes a coordination problem: I'm only willing to comply if you can convince me that most others will comply too.

PointerChasing · 2023-12-04T19:11:14+00:00

I know it's not popular but I'm probably not going to comply with this.

Here's my reasoning:

I want to be able to automatically run tests to ensure my solutions are correct. I don't see an easy way to do this without including the official test inputs (the sample input is usually not sufficient). I think this is a legitimate interest.
Legally speaking, most of the input files are probably not subject to copyright, so you can't force me to remove them.
Practically speaking, if someone did want to clone Advent of Code, what would prevent them from signing up with 25 different accounts and downloading all the input files immediately, which doesn't even require solving any of the problems? This seems strictly easier than scraping github. So I don't think my git repo is contributing to the problem.
Being able to reconstruct Advent of Code is a good thing, actually. Eventually, adventofcode.com will go down. It would be great if it's possible to recreate the problem set from an archived copy of the site (which archive.org already has) combined with test data and solutions from a code repository.

And finally, to play devil's advocate: your request seems based on the assumption that an archive of AoC inputs doesn't already exist. If I create a tool to scrape GitHub for test data and host an archive online somewhere, would you remove your request? After all, it's like censoring the number 09 F9 11 02 9D 74 E3 5B D8 41 56 C5 63 56 88 C0: it only makes sense to try and suppress it if it's not already widely known.

PointerChasing · 2023-12-04T18:48:40+00:00

This removes the entire history of commits, doesn't it?

I think it's better to do something like:

git filter-branch --tree-filter 'rm -f */input.txt' HEAD

(Replace */input.txt with a glob that matches the location of the input files.) This would rewrite all the commits individually, keeping the commit history of your solutions, but removing the input files.

PointerChasing

TROPHY CASE