aoc/year2018/
day03.rs

1//! # No Matter How You Slice It
2//!
3//! Brute force approach using bitmasks for efficiency. Assumes that no claim is wider than 65
4//! inches.
5use crate::util::iter::*;
6use crate::util::parse::*;
7
8type Input = (u32, usize);
9
10pub fn parse(input: &str) -> Input {
11    let claims: Vec<_> = input
12        .iter_unsigned::<usize>()
13        .chunk::<5>()
14        .map(|[_, x1, y1, width, height]| {
15            let start = 16 * y1 + (x1 / 64);
16            let end = start + 16 * height;
17
18            // Create bitmask for each claim, for example `#123 @ 3,2: 5x4` becomes `11111000`.
19            // Use an intermediate u128 to handle claims up to 65 inches wide.
20            let mask: u128 = ((1 << width) - 1) << (x1 % 64);
21            let lower = mask as u64;
22            let upper = (mask >> 64) as u64;
23
24            (start, end, lower, upper)
25        })
26        .collect();
27
28    // Each square inch of fabric is stored in a single bit.
29    // The fabric is 1000 inches wide requiring sixteen `u64`.
30    let mut fabric = vec![0; 16 * 1000];
31    let mut overlap = vec![0; 16 * 1000];
32
33    for &(start, end, lower, upper) in &claims {
34        for index in (start..end).step_by(16) {
35            overlap[index] |= fabric[index] & lower;
36            fabric[index] |= lower;
37
38            if upper > 0 {
39                overlap[index + 1] |= fabric[index + 1] & upper;
40                fabric[index + 1] |= upper;
41            }
42        }
43    }
44
45    // Find the first claim that doesn't overlap with any other claim.
46    let position = claims.iter().position(|&(start, end, lower, upper)| {
47        (start..end).step_by(16).all(|index| {
48            (overlap[index] & lower == 0) && (upper == 0 || overlap[index + 1] & upper == 0)
49        })
50    });
51
52    let part_one = overlap.iter().map(|n| n.count_ones()).sum();
53    let part_two = position.unwrap() + 1;
54    (part_one, part_two)
55}
56
57pub fn part1(input: &Input) -> u32 {
58    input.0
59}
60
61pub fn part2(input: &Input) -> usize {
62    input.1
63}
aoc/year2018/day03.rs

aoc/year2018/
day03.rs
