Last active
December 16, 2020 12:35
-
-
Save whiter4bbit/af2f560e99c58b1b3b4efeca05b5c6f0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| use std::io; | |
| use regex::Regex; | |
| use std::fs; | |
| use std::str::FromStr; | |
| use std::convert::Into; | |
| use std::ops::RangeInclusive; | |
| use std::collections::{HashMap, VecDeque}; | |
| type Ticket = Vec<u32>; | |
| #[derive(Debug, Clone)] | |
| struct Range { | |
| first: RangeInclusive<u32>, | |
| second: RangeInclusive<u32>, | |
| } | |
| #[derive(Debug, Clone)] | |
| struct Notes { | |
| ranges: Vec<(String, Range)>, | |
| your: Ticket, | |
| nearby: Vec<Ticket>, | |
| } | |
| impl Notes { | |
| fn in_any_range(&self, target: &u32) -> bool { | |
| self.ranges.iter() | |
| .any(|(_, range)| range.first.contains(target) || range.second.contains(target)) | |
| } | |
| fn fields_valid_for(&self, target: &u32) -> u32 { | |
| self.ranges.iter().enumerate() | |
| .filter(|(_, (_, range))| range.first.contains(target) || range.second.contains(target)) | |
| .fold(0u32, |mask, (i, _)| mask | (1 << i)) | |
| } | |
| } | |
| impl Into<Notes> for String { | |
| fn into(self) -> Notes { | |
| let mut notes = Notes { | |
| ranges: Vec::new(), | |
| your: Ticket::new(), | |
| nearby: Vec::new(), | |
| }; | |
| let mut your_ticket_start = false; | |
| let mut nearby_tickets_start = false; | |
| let range_re = Regex::new(r"(.*): (\d+)\-(\d+) or (\d+)-(\d+)").unwrap(); | |
| for line in self.lines().map(|line| line.trim()) { | |
| match range_re.captures(line) { | |
| Some(capture) => notes.ranges.push( | |
| ( | |
| capture[1].to_string(), | |
| Range { | |
| first: u32::from_str(&capture[2]).unwrap()..=u32::from_str(&capture[3]).unwrap(), | |
| second: u32::from_str(&capture[4]).unwrap()..=u32::from_str(&capture[5]).unwrap(), | |
| } | |
| ) | |
| ), | |
| None => match line { | |
| "your ticket:" => your_ticket_start = true, | |
| "nearby tickets:" => nearby_tickets_start = true, | |
| _ => if !line.is_empty() { | |
| let ticket: Ticket = line.split(",").filter_map(|entry| u32::from_str(entry).ok()).collect(); | |
| if nearby_tickets_start { | |
| notes.nearby.push(ticket); | |
| } else if your_ticket_start { | |
| notes.your = ticket; | |
| } | |
| } | |
| } | |
| }; | |
| }; | |
| notes | |
| } | |
| } | |
| fn sum_unmatching<T: Into<Notes>>(src: T) -> u32 { | |
| let notes = &src.into(); | |
| notes.nearby.iter() | |
| .map(|ticket| ticket.iter().filter(|value| !notes.in_any_range(value)).sum::<u32>()) | |
| .sum::<u32>() | |
| } | |
| fn filter_matching<T: Into<Notes>>(src: T) -> Notes { | |
| let notes = &src.into(); | |
| let mut matching = notes.clone(); | |
| matching.nearby = notes.nearby.iter() | |
| .filter(|ticket| ticket.iter().all(|value| notes.in_any_range(value))) | |
| .map(|ticket| ticket.clone()) | |
| .collect(); | |
| matching | |
| } | |
| fn rightmost_one_shift(v: u32) -> u32 { | |
| let mut shift = 0; | |
| while ((1 << shift) & v) == 0 { | |
| shift += 1; | |
| } | |
| return shift | |
| } | |
| fn match_fields_with_values(notes: &Notes) -> HashMap<String, u32>{ | |
| let mut fields_for_position: Vec<u32> = notes.your.iter() | |
| .enumerate() | |
| .map(|(i, value)| | |
| notes.nearby.iter() | |
| .fold(notes.fields_valid_for(value), |mask, ticket| mask & notes.fields_valid_for(&ticket[i])) | |
| ).collect(); | |
| let mut queue: VecDeque<u32> = fields_for_position.iter() | |
| .filter(|mask| mask.count_ones() == 1) | |
| .map(|mask| *mask) | |
| .collect(); | |
| while let Some(mask) = queue.pop_front() { | |
| for i in 0..fields_for_position.len() { | |
| if (fields_for_position[i] & mask) == mask && fields_for_position[i] != mask { | |
| fields_for_position[i] = fields_for_position[i] ^ mask; | |
| if fields_for_position[i].count_ones() == 1 { | |
| queue.push_back(fields_for_position[i]); | |
| } | |
| } | |
| } | |
| } | |
| notes.your.iter() | |
| .enumerate() | |
| .map(|(i, value)| (notes.ranges[rightmost_one_shift(fields_for_position[i]) as usize].0.clone(), *value)) | |
| .collect() | |
| } | |
| #[test] | |
| fn test_sum_matching() { | |
| assert_eq!(71, sum_unmatching( | |
| "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".to_string() | |
| )); | |
| } | |
| #[allow(dead_code)] | |
| pub fn solve_p1(input: &str) -> io::Result<u32> { | |
| Ok(sum_unmatching(fs::read_to_string(input)?.to_string())) | |
| } | |
| #[allow(dead_code)] | |
| pub fn solve_p2(input: &str) -> io::Result<u64> { | |
| let valid = filter_matching(fs::read_to_string(input)?.to_string()); | |
| Ok(match_fields_with_values(&valid).iter() | |
| .filter(|(field, _)| field.starts_with("departure")) | |
| .map(|(_, value)| value) | |
| .fold(1u64, |product, cur| product * (*cur as u64))) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment