Skip Navigation

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

15
15 comments
  • 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

    Source

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

      • This was actually something I learned for my job, it was nice to be able to apply it here.

        I like your commitment to wheel-reinvention, it can be a lot more fun than going for an existing or 'intended' approach.

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

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

    https://github.com/sjmulder/aoc/blob/master/2023/c/day18.c

    • 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') &lt;* char '\n' &lt;* eof) . unpack
      where
        parseAction = do
          dir &lt;- choice [U &lt;$ char 'U', D &lt;$ char 'D', L &lt;$ char 'L', R &lt;$ char 'R'] &lt;* char ' '
          x &lt;- Unsafe.read &lt;$> munch1 isDigit &lt;* char ' '
          y &lt;- char '(' *> char '#' *> (Unsafe.read . ("0x" ++) &lt;$> count 5 (satisfy isHexDigit))
          dir' &lt;- choice [R &lt;$ char '0', D &lt;$ char '1', L &lt;$ char '2', U &lt;$ char '3'] &lt;* 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 :) &amp;&amp;&amp; (++ [origin]) $ vertices a
        x = zipWith (*) (fst &lt;$> p) (snd &lt;$> rp)
        y = zipWith (*) (snd &lt;$> p) (fst &lt;$> rp)
    perimeter = sum . fmap (\(Action _ n) -> n)
    solve = area &amp;&amp;&amp; (`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) &lt;*> 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 &lt;- map readInput . lines &lt;$> 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{}, &amp;HorizontalEdge::y);
        long area{};
        long y = he.front().y;
    
        for(auto const&amp; 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&amp; 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&amp; 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&amp; lhs, auto const&amp; 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 &lt; is.size(); ++j) {
            auto const&amp; 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 &lt; 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>
15 comments