The colors were such a red herring. I went with a scanline approach, because it felt natural for filling a polygon. After all the tricks I could think of, part 2 still took 5s (900ms parallelized). Figured I'll look into those shoe laces everyone mentioned with the other problem and... got rid of tons of code and it runs in a little over 200us. If I ever again need the area of a concave polygon, I'll be prepared now.. Same as you, I got the area with shoe lace, added half the perimeter and added 1, not out of understanding, but because the numbers basically screamed at me to do it. I just rationalized that with the grid and integers the area effectively only includes half the perimeter and the start position adds the +1.
Elaborating the half: if I picture the outline to go through the center of each tile, then the area would be missing the outer half of the perimeter. So adding half of it would make sense.
At first, I tried keeping track of all of the grid points on the perimeter, and the odd/even crossing logic for interior/exterior (what you eventually got working). I flailed around trying to account for the horizontal lines, and finally gave up on that approach. As I was trying to figure out that logic, I wrote a quick Python script to draw turtle graphics based on the input, so I could visualize the shape. Then I switched to a semi-brute force approach of keeping track of the input line segments, looping over all possible y values, but looking at pairs of vertical lines that intersect the given y value (and subtracting for horizontal lines that have the same y value and are between the two vertical lines). That worked pretty quickly. To my surprise, that semi-brute force approach completed in a reasonable time (under 5 seconds in release mode) for part 2. I'm pretty sure I could speed that up by processing ranges of y values (between two horizontal lines) all at once -- essentially breaking up the shape into rectangles. But I'll leave that to a later time, and work on the other AoC days that I haven't finished yet. I was afraid that the hex stuff was going to be depth, and we were going to need to compute volume of the pit. Glad I was wrong! 😅
I converted the instructions into vertices on the outside of the polygon (assuming clockwise winding and no self-crossings this was only 8 cases), then I collected all the horizontal spans (y, x0, x1), sorted them, and then looped over them from top to bottom, keeping a tally of the current total width of the polygon by adding the width of the spans (positive for spans going right, negative for spans going left), and multiplying the width with the vertical distance from the last horizontal span. Not my first attempt at a solution but it turned out pretty elegant, I think. It handles part 2 just as fast as part 1 because it doesn't care about the size of the numbers involved. Runtime is about 1.1ms, according to hyperfine.
Man the whole video I’ve been wanting to comment: “use shoelace theorem and pick’s theorem”, but you somehow managed to get it to work in the end. 👍 The area formula you used was the shoelace theorem. The area you got from that can be used in the pick’s theorem which is: area = I + (B/2) - 1, where I is the grid points in the polygon and B is the parameter. Solve for I, and the number of points in the lagoon is I + the parameter. Also fun fact: the same formulas could’ve been used to solve the pipe maze problem from day 10
It was definitely one of those days 😅 with 20/20 hindsight I obviously took the wrong approach to start, but I really thought we were going to have to actually use the colors in part 2 to color pixels or similar. I have a bit further to go in understanding shoelace/picks but I definitely learned something today! I'll have to try to go back to day 10 and apply this.
You need to take the abs() of the area/2 before adding perimeter/2 + 1. If you were to go through the vertices in the reverse direction, you'd end up adding a negative area to a positive perimeter, and then taking abs(), which would be the wrong result.
BTW, I've been keeping up with your entire series of AoC this year. Each day, I first solve it myself - and then only after solving it, I'll take a look at how you approached the problem. Thanks for sharing your solutions (and struggles)!
I initially tried to create a giant 1024x1024 boolean grid and solve with the crossing rules like you did and it didnt work at all, basically, not enough context from a single # or even a couple of them, so I changed it to be in the same format as day 10,cropped it and ran the day 10 algorithm on it. Then for part 2 this obviously doesnt work and I found out about shoelace and Pick's and applied it to both. Ill go back to apply it to day 10 eventually.
The colors were such a red herring. I went with a scanline approach, because it felt natural for filling a polygon. After all the tricks I could think of, part 2 still took 5s (900ms parallelized). Figured I'll look into those shoe laces everyone mentioned with the other problem and... got rid of tons of code and it runs in a little over 200us. If I ever again need the area of a concave polygon, I'll be prepared now..
Same as you, I got the area with shoe lace, added half the perimeter and added 1, not out of understanding, but because the numbers basically screamed at me to do it. I just rationalized that with the grid and integers the area effectively only includes half the perimeter and the start position adds the +1.
Elaborating the half: if I picture the outline to go through the center of each tile, then the area would be missing the outer half of the perimeter. So adding half of it would make sense.
The +1 actually comes from arranging the formula correctly, you're supposed to solve for i, not for A, I made the same mistake.
At first, I tried keeping track of all of the grid points on the perimeter, and the odd/even crossing logic for interior/exterior (what you eventually got working). I flailed around trying to account for the horizontal lines, and finally gave up on that approach. As I was trying to figure out that logic, I wrote a quick Python script to draw turtle graphics based on the input, so I could visualize the shape.
Then I switched to a semi-brute force approach of keeping track of the input line segments, looping over all possible y values, but looking at pairs of vertical lines that intersect the given y value (and subtracting for horizontal lines that have the same y value and are between the two vertical lines). That worked pretty quickly.
To my surprise, that semi-brute force approach completed in a reasonable time (under 5 seconds in release mode) for part 2. I'm pretty sure I could speed that up by processing ranges of y values (between two horizontal lines) all at once -- essentially breaking up the shape into rectangles. But I'll leave that to a later time, and work on the other AoC days that I haven't finished yet.
I was afraid that the hex stuff was going to be depth, and we were going to need to compute volume of the pit. Glad I was wrong! 😅
I converted the instructions into vertices on the outside of the polygon (assuming clockwise winding and no self-crossings this was only 8 cases), then I collected all the horizontal spans (y, x0, x1), sorted them, and then looped over them from top to bottom, keeping a tally of the current total width of the polygon by adding the width of the spans (positive for spans going right, negative for spans going left), and multiplying the width with the vertical distance from the last horizontal span.
Not my first attempt at a solution but it turned out pretty elegant, I think. It handles part 2 just as fast as part 1 because it doesn't care about the size of the numbers involved. Runtime is about 1.1ms, according to hyperfine.
Man the whole video I’ve been wanting to comment: “use shoelace theorem and pick’s theorem”, but you somehow managed to get it to work in the end. 👍
The area formula you used was the shoelace theorem. The area you got from that can be used in the pick’s theorem which is: area = I + (B/2) - 1, where I is the grid points in the polygon and B is the parameter. Solve for I, and the number of points in the lagoon is I + the parameter.
Also fun fact: the same formulas could’ve been used to solve the pipe maze problem from day 10
It was definitely one of those days 😅 with 20/20 hindsight I obviously took the wrong approach to start, but I really thought we were going to have to actually use the colors in part 2 to color pixels or similar.
I have a bit further to go in understanding shoelace/picks but I definitely learned something today! I'll have to try to go back to day 10 and apply this.
You need to take the abs() of the area/2 before adding perimeter/2 + 1. If you were to go through the vertices in the reverse direction, you'd end up adding a negative area to a positive perimeter, and then taking abs(), which would be the wrong result.
BTW, I've been keeping up with your entire series of AoC this year. Each day, I first solve it myself - and then only after solving it, I'll take a look at how you approached the problem. Thanks for sharing your solutions (and struggles)!
I initially tried to create a giant 1024x1024 boolean grid and solve with the crossing rules like you did and it didnt work at all, basically, not enough context from a single # or even a couple of them, so I changed it to be in the same format as day 10,cropped it and ran the day 10 algorithm on it.
Then for part 2 this obviously doesnt work and I found out about shoelace and Pick's and applied it to both.
Ill go back to apply it to day 10 eventually.