Just in case anyone is stuck on the second part, here are the things I checked to verify whether a particular block was valid.
Are there any line segments that have an endpoint inside the box (not just touching the border, but inside it). That would suggest that part of the box is outside the figure.While I use two endpoints to define the box, I have to check to see that the other two corners are also within the figure. I use an odd-even ray casting method to determine if a point lies within the figure.Sometimes a corner may be within the figure, but the points immediately adjacent to it aren’t, so I check the 8 points that are immediately adjacent to the four corners.Finally, I check to see if any line segment crosses through the box, where each endpoint is outside the box, but the line passes through.
I’m not quite sure I follow your last next-to-last lines: do you mean 8 points for each of the 4 corners, so 32 in all?
I tinkered with sketches of the example polygon and rectangles until I finally gave up and consulted the Reddit solutions. There are some interesting solutions, but none seem simple.
The approach I took was mentioned by at least one person. It has two parts.
I did at least think of the first part on my own: ray-casting from the rectangle’s corners. I’ve seen references to it in past years for deciding if a point is within a polygon, so it seemed pretty obvious to try it this year. So I finally implemented that for the first time evah! but one reason I hadn’t tried that before skimming other solutions was that it clearly shouldn’t do the job by itself – and unless you’re really lucky with your input, it doesn’t.
You can’t do that for every point of the rectangle, though; that would take far too long. It does suffice to check that the edge points are valid, but even doing that technique would take far too long. So verify that edges of the figure don’t pass completely through the edges of the rectangle, which is reasonably straightforward.
Even so, I didn’t think to perturb the rectangle corners so as to avoid issues with vertices and edges.
There’s a very clever approach that several people use to compress the points of the figure to a much, much smaller, not-to-scale figure. I think that a brute force-like approach becomes trivial at that point, but as far as I can tell, they didn’t do that. Anyway, I like the elegance of the approach.
Oh, and if anyone is curious, someone posted an image of what the figure looks like. It would not surprise me if they all look more or less like that, only translated and maybe rotated.
For part 2 I visualized the shape before trying to solve the puzzle. I thought I had a sound solution for this problem, but someone on reddit made a post about the same algorithm where commenters showed counterexamples it fails on. So my “solution” may just be a case of exploiting a property of the input. Hard to say whether or not this is intended, but every year seems to have a problem where the input has some special properties… If Eric wanted to be mean he would have made the concave region largest.
First of all, the line segments in this puzzle are not really lines - they have area and behave like rectangles with either a width or height of 1 for vertical and horizontal lines respectively.
My formalization of the problem:
When a line segment along the polygon runs parallel to and intersects a box line segment, I call this a “common intersection.” When a polygon line segment pokes into the box, I call this a “crossing intersection.” “Pokes into the box” means that a line segment from the polygon crosses at least one unit further into the box from its 1-unit border. If this happens, the line segment must cross out of the box somewhere else so that part of the box must be outside the polygon. We just need to find the largest box having only common intersections. This criteria turned out to be incorrect, because it can select a box occupying a concave region. We need to also apply a point-in-polygon algorithm like @wutka did to solve the general case.
The easiest way to implement this is to just pick all possible boxes and exclude any box with crossing intersections. We can ignore common intersections because they don’t affect the result. The box with the largest size is the solution.