year2020/
day05.rs

1use utils::prelude::*;
2
3/// Decoding binary numbers.
4///
5/// The key optimization is that `F`/`B` and `L`/`R` differ only in bit 2. Inverting that bit in
6/// each of the first 8 bytes and gathering the results with one multiply decodes the row and the
7/// first column bit together.
8///
9/// Validation compares each byte against the all-zeros and all-ones passes for its position.
10/// lcm(11, 16) = 176 and lcm(12, 16) = 48, so repeating those two lines to fill a block gives
11/// templates the compiler can check 16 bytes at a time. This is ~3x faster than parsing bytes one
12/// at a time.
13#[derive(Clone, Debug)]
14pub struct Day05 {
15    seats: [u64; 18],
16}
17
18const LETTER_BIT: u8 = 1 << 2;
19const LOW_BITS: u64 = 0x0101_0101_0101_0101;
20const PACK_MULTIPLIER: u64 = 0x8040_2010_0804_0201;
21const LF_ZEROS: [u8; 176] = template(b"FFFFFFFLLL\n");
22const LF_ONES: [u8; 176] = template(b"BBBBBBBRRR\n");
23const CRLF_ZEROS: [u8; 48] = template(b"FFFFFFFLLL\r\n");
24const CRLF_ONES: [u8; 48] = template(b"BBBBBBBRRR\r\n");
25
26const fn template<const N: usize>(pass: &[u8]) -> [u8; N] {
27    assert!(N.is_multiple_of(pass.len()) && N.is_multiple_of(16));
28    let mut template = [0; N];
29    let mut i = 0;
30    while i < N {
31        template[i] = pass[i % pass.len()];
32        i += 1;
33    }
34    template
35}
36
37impl Day05 {
38    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
39        if input.is_empty() {
40            return Err(InputError::new(input, 0, "expected one of 'B', 'F'"));
41        }
42
43        let parsed = if input.as_bytes().get(10) == Some(&b'\r') {
44            Self::parse::<12, _>(input.as_bytes(), &CRLF_ZEROS, &CRLF_ONES)
45        } else {
46            Self::parse::<11, _>(input.as_bytes(), &LF_ZEROS, &LF_ONES)
47        };
48        parsed.ok_or_else(|| Self::parse_error(input))
49    }
50
51    fn parse<const STRIDE: usize, const BLOCK: usize>(
52        bytes: &[u8],
53        zeros: &[u8; BLOCK],
54        ones: &[u8; BLOCK],
55    ) -> Option<Self> {
56        // 1,024 seat bits, with one element of padding on each side
57        let mut seats = [0u64; 18];
58        let mut valid = true;
59
60        let (blocks, tail) = bytes.as_chunks::<BLOCK>();
61        for block in blocks {
62            for ((&b, &zero), &one) in block.iter().zip(zeros).zip(ones) {
63                valid &= b == zero || b == one;
64            }
65            for pass in block.as_chunks::<STRIDE>().0 {
66                Self::decode_pass(pass, &mut seats);
67            }
68        }
69
70        for ((&b, &zero), &one) in tail.iter().zip(zeros).zip(ones) {
71            valid &= b == zero || b == one;
72        }
73        let (tail_passes, last) = tail.as_chunks::<STRIDE>();
74        for pass in tail_passes {
75            Self::decode_pass(pass, &mut seats);
76        }
77
78        if last.len() == 10 {
79            Self::decode_pass(last, &mut seats);
80        } else {
81            valid &= last.is_empty();
82        }
83
84        let line_count = bytes.len() / STRIDE + usize::from(last.len() == 10);
85        let seat_count = seats[1..17]
86            .iter()
87            .map(|bits| bits.count_ones() as usize)
88            .sum::<usize>();
89        valid &= line_count == seat_count;
90
91        valid.then_some(Self { seats })
92    }
93
94    #[inline]
95    fn decode_pass(pass: &[u8], seats: &mut [u64; 18]) {
96        let first = u64::from_le_bytes(pass[..8].try_into().unwrap());
97
98        // F and L have bit 2 set, so invert and pack 1 bit from each byte
99        let bits = (!first >> 2) & LOW_BITS;
100        let high = (bits.wrapping_mul(PACK_MULTIPLIER) >> 56) as usize;
101        let bit1 = usize::from(pass[8] & LETTER_BIT == 0);
102        let bit0 = usize::from(pass[9] & LETTER_BIT == 0);
103        let seat = (high << 2) | (bit1 << 1) | bit0;
104
105        seats[(seat / 64) + 1] |= 1 << (seat % 64);
106    }
107
108    #[cold]
109    fn parse_error(input: &str) -> InputError {
110        // Re-parse with the combinator parser to find the exact error position
111        let row =
112            parser::byte_map!(b'F' => 0, b'B' => 1)
113                .repeat_fold(parser::noop(), 7, 0, |acc, b| (acc << 1) | b);
114        let col =
115            parser::byte_map!(b'L' => 0, b'R' => 1)
116                .repeat_fold(parser::noop(), 3, 0, |acc, b| (acc << 1) | b);
117        let parser = row
118            .then(col)
119            .map(|(row, col)| (row << 3) | col)
120            .with_consumed()
121            .with_eol();
122
123        let mut seats = [false; 1024];
124        for result in parser.parse_iterator(input) {
125            let (seat, pass) = match result {
126                Ok(pass) => pass,
127                Err(error) => return error,
128            };
129            if pass.len() != 10 {
130                return InputError::new(input, pass, "expected 10-character boarding pass");
131            }
132            if seats[seat as usize] {
133                return InputError::new(input, pass, "duplicate boarding pass");
134            }
135            seats[seat as usize] = true;
136        }
137
138        // Input that fails the fast chunk parser but passes this parser must have mixed endings
139        InputError::new(input, 0, "expected consistent line endings")
140    }
141
142    #[must_use]
143    pub fn part1(&self) -> u16 {
144        self.seats[1..17]
145            .iter()
146            .enumerate()
147            .rev()
148            .find_map(|(index, &bits)| {
149                (bits != 0).then_some(index as u16 * 64 + 63 - bits.leading_zeros() as u16)
150            })
151            .expect("input contains at least one boarding pass")
152    }
153
154    #[must_use]
155    pub fn part2(&self) -> u16 {
156        self.seats
157            .array_windows()
158            .enumerate()
159            .find_map(|(index, &[previous, current, next])| {
160                let missing = !current
161                    & ((current << 1) | (previous >> 63))
162                    & ((current >> 1) | (next << 63));
163                (missing != 0).then_some(index as u16 * 64 + missing.trailing_zeros() as u16)
164            })
165            .expect("no solution found")
166    }
167}
168
169examples!(Day05 -> (u16, u16) [
170    {input: "FBFBBFFRLR", part1: 357},
171    {input: "BFFFBBFRRR", part1: 567},
172    {input: "FFFBBBFRRR", part1: 119},
173    {input: "BBFFBBFRLL", part1: 820},
174    {input: "BFFFBBFRRR\nFFFBBBFRRR\nBBFFBBFRLL", part1: 820},
175]);
year2020/day05.rs

year2020/
day05.rs
