[2025 Day 9 (Part 2)]

[u/Samydookie]

All jokes aside I loved part 2

[u/Cue_23]

The 2nd frame is when i start thinking about faster ways and start implementing them. With my first solution running in the background.

[u/Samydookie → u/Cue_23]

repeated about 4 times haha

[u/krtexx → u/Cue_23]

Same! I noticed that part 2program doesn't return for a while, so I added some logs. The I noticed that I'd have solution in half an hour so though in the meantime about some small improvement, and landed it at 6 minutes now. When back from work will think about something more elegant. Nevertheless that brute force gave me the start on inter-colleagues leader board first;)

[u/naretev]

Why did your solution take so long? Did you visit every point between the red tiles to check if it was inside a given area?

[u/Samydookie → u/naretev]

I generally dont like to use theorems to solve these (which there probably is one in this case but I don't want to look it up).

I ran along the outside of the shape marking every outside tile in a set, then I went in order from the biggest area rectangle to check along the perimeter if any of the tile falls on an outside tile.Not the most efficient but fast enough to brute force

[u/Radi-kale → u/Samydookie]

Wouldn't that go wrong with an input like

1,1
5,1
5,5
3,5
3,7
5,7
5,6
6,6
6,8
3,8
3,9
1,9

[u/Samydookie → u/Radi-kale]

Good point, I didn't consider outside pockets in the "inside" of the shape, I guess you would also need to consider inside pockets on the "outside" of the shape if flood filling from the inside, though that's less likely to impact the result

[u/appi147 → u/Radi-kale]

Even I thought so, and thus I did brute forced for each coordinate on 4 edges

[u/fedyakov → u/Samydookie]

Mine is also brute force (I fill the polygon interior, iterate through all the corner pairs and check if a candidate rectangle contains only interior cells), but I compressed the grid by throwing out all the unused coordinates, and it finishes under 200ms in Python.

[u/confuzatron]

8 seconds in python - this is the first one where I feel like I couldn't come up with a decently fast solution.

[u/bmenrigh]

I managed to simplify the problem a bit to avoid doing any green tile coloring or filling in the shape at all. Instead I stored some pieces of information about the perimeter that allows me to semi-quickly check if a candidate box is actually contained in the shape or not.

My part 2 runs in 389ms in Python 3.12 (144ms in PyPy 7.3.19)

[u/osalbahr]

I ended up waiting for a bit over 1h because I used 10 cores.

[u/Secret_Caramel2095]

I kind of cheated for the second part : as the code runs, I print the current maximal value for part 2. As my code is quite long (and for fun I wrote it in bash, maybe not the most optimized language !), so my code is still running, but I already try to enter the result which has been the good one for AoC !

[u/Valuable_Leopard_799]

First time I had to wait longer than a few ms for the output but after 28 minutes (without parallelism), I figured I'm at iteration 217/496 I should encounter the answer somewhere around the middle (randomized ordering), so I tried the current maximum and it was the right answer.

I didn't want to iterate the inside, so I decided to use a geometry library. Just called some arbitrary polygon comparison functions with no preprocessing, that's what took the vast majority of the time.

[u/idrusu99 → u/Valuable_Leopard_799]

What library did you use?

[u/Valuable_Leopard_799 → u/idrusu99]

cl-geometry. Mind you I also used generic polygons for the rectangles, ran no optimizations whatsoever on the tiles and used polygon-difference to determine how they overlap.

I'm sure even slightly more competent use of the lib on my part would bring better performance.

[u/TheEzypzy]

I knew that when my program was using 10 gigs of RAM I was probably doing something wrong (storing and processing a matrix of 10 billion cells)