day16.rs

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)))
}