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<_> = 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            let check = ranges.iter().any(|range| range.contains(n));
86            if !check {
87                total += n;
88                valid[i] = false;
89            }
90        }
91    }
92
93    (total, valid)
94}
95
96fn solve_part_two(
97    rules: &[Rule],
98    your_ticket: &Ticket,
99    nearby_tickets: &[Ticket],
100    valid: &[bool],
101) -> u64 {
102    let mut rules_by_column = Vec::new();
103    let mut product = 1;
104
105    for ticket in nearby_tickets {
106        let mut remaining = rules.to_vec();
107
108        for (&valid, &n) in valid.iter().zip(ticket.iter()) {
109            if valid {
110                remaining.retain(|rule| rule.check(n));
111            }
112        }
113
114        rules_by_column.push(remaining);
115    }
116
117    while rules_by_column.iter().any(|rules| rules.len() > 1) {
118        for i in 0..rules_by_column.len() {
119            if rules_by_column[i].len() == 1 {
120                let found = rules_by_column[i].pop().unwrap();
121
122                if found.departure {
123                    product *= your_ticket[i] as u64;
124                }
125
126                for remaining in &mut rules_by_column {
127                    remaining.retain(|&rule| rule != found);
128                }
129            }
130        }
131    }
132
133    product
134}
aoc/year2020/day16.rs

aoc/year2020/
day16.rs
