150 lines
4.5 KiB
Rust
150 lines
4.5 KiB
Rust
use aoc_runner_derive::{aoc, aoc_generator};
|
|
use std::collections::{HashMap, HashSet};
|
|
#[derive(Debug)]
|
|
pub struct Input {
|
|
ranges: HashMap<String, Vec<(usize, usize)>>,
|
|
my_ticket: Vec<usize>,
|
|
other_tickets: Vec<Vec<usize>>,
|
|
}
|
|
|
|
type Data = Input;
|
|
|
|
#[aoc_generator(day16)]
|
|
pub fn input_generator(input: &str) -> Data {
|
|
let l = input.lines();
|
|
let ranges: HashMap<String, Vec<(usize, usize)>> = l
|
|
.take_while(|l| !l.trim().is_empty())
|
|
.map(|s| {
|
|
let parts: Vec<_> = s.to_owned().split(": ").map(|v| v.to_owned()).collect();
|
|
let name = parts.get(0).unwrap().trim().to_owned();
|
|
let ranges: Vec<(usize, usize)> = parts
|
|
.get(1)
|
|
.unwrap()
|
|
.to_owned()
|
|
.split(" or ")
|
|
.map(|l| {
|
|
let r: Vec<usize> = l
|
|
.to_owned()
|
|
.split('-')
|
|
.map(|v| v.to_owned().parse().unwrap())
|
|
.collect();
|
|
(r[0], r[1])
|
|
})
|
|
.collect();
|
|
(name, ranges)
|
|
})
|
|
.collect();
|
|
let mut l = input.lines().skip(ranges.len() + 2);
|
|
let my_ticket = l
|
|
.next()
|
|
.unwrap()
|
|
.split(',')
|
|
.map(|v| v.parse().unwrap())
|
|
.collect();
|
|
let other_tickets = l
|
|
.skip(2)
|
|
.map(|nums| nums.split(',').map(|v| v.parse().unwrap()).collect())
|
|
.collect();
|
|
Data {
|
|
ranges,
|
|
my_ticket,
|
|
other_tickets,
|
|
}
|
|
}
|
|
|
|
fn in_ranges(num: usize, ranges: &[(usize, usize)]) -> bool {
|
|
let mut in_range = false;
|
|
for (min, max) in ranges {
|
|
in_range |= (num >= *min) && (num <= *max);
|
|
}
|
|
return in_range;
|
|
}
|
|
|
|
#[aoc(day16, part1)]
|
|
pub fn solve_part1(input: &Data) -> usize {
|
|
let mut inv_nums = vec![];
|
|
for ticket in &input.other_tickets {
|
|
for num in ticket {
|
|
let mut in_any_range = false;
|
|
for range in input.ranges.values() {
|
|
let mut in_range = false;
|
|
for (min, max) in range {
|
|
in_range |= (num >= min) && (num <= max);
|
|
}
|
|
in_any_range |= in_range;
|
|
}
|
|
if !in_any_range {
|
|
inv_nums.push(*num);
|
|
}
|
|
}
|
|
}
|
|
inv_nums.iter().sum()
|
|
}
|
|
|
|
#[aoc(day16, part2)]
|
|
pub fn solve_part2(input: &Data) -> usize {
|
|
let mut field_candicates: Vec<HashSet<String>> = vec![HashSet::new(); input.my_ticket.len()];
|
|
let mut valid_tickets = vec![];
|
|
for ticket in &input.other_tickets {
|
|
let mut valid = true;
|
|
for num in ticket {
|
|
let mut in_any_range = false;
|
|
for range in input.ranges.values() {
|
|
let mut in_range = false;
|
|
for (min, max) in range {
|
|
in_range |= (num >= min) && (num <= max);
|
|
}
|
|
in_any_range |= in_range;
|
|
}
|
|
if !in_any_range {
|
|
valid = false;
|
|
break;
|
|
}
|
|
}
|
|
if valid {
|
|
valid_tickets.push(ticket.clone());
|
|
}
|
|
}
|
|
for field in input.ranges.keys() {
|
|
for f in field_candicates.iter_mut() {
|
|
f.insert(field.clone());
|
|
}
|
|
}
|
|
for (field, ranges) in &input.ranges {
|
|
for ticket in &valid_tickets {
|
|
for (i, num) in ticket.iter().enumerate() {
|
|
if !in_ranges(*num, ranges) {
|
|
field_candicates[i].remove(field);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
let mut fixed: HashSet<String> = HashSet::new();
|
|
let mut field_candicates: Vec<(usize, HashSet<String>)> =
|
|
field_candicates.drain(..).enumerate().collect();
|
|
field_candicates.sort_unstable_by_key(|(_, v)| v.len());
|
|
while field_candicates.iter().any(|(_, v)| v.len() != 1) {
|
|
for c in field_candicates.iter_mut() {
|
|
if c.1.len() == 1 {
|
|
fixed.extend(c.1.iter().cloned());
|
|
} else {
|
|
for val in &fixed {
|
|
c.1.remove(val);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
field_candicates.sort_unstable_by_key(|(n, _)| *n);
|
|
let field_names: Vec<String> = field_candicates
|
|
.drain(..)
|
|
.map(|(_, n)| n.iter().next().unwrap().clone())
|
|
.collect();
|
|
let mut ret = 1;
|
|
for (field, value) in field_names.iter().zip(input.my_ticket.iter()) {
|
|
if field.starts_with("departure") {
|
|
ret *= value;
|
|
}
|
|
}
|
|
return ret;
|
|
}
|