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
```

</details>
``````

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

1. [7]
first-must-burn
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
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
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
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.)

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

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
``````
1. first-must-burn
Impressive, and still pretty brief compared to my code!

Impressive, and still pretty brief compared to my code!

1 vote
3. first-must-burn