You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

113 lines
3.6 KiB

use std::ops::RangeInclusive;
use std::collections::{HashSet, HashMap};
const INPUT: &str = include_str!("../../data/day16");
#[derive(Clone, Debug)]
struct Field {
name: String,
ranges: Vec<RangeInclusive<u64>>,
}
impl Field {
fn matches(&self, value: u64) -> bool {
self.ranges.iter().any(|range| range.contains(&value))
}
fn parse(line: &str) -> Self {
let pos = line.find(": ").unwrap();
let name = line[..pos].to_string();
let ranges = line[pos+2..].split(" or ").map(|range| {
let pos = range.find("-").unwrap();
let start = range[..pos].parse().unwrap();
let end = range[pos+1..].parse().unwrap();
start..=end
}).collect();
Self { name, ranges }
}
}
#[derive(Clone, Debug)]
struct Ticket(Vec<u64>);
impl Ticket {
fn invalid_values<'a>(&'a self, fields: &'a Vec<Field>) -> impl Iterator<Item=u64> + 'a {
self.0.iter().cloned().filter(move |&nr| {
!fields.iter().any(|field| field.matches(nr))
})
}
fn completely_invalid(&self, fields: &Vec<Field>) -> bool {
// at least one invalid value?
self.invalid_values(fields).next().is_some()
}
fn parse(line: &str) -> Self {
Self(line.split(",").map(|n| n.parse().unwrap()).collect())
}
}
#[derive(Clone, Debug)]
struct Input {
fields: Vec<Field>,
your_ticket: Ticket,
tickets: Vec<Ticket>,
}
impl Input {
fn parse(data: &str) -> Self {
let mut parts = data.split("\n\n");
let fields = parts.next().unwrap().lines().map(Field::parse).collect();
let your_ticket = Ticket::parse(
parts.next().unwrap().strip_prefix("your ticket:\n").unwrap()
);
let tickets = parts.next().unwrap()
.strip_prefix("nearby tickets:\n").unwrap()
.lines().map(|line| Ticket::parse(line))
.collect();
assert!(parts.next().is_none());
Self { fields, your_ticket, tickets }
}
}
fn main() {
let input = Input::parse(INPUT);
println!("Error rate: {}",
input.tickets.iter().map(|ticket| {
ticket.invalid_values(&input.fields)
}).flatten().sum::<u64>()
);
let nearby_tickets: Vec<_> = input.tickets.iter().filter(|ticket| {
!ticket.completely_invalid(&input.fields)
}).cloned().collect();
let mut field_columns = input.fields.iter().enumerate().map(|(ndx, field)| {
let columns = (0..input.fields.len()).filter(|&column| {
nearby_tickets.iter().all(|ticket| {
field.matches(ticket.0[column])
})
}).collect::<HashSet<usize>>();
(ndx, columns)
}).collect::<HashMap<usize, _>>();
let mut columns: HashMap<usize, usize> = HashMap::new();
let mut dep_product = 1;
while !field_columns.is_empty() {
let (ndx, col) = field_columns.iter().filter_map(|(ndx, set)| {
if set.len() == 1 {
Some((*ndx, *set.iter().next().unwrap()))
} else {
None
}
}).next().unwrap();
// println!("Possbile columns for fields: {:?}", field_columns);
// println!("Field [{:2} -> {:2}] {}: {}", ndx, col, input.fields[ndx].name, input.your_ticket.0[col]);
if input.fields[ndx].name.starts_with("departure") {
dep_product *= input.your_ticket.0[col];
}
field_columns.remove(&ndx);
columns.insert(ndx, col);
for col_set in field_columns.values_mut() {
col_set.remove(&col);
}
}
println!("Departure product: {}", dep_product);
}