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], direction) {
41            (b'7', UP) | (b'J', DOWN) => LEFT,
42            (b'F', UP) | (b'L', DOWN) => RIGHT,
43            (b'7' | b'F', _) => DOWN,
44            (b'J' | b'L', _) => UP,
45            _ => {
46                // We've looped all the way back to the start.
47                area += determinant(corner, position);
48                break;
49            }
50        };
51
52        area += determinant(corner, position);
53        corner = position;
54        position += direction;
55        steps += 1;
56    }
57
58    let part_one = steps / 2;
59    let part_two = area.abs() / 2 - steps / 2 + 1;
60    (part_one, part_two)
61}
62
63pub fn part1(input: &Input) -> i32 {
64    input.0
65}
66
67pub fn part2(input: &Input) -> i32 {
68    input.1
69}
aoc/year2023/day10.rs

aoc/year2023/
day10.rs
