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 with O, 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.

• Day 18, part 1