aoc/year2021/
day05.rs

1//! # Hydrothermal Venture
2//!
3//! No subtlety with this solution, we create an 1 dimensional arrray of 1 million `u8` elements
4//! to store all possible points then increment values for each line. This assumes that no lines
5//! cross more than 255 times. This approach is much faster but less flexible than using a
6//! `HashMap` to store mappings of point to values.
7//!
8//! To avoid the overhead of a nested 2 dimensional array, each point `(x, y)` is mapped to
9//! an index `y * 1000 + x`. For each line direction the index delta is calculated using
10//! the handy [`signum`] function.
11//!
12//! [`signum`]: i32::signum
13use crate::util::iter::*;
14use crate::util::parse::*;
15
16type Vent = [u32; 4];
17
18pub fn parse(input: &str) -> [usize; 2] {
19    let all: Vec<_> = input.iter_unsigned().chunk::<4>().collect();
20    let (orthogonal, diagonal): (Vec<_>, Vec<_>) =
21        all.iter().partition(|[x1, y1, x2, y2]| x1 == x2 || y1 == y2);
22
23    let mut grid = vec![0_u8; 1_000_000];
24    let first = vents(&orthogonal, &mut grid);
25    let second = vents(&diagonal, &mut grid);
26
27    [first, second]
28}
29
30pub fn part1(input: &[usize]) -> usize {
31    input[0]
32}
33
34pub fn part2(input: &[usize]) -> usize {
35    input[0] + input[1]
36}
37
38fn vents(input: &[Vent], grid: &mut [u8]) -> usize {
39    let mut result = 0;
40
41    for &[x1, y1, x2, y2] in input {
42        let (x1, y1, x2, y2) = (x1 as i32, y1 as i32, x2 as i32, y2 as i32);
43        let count = (y2 - y1).abs().max((x2 - x1).abs());
44        let delta = (y2 - y1).signum() * 1000 + (x2 - x1).signum();
45        let mut index = y1 * 1000 + x1;
46
47        for _ in 0..=count {
48            if grid[index as usize] == 1 {
49                result += 1;
50            }
51            grid[index as usize] += 1;
52            index += delta;
53        }
54    }
55
56    result
57}
aoc/year2021/day05.rs

aoc/year2021/
day05.rs
