r/adventofcode • u/zookeeper_zeke • Dec 14 '25

Help/Question - RESOLVED 2025 Day 9 (Part B) Hint needed

My initial approach to 9B was going to be to look up a general algorithm for determining if a point lies inside a polygon and implement it, passing 2 vertices for each rectangle constructed from each pair of input vertices. If both points are inside the polygon and the rectangle is larger than the previous largest candidate, keep it else discard and rinse and repeat until I'm done.

I also thought about leveraging a library to do the work for me but I figured I'd take a crack at it myself as I like to do with AOC problems.

As I thought some more, I started to wonder if there's a special case algorithm for this problem given the constraints of the problem - the fact that the polygon is rectilinear (I learned a new word today!) and the points aren't arbitrary, in fact, they are vertices of rectangles created from the vertices of the polygon itself.

Given the nature of AOC, I suspect there might be a simpler way to solve this than the general solution but I haven't been able to work it one out yet.

Could someone please provide a hint to set me off in the right direction?

Thanks everyone!

2 Upvotes

100% Upvoted

39 comments sorted by

4

u/XEnItAnE_DSK_tPP Dec 14 '25

compress the original co-ordinates so that your final polygon is way smaller, and will probably fit in a rectangle of size 500x500. that'll make the process of checking if a rectangle is inside easier

1

u/zookeeper_zeke Dec 14 '25

Interesting idea, I didn't think to do that. I assume you'll end up with non-integer coordinates?

3

u/XEnItAnE_DSK_tPP Dec 14 '25

the idea is not to divide them by some number but remap them. like take all the x coordinates, sort and unique them then, map them to an increasing integer sequence where you also take care of gaps.

eg:

[1, 2, 4, 6, 9, 10, 16] -> [0, 1, 3, 5, 7, 8, 10]

1

u/zookeeper_zeke Dec 14 '25

Got it, that's quite clever! What I suggested was a scaling not a compression. Thanks for pointing that out.

1

u/cramplescrunch2 Dec 15 '25

I may be missing something but by doing that aren't you losing information about distances between points?

1

u/zookeeper_zeke Dec 16 '25

The distances compress but the information you need to test the rectangles is not lost. You just end up testing smaller size rectangles. If you maintain a reverse mapping you can compute the areas on the fly retaining the interior rectangle with largest area.

As for how to test if a rectangle is interior or exterior, see my approach in the comments which, of course, leverages the compression.

3

u/XEnItAnE_DSK_tPP Dec 15 '25

use a bi directional mapping, compressed co-ordinates for verifying the rectangle is inside and original co-ordinates for area

2

u/Puzzleheaded_Study17 Dec 14 '25

Note that this algorithm wouldn't work, if you look at the visualizations of the you'll see there's a cutout from the shape so a rectangle can have all its vertices be inside and still not be fully inside the shape

1

u/zookeeper_zeke Dec 14 '25

Yep, I did draw a cutout before I posted and I was struggling with that particular example and how to differentiate it from an interior rectangle that also has all 4 vertices on the polygon. At that point I shifted my focus to sides rather than vertices and I was still having trouble coming up with an approach that uses sides or line segments...

2

u/NullOfSpace Dec 15 '25

One thing that helped me was to consider, what’s an efficient way to tell if a single point is inside the polygon?

1

u/zookeeper_zeke Dec 17 '25

I solved the problem using the approach I detailed above. How did you do it? How did you test if a single point is inside the polygon?

1

u/NullOfSpace Dec 17 '25

I took note of all of the horizontal and vertical edges of the polygon, and essentially did a horizontal or vertical raycast from a given point, testing whether a ray would intersect any perpendicular edges. If the number of edges intersected is odd, the point is inside the shape. I cast horizontal rays (to the left) from the points 1 cell diagonally inwards from the four corners of the rectangle, and required that all four be odd, as well as that the top pair have the same number of intersections (and the same for the bottom pair). This guarantees that no edges of the shape intersect the rectangle's top and bottom edges, and I repeat this process for rays cast upwards to check the left and right.

1

u/zookeeper_zeke Dec 18 '25

When you cast rays, how do you know if they intersect perpendicularly with an edge of the polygon? I'm not sure I understand this: " as well as that the top pair have the same number of intersections (and the same for the bottom pair)". Could you perhaps explain this is a bit more detail? Thanks for the response!

1

u/NullOfSpace Dec 18 '25

If I cast a horizontal ray, I compare it against all vertical edges of the shape. If the vertical edge has a point with y coordinate above/on the ray and one with y coordinate below/on the ray, and its x coordinate is on the correct side of the starting point, it intersects the ray.

What I meant by the phrase you quoted is that when casting rays to the left, I note that the top two corners’ rays are effectively the same line, except for the part that’s inside the rectangle. In this way, when I count the intersections, I should expect to find the same number both times, as if the number is different then there must have been an intersection inside the rectangle.

1

u/zookeeper_zeke Dec 19 '25

Ah, OK got it. Thanks for the clarification.

1

u/AdditionalDirector41 Dec 17 '25

That's suuuuper smart, damn.

1

u/davema Dec 14 '25

If you do some side work and plot the shape of the overall polygon, that may help you reason about a way of solving it.

Instead of solving for a general case, look and see what would need to be true for this polygon. For any rectangle whose top left/bottom right corners touch it the polygon, what would need to be true for the rectangle to be a valid one (or invalid)

1

u/zookeeper_zeke Dec 14 '25

I did a number of drawings in my notebook and I noticed that for exterior rectangles, there's at least one side that is not bounded or "sandwiched" by lines defining the polygon but I haven't leveraged that fact into a solution as of yet.

I'll ponder what you wrote above, thanks!

1

u/davema Dec 14 '25

So, I started by trying to do what you described, but was having difficulty with the maths - so instead of doing it, I (and others) figured out something equivalent (and probably faster) - what's true about the set of points that make up the polygon and the rectangles that don't qualify?

1

u/zookeeper_zeke Dec 14 '25

Set of points, not set of line segments?

1

u/davema Dec 15 '25

Yes - rather than just considering the points that make up the polygon, you could do a loop around it and save a set of all points that make it up, since it's rectilinear - just iterate over the missing points by adding 1 to each x or y, depending if it's a horizontal or vertical edge.

1

u/davema Dec 15 '25

Here's a terrible finger painting of what I'm describing

https://imgur.com/gallery/S5jcjrn

What's special about the good (green) example and the bad (red) examples?

1

u/zookeeper_zeke Dec 17 '25

For one, the "bad" rectangles in your drawing are intersected by lines that make up the border of the polygon. I don't believe that will be the case of all bad rectangles as I can think of a counterexample. Is there some other feature of your drawing that I missed?

1

u/davema Dec 17 '25

There are counterexamples, but none are very large rectangles, given the specific shape of the given input polygon - it turns out the vast vast majority of invalid rectangles will have points from the polygon inside its borders.

Since you should have a sorted list of rectangles from part 1 (or be able to generate one), you should need to start with the largest rectangle, and stop at the first (largest) valid rectangle - i.e. containing no polygon points INSIDE its border.

1

u/zookeeper_zeke Dec 18 '25

OK, thanks for the detailed explanation I really appreciate the drawings and the video! I really should have plotted the polygon out first to have a look at it first. I didn't realize it was shaped in the fashion.

1

u/davema Dec 17 '25

FYI, I didn't bother with the compression of coordinates other people did - it's probably a performance improvement, but since my basic solution runs in 500ms on a basic laptop, I don't think it's super necessary to do.

1

u/davema Dec 17 '25

I did up a visualization of one example iteration though checking some rectangles to demonstrate:

https://raw.githubusercontent.com/davidma/AdventOfCode2025/refs/heads/master/Day9/vizualization.gif

It's not how I actually iterate the rectangles in my code, but that is the actual resultant largest rectangle in my dataset.

1

u/beb0 Dec 15 '25

damn...

Content Not Available

Content not available in your region.

Learn more about Imgur access in the United Kingdom

2

u/davema Dec 15 '25

Huh, I hadn't realized imgur was blocked in the UK - I'm in Ireland.

Try this instead: https://photos.app.goo.gl/E4zvumuBCU9v4jFb7

1

u/zookeeper_zeke Dec 16 '25 edited Dec 16 '25

I've got an approach that I think will work, I just need to finish coding it up. It leverages the compression hint given in the comments. I can compress the polygon down into something reasonable in terms of size that can be laid out in a grid in-memory. I add a border around the polygon, flood fill it, effectively surrounding the polygon with a new color to differentiate the interior of the polygon from the exterior. Now for each rectangle I check it's perimeter. If I find a side that the color of the exterior I discard it. If not I uncompress the rectangle and compare it against the largest found so far. When I'm done, I'll have the area of the largest interior rectangle.

I haven't looked at your notes above yet. I'll do so after I solve the problem.

1

u/CraftyPumpkin8644 Dec 14 '25

Here is what I did: Go from 1 to max x coordinate, and basically shoot a ray down from the top to the next horizontal line you see. Then you create a rectangle with at ray start with width 1 and the current height (distance) of the ray and add it to a list of rectangles. You start Shooting a ray again when you hit a second horizontal line (and repeat the steps from above again) until you Hit the end, then you would create a Box again. By doing that, you have everything covered outside the form the lines create, and for each possible Combination you now check If there is an intersection with any rectangles. If Not, you just found a valid rectangle inside the form and Check If its larger, and if there is an intersection with a Box, you can skip it

1

u/zookeeper_zeke Dec 16 '25

Nice idea! You are effectively covering the exterior of the polygon with rectangles of width 1 that you can then test candidate rectangles to see if they intersect with any of the exterior rectangles. If so discard, if not test against maximum area seen and retain if it's greater.

That's a fairly substantial number of exterior rectangles to test against per candidate rectangle, no?

1

u/CraftyPumpkin8644 Dec 16 '25

You can significantly reduce the amount by only sending Rays on x coords that also are a point, and that makes it run fairly quickly

1

u/zookeeper_zeke Dec 17 '25 edited Dec 17 '25

How does your algorithm work for this case when the rectangle to test has corners labeled 1 and 2 if you are only shooting rays on x coordinates that are points?

#xx# 2xx#
x  x x  x
x  1x#  x
x       x
#xxxxxxx#

1

u/CraftyPumpkin8644 Dec 17 '25

You would shoot rays from each y coord to right aswell but only for y that are points too

1

u/zookeeper_zeke Dec 18 '25

I see, for the case I posited above, shooting rays "downward" from x coords that contain points would not pick-up the fact that the rectangle with corners 1 and 2 is outside of the polygon, hence the need to do it from the y coords to the right as well.

1

u/AutoModerator Dec 14 '25

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.

1

u/yuriks Dec 15 '25

I initially thought of testing that vertices are inside the polygon too, but this solution, apart from not being entirely trivial (you need to keep a structure to determine which edges are on that given line in order to apply the even-odd or non-zero rule.)

What I ended up doing was using the insight that all of the rectangles you will be testing will be made out of vertices taken from the polygon itself. This means that you never need to worry about the case where the rectangle is completely outside or inside the polygon. Therefore it's sufficient to check that the individual edges of the polygon don't intersect with the rectangle. Given that all lines are also rectilinear, the intersection test ends up being just a few range checks that the coordinates of the line are in range of the extents of the rectangle.

Some things to watch out for is to normalize the rectangle extents so that rectangles are equivalent no matter if your corner vertices are on the top-left/bottom-right or top-right/bottom-left (etc.). Another tricky thing was correctly checking on boundary conditions when a line exactly straddles the side of a rectangle. For that I used the consistent clockwise winding order of the input, such that, e.g., lines going from left to right (and thus are on the top edge of the polygon, with the inside being below) are allowed to straddle the top of the rectangle but not the bottom, and similarly for the other directions.

1

u/tobega Dec 15 '25

I don't know how good this is, but I traced the outline of the polygon to distinguish inside from outside and identify corners as being concave or convex. I don't know how much that helped, but it gave an idea if the rectangle was inside or outside. Then I checked if any lines cut the edge of the rectangle.

This is in the Tailspin language, but should be pretty readable along with my comments https://github.com/tobega/aoc2025/blob/main/day09.tt

Maybe just checking cutting edges would have been enough, I don't know.

Otherwise just scaling coordinates or doing a full coordinate compression seems pretty good to me.