aoc/year2021/
day05.rs

1//! # Hydrothermal Venture
2//!
3//! No subtlety with this solution, we create a 1-dimensional array 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 Input = (usize, usize);
17
18pub fn parse(input: &str) -> Input {
19    let (orthogonal, diagonal): (Vec<_>, Vec<_>) =
20        input.iter_unsigned().chunk::<4>().partition(|&[x1, y1, x2, y2]| x1 == x2 || y1 == y2);
21
22    let mut grid = vec![0_u8; 1_000_000];
23    let first = vents(&orthogonal, &mut grid);
24    let second = vents(&diagonal, &mut grid);
25
26    (first, first + second)
27}
28
29pub fn part1(input: &Input) -> usize {
30    input.0
31}
32
33pub fn part2(input: &Input) -> usize {
34    input.1
35}
36
37fn vents(input: &[[usize; 4]], grid: &mut [u8]) -> usize {
38    let mut result = 0;
39
40    for &[x1, y1, x2, y2] in input {
41        let (x1, y1, x2, y2) = (x1 as i32, y1 as i32, x2 as i32, y2 as i32);
42        let count = (y2 - y1).abs().max((x2 - x1).abs());
43        let delta = (y2 - y1).signum() * 1000 + (x2 - x1).signum();
44        let mut index = y1 * 1000 + x1;
45
46        for _ in 0..count + 1 {
47            if grid[index as usize] == 1 {
48                result += 1;
49            }
50            grid[index as usize] += 1;
51            index += delta;
52        }
53    }
54
55    result
56}
aoc/year2021/day05.rs

aoc/year2021/
day05.rs
