aoc/year2023/
day10.rs

1//! # Pipe Maze
2//!
3//! This solution uses 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//! Starting at `S` we trace out the path followed by the pipes. Each corner piece
7//! (`7`, `F`, `J`, `L` and finally `S`) is considered a vertex and added to the running total
8//! for the area using the Shoelace formula. Additionally we keep track of the perimeter length.
9//!
10//! As the path is a loop the answer for part one is half the perimeter length.
11//!
12//! The answer for part two is the number of interior points. Rearranging Pick's theorem:
13//!
14//! `A = i + b / 2 - 1 => i = A - b / 2 + 1`
15use crate::util::grid::*;
16use crate::util::point::*;
17
18type Input = (i32, i32);
19
20pub fn parse(input: &str) -> Input {
21    let grid = Grid::parse(input);
22    let determinant = |a: Point, b: Point| a.x * b.y - a.y * b.x;
23
24    // Find the starting position and direction.
25    let mut corner = grid.find(b'S').unwrap();
26    let mut direction = if matches!(grid[corner + UP], b'|' | b'7' | b'F') { UP } else { DOWN };
27    let mut position = corner + direction;
28    // Incrementally add up both perimeter and area.
29    let mut steps = 1;
30    let mut area = 0;
31
32    loop {
33        // Follow straight paths.
34        while grid[position] == b'-' || grid[position] == b'|' {
35            position += direction;
36            steps += 1;
37        }
38
39        // Change direction at corner pieces.
40        direction = match grid[position] {
41            b'7' if direction == UP => LEFT,
42            b'F' if direction == UP => RIGHT,
43            b'J' if direction == DOWN => LEFT,
44            b'L' if direction == DOWN => RIGHT,
45            b'J' | b'L' => UP,
46            b'7' | b'F' => DOWN,
47            _ => {
48                // We've looped all the way back to the start.
49                area += determinant(corner, position);
50                break;
51            }
52        };
53
54        area += determinant(corner, position);
55        corner = position;
56        position += direction;
57        steps += 1;
58    }
59
60    let part_one = steps / 2;
61    let part_two = area.abs() / 2 - steps / 2 + 1;
62    (part_one, part_two)
63}
64
65pub fn part1(input: &Input) -> i32 {
66    input.0
67}
68
69pub fn part2(input: &Input) -> i32 {
70    input.1
71}
aoc/year2023/day10.rs

aoc/year2023/
day10.rs
