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 iter = input.bytes();
29    let mut check_group = false;
30
31    // End the input with a double newline, to include last group in the total.
32    for ch in iter.chain(once(b'\n')) {
33        match ch {
34            b'\n' if check_group => {
35                // A second newline ends one group and prepares for the next.
36                check_group = false;
37                part_one += any.count_ones();
38                part_two += all.count_ones();
39                any = 0;
40                all = u32::MAX;
41            }
42            b'\n' => {
43                // A single newline separates passengers within a group.
44                any |= passenger;
45                all &= passenger;
46                passenger = 0;
47                check_group = true;
48            }
49            _ => {
50                // A letter sets the next bit for the given passenger.
51                // Masking to bits 1-26 is more efficient than subtracting to bits 0-25.
52                check_group = false;
53                passenger |= 1 << (ch & 31);
54            }
55        }
56    }
57
58    (part_one, part_two)
59}
60
61pub fn part1(input: &Input) -> u32 {
62    input.0
63}
64
65pub fn part2(input: &Input) -> u32 {
66    input.1
67}
aoc/year2020/day06.rs

aoc/year2020/
day06.rs
