bp#AdventOfCode day 18
wow this was a doozy, and probably the first interesting problem of the year for me
so, fine, there's a formula that gives you the area of a polygon given its coordinates. the problem is that, if I just follow the steps given by the problem, I end up tracing the orange path, when I want the blue path that actually envelops every cubic meter of earth being dug up. I could not, for the life of me, figure out how to turn the orange path into the blue path
but if I take the orange line and just slide it by half a unit down and to the right, and I already have the area within the orange line, it becomes clear that the orange line is somewhat "concentric" to the blue line. To go from orange to blue you kinda have to grow it outside by half a unit. Beats me how to do it, though.
Instead, I can try and calculate the AREA of that difference
and, like, if you stare at this really simple version of the problem for long enough, it sure seems like you take the orange surface and you add three quarters for every corner and one half for every straight bit of the perimeter
of course that's too simple: if I try that approach on the sample input I get 64.5 instead of 62
(meanwhile the internet buddies I'm infodumping on are wondering why I'm using decimal points at all)
so by looking at the sample input and coloring every bit of the path that's being drawn, it turns out there are some edge elements that add .75 (green), some edge elements that add .50 (purple) and some edge elements that add .25 (green)
stare at it for a bit and it becomes clear that (so long as the orange line is defined clockwise) the green bits are clockwise corners, and the red bits are counterclockwise corners
this is just as well because, while using the polygon area formula on my square example input that I happened to define as D 1, R 1, U 1, L 1, I got an area for the orange path of -1 instead of +1
see, I defined my path COUNTERclockwise and so its SIGNED area was NEGATIVE
so it makes sense that the clockwisedness of the corners is relevant to the result
I typically try and make sure my mastodon images have descriptions added, but in this case... words eluded me (and somewhat still do) and this meant I took like three hours of active time solving this when I should be packing for Italy instead
the actually nice way to do it (I guess you could say the @ramuuns way to do it) is to intuit that the difference between the orange and blue lines is perimeter/2 + 1
divide by two the same way the shoestring formula does
and then realize you're off by one
I mean I guess you could unfurl this border area into some kind of 1 x (perimeter/2) rectangle, though I don't know why you're still off by one. Oh well.
Kevin Yap@bp The intuition from your earlier posts helps explain this — take a simple rectangle. If you add perimeter/2, you're account for all the area on the "edges" you're missing, plus 1/2 for all 4 of the "outer corners". Each outer corner *actually* contributes 3/4 units, so you need 1/4 * 4 = 1 more unit (the +1).
For more complex polygons, each "inner corners" (1/4 unit area) necessitates an extra "outer corner" (3/4 unit area) so they are net equal to 2 edge pieces.
@bp Apparently, this is also equivalent to using Pick's theorem, where `i` is the internal area from whatever method you choose, `b` is our perimeter, and algebraically rearranging to solve for b + i. https://en.m.wikipedia.org/wiki/Pick%27s_theorem#Formula
Really liked this problem as well; it was super satisfying to derive this solution (and I'm quite surprised it hadn't appeared in any past years' Advent of Code problems).
