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

aoc/year2018/
day03.rs
