8
votes
Day 18: Lavaduct Lagoon
Today's problem description: https://adventofcode.com/2023/day/18
Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python
with any of the "short names" listed in this page of supported languages):
<details>
<summary>Part 1</summary>
```python
Your code here.
```
</details>
Part 2 minor spoiler discussion
Well, for part 2 I didn't have quite the right answer, but I suspected kind of what was going wrong. So I tried to fix it. But that didn't work. So then I added a factor of 2 to the thing it was off by, and it was off by 1. So then I added one. And then it was correct on both the test & input cases!
Do I know why it was off by the factor of 2 or 1? Nope!!
Part 1
Did a straightforward flood fill here, using my Grid class. But my Grid class is very new and I had a small mistake in it so I had to workaround it. The thing is, I tested this and it seemed right so idk what is going on?? Need to look at this now.edit: fixed,
I did look at the result by zooming way out in notepad++ and clicking randomly in the center to find a valid starting square for my flood fill.
Part 2
Honestly...I asked ChatGPT what algorithm to use to find the area inside of a list of points. I thought it was going to be somewhat similar to the expanding galaxies one, but I couldn't figure it out on my own and idk DSA that well. It said to use Shoelace so I was like "sure why not" but I got the wrong input from the test.I thought it was an off by "1" for the perimeter, but adding the perimeter to the answer didn't work. So then I was like "YOLO divide by 2" and then it was only off by 1 so I just /2 the perimeter and then +1 and it was correct for the main input. Yay!
Python solutions
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah to avoid spoiler leakage.
Spoiler
I didn't look at your solutions, but is it possible you're missing the 1/2 in the shoelace algorithm formula?
https://artofproblemsolving.com/wiki/index.php?title=Shoelace_Theorem
The +1 is more mysterious. Possibly rounding error?
oh I didn't know you had to do that to avoid spoilers in push notifications! Here's some more text too
Part 1
It's not that the area was off by 2, but I was trying area/2 + perimeter + 1...but the correct answer was area/2 + perimeter/2 + 1.I'm guessing that you actually do count the perimeter once when doing shoelace, and it's only the "opposite" sides you have to count? So that's why you do perimeter/2 ? But honestly I'm not sure haha
The leakage appears in the summary when the comment is collapsed -- it ignores the spoiler tag. I filed a bug for it though.
Spoiler
Interesting. I was thinking of the path as a thin line, and I expanded it by 0.5 to run the shoelace on the whole area. But if you didn't do that, then you captured the inside half of the perimeter blocks in the shoelace, so it makes sense that adding half the perimeter would be approximately the solution.
If the perimeter was exactly a rectangle, then the +1 would be the "extra" 0.25 in the four corners. The fact that it worked in the test and the answer suggests there's some property of the closed shape so that the other corners cancel. Pretty neat.
Spoiler
If you calculate the area of the perimeter line by `end - start`, you're going from the center of one cell to the center of the other cell, which doesn't account for the half a cell before the center of the first cell or the half a cell after the center of the second cell. Since you're dividing the area in half (to only count the outside), you're missing the very first quarter cell and the last quarter cell.To illustrate this a bit, consider the following square area:
The dots are the interior of the polygon, and are what you calculate with the shoelace algorithm. The parts marked with “e” are what you get by taking the half the length of the perimeter. The question marks are what's left over. The leftover part will always be a unit square, because the perimeter makes a complete circuit. (If there are other points, you'll get a mixture of concave corners, where the perimeter area double-counts the corner, and convex corners, where the perimeter area misses a corner. There will always be exactly four corners more that are missed than were double-counted, because the sum of the exterior angles of a polygon is always 360 degrees.)
Excellent explanation. Thank you!
Ahh, yeah that makes sense -
Part 1
How did you increase the boundary by .5? I actually considered doing something like that but it seemed pretty hard to tell inside from outside as it turns.
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah to avoid spoiler leakage.
Part 1
It actually wasn't too bad. There are just 8 cases for the direction before and after the corner (the direction of the N and N+1 instruction): NxE, NxW, SxE, SxW, ExN, ExS, WxN, and was. Each one is always the same positive or negative delta for X and Y.
I worked each cse out and put them in a map of the direction pair to the delta, then just run the instruction loop doing index and index+1 mod len.
That part took me surprisingly little time. It was messing around with the raycasting (that didn't scale) that took so long, but I placed about where I usually do when I start at midnight (~4k), so it must have been pretty challenging for most people.
Quite a tricky part 2! My earlier attempts at brevity have gone out the window, but I'm happy to say I was able to come up with a solution and implement it without giving in and looking anything up.
Part 1
Nothing clever with this one, just stepped out the border into a set of coordinates and then flood-filled. I cheated a little by inspecting the border and checking where I could place the first point to ensure it was inside the bounds, so this could fail for a more generic input case.
Part 2
While probably not the most elegant solution, I'm fairly proud of coming up with this one: first I sliced the space on horizontal and vertical lines through every corner point, creating an irregular grid of rectangles. Each of these rectangles should be wholly inside or outside the shape, so I can just filter for the ones inside the shape and then add up their areas. Accounting for overlapping edges/corners was kind of a pain, but otherwise not too bad.
I'm glad I remembered a trick for identifying whether a point is inside a polygon: draw a ray from the point in any direction and count the number of edges that the ray crosses, if it's odd it's inside the shape!
Impressive, and still pretty brief compared to my code!
Golang solution
I learned something new in this one.
Discussion
The color stuff was a red herring for me. I thought part 2 was going to be growing the colors from the edges to see how many of each were in the center fill area. But also, this grid was not anchored in the positive domain, so I spent some time implementing a sparse grid class. Still getting a lot of mileage out of the Coordinate direction handling.
But instead, part 2 was just big. I spent some time on a variation of the ray cast algorithm from earlier to make an implementation that did every cell in the row in a single pass. This was a lot faster, but still not fast enough. I figured there must be a geometric solution to the problem, so I went looking and found out about the shoelace algorithm. I'm not sure I entirely understand the proof, but the formula is clear enough. From there, it was just a matter of getting points from the instructions list and expanding them to the outside corners.