13
๐ถ - 2023 DAY 18 SOLUTIONS -๐ถ
(programming.dev)
An unofficial home for the advent of code community on programming.dev!
Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.
Solution Threads
M | T | W | T | F | S | S |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 |
Icon base by Lorc under CC BY 3.0 with modifications to add a gradient
console.log('Hello World')
Nim
I am not making good time on these anymore.
For part 1, I walked through the dig plan instructions, keeping track of the highest and lowest x and y values reached, and used those to create a character grid, with an extra 1 tile border around it. Walked the instructions again to plot out the trench with
#
, flood-filled the exterior withO
, and then counted the non-O
tiles. Sort of similar to the pipe maze problem.This approach wouldn't have been viable for part 2, due to the scale of the numbers involved. Instead I counted the number of left and right turns in the trench to determine whether it was being dug in a clockwise or counterclockwise direction, and assumed that there were no intersections. I then made a polygon that followed the outer edge of the trench. Wherever there was a run of 3 inward turns in a row, that meant there was a rectangular protrusion that could be chopped off of the main polygon. Repeatedly chopping these off eventually turns the polygon into a rectangle, so it's just a matter of adding up the area of each. This worked great for the example input.
Unfortunately when I ran it on the actual input, I ran out of sets of inward turns early, leaving an "inside out" polygon. I thought this meant that the input must have intersections in it that I would have to untwist somehow. To keep this short, after a long debugging process I figured out that I was introducing intersections during the chopping process. The chopped regions can have additional trench inside of them, which results in those parts ending up outside of the reduced polygon. I solved this by chopping off the narrowest protrusions first.
Good job on persevering with this one. Your approach for part 2 sounds quite viable, it is very similar to the Ear clipping method for triangulating a polygon.
Yeah, I read up on ear clipping for a small game dev project a while back, though I don't remember if I actually ended up using it. So my solution is inspired by what I remember of that.