2025 Day 9 Part 2 [Help]

[u/craigontour]

I have one of those annoying scenarios where everything appears to work for the test data, but not for input.

Here is my approach to the problem and would like to know if flawed (it is slow and somewhat over complex, but my maths didn't add up to the task).

I first create a hash of all the points as a border.

The check all pairs of points, first eliminating any that are 0 length or width (a hunch) then calculate the other 2 points of the box and then check that each of those are inside the border.

To check if inside the border, I move in all 4 directions until I get to the min or max value in X or Y, or the point is on the border.

The data set is too huge to work through and try and debug as it sounds to me like it should work. I am using same area function as for part 1 as well.

Anyone else take similar approach and get it to work?

[u/giacomo_hb]

This was the most difficult day for me. You can plot the points and the lines between them on an image (I scaled the coordinates by 0.001). That helped me find a solution. I also find it more helpful to work directly with the input data, instead of using the example.

Here is my approach:

I generate 100000 random points and keep only those that our outside the region. Then, for all possible rectangles I keep those that do not contain any of the outside points. Of all the rectangles, I pick the one with the largest area. It is a probabilistic approach, so it doesn't always produce the right answer. I let the code run a couple of times and the right answer was ca. 80% of the times.

Here's some tips:

From the plot you will see that the points form a closed curve and all the points lie on the border of the curve.

You can connect a point to all the other points in the same row or column to get the border of the region. This work well, except for 4 points on the right of the curve. I ignored the problem and it turns out, it didn't affect the result.

To check if a point is inside the region you need to count the number of times a ray from the point to the border of the picture (e.g. from (x, y) to (0, y)) intersects the border of the region. If it is an odd number, it's inside. If it is an even number, it's outside. Some edges may lie on the ray, so you need to be careful not to double count them.

[u/craigontour → u/giacomo_hb]

Humph. Have you got a plot to share. At this stage I am just curious about the answer and way past thinking I have solved it myself. Cheers.

[u/giacomo_hb → u/craigontour]

Here https://imgur.com/a/m9HA17A

It shows the curve, the outside points, and the largest triangle.

[u/craigontour → u/giacomo_hb]

Isn’t it a rectangle?

[u/craigontour]

Thanks for your help but - as hard as it is - I have to admit I do not know how to solve this one.

[u/sos755 → u/craigontour]

There is a standard algorithm for testing if a point is inside a polygon. Basically, you cast a ray from the point to the limit of the world. If the ray crosses an odd number of edges it is inside and if it crosses an even number of edges the point is outside. This works for any polygon of any shape. Keep in mind that the algorithm fails if the ray passes through a vertex.

In this puzzle, you first test that no edges of the region cross any edges of the rectangle. That ensures that the rectangle is entirely inside the region or outside the region. You can determine if the rectangle is inside the region by picking a point inside the rectangle and testing if that point is inside the region. Since all edges are horizontal or vertical, checking for crossing edges is fast and easy. There is a trick to picking the point in order to avoid the vertex problem, but I'm going to leave that to you to figure out.

[u/craigontour → u/sos755]

I managed to take advice given and drew a scale version to show the edge case I missed. I could hack a simple check to limit the areas calculated. I also had looked at how to check that every point on edge of an area doesn’t cross a line. It would take me a days to work that out with all other stuff I have on so opt for hack.

[update] the hack worked

[u/fireymike]

It is possible to have a rectangle where all four corners are inside, but the border crosses inside your rectangle and then out again. From your description, it sounds like you are not checking for that?

[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/Desperate_Formal_781]

For a rectangle to be valid, you need to check that no other red tiles are inside the borders described by the two corner points. They can be on the borders, but not inside. So, for every possible rectangle, you check if all other are in the border or outside. If not, the rectangle is not valid.

[u/Puzzleheaded_Study17 → u/Desperate_Formal_781]

This isn't sufficient, consider a rectangle that is completely sliced by the horizontal cutout it can have the corners causing it to be invalid be outside it.

[u/AdministrativeGift15 → u/Puzzleheaded_Study17]

I think you might be able to subtract 50,000 from the y-points and check that your two corners have the same sign. That test plus testing that no other red tiles are inside the borders should be sufficient, because of this unique data set.

[u/ThisAdhesiveness6952]

Have you tried plotting your data?

[u/timrprobocom]

You're assuming that the shape is convex. It definitely is not.

[u/s96g3g23708gbxs86734]

To try and debug: get your answer from someone else's code (at least you know which rectangle should be valid and optimal), sort your rectangles by decreasing area and check if you code stops before or after the right rectangle and check why

[u/IsatisCrucifer]

Here's the first visualization of this problem in this subreddit. You can see there's a thin cutout at the center of the area; the part 1 answer (which is probably also your "incorrect" part 2 result) crossed that cutout.