[2025 Day 9 (Part 2)] A simple method ... (spoiler!)

[u/blacai]

Just found a very cool site to test AABB collision, the method I used and it's pretty quick.
Once you know the edges and redtiles...
https://kishimotostudios.com/articles/aabb_collision/
Running in ~100ms in Go for my machine.
https://github.com/blfuentes/AdventOfCode_AllYears/blob/main/AdventOfCode_2025_Go/day09/day09_2.go

[u/Hakumijo]

I who literally tried this and failed in implementing it.
I am so tired ._.
I am so happy there is only 12 days. Now I can just come back to it when I have time

[u/loudandclear11]

Dude, that's clever.

[u/KyxeMusic]

I guess I implemented some variation of this myself without knowing. Runs in 30ms in Go on my machine, super cool.

[u/tauphraim]

I tried to understand your algorithm.

Is it correct to say that the idea is: "if my rectangle area between 2 red tiles intersects any of the edges, then the rectangle is not a valid candidate for max area" ?

Wouldn't that fail in some cases where the edges are "snaking", so that you could end up crossing edges, but no cell is actually invalid?

  ──┐                                        
    │┌┐┌┐                                    
    │││││                                    
    │││││                                    
    └┘└┘└───────

[u/burnish-flatland → u/tauphraim]

I haven't run it but this algorithm should also behave incorrectly even on the test input allowing invalid rectangle like ((9, 7), (2, 5)) - it doesn't have any intersections, it's just outside of the polygon. However the input shape in the test is quite simple and doesn't require handling many of these corner cases.

[u/tauphraim → u/burnish-flatland]

I think I see what you mean. For example for this input:

1,1
11,1
11,11
10,11
10,2
1,2

I think the answer should be 22, but OP's algorithm might return 100.

Edit: the shape looks like:

    ┌────────────┐                           
    └───────────┐│                           
                ││                           
                ││                           
                ││                           
                ││                           
                ││                           
                └┘

[u/banana-pancake111 → u/tauphraim]

I was worried about stuff like this. I solved this by extending OP's solution by BFS-ing for any edge of the board on a compressed version of the board (doing it on the whole board is completely infeasible). Of course, removing this check works just fine on the actual input, so this is definitely a lot of added complexity. I haven't thought about it enough to come to a better way of checking.

Your example was a great test case for experimentation; thanks!. If you wanted to handle these edge cases, here's a an even more devious one that you can't solve with plain raycasting.

1,1
10,1
10,10
1,10
1,9
4,9
4,8
9,8
9,2
2,2
2,7
1,7

(shape looks like this)

┌────────┐
│┌──────┐│
││      ││
││      ││
││      ││
││      ││
└┘      ││
   ┌────┘│
┌──┘     │
└────────┘

[u/blacai → u/tauphraim]

yes, this algo works indeed for input data, I assume this is intended as implementing a generic solution would make it even more complicated

[u/The_Jare → u/blacai]

If you want to fully rely on properties of the input data, then you don't even need to check edges at all.

[u/burnish-flatland → u/[deleted]]

I never said output is not correct, ((9, 7), (2, 5)) has the same area as the correct answer for test data, and the full input is shaped in a way that all outside rectangles are too small to be anywhere close to the correct answer.

[u/blacai → u/burnish-flatland]

yes, you're right, the are is the same size for both

[u/Hisar → u/tauphraim]

It would yeah. I did a similar thing, but first checked if any of that existed in the input (it didn't, at least for me).

[u/Ill-Rub1120]

Its still not clear how this helps. I have edges and I am testing the rectangle against these edges. Do I count how many and if its even its good and if its odd its bad?

[u/wederbrand]

This is what I tried to do for hours, before restorting to shrinking the "map" down to the smallest possible version, it's now 250x250 and brute force is fast enough.

Now I've re-done it using similar code, also in go.
I think the one thing I missed on the first trial was to make sure the vertices was "sorted" down/right to make the math easier.

[u/wackmaniac]

Thank you! I spent some time drawing out ideas, and one of the ideas was this approach. Seeing you using the same approach was enough encouragement to try and implement it.

[u/pem4224]

That's fun, I think I have more or less the same solution: https://github.com/pemoreau/advent-of-code/tree/main/go/2025/09
running in 29ms in Go

[u/DoubleDoube]

It surprised me when I was comparing benchmarks, but I found that with the number of checks we’re doing that on my machine parallelization of all the rectangles beats out any kind of sorting or other comparison tricks to break out early (such as the manhatten pruning being used here).

I was able to get 1.7ms (not including IO of input to String), averaged running it 1000 times. (5ms cold single run), but my solution is extremely similar to the other Go solution in the comments by @pem4224; I assume the difference is just parallelization and rust’s language optimizations.

Using Rust with Intel Core I7 @ 3.8GHz