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    let mut first = Vec::with_capacity(1000);
20    let mut second = Vec::with_capacity(1000);
21
22    for [a, b, c] in input.split_ascii_whitespace().chunk::<3>() {
23        // Parse part one
24        let direction = Point::from(a.as_bytes()[0]);
25        let amount = b.signed();
26        first.push((direction, amount));
27
28        // Parse part two
29        let direction = match c.as_bytes()[7] {
30            b'0' => RIGHT,
31            b'1' => DOWN,
32            b'2' => LEFT,
33            b'3' => UP,
34            _ => unreachable!(),
35        };
36        let hex = &c[2..c.len() - 2];
37        let amount = i32::from_str_radix(hex, 16).unwrap();
38        second.push((direction, amount));
39    }
40
41    (first, second)
42}
43
44pub fn part1(input: &Input) -> i64 {
45    lava(&input.0)
46}
47
48pub fn part2(input: &Input) -> i64 {
49    lava(&input.1)
50}
51
52/// Find the volume of the lava which is the number of interior and boundary points.
53fn lava(moves: &[Move]) -> i64 {
54    let mut previous;
55    let mut position = ORIGIN;
56    let mut area = 0;
57    let mut perimeter = 0;
58
59    for &(direction, amount) in moves {
60        previous = position;
61        position += direction * amount;
62        area += determinant(previous, position);
63        perimeter += amount as i64;
64    }
65
66    // Pick's theorem counting both interior and boundary points.
67    area / 2 + perimeter / 2 + 1
68}
69
70/// Find the determinant of each pair of points casting to `i64` to prevent overflow.
71fn determinant(a: Point, b: Point) -> i64 {
72    (a.x as i64) * (b.y as i64) - (a.y as i64) * (b.x as i64)
73}
aoc/year2023/day18.rs

aoc/year2023/
day18.rs
