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 same position.
12//!
13//! To solve 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 Result = (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 <= n && n <= self.b) || (self.c <= n && n <= self.d)
41    }
42}
43
44pub fn parse(input: &str) -> Result {
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: &Result) -> u32 {
61    input.0
62}
63
64pub fn part2(input: &Result) -> u64 {
65    input.1
66}
67
68fn solve_part_one(rules: &[Rule], tickets: &[Ticket]) -> (u32, Vec<bool>) {
69    let mut ranges = Vec::new();
70    for rule in rules {
71        ranges.push(rule.a..rule.b + 1);
72        ranges.push(rule.c..rule.d + 1);
73    }
74    ranges.sort_unstable_by_key(|r| r.start);
75
76    let mut i = 1;
77    while i < ranges.len() {
78        if ranges[i].start < ranges[i - 1].end {
79            ranges[i - 1].end = ranges[i - 1].end.max(ranges[i].end);
80            ranges.remove(i);
81        } else {
82            i += 1;
83        }
84    }
85
86    let mut total = 0;
87    let mut valid = vec![true; tickets[0].len()];
88
89    for column in tickets {
90        for (i, n) in column.iter().enumerate() {
91            let check = ranges.iter().any(|range| range.contains(n));
92            if !check {
93                total += n;
94                valid[i] = false;
95            }
96        }
97    }
98
99    (total, valid)
100}
101
102fn solve_part_two(
103    rules: &[Rule],
104    your_ticket: &Ticket,
105    nearby_tickets: &[Ticket],
106    valid: &[bool],
107) -> u64 {
108    let mut rules_by_column = Vec::new();
109    let mut product = 1;
110
111    for ticket in nearby_tickets {
112        let mut remaining = rules.to_vec();
113
114        for (&valid, &n) in valid.iter().zip(ticket.iter()) {
115            if valid {
116                remaining.retain(|rule| rule.check(n));
117            }
118        }
119
120        rules_by_column.push(remaining);
121    }
122
123    while rules_by_column.iter().any(|rules| rules.len() > 1) {
124        for i in 0..rules_by_column.len() {
125            if rules_by_column[i].len() == 1 {
126                let found = rules_by_column[i].pop().unwrap();
127
128                if found.departure {
129                    product *= your_ticket[i] as u64;
130                }
131
132                for remaining in &mut rules_by_column {
133                    remaining.retain(|&rule| rule != found);
134                }
135            }
136        }
137    }
138
139    product
140}
aoc/year2020/day16.rs

aoc/year2020/
day16.rs
