year2018/
day03.rs

1use utils::prelude::*;
2
3/// Identifying the region that isn't overlapped.
4#[derive(Clone, Debug)]
5pub struct Day03 {
6    part1: u32,
7    part2: u32,
8}
9
10#[derive(Debug)]
11struct Claim {
12    id: u32,
13    y: usize,
14    height: usize,
15    idx: usize,
16    mask0: u32,
17    mask1: u32,
18}
19
20impl Day03 {
21    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
22        let coordinate = parser::number_range(0usize..=991);
23        let dimension = parser::number_range(1usize..=31);
24
25        let claims: Vec<Claim> = parser::u32()
26            .with_prefix(b'#')
27            .with_suffix(" @ ")
28            .then(coordinate.with_suffix(b','))
29            .then(coordinate.with_suffix(": "))
30            .then(dimension.with_suffix(b'x'))
31            .then(dimension)
32            .map_res(|(id, x, y, width, height)| {
33                if x + width > 1000 || y + height > 1000 {
34                    Err("claim out of bounds")
35                } else {
36                    let mask = ((1u64 << width) - 1) << (x % 32);
37
38                    Ok(Claim {
39                        id,
40                        y,
41                        height,
42                        idx: (x / 32),
43                        mask0: mask as u32,
44                        mask1: (mask >> 32) as u32,
45                    })
46                }
47            })
48            .parse_lines(input)?;
49
50        let mut grid = [[0u32; 32]; 1000];
51        let mut overlaps = [[0u32; 32]; 1000];
52        for claim in &claims {
53            // This is enforced by the max accepted coordinate. 991 div 32 = 30
54            assert!(claim.idx + 1 < 32);
55
56            for y in claim.y..claim.y + claim.height {
57                overlaps[y][claim.idx] |= grid[y][claim.idx] & claim.mask0;
58                grid[y][claim.idx] |= claim.mask0;
59
60                overlaps[y][claim.idx + 1] |= grid[y][claim.idx + 1] & claim.mask1;
61                grid[y][claim.idx + 1] |= claim.mask1;
62            }
63        }
64
65        Ok(Self {
66            part1: overlaps.as_flattened().iter().map(|x| x.count_ones()).sum(),
67            part2: claims
68                .iter()
69                .find(|claim| {
70                    overlaps[claim.y..claim.y + claim.height].iter().all(|o| {
71                        o[claim.idx] & claim.mask0 == 0 && o[claim.idx + 1] & claim.mask1 == 0
72                    })
73                })
74                .ok_or_else(|| InputError::new(input, 0, "all claims overlap"))?
75                .id,
76        })
77    }
78
79    #[must_use]
80    pub fn part1(&self) -> u32 {
81        self.part1
82    }
83
84    #[must_use]
85    pub fn part2(&self) -> u32 {
86        self.part2
87    }
88}
89
90examples!(Day03 -> (u32, u32) [
91    {input: "#1 @ 1,3: 4x4\n#2 @ 3,1: 4x4\n#3 @ 5,5: 2x2", part1: 4},
92]);
year2018/day03.rs

year2018/
day03.rs
