year2020/
day16.rs

1use utils::prelude::*;
2
3/// Validating records and inferring column order.
4///
5/// Assumes there is always a remaining column with only one possible field.
6/// See also [2018 Day 16](../year2018/struct.Day16.html).
7#[derive(Clone, Debug)]
8pub struct Day16 {
9    part1: u64,
10    part2: u64,
11}
12
13const MAX_FIELDS: usize = 20;
14const MAX_VALUE: u16 = 999;
15
16impl Day16 {
17    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
18        let number = parser::number_range(0..=MAX_VALUE);
19        let range = number
20            .then(number.with_prefix(b'-'))
21            .map_res(|(start, end)| {
22                (start <= end)
23                    .then_some((start, end))
24                    .ok_or("range end cannot be less than start")
25            });
26        let name = parser::take_while1(u8::is_ascii_lowercase)
27            .repeat_fold(b' ', 1, (), |(), _| ())
28            .with_consumed()
29            .map(|(_, name)| name)
30            .with_suffix(": ");
31        let rule = name
32            .then(range.repeat_n::<2, _>(" or "))
33            .map_res(|(name, ranges)| {
34                (ranges[0].1 < ranges[1].0)
35                    .then_some((name, ranges))
36                    .ok_or("ranges must be sorted and disjoint")
37            });
38        let ticket = number
39            .repeat_arrayvec::<MAX_FIELDS, _>(b',', 1)
40            .with_consumed();
41
42        let (rules, your_ticket, nearby_tickets) = rule
43            .repeat_arrayvec::<MAX_FIELDS, _>(parser::eol(), 1)
44            .with_eol()
45            .with_eol()
46            .then(
47                ticket
48                    .with_prefix("your ticket:".with_eol())
49                    .with_eol()
50                    .with_eol(),
51            )
52            .then(
53                ticket
54                    .repeat(parser::eol(), 1)
55                    .with_prefix("nearby tickets:".with_eol()),
56            )
57            .parse_complete(input)?;
58
59        for (index, &(name, _)) in rules.iter().enumerate() {
60            if rules[..index].iter().any(|(other, _)| *other == name) {
61                return Err(InputError::new(input, name, "duplicate field name"));
62            }
63        }
64        for (ticket, text) in nearby_tickets.iter().chain([&your_ticket]) {
65            if ticket.len() != rules.len() {
66                return Err(InputError::new(
67                    input,
68                    *text,
69                    "ticket field count does not match rule count",
70                ));
71            }
72        }
73
74        let all_fields = (1u32 << rules.len()) - 1;
75        let departure_fields = rules
76            .iter()
77            .enumerate()
78            .filter(|(_, (name, _))| name.starts_with(b"departure"))
79            .fold(0, |mask, (field, _)| mask | 1 << field);
80
81        // Calculate a mask of the valid fields for each value, using each range's start and end + 1
82        // to toggle the field's bit, followed by XORing the changes with the previous mask in a
83        // loop to give the set of valid fields at each value.
84        let mut valid_fields = [0u32; MAX_VALUE as usize + 2];
85        for (field, (_, ranges)) in rules.iter().enumerate() {
86            for &(start, end) in ranges {
87                valid_fields[usize::from(start)] ^= 1 << field;
88                valid_fields[usize::from(end) + 1] ^= 1 << field;
89            }
90        }
91        let mut fields = 0;
92        for change in &mut valid_fields {
93            fields ^= *change;
94            *change = fields;
95        }
96
97        let (your_ticket, your_text) = your_ticket;
98        if your_ticket
99            .iter()
100            .any(|&value| valid_fields[usize::from(value)] == 0)
101        {
102            return Err(InputError::new(
103                input,
104                your_text,
105                "your ticket contains an invalid value",
106            ));
107        }
108
109        let mut part1 = 0;
110        let mut candidates = [all_fields; MAX_FIELDS];
111        let mut column_fields = [0; MAX_FIELDS];
112        for (ticket, _) in nearby_tickets {
113            let mut valid_ticket = true;
114            for (column, &value) in ticket.iter().enumerate() {
115                column_fields[column] = valid_fields[usize::from(value)];
116                if column_fields[column] == 0 {
117                    part1 += u64::from(value);
118                    valid_ticket = false;
119                }
120            }
121
122            if valid_ticket {
123                for column in 0..rules.len() {
124                    candidates[column] &= column_fields[column];
125                }
126            }
127        }
128
129        let mut part2 = 1u64;
130        for _ in 0..rules.len() {
131            let Some(column) = candidates[..rules.len()]
132                .iter()
133                .position(|fields| fields.count_ones() == 1)
134            else {
135                return Err(InputError::new(
136                    input,
137                    0,
138                    "expected unique field assignment",
139                ));
140            };
141
142            let field = candidates[column];
143            candidates[..rules.len()]
144                .iter_mut()
145                .for_each(|fields| *fields &= !field);
146
147            if field & departure_fields != 0 {
148                part2 *= u64::from(your_ticket[column]);
149            }
150        }
151
152        Ok(Self { part1, part2 })
153    }
154
155    #[must_use]
156    pub fn part1(&self) -> u64 {
157        self.part1
158    }
159
160    #[must_use]
161    pub fn part2(&self) -> u64 {
162        self.part2
163    }
164}
165
166examples!(Day16 -> (u64, u64) [
167    {file: "day16_example0.txt", part1: 71},
168]);
year2020/day16.rs

year2020/
day16.rs
