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>

11 comments

  1. [8]
    RheingoldRiver
    (edited )
    Link
    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...
    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

    3 votes
    1. [7]
      first-must-burn
      Link Parent
      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...

      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?

      1. [6]
        RheingoldRiver
        Link Parent
        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...

        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

        1. [5]
          first-must-burn
          Link Parent
          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...

          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.

          1 vote
          1. [2]
            asciipip
            Link Parent
            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...
            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:

            +-----+-----+-----+
            |??eee|eeeee|eee??|
            |ee*-----------*ee|
            |ee|..|.....|..|ee|
            +--|--+-----+--|--+
            |ee|..|.....|..|ee|
            |ee|..|.....|..|ee|
            |ee|..|.....|..|ee|
            +--|--+-----+--|--+
            |ee|..|.....|..|ee|
            |ee*-----------*ee|
            |??eee|eeeee|eee??|
            +-----+-----+-----+
            

            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.)

            4 votes
          2. [2]
            RheingoldRiver
            Link Parent
            Ahh, yeah that makes sense - Part 1 1/2 of each of the perimeter cells, and + 1/4 each of the corner cells. And there happen to be 4 corners, so it's +1. How did you increase the boundary by .5? I...

            Ahh, yeah that makes sense -

            Part 1
            • 1/2 of each of the perimeter cells, and + 1/4 each of the corner cells. And there happen to be 4 corners, so it's +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.

            1. first-must-burn
              Link Parent
              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...

              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.

  2. [2]
    scarecrw
    Link
    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...

    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.

    type Instruction = (Direction, Integer)
    data Direction = North | South | East | West deriving (Eq, Show)
    type Coord = (Integer, Integer)
    type TrenchMap = Set Coord
    
    moveDirN :: Integer -> Direction -> Coord -> Coord
    moveDirN n North (r, c) = (r-n, c)
    moveDirN n South (r, c) = (r+n, c)
    moveDirN n East (r, c) = (r, c+n)
    moveDirN n West (r, c) = (r, c-n)
    
    moveDir :: Direction -> Coord -> Coord
    moveDir = moveDirN 1
    
    neighbors :: Coord -> [Coord]
    neighbors (r, c) = [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]
    
    parseInput1 :: String -> [Instruction]
    parseInput1 input = map parseRow (lines input) where
        parseRow row = (direction, distance) where
            [dir, dist, col] = words row
            direction = case head dir of
                'R' -> East
                'L' -> West
                'U' -> North
                'D' -> South
            distance = read dist
    
    solve1 :: [Instruction] -> Int
    solve1 input = result where
        trench = digTrench (0, 0) Set.empty input
        fill = floodFill (1, 1) trench
        result = Set.size fill + Set.size trench
        digTrench :: Coord -> Set Coord -> [Instruction] -> Set Coord
        digTrench _ trenchMap [] = trenchMap
        digTrench pos trenchMap ((direction, distance):xs) = digTrench pos' trenchMap' xs where
            (pos', trenchMap') = digLine pos trenchMap distance
            digLine p tMap 0 = (p, tMap)
            digLine p tMap d = digLine (moveDir direction p) (Set.insert p tMap) (d-1)
    
    floodFill :: Coord -> Set Coord -> Set Coord
    floodFill startingPos walls = flood [startingPos] walls Set.empty where
        flood [] _ seen = seen
        flood (x:xs) walls seen
            | Set.member x seen = flood xs walls seen
            | Set.member x walls = flood xs walls seen
            | otherwise = flood (neighbors x ++ xs) walls (Set.insert x seen)
    
    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!

    type Rectangle = (Coord, Coord)
    type Line = (Coord, Coord)
    
    area :: Rectangle -> Integer
    area ((r1, c1), (r2, c2)) = (r2 - r1 + 1) * (c2 - c1 + 1)
    
    lineLength :: Line -> Integer
    lineLength ((r1, c1), (r2, c2))
        | r1 == r2 = abs (c2 - c1) + 1
        | c1 == c2 = abs (r2 - r1) + 1
        | otherwise = error "not a line"
    
    rectangleCorners :: Rectangle -> [Coord]
    rectangleCorners((r1, c1), (r2, c2)) = [(r1, c1), (r1, c2), (r2, c1), (r2, c2)]
    
    rectangleLines :: Rectangle -> [Line]
    rectangleLines ((r1, c1), (r2, c2)) = [
        ((r1, c1), (r1, c2)), 
        ((r1, c1), (r2, c1)), 
        ((r1, c2), (r2, c2)), 
        ((r2, c1), (r2, c2))
        ]
    
    parseInput2 :: String -> [Instruction]
    parseInput2 input = map parseRow (lines input) where
        parseRow row = (direction, distance) where
            row' = dropWhile (/='#') row
            dir = row' !! 6
            dist = take 5 $ drop 1 row'
            direction = case dir of
                '0' -> East
                '1' -> South
                '2' -> West
                '3' -> North
            distance = parseHex dist
    
    solve2 :: [Instruction] -> Integer
    solve2 input = filledArea - lineCorrection + pointCorrection where
        corners = findCorners (0, 0) input []
        rows = (Set.elems . Set.fromList) $ map fst corners
        cols = (Set.elems . Set.fromList) $ map snd corners
        rectangles = [((r1, c1), (r2, c2)) | (r1, r2) <- zip rows (tail rows), (c1, c2) <- zip cols (tail cols)]
        filledRectangles = filter inShape rectangles
    
        findCorners p [] pts = p : pts
        findCorners p ((dir, dist):inst) pts = findCorners (moveDirN dist dir p) inst (p : pts)
    
        filledArea = sum (map area filledRectangles)
        lineCorrection = findLineCorrection filledRectangles Set.empty
        pointCorrection = findPointCorrection filledRectangles
    
        inShape :: Rectangle -> Bool
        inShape ((r1, c1), (r2, c2)) = crossCount `mod` 2 == 1 where
            rAvg = (r1 + r2) `div` 2
            cAvg = (c1 + c2) `div` 2
            crossCount = length $ filter crossRight (zip corners (tail corners))
            crossRight ((r1, c1), (r2, c2)) = min r1 r2 < rAvg && rAvg < max r1 r2 && c1 > cAvg
    
        findLineCorrection :: [Rectangle] -> Set Line -> Integer
        findLineCorrection [] _ = 0
        findLineCorrection (rect:rects) seen = n + findLineCorrection rects seen' where
            seen' = foldr Set.insert seen $ rectangleLines rect
            n = sum $ map lineLength $ filter (`Set.member` seen) $ rectangleLines rect
    
        findPointCorrection :: [Rectangle] -> Integer
        findPointCorrection rects = pntCorrect allPoints where
            allPoints = concatMap rectangleCorners rects
            pntCorrect :: [Coord] -> Integer
            pntCorrect = genericLength . filter (==4) . Map.elems . counts
    
    2 votes
    1. first-must-burn
      Link Parent
      Impressive, and still pretty brief compared to my code!

      Impressive, and still pretty brief compared to my code!

      1 vote
  3. first-must-burn
    Link
    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...

    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.

    1 vote