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' => {
42                if direction == UP {
43                    LEFT
44                } else {
45                    DOWN
46                }
47            }
48            b'F' => {
49                if direction == UP {
50                    RIGHT
51                } else {
52                    DOWN
53                }
54            }
55            b'J' => {
56                if direction == DOWN {
57                    LEFT
58                } else {
59                    UP
60                }
61            }
62            b'L' => {
63                if direction == DOWN {
64                    RIGHT
65                } else {
66                    UP
67                }
68            }
69            _ => {
70                // We've looped all the way back to the start.
71                area += determinant(corner, position);
72                break;
73            }
74        };
75
76        area += determinant(corner, position);
77        corner = position;
78        position += direction;
79        steps += 1;
80    }
81
82    let part_one = steps / 2;
83    let part_two = area.abs() / 2 - steps / 2 + 1;
84    (part_one, part_two)
85}
86
87pub fn part1(input: &Input) -> i32 {
88    input.0
89}
90
91pub fn part2(input: &Input) -> i32 {
92    input.1
93}
aoc/year2023/day10.rs

aoc/year2023/
day10.rs
