2023 Day 18: Lavaduct Lagoon

[cantanima]

Part 1 was pretty straightforward.

After several hours of looking at Part 2, it looks as if I had two really good ideas, but gave up on them too early. (Short on time lately.)

My favorite idea was to (identify an end rectangle, remove it, then identify another one, then remove it, etc.). But when I applied it to the example, I realized, to my horror, that it depended on an unspoken assumption: just because two vertices share a row or column coordinate, that does not mean they are “end” rectangles; they might be “cut-ins”.. After starting at it a while and watching an hour or so go by, I despaired and gave up. I still like the idea (and apparently someone else did do it this way!), so I hope to return to it eventually.

Then I thought about trying a scanline approach: order the vertices in a certain way that would allow me to, say, scan up from minimum row value to maximum row value, counting the number of points along the way. I still like that idea, but just as I was on the verge of implementing it I got cold feet. (From what I read, at least one person did something to this effect, too.)

As the hour drew very, very late, I visited the Reddit page and learned that most people seem to be solving it using Pick’s Theorem and the Shoelace Formula… neither of which I’ve ever heard of. (I’d be embarrassed, since I have a PhD in mathematics, but someone else commented that he has a PhD in computational geometry, and he hadn’t heard of it either, so there.) But even that isn’t trivial; you can’t just copy & paste the formulas from Wikipedia. And since the same approach was useful on Day 10, these formulas may prove useful a third time.

I don’t suppose he’ll ever supply a puzzle that relies on my old research topics…

LOL, one person on the Reddit page says, “Finally, a relaxing day again…” That’s what I thought of the entire previous week between days 10 and 17…

[zertovitch]

This puzzle is similar to one of the last three years, except it is 2D instead of 3D.
A way of solving Part 2 is to index all x-values and y-values of points appearing in the edge drawing rules encoded in the data. Actually you need to index the 9 cells around each point.
Then, you flood-fill the outside part. But not the actual points (it would be a gigantic bitmap, too large for the memory and to slow to fill); instead, you flood-fill the index map. Each cell of the index map is a rectangle in the actual bitmap. It can be a 1x1 square to a big rectangle. You sum up the rectangles’ areas that are marked “outside” from the flood-fill. Then, the giant bitmap area minus that sum is your answer.

[cantanima]

@zertovitch

Then, you flood-fill the outside part. But not the actual points (it would be a gigantic bitmap, too large for the memory and to slow to fill); instead, you flood-fill the index map.

I read that someone did something like that, but you’ve explained it much better, thanks.

@zertovitch

This puzzle is similar to one of the last three years, except it is 2D instead of 3D.

The 3d puzzles always give me a hard time, so you’d think I’d learn. Nope. I’ve gotten to the point where as soon as I see a 3d puzzle in Advent of Code, I…

[cantanima]

@cantanima

My favorite idea was to ( identify an end rectangle, remove it, then identify another one, then remove it, etc. )

FInally got this working! Here’s some more detail on what I meant.

Consider the following diagram (gee, where did it come from):

+--------+    +---+
|        |    |   |
|        |    |   |
|        |    |   |
|        +----+   |
|                 |
|                 |
|                 |
|   +-----+       |
|   |     |       |
|   |     |   +---+
|   |     |   |
+---+     +---+

The idea is to find a “table” that “sticks out”, then “munch” it, like so.

2--------3    +---+
|XXXXXXXX|    |   |
|XXXXXXXX|    |   |
|XXXXXXXX|    |   |
+--------4----+   |
|                 |
|                 |
|                 |
|   +-----+       |
|   |     |       |
|   |     |   +---+
|   |     |   |
1---+     +---+

Numbers indicate how the implementation labels vertices. Notice that 1 and 4 do not line up; that’s common, but 2 and 3 must always align on a row or column.

The area of the entire “meal” is the sum of all the munches.

We have to be a little careful, since we don’t want to add the notches,
and we also have to watch out for situations where we try to munch a notched table:

2-----------------3
|XXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXX|
|XXXXXXXXXXXXXXXXX|
|XXX+-----+XXXXXXX|
|XXX|XXXXX|XXXXXXX|
|   |  |  |   +---4
|   |oops!|   |
1---+     +---+

True, Pick’s Theorem with the Shoelace Formula is probably easier and faster, but I really like this.