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 points 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    // The `->` separator rules out `iter_signed`, so convert to `i32` after parsing instead.
20    let (orthogonal, diagonal): (Vec<[i32; 4]>, Vec<_>) = input
21        .iter_unsigned::<u32>()
22        .map(|n| n as i32)
23        .chunk::<4>()
24        .partition(|&[x1, y1, x2, y2]| x1 == x2 || y1 == y2);
25
26    let mut grid = vec![0_u8; 1_000_000];
27    let first = vents(&orthogonal, &mut grid);
28    let second = vents(&diagonal, &mut grid);
29
30    (first, first + second)
31}
32
33pub fn part1(input: &Input) -> usize {
34    input.0
35}
36
37pub fn part2(input: &Input) -> usize {
38    input.1
39}
40
41fn vents(input: &[[i32; 4]], grid: &mut [u8]) -> usize {
42    let mut result = 0;
43
44    for &[x1, y1, x2, y2] in input {
45        let count = (y2 - y1).abs().max((x2 - x1).abs());
46        let delta = (y2 - y1).signum() * 1000 + (x2 - x1).signum();
47        let mut index = y1 * 1000 + x1;
48
49        for _ in 0..count + 1 {
50            result += usize::from(grid[index as usize] == 1);
51            grid[index as usize] += 1;
52            index += delta;
53        }
54    }
55
56    result
57}
aoc/year2021/day05.rs

aoc/year2021/
day05.rs
