aoc/year2020/
day16.rs

1//! # Ticket Translation
2//!
3//! Part one is optimized by first merging as many of the rules as possible. The trick to merge
4//! ranges efficiently is to first sort them by start, then combine any that start before the end
5//! of the previous range. For my input this cut down the checks for each number from 40 to 1.
6//! The invalid rows are saved and passed to part two.
7//!
8//! Part two is a [constraint satisfaction problem](https://en.wikipedia.org/wiki/Constraint_satisfaction_problem).
9//! First we transpose the ticket rows to columns, grouping each number in the same position in the
10//! ticket. For each column we check every number, eliminating rules that don't fit, since
11//! we know that potential rules must be valid for every field in the same position.
12//!
13//! To solve this, there must be at least one column with only one rule remaining. As this rule can
14//! only belong to this column, we eliminate it from other columns. This causes a chain reaction
15//! where a second column will reduce to only one rule, continuing until all columns have been
16//! resolved.
17use crate::util::iter::*;
18use crate::util::parse::*;
19
20type Input = (u32, u64);
21type Ticket = Vec<u32>;
22
23#[derive(Clone, Copy, PartialEq, Eq)]
24struct Rule {
25    departure: bool,
26    a: u32,
27    b: u32,
28    c: u32,
29    d: u32,
30}
31
32impl Rule {
33    fn from(line: &str) -> Rule {
34        let departure = line.starts_with("departure");
35        let [a, b, c, d] = line.iter_unsigned().chunk::<4>().next().unwrap();
36        Rule { departure, a, b, c, d }
37    }
38
39    fn check(&self, n: u32) -> bool {
40        (self.a..=self.b).contains(&n) || (self.c..=self.d).contains(&n)
41    }
42}
43
44pub fn parse(input: &str) -> Input {
45    let [first, second, third] = input.splitn(3, "\n\n").chunk::<3>().next().unwrap();
46    let rules: Vec<_> = first.lines().map(Rule::from).collect();
47    let your_ticket: Ticket = second.iter_unsigned().collect();
48    let mut nearby_tickets = vec![Vec::new(); rules.len()];
49
50    for (i, n) in third.iter_unsigned().enumerate() {
51        nearby_tickets[i % rules.len()].push(n);
52    }
53
54    let (error_rate, valid) = solve_part_one(&rules, &nearby_tickets);
55    let product = solve_part_two(&rules, &your_ticket, &nearby_tickets, &valid);
56
57    (error_rate, product)
58}
59
60pub fn part1(input: &Input) -> u32 {
61    input.0
62}
63
64pub fn part2(input: &Input) -> u64 {
65    input.1
66}
67
68fn solve_part_one(rules: &[Rule], tickets: &[Ticket]) -> (u32, Vec<bool>) {
69    let mut ranges: Vec<_> = rules.iter().flat_map(|r| [r.a..r.b + 1, r.c..r.d + 1]).collect();
70    ranges.sort_unstable_by_key(|r| r.start);
71    ranges.dedup_by(|next, prev| {
72        if next.start <= prev.end {
73            prev.end = prev.end.max(next.end);
74            true
75        } else {
76            false
77        }
78    });
79
80    let mut total = 0;
81    let mut valid = vec![true; tickets[0].len()];
82
83    for column in tickets {
84        for (i, n) in column.iter().enumerate() {
85            if !ranges.iter().any(|range| range.contains(n)) {
86                total += n;
87                valid[i] = false;
88            }
89        }
90    }
91
92    (total, valid)
93}
94
95fn solve_part_two(
96    rules: &[Rule],
97    your_ticket: &Ticket,
98    nearby_tickets: &[Ticket],
99    valid: &[bool],
100) -> u64 {
101    let mut rules_by_column = Vec::new();
102    let mut product = 1;
103
104    for ticket in nearby_tickets {
105        let mut remaining = rules.to_vec();
106
107        for (&valid, &n) in valid.iter().zip(ticket.iter()) {
108            if valid {
109                remaining.retain(|rule| rule.check(n));
110            }
111        }
112
113        rules_by_column.push(remaining);
114    }
115
116    while rules_by_column.iter().any(|rules| rules.len() > 1) {
117        for i in 0..rules_by_column.len() {
118            if rules_by_column[i].len() == 1 {
119                let found = rules_by_column[i].pop().unwrap();
120
121                if found.departure {
122                    product *= your_ticket[i] as u64;
123                }
124
125                for remaining in &mut rules_by_column {
126                    remaining.retain(|&rule| rule != found);
127                }
128            }
129        }
130    }
131
132    product
133}
aoc/year2020/day16.rs

aoc/year2020/
day16.rs
