# 2023 Day 18: Lavaduct Lagoon

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â€¦

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.

1 Like

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

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â€¦

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.