1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

//! # Ticket Translation
//!
//! Part one is optimized by first merging as many of the rules as possible. The trick to merge
//! ranges efficiently is to first sort them by start, then combine any that start before the end
//! of the previous range. For my input this cut down the checks for each number from 40 to 1.
//! The invalid rows are saved and passed to part two.
//!
//! Part two is a [constraint satisfaction problem](https://en.wikipedia.org/wiki/Constraint_satisfaction_problem).
//! First we transpose the ticket rows to columns, grouping each number in the same position in the
//! ticket. For each column we check every number, eliminating rules that don't fit, since
//! we know that potential rules must be valid for every field in same position.
//!
//! To solve there must be at least one column with only one rule remaining. As this rule can
//! only belong to this column, we eliminate it from other columns. This causes a chain reaction
//! where a second column will reduce to only one rule, continuing until all columns have been
//! resolved.
use crate::util::iter::*;
use crate::util::parse::*;

type Result = (u32, u64);
type Ticket = Vec<u32>;

#[derive(Clone, Copy, PartialEq, Eq)]
struct Rule {
    departure: bool,
    a: u32,
    b: u32,
    c: u32,
    d: u32,
}

impl Rule {
    fn from(line: &str) -> Rule {
        let departure = line.starts_with("departure");
        let [a, b, c, d] = line.iter_unsigned().chunk::<4>().next().unwrap();
        Rule { departure, a, b, c, d }
    }

    fn check(&self, n: u32) -> bool {
        (self.a <= n && n <= self.b) || (self.c <= n && n <= self.d)
    }
}

pub fn parse(input: &str) -> Result {
    let [first, second, third] = input.splitn(3, "\n\n").chunk::<3>().next().unwrap();
    let rules: Vec<_> = first.lines().map(Rule::from).collect();
    let your_ticket: Ticket = second.iter_unsigned().collect();
    let mut nearby_tickets = vec![Vec::new(); rules.len()];

    for (i, n) in third.iter_unsigned().enumerate() {
        nearby_tickets[i % rules.len()].push(n);
    }

    let (error_rate, valid) = solve_part_one(&rules, &nearby_tickets);
    let product = solve_part_two(&rules, &your_ticket, &nearby_tickets, &valid);

    (error_rate, product)
}

pub fn part1(input: &Result) -> u32 {
    input.0
}

pub fn part2(input: &Result) -> u64 {
    input.1
}

fn solve_part_one(rules: &[Rule], tickets: &[Ticket]) -> (u32, Vec<bool>) {
    let mut ranges = Vec::new();
    for rule in rules {
        ranges.push(rule.a..rule.b + 1);
        ranges.push(rule.c..rule.d + 1);
    }
    ranges.sort_unstable_by_key(|r| r.start);

    let mut i = 1;
    while i < ranges.len() {
        if ranges[i].start < ranges[i - 1].end {
            ranges[i - 1].end = ranges[i - 1].end.max(ranges[i].end);
            ranges.remove(i);
        } else {
            i += 1;
        }
    }

    let mut total = 0;
    let mut valid = vec![true; tickets[0].len()];

    for column in tickets {
        for (i, n) in column.iter().enumerate() {
            let check = ranges.iter().any(|range| range.contains(n));
            if !check {
                total += n;
                valid[i] = false;
            }
        }
    }

    (total, valid)
}

fn solve_part_two(
    rules: &[Rule],
    your_ticket: &Ticket,
    nearby_tickets: &[Ticket],
    valid: &[bool],
) -> u64 {
    let mut rules_by_column = Vec::new();
    let mut product = 1;

    for ticket in nearby_tickets {
        let mut remaining = rules.to_vec();

        for (&valid, &n) in valid.iter().zip(ticket.iter()) {
            if valid {
                remaining.retain(|rule| rule.check(n));
            }
        }

        rules_by_column.push(remaining);
    }

    while rules_by_column.iter().any(|rules| rules.len() > 1) {
        for i in 0..rules_by_column.len() {
            if rules_by_column[i].len() == 1 {
                let found = rules_by_column[i].pop().unwrap();

                if found.departure {
                    product *= your_ticket[i] as u64;
                }

                for remaining in &mut rules_by_column {
                    remaining.retain(|&rule| rule != found);
                }
            }
        }
    }

    product
}