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#Trapezoid_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, i64);
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..7];
35 let second = (direction, i64::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 height = 0;
53 let mut half_area = 0;
54 let mut perimeter = 0;
55
56 // Instead of computing the area by the shoelace formula (a determinant per vertex), it is
57 // faster to use the trapezoid formula: sum((y[i]+y[i+1])*(x[i]-x[i+1])). But all vertical
58 // segments have x[i]-x[i+1]=0, so only the horizontal segments, where y[i]+y[i+1]=2y,
59 // actually contribute to the area.
60 for &(direction, amount) in moves {
61 half_area += amount * height * direction.x as i64;
62 height += amount * direction.y as i64;
63 perimeter += amount;
64 }
65
66 // Pick's theorem counting both interior and boundary points.
67 half_area.abs() + perimeter / 2 + 1
68}