259 lines
7.8 KiB
Rust
259 lines
7.8 KiB
Rust
use std::io::Read;
|
|
use std::str::FromStr;
|
|
use std::ops::Range;
|
|
use std::collections::HashMap;
|
|
use std::ops::Deref;
|
|
|
|
#[derive(Debug, PartialEq)]
|
|
struct FieldRule(Range<usize>, Range<usize>);
|
|
type FieldsInfo = HashMap<String, FieldRule>;
|
|
type TicketContent = Vec<usize>;
|
|
#[derive(Debug, PartialEq, Clone)]
|
|
struct Ticket(TicketContent);
|
|
type Tickets = Vec<Ticket>;
|
|
|
|
#[derive(Debug, PartialEq)]
|
|
struct TicketsInfo {
|
|
fields: FieldsInfo,
|
|
my_ticket: Ticket,
|
|
nearby_tickets: Tickets,
|
|
}
|
|
|
|
impl Deref for Ticket {
|
|
type Target = TicketContent;
|
|
fn deref(&self) -> &Self::Target {
|
|
&self.0
|
|
}
|
|
}
|
|
|
|
impl FromStr for Ticket {
|
|
type Err = ();
|
|
fn from_str(s: &str) -> Result<Self, Self::Err> {
|
|
Ok(Ticket(s.split(',')
|
|
.map(|n| n.parse::<usize>().unwrap())
|
|
.collect::<TicketContent>()))
|
|
}
|
|
}
|
|
|
|
|
|
impl FromStr for FieldRule {
|
|
type Err = ();
|
|
fn from_str(s: &str) -> Result<Self, Self::Err> {
|
|
let splited: Vec<_> = s.split(" or ").collect();
|
|
let mut ranges: Vec<_> = splited.iter().map(|s| {
|
|
let bondaries: Vec<_> = s.split('-').map(|n| n.parse::<usize>().unwrap()).collect();
|
|
Range {
|
|
start: bondaries[0],
|
|
end: bondaries[1] + 1,
|
|
}
|
|
}).collect();
|
|
let second = ranges.pop().unwrap();
|
|
let first = ranges.pop().unwrap();
|
|
Ok(FieldRule(first, second))
|
|
}
|
|
}
|
|
|
|
|
|
impl FromStr for TicketsInfo {
|
|
type Err = ();
|
|
fn from_str(s: &str) -> Result<Self, Self::Err> {
|
|
let content: Vec<_> = s.split("\n\n").collect();
|
|
let fields: FieldsInfo = content[0].lines().map(|l| {
|
|
let splited: Vec<_> = l.split(": ").collect();
|
|
(splited[0].into(), splited[1].parse::<FieldRule>().unwrap())
|
|
}).collect();
|
|
|
|
let my_ticket = content[1].lines()
|
|
.skip(1).next()
|
|
.map(|l| l.parse::<Ticket>().unwrap()).unwrap();
|
|
|
|
let nearby_tickets = content[2].lines()
|
|
.skip(1)
|
|
.map(|l| l.parse::<Ticket>().unwrap())
|
|
.collect::<Tickets>();
|
|
|
|
Ok(TicketsInfo {
|
|
fields,
|
|
my_ticket,
|
|
nearby_tickets,
|
|
})
|
|
}
|
|
}
|
|
|
|
|
|
impl Ticket {
|
|
fn validate_tickets(&self, fields_info: &FieldsInfo) -> usize {
|
|
self.iter().filter(|value| {
|
|
!fields_info.iter().any(|(_name, rule)| rule.is_valid_value(value))
|
|
})
|
|
.sum()
|
|
}
|
|
}
|
|
|
|
impl FieldRule {
|
|
fn find_candidates(&self, tickets: &Tickets) -> Vec<usize> {
|
|
let fields_count = tickets[0].len();
|
|
let tickets_count = tickets.len();
|
|
(0..fields_count).filter(|&field_index|
|
|
(0..tickets_count).all(|ticket_index|
|
|
self.is_valid_value(&tickets[ticket_index][field_index])
|
|
)
|
|
).collect()
|
|
}
|
|
|
|
fn is_valid_value(&self, value: &usize) -> bool {
|
|
self.0.contains(value) || self.1.contains(value)
|
|
}
|
|
}
|
|
|
|
impl TicketsInfo {
|
|
fn validate_nearby_tickets(&self) -> usize {
|
|
self.nearby_tickets.iter().map(|ticket| ticket.validate_tickets(&self.fields)).sum()
|
|
}
|
|
|
|
fn discard_bad_tickets(&mut self) {
|
|
self.nearby_tickets = self.nearby_tickets.iter()
|
|
.cloned()
|
|
.filter(|ticket| ticket.validate_tickets(&self.fields) == 0)
|
|
.collect();
|
|
}
|
|
|
|
fn assign_fields(&self) -> HashMap<String, usize> {
|
|
let mut filtered_candidates: Vec<(String, Vec<usize>)> = self.fields.iter()
|
|
.map(|(name, rule)| (name.into(), rule.find_candidates(&self.nearby_tickets)))
|
|
.collect();
|
|
filtered_candidates.sort_by_key(|(_name, v)| v.len());
|
|
let mut ordered_fields: Vec<Option<String>> = (0..self.fields.len()).map(|_| None).collect();
|
|
for (name, mut candidates) in filtered_candidates.drain(..) {
|
|
for candidate in candidates.drain(..) {
|
|
if ordered_fields[candidate].is_none() {
|
|
ordered_fields[candidate] = Some(name);
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
ordered_fields.iter().zip(self.my_ticket.iter()).map(|(f, v)| (f.as_ref().unwrap().into(), *v)).collect()
|
|
}
|
|
}
|
|
|
|
|
|
pub fn part1<F: Read> (mut input: F) {
|
|
let mut buffer = String::new();
|
|
input.read_to_string(&mut buffer).unwrap();
|
|
let info: TicketsInfo = buffer.parse().unwrap();
|
|
println!("{}", info.validate_nearby_tickets());
|
|
}
|
|
|
|
pub fn part2<F: Read> (mut input: F) {
|
|
let mut buffer = String::new();
|
|
input.read_to_string(&mut buffer).unwrap();
|
|
let mut info: TicketsInfo = buffer.parse().unwrap();
|
|
info.discard_bad_tickets();
|
|
let ticket = info.assign_fields();
|
|
let checksum: usize = ticket.iter()
|
|
.filter(|(name, _value)| name.starts_with("departure"))
|
|
.fold(1, |acc, (_name, value)| acc * value);
|
|
println!("{}", checksum);
|
|
}
|
|
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
|
|
#[test]
|
|
pub fn test_parse() {
|
|
let input = r#"class: 1-3 or 5-7
|
|
row: 6-11 or 33-44
|
|
seat: 13-40 or 45-50
|
|
|
|
your ticket:
|
|
7,1,14
|
|
|
|
nearby tickets:
|
|
7,3,47
|
|
40,4,50
|
|
55,2,20
|
|
38,6,12"#;
|
|
let expected = TicketsInfo {
|
|
fields: vec![
|
|
(String::from("class"), FieldRule(1..4, 5..8)),
|
|
(String::from("row"), FieldRule(6..12, 33..45)),
|
|
(String::from("seat"), FieldRule(13..41, 45..51)),
|
|
].drain(..).collect(),
|
|
my_ticket: Ticket(vec![7, 1, 14]),
|
|
nearby_tickets: vec![
|
|
Ticket(vec![7, 3, 47]),
|
|
Ticket(vec![40, 4, 50]),
|
|
Ticket(vec![55, 2, 20]),
|
|
Ticket(vec![38, 6, 12]),
|
|
]
|
|
};
|
|
assert_eq!(expected, input.parse::<TicketsInfo>().unwrap())
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_validate() {
|
|
let info = TicketsInfo {
|
|
fields: vec![
|
|
(String::from("class"), FieldRule(1..4, 5..8)),
|
|
(String::from("row"), FieldRule(6..12, 33..45)),
|
|
(String::from("seat"), FieldRule(13..41, 45..51)),
|
|
].drain(..).collect(),
|
|
my_ticket: Ticket(vec![7, 1, 14]),
|
|
nearby_tickets: vec![
|
|
Ticket(vec![7, 3, 47]),
|
|
Ticket(vec![40, 4, 50]),
|
|
Ticket(vec![55, 2, 20]),
|
|
Ticket(vec![38, 6, 12]),
|
|
]
|
|
};
|
|
assert_eq!(71, info.validate_nearby_tickets())
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_discard() {
|
|
let mut info = TicketsInfo {
|
|
fields: vec![
|
|
(String::from("class"), FieldRule(1..4, 5..8)),
|
|
(String::from("row"), FieldRule(6..12, 33..45)),
|
|
(String::from("seat"), FieldRule(13..41, 45..51)),
|
|
].drain(..).collect(),
|
|
my_ticket: Ticket(vec![7, 1, 14]),
|
|
nearby_tickets: vec![
|
|
Ticket(vec![7, 3, 47]),
|
|
Ticket(vec![40, 4, 50]),
|
|
Ticket(vec![55, 2, 20]),
|
|
Ticket(vec![38, 6, 12]),
|
|
]
|
|
};
|
|
info.discard_bad_tickets();
|
|
assert_eq!(1, info.nearby_tickets.len());
|
|
}
|
|
|
|
#[test]
|
|
pub fn test_assign_fields() {
|
|
let mut info = TicketsInfo {
|
|
fields: vec![
|
|
(String::from("class"), FieldRule(0..2, 4..20)),
|
|
(String::from("row"), FieldRule(0..6, 8..20)),
|
|
(String::from("seat"), FieldRule(0..14, 16..20)),
|
|
].drain(..).collect(),
|
|
my_ticket: Ticket(vec![11, 12, 13]),
|
|
nearby_tickets: vec![
|
|
Ticket(vec![3, 9, 18]),
|
|
Ticket(vec![15, 1, 5]),
|
|
Ticket(vec![5, 14, 5]),
|
|
]
|
|
};
|
|
let expected: HashMap<String, usize> = vec![
|
|
(String::from("class"), 12),
|
|
(String::from("row"), 11),
|
|
(String::from("seat"), 13),
|
|
].drain(..).collect();
|
|
|
|
info.discard_bad_tickets();
|
|
assert_eq!(expected, info.assign_fields());
|
|
}
|
|
}
|