Python

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

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

Rust

use std::fs;
use std::path::PathBuf;

use clap::Parser;

#[derive(Parser)]
#[command(author, version, about, long_about = None)]
struct Cli {
    /// A file containing the input
    input_file: PathBuf,

    #[arg(short, long)]
    part: Option,
}

fn main() {
    // Parse CLI arguments
    let cli = Cli::parse();

    // Read file
    let input_text = fs::read_to_string(&cli.input_file)
        .expect(format!("File \"{}\" not found", cli.input_file.display()).as_str());

    let (run_part_1, run_part_2) = if let Some(part) = cli.part {
        match part {
            1 => (true, false),
            2 => (false, true),
            _ => unimplemented!(),
        }
    } else {
        (true, true)
    };
    let (it1, it2) = preprocess(&input_text);

    if run_part_1 {
        let solution = solve(it1);
        println!("Part 1: {solution}");
    }
    if run_part_2 {
        let solution = solve(it2);
        println!("Part 2: {solution}");
    }
}

/// Preprocessing for solving
/// Extracts important information from the input
/// `part` specifies which part to preprocess for.
/// Returns a vector for each part containing a direction and amount
fn preprocess(input: &str) -> (Vec<((isize, isize), isize)>, Vec<((isize, isize), isize)>) {
    let it = input.lines().map(|l| {
        let line: Vec<_> = l.split(' ').collect();
        let direction: char = line[0].chars().nth(0).unwrap();
        let amount: isize = line[1].parse().unwrap();
        let color: &str = &line[2][2..8];

        let direction = match direction {
            'R' => (1, 0),
            'L' => (-1, 0),
            'U' => (0, 1),
            'D' => (0, -1),
            _ => unreachable!(),
        };

        ((direction, amount), {
            let amount: isize = isize::from_str_radix(&color[..5], 16).unwrap();
            let direction = match &color[5..] {
                "0" => (1, 0),
                "1" => (0, -1),
                "2" => (-1, 0),
                "3" => (0, 1),
                _ => unreachable!(),
            };
            (direction, amount)
        })
    });

    let it1 = it.clone().map(|(i1, _i2)| i1).collect();
    let it2 = it.map(|(_i1, i2)| i2).collect();

    (it1, it2)
}

/// Finds the area using the shoelace formula
fn solve(it: Vec<((isize, isize), isize)>) -> isize {
    // Get coordinates from it
    let mut coords: Vec<(isize, isize)> = Vec::with_capacity(it.len() + 1);

    // Start at (0, 0)
    coords.push((0, 0)); // Needs to be at both begining and end
    let (mut x, mut y) = (0, 0);

    let mut perimeter_length = 0;

    // Compute and add the coords
    for (direction, amount) in it {
        let translation = (direction.0 * amount, direction.1 * amount);
        x += translation.0;
        y += translation.1;

        coords.push((x, y));
        perimeter_length += amount;
    }

    // Should end where it started
    assert_eq!(coords.last().unwrap(), &(0, 0));

    // Shoelace formula
    let a = coords
        .iter()
        .zip(coords.iter().skip(1))
        .map(|((x1, y1), (x2, y2))| (x1 * y2) - (x2 * y1))
        .sum::()
        / 2;

    // Found by drawing, then trial and error
    // Shoelace area missing 1/2 of perimeter
    // Inside and outside corners cancel out except for one
    a.abs() + perimeter_length / 2 + 1
}

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

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.

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{}, &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>

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