149 lines
3.9 KiB
Rust
149 lines
3.9 KiB
Rust
use std::collections::{HashMap, HashSet};
|
|
use std::error::Error;
|
|
use std::fs::File;
|
|
use std::io::{self, BufRead};
|
|
use std::vec::Vec;
|
|
|
|
#[macro_use]
|
|
extern crate lazy_static;
|
|
extern crate regex;
|
|
|
|
use regex::Regex;
|
|
|
|
struct Rule {
|
|
lower1: u32,
|
|
upper1: u32,
|
|
lower2: u32,
|
|
upper2: u32,
|
|
}
|
|
|
|
impl Rule {
|
|
fn validate(&self, n: u32) -> bool {
|
|
(n >= self.lower1 && n <= self.upper1) || (n >= self.lower2 && n <= self.upper2)
|
|
}
|
|
}
|
|
|
|
fn rule_from_string(rule: String) -> (String, Rule) {
|
|
lazy_static! {
|
|
static ref RULE_RE: Regex =
|
|
Regex::new(r"^([a-zA-z ]+): ([0-9]+)-([0-9]+) or ([0-9]+)-([0-9]+)").unwrap();
|
|
}
|
|
|
|
if let Some(cap) = RULE_RE.captures_iter(&rule).nth(0) {
|
|
(
|
|
cap[1].to_string(),
|
|
Rule {
|
|
lower1: cap[2].parse().unwrap(),
|
|
upper1: cap[3].parse().unwrap(),
|
|
lower2: cap[4].parse().unwrap(),
|
|
upper2: cap[5].parse().unwrap(),
|
|
},
|
|
)
|
|
} else {
|
|
panic!("Unable to parse line: {}", rule)
|
|
}
|
|
}
|
|
|
|
fn ticket_from_string(ticket: String) -> Vec<u32> {
|
|
ticket.split(',').map(|n| n.parse().unwrap()).collect()
|
|
}
|
|
|
|
fn get_invalid_field(ticket: &Vec<u32>, rules: &HashMap<String, Rule>) -> u32 {
|
|
for field in ticket {
|
|
if !rules.values().any(|r| r.validate(*field)) {
|
|
return *field;
|
|
}
|
|
}
|
|
|
|
0
|
|
}
|
|
|
|
fn main() -> Result<(), Box<dyn Error>> {
|
|
let file = File::open("inputs/day16.txt")?;
|
|
let mut lines = io::BufReader::new(file).lines().map(|l| l.unwrap());
|
|
|
|
let mut line = lines.next().unwrap();
|
|
let mut rules: HashMap<String, Rule> = HashMap::new();
|
|
while line != "" {
|
|
let (name, rule) = rule_from_string(line);
|
|
rules.insert(name, rule);
|
|
line = lines.next().unwrap();
|
|
}
|
|
|
|
//Skip Text
|
|
lines.next().unwrap();
|
|
let line = lines.next().unwrap();
|
|
let my_ticket = ticket_from_string(line);
|
|
|
|
//Skip Text
|
|
lines.next().unwrap();
|
|
lines.next().unwrap();
|
|
|
|
let mut tickets: Vec<Vec<u32>> = Vec::new();
|
|
while let Some(line) = lines.next() {
|
|
tickets.push(ticket_from_string(line));
|
|
}
|
|
|
|
let invalid_count = tickets
|
|
.iter()
|
|
.map(|t| get_invalid_field(t, &rules))
|
|
.fold(0, |x, y| x + y);
|
|
|
|
println!("Invalid tickets: {}", invalid_count);
|
|
|
|
// Part2
|
|
|
|
let valid_tickes: Vec<&Vec<u32>> = tickets
|
|
.iter()
|
|
.filter(|t| get_invalid_field(t, &rules) == 0)
|
|
.collect();
|
|
|
|
let mut canidates: Vec<HashSet<String>> = Vec::new();
|
|
for _ in 0..my_ticket.len() {
|
|
canidates.push(rules.keys().cloned().collect());
|
|
}
|
|
|
|
for ticket in valid_tickes {
|
|
for i in 0..ticket.len() {
|
|
let mut new_canidates = canidates[i].clone();
|
|
for rule_name in canidates[i].iter() {
|
|
if !rules[rule_name].validate(ticket[i]) {
|
|
println!("Eliminated {} for field {}", rule_name, i);
|
|
new_canidates.remove(rule_name);
|
|
}
|
|
}
|
|
canidates[i] = new_canidates;
|
|
}
|
|
}
|
|
|
|
let mut done = false;
|
|
while !done {
|
|
done = true;
|
|
for i in 0..my_ticket.len() {
|
|
if canidates[i].len() == 1 {
|
|
let single_rule = canidates[i].iter().nth(0).unwrap().clone();
|
|
for j in 0..my_ticket.len() {
|
|
if i != j {
|
|
if canidates[j].remove(&single_rule) {
|
|
println!("Eliminated {} for field {}", single_rule, i);
|
|
done = false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
let mut res = 1u64;
|
|
for i in 0..my_ticket.len() {
|
|
if canidates[i].iter().any(|k| k.starts_with("departure")) {
|
|
println!("Field {} is a departure field", i);
|
|
res *= my_ticket[i] as u64;
|
|
}
|
|
}
|
|
|
|
println!("Answer: {}", res);
|
|
|
|
Ok(())
|
|
}
|