use std::collections::HashMap;

use regex::Regex;

#[derive(Debug,Clone)]
struct Track {
    current_valve: String,
    final_pressure_release: u32,
    valves_opened: Vec<String>,
    debug: String,
}
#[derive(Debug)]
struct Valve {
    flow_rate: u32,
    next_valves: Vec<String>,
}
pub fn run(input: String) {
    let re = Regex::new(r"^Valve ([A-Z]+) has flow rate=(\d+); tunnels? leads? to valves? ([A-Z, ]+)$").unwrap();
    let valves: HashMap<String,Valve> = input.lines().map(|line| {
        let cap = re.captures(line).expect(format!("line didn't match regex! {}", line).as_str());
        let name = cap[1].to_string();
        let flow_rate: u32 = cap[2].parse().expect("flow rate wasn't a u32!");
        let next_valves: Vec<String> = cap[3].split(", ").map(|x| { x.to_string() }).collect();
        (name, Valve{flow_rate,next_valves})
    }).collect();
    // How to do this one?
    // I think... tracking all options? It's basically a tree right?
    // max depth of the tree is 30,corresponding to minutes
    // at each depth, options are -> open valve OR move to another valve
    // and at each depth we have a score, and a list of already-opened valves 

    let root = Track {current_valve: "AA".to_string(), final_pressure_release:0, valves_opened: vec![], debug: "Start at AA".to_string()};
    let mut tracks: Vec<Track> = vec![root];
    let mut next_tracks: Vec<Track> = Vec::new();
    let total_mins: u32 = 30;
    for minute in 0..=total_mins {
        let mins_remaining = total_mins - minute;
        for track in &tracks {
            let cv = &valves[&track.current_valve];
            // try open the valve (if it's got any flow, and if it's not already open)
            if cv.flow_rate > 0 && !track.valves_opened.contains(&track.current_valve) {
                let mut nt = track.clone();
                nt.valves_opened.push(track.current_valve.clone());
                if mins_remaining > 0 {
                    nt.final_pressure_release += cv.flow_rate * (mins_remaining-1);
                }
                nt.debug.push_str(format!(", Opened {}", track.current_valve).as_str());
                next_tracks.push(nt);
            }
            // Alt, try moving to another valve
            for nv in &cv.next_valves {
                let mut nt = track.clone();
                nt.current_valve = nv.clone();
                nt.debug.push_str(format!(", Moved to {}", nv).as_str());
                next_tracks.push(nt);
            }
        }
        next_tracks.sort_by(|t1, t2| {t1.final_pressure_release.cmp(&t2.final_pressure_release)}.reverse());
        next_tracks.truncate(3_usize.pow(5));
        tracks = next_tracks.clone();
        next_tracks = Vec::new();// prune? keep the top N scorers?
    }
    // Find the track with the biggest final score
    let max_track = tracks.iter().max_by(|t1,t2| {t1.final_pressure_release.cmp(&t2.final_pressure_release)}).unwrap();
    //let max_pressure_release = tracks.iter().map(|t| {t.final_pressure_release}).max().unwrap();
    println!("Day 16: {}", max_track.final_pressure_release);
}