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