aoc/year2023/
day18.rs

1//! # Lavaduct Lagoon
2//!
3//! Similar approach to [`Day 10`] using the [Shoelace formula](https://en.wikipedia.org/wiki/Shoelace_formula)
4//! and [Pick's theorem](https://en.wikipedia.org/wiki/Pick%27s_theorem).
5//!
6//! One nuance is that we want the number of interior *and* boundary points so the final formula is:
7//!
8//! `i + b => A - b / 2 + 1 + b => A + b / 2 + 1`
9//!
10//! [`Day 10`]: crate::year2023::day10
11use crate::util::iter::*;
12use crate::util::parse::*;
13use crate::util::point::*;
14
15type Move = (Point, i32);
16type Input = (Vec<Move>, Vec<Move>);
17
18pub fn parse(input: &str) -> Input {
19    input
20        .split_ascii_whitespace()
21        .chunk::<3>()
22        .map(|[a, b, c]| {
23            // Parse part one.
24            let first = (Point::from(a.as_bytes()[0]), b.signed());
25
26            // Parse part two.
27            let direction = match c.as_bytes()[7] {
28                b'0' => RIGHT,
29                b'1' => DOWN,
30                b'2' => LEFT,
31                b'3' => UP,
32                _ => unreachable!(),
33            };
34            let hex = &c[2..c.len() - 2];
35            let second = (direction, i32::from_str_radix(hex, 16).unwrap());
36
37            (first, second)
38        })
39        .unzip()
40}
41
42pub fn part1(input: &Input) -> i64 {
43    lava(&input.0)
44}
45
46pub fn part2(input: &Input) -> i64 {
47    lava(&input.1)
48}
49
50/// Find the volume of the lava which is the number of interior and boundary points.
51fn lava(moves: &[Move]) -> i64 {
52    let mut position = ORIGIN;
53    let mut area = 0;
54    let mut perimeter = 0;
55
56    for &(direction, amount) in moves {
57        let previous = position;
58        position += direction * amount;
59        area += determinant(previous, position);
60        perimeter += amount as i64;
61    }
62
63    // Pick's theorem counting both interior and boundary points.
64    area / 2 + perimeter / 2 + 1
65}
66
67/// Find the determinant of each pair of points casting to `i64` to prevent overflow.
68fn determinant(a: Point, b: Point) -> i64 {
69    (a.x as i64) * (b.y as i64) - (a.y as i64) * (b.x as i64)
70}
aoc/year2023/day18.rs

aoc/year2023/
day18.rs
