๐ถ - 2023 DAY 18 SOLUTIONS -๐ถ

๐ถ - 2023 DAY 18 SOLUTIONS -๐ถ

# Day 18: Lavaduct Lagoon

## Megathread guidelines

- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

## FAQ

- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465

# Python

Also on Github

0.09 line-seconds (third simplest after days 6 and 2).

`from .solver import Solver class Day18(Solver): def __init__(self): super().__init__(18) def presolve(self, input: str): self.lines = input.splitlines() def solve_first_star(self): commands = [] for line in self.lines: direction, distance, *_ = line.split(' ') commands.append((direction, int(distance))) return self._solve(commands) def solve_second_star(self): commands = [] for line in self.lines: _, _, command = line.split(' ') distance = int(command[2:-2], 16) direction = ('R', 'D', 'L', 'U')[int(command[-2])] commands.append((direction, distance)) return self._solve(commands) def _solve(self, commands: list[tuple[str, int]]): points: list[tuple[int, int]] = [(0, 0)] perimeter_integer_points = 1 x, y = 0, 0 for direction, distance in commands: dx, dy = {'R': (1, 0), 'L': (-1, 0), 'U': (0, -1), 'D': (0, 1)}[direction] x, y = x + dx * distance, y + dy * distance perimeter_integer_points += distance points.append((x, y)) last_x, last_y = points[-1] perimeter_integer_points += abs(last_x) + abs(last_y) - 1 area_x2 = sum((points[i][1] + points[(i+1) % len(points)][1]) * (points[i][0] - points[(i+1) % len(points)][0]) for i in range(len(points))) interior_integer_points = (area_x2 - perimeter_integer_points) // 2 + 1 return interior_integer_points + perimeter_integer_points`

# Nim

Decided to go for a polygon approach for part 1 using the Shoelace formula to calculate the area. This meant part 2 only resulted in larger values, no additional computation.

Code runs in <1ms for part 1 and 2 combined

Shoelace formula

This would have been really useful to know about. I've committed to a certain level of wheel-reinvention for this event unless I get really stuck, but I'm sure it'll come up again in the future.

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

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.

### C

Fun and interesting puzzle! In part 1 I fumbled a bit trying to implement even/odd outside/inside tracking before realizing that wouldn't work for this shape and just did the flood fill.

For part 2 I correctly guessed that like the intersecting cuboids (2021 day 22) it would be about finding a better representation for the grid or avoiding representing it entirely. Long story shorter:

`/* * Conceptually: the raw map, which is too large to fit directly in * memory for part 2, is made much smaller by collapsing (and counting) * identical rows and columns. Another way to look it at is that a grid * is fitted to make 'opaque' cells. * | |#|##|# * For example: -+---+-+--+- * #|###|#| |# * #### ### 1 -+---+-+--+- * ##### # ### # 1 #| | | |# * # # becomes # # 2 or: #| | | |# * # # ##### 1 -+---+-+--+- * ######## 13121 #|###|#|##|# * * To avoid a lot of complex work, instead of actually collapsing and * splitting rows and columns, we first generate the wall rectangles and * collect the unique X and Y coordinates. Those are locations of our * virtual grid lines. */`

Despite being quite happy with this solution, I couldn't help but notice the brevity and simplicity of the other solutions here. Gonna have a look what's happening there and see if I can try that approach too.

(Got bitten by a nasty overflow btw, the list of unique X coordinates was overwriting the list of unique Y coordinates. Oh well, such is the life of a C programmer.)

Oh, just like day 11! I hadn't thought of that. I was initially about to try something similar by separating into rectangular regions, as in ear-clipping triangulation. But that would require a lot of iterating, and something about "polygon" and "walking the edges" went ping in my memory...

### Haskell

`import Data.ByteString.Char8 (unpack) import Data.Char (isDigit, isHexDigit) import Relude import qualified Relude.Unsafe as Unsafe import Text.ParserCombinators.ReadP data Dir = R | D | L | U deriving (Show, Eq) type Pos = (Int, Int) data Action = Action Dir Int deriving (Show, Eq) parse :: ByteString -> Maybe [(Action, Action)] parse = fmap fst . viaNonEmpty last . readP_to_S (sepBy1 parseAction (char '\n') <* char '\n' <* eof) . unpack where parseAction = do dir <- choice [U <$ char 'U', D <$ char 'D', L <$ char 'L', R <$ char 'R'] <* char ' ' x <- Unsafe.read <$> munch1 isDigit <* char ' ' y <- char '(' *> char '#' *> (Unsafe.read . ("0x" ++) <$> count 5 (satisfy isHexDigit)) dir' <- choice [R <$ char '0', D <$ char '1', L <$ char '2', U <$ char '3'] <* char ')' return (Action dir x, Action dir' y) vertices :: [Action] -> [Pos] vertices = scanl' (flip step) origin where step (Action U n) = first $ subtract n step (Action D n) = first (+ n) step (Action L n) = second $ subtract n step (Action R n) = second (+ n) origin :: Pos origin = (0, 0) area, perimeter, solve :: [Action] -> Int area a = (`div` 2) . abs . sum $ zipWith (-) x y where (p, rp) = (origin :) &&& (++ [origin]) $ vertices a x = zipWith (*) (fst <$> p) (snd <$> rp) y = zipWith (*) (snd <$> p) (fst <$> rp) perimeter = sum . fmap (\(Action _ n) -> n) solve = area &&& (`div` 2) . perimeter >>> uncurry (+) >>> succ part1, part2 :: [(Action, Action)] -> Int part1 = solve . fmap fst part2 = solve . fmap snd`

### Haskell

Wasn't able to start on time today, but this was a fun one! Got to apply the two theorems I learned from somebody else's solution to Day 10.

## Solution

`import Data.Char import Data.List readInput :: String -> (Char, Int, String) readInput s = let [d, n, c] = words s in (head d, read n, drop 2 $ init c) boundary :: [(Char, Int)] -> [(Int, Int)] boundary = scanl' step (0, 0) where step (x, y) (d, n) = let (dx, dy) = case d of 'U' -> (0, 1) 'D' -> (0, -1) 'L' -> (-1, 0) 'R' -> (1, 0) in (x + n * dx, y + n * dy) area :: [(Char, Int)] -> Int area steps = let a = -- shoelace formula (abs . (`quot` 2) . sum) . (zipWith (\(x, y) (x', y') -> x * y' - x' * y) <*> tail) $ boundary steps in a + 1 + sum (map snd steps) `quot` 2 -- Pick's theorem part1, part2 :: [(Char, Int, String)] -> Int part1 = area . map (\(d, n, _) -> (d, n)) part2 = area . map (\(_, _, c) -> decode c) where decode s = ("RDLU" !! digitToInt (last s), read $ "0x" ++ init s) main = do input <- map readInput . lines <$> readFile "input18" print $ part1 input print $ part2 input`

# C++

No scala today

`#include #include #include <map> #include #include #include #include #include #include #include #include struct HorizontalEdge { boost::icl::discrete_interval x; long y; }; long area(std::vector he) { if(he.empty()) return 0; boost::icl::interval_set intervals; std::ranges::sort(he, std::less{}, &HorizontalEdge::y); long area{}; long y = he.front().y; for(auto const& e : he) { area += intervals.size() * (e.y - std::exchange(y, e.y)); if(intervals.find(e.x) != intervals.end()) intervals.erase(e.x); else intervals.add(e.x); } return area; } struct Instruction { long l; int d; std::string color; }; enum Dir { R=0, U=1, L=2, D=3 }; std::unordered_map char_to_dir = {{'R', R}, {'U', U}, {'L', L}, {'D', D}}; auto transcode(std::vector const& is) { return flux::from(std::move(is)).map([](Instruction in) { long v = std::stoul(in.color.substr(0, 5), nullptr, 16); return Instruction{.l = v, .d = (4 - (in.color.at(5) - '0')) % 4, .color=""}; }).to>(); } std::vector read(std::string path) { std::ifstream in(std::move(path)); return flux::getlines(in).map([](std::string const& s) { Instruction i; char dir; if(auto r = scn::scan(s, "{} {} (#{:6})", dir, i.l, i.color)) { i.d = char_to_dir[dir]; return i; } else { throw std::runtime_error{r.error().msg()}; } }).to>(); } auto turns(std::vector is) { if(is.empty()) throw std::runtime_error{"Too few elements"}; is.push_back(is.front()); return flux::from(std::move(is)).pairwise_map([](auto const& lhs, auto const& rhs) { return (rhs.d - lhs.d + 4) % 4 == 1; }); } std::vector toEdges(std::vector is, bool left) { std::vector res; long x{}, y{}; auto t = turns(is).to>(); // some magic required to turn the ### path into its outer edge // (which is the actual object we want to compute the area for) for(size_t j = 0; j < is.size(); ++j) { auto const& i = is.at(j); bool s1 = t.at((j + t.size() - 1) % t.size()) == left; bool s2 = t.at(j) == left; long sign = (i.d == U || i.d == L) ? -1 : 1; long old_x = x; if(i.d == R || i.d == L) { x += i.l * sign; auto [l, r] = old_x < x ? std::tuple{old_x + !s1, x + s2} : std::tuple{x + !s2, old_x + s1}; res.push_back(HorizontalEdge{.x = {l, r, boost::icl::interval_bounds::right_open()}, .y = y}); } else { y += (i.l + s1 + s2 - 1) * sign; } } return res; } long solve(std::vector is) { auto tn = turns(is).sum() - ssize(is); return area(toEdges(std::move(is), tn > 0)); } int main(int argc, char* argv[]) { auto instructions = read(argc > 1 ? argv[1] : "../task1.txt"); auto start = std::chrono::steady_clock::now(); fmt::print("task1={}\ntask2={}\n", solve(instructions), solve(transcode(std::move(instructions)))); fmt::print("took {}\n", std::chrono::steady_clock::now() - start); } ```</map>`

looks like some broken XSS protection is killing the includes, can't really fix that