aoc/year2020/
day06.rs

1//! # Custom Customs
2//!
3//! This is a disguised binary question like the previous [`day 5`].
4//!
5//! We can store each passenger's answers as an implicit set in a `u32` since the cardinality
6//! is only 26. For each yes answer we set a bit, shifting left based on the letter. For example
7//! `acf` would be represented as `100101`.
8//!
9//! For part one to find groups where any person answered yes, we reduce the group using
10//! [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation) then count the number of ones
11//! for each group using the blazing fast [`count_ones`] intrinsic.
12//!
13//! Part two is very similar, except that we use a bitwise AND instead. It is faster to run
14//! both parts at once during the parse.
15//!
16//! [`day 5`]: crate::year2020::day05
17//! [`count_ones`]: u32::count_ones
18use std::iter::once;
19
20type Input = (u32, u32);
21
22pub fn parse(input: &str) -> Input {
23    let mut any = 0_u32;
24    let mut all = u32::MAX;
25    let mut passenger = 0;
26    let mut part_one = 0;
27    let mut part_two = 0;
28    let mut check_group = false;
29
30    // End the input with a double newline, to include last group in the total.
31    for ch in input.bytes().chain(once(b'\n')) {
32        match ch {
33            b'\n' if check_group => {
34                // A second newline ends one group and prepares for the next.
35                check_group = false;
36                part_one += any.count_ones();
37                part_two += all.count_ones();
38                any = 0;
39                all = u32::MAX;
40            }
41            b'\n' => {
42                // A single newline separates passengers within a group.
43                any |= passenger;
44                all &= passenger;
45                passenger = 0;
46                check_group = true;
47            }
48            _ => {
49                // A letter sets the next bit for the given passenger.
50                // Masking to bits 1-26 is more efficient than subtracting to bits 0-25.
51                check_group = false;
52                passenger |= 1 << (ch & 31);
53            }
54        }
55    }
56
57    (part_one, part_two)
58}
59
60pub fn part1(input: &Input) -> u32 {
61    input.0
62}
63
64pub fn part2(input: &Input) -> u32 {
65    input.1
66}
aoc/year2020/day06.rs

aoc/year2020/
day06.rs
