use std::io;
use std::io::BufRead;
use std::cmp;
use std::ops;
use std::str;
use std::iter;
use std::collections::HashMap;
use regex::Regex;
use lazy_static::lazy_static;

#[derive(Copy, Clone, PartialEq, Eq)]
enum Attack {
    Radiation,
    Bludgeoning,
    Fire,
    Slashing,
    Cold,
}

impl str::FromStr for Attack {
    type Err = io::Error;
    fn from_str(s: &str) -> io::Result<Attack> {
        Ok(match s {
            "radiation" => Attack::Radiation,
            "bludgeoning" => Attack::Bludgeoning,
            "fire" => Attack::Fire,
            "slashing" => Attack::Slashing,
            "cold" => Attack::Cold,
            _ => panic!("Unknown attack type"),
        })
    }
}

#[derive(Clone, PartialEq, Eq)]
struct Group {
    units: i32,
    hp: i32,
    damage: i32,
    initiative: i32,
    attack_type: Attack,
    weak: Vec<Attack>,
    immune: Vec<Attack>,
}

impl Group {
    fn eff_power(&self) -> i32 {
        self.units * self.damage
    }

    fn sort_key(&self) -> cmp::Reverse<(i32, i32)> {
        cmp::Reverse((self.eff_power(), self.initiative))
    }

    fn damage_to(&self, o: &Group) -> i32 {
        if o.weak.contains(&self.attack_type) {
            2 * self.eff_power()
        } else if o.immune.contains(&self.attack_type) {
            0
        } else {
            self.eff_power()
        }
    }
}

impl cmp::PartialOrd for Group {
    fn partial_cmp(&self, o: &Group) -> Option<cmp::Ordering> {
        self.sort_key().partial_cmp(&o.sort_key())
    }
}

impl cmp::Ord for Group {
    fn cmp(&self, o: &Group) -> cmp::Ordering {
        self.sort_key().cmp(&o.sort_key())
    }
}

type Army = Vec<Group>;

fn parse_group(line: &str) -> Group {
    lazy_static! {
        static ref RE: Regex = Regex::new(r"^(\d+) units each with (\d+) hit points(?: \((?:(\w+) to ([\w, ]+))?(?:; )?(?:(\w+) to ([\w, ]+))?\))? with an attack that does (\d+) (\w+) damage at initiative (\d+)$").unwrap();
    }

    let caps = match RE.captures(line) {
        Some(caps) => caps,
        None => panic!("Unparseable group"),
    };

    let weak;
    let immune;
    match (caps.get(3), caps.get(5)) {
        (None, None) => {
            weak = "";
            immune = "";
        }
        (Some(s), None) if s.as_str() == "weak" => {
            weak = &caps.get(4).unwrap().as_str();
            immune = "";
        }
        (Some(s), None) if s.as_str() == "immune" => {
            immune = &caps.get(4).unwrap().as_str();
            weak = "";
        }
        (Some(s1), Some(s2)) if s1.as_str() == "weak" && s2.as_str() == "immune" => {
            weak = &caps.get(4).unwrap().as_str();
            immune = &caps.get(6).unwrap().as_str();
        }
        (Some(s1), Some(s2)) if s1.as_str() == "immune" && s2.as_str() == "weak" => {
            immune = &caps.get(4).unwrap().as_str();
            weak = &caps.get(6).unwrap().as_str();
        }
        _ => panic!("Strange group"),
    }

    let weak_v = if weak.len() == 0 { Vec::new() } else { weak.split(", ").collect() };
    let immune_v = if immune.len() == 0 { Vec::new() } else { immune.split(", ").collect() };

    Group {
        units: caps.get(1).unwrap().as_str().parse().unwrap(),
        hp: caps.get(2).unwrap().as_str().parse().unwrap(),
        damage: caps.get(7).unwrap().as_str().parse().unwrap(),
        initiative: caps.get(9).unwrap().as_str().parse().unwrap(),
        attack_type: caps.get(8).unwrap().as_str().parse().unwrap(),
        weak: weak_v.iter().map(|s| s.parse().unwrap()).collect(),
        immune: immune_v.iter().map(|s| s.parse().unwrap()).collect(),
    }
}

fn parse_army<T: BufRead>(mut lines: iter::Peekable<io::Lines<T>>) -> (iter::Peekable<io::Lines<T>>, Army) {
    let mut army = Vec::new();
    loop {
        match lines.peek() {
            Some(Ok(line)) if line.len() > 0 => {
                army.push(parse_group(&lines.next().unwrap().unwrap()));
            }
            _ => break,
        }
    }
    (lines, army)
}

fn parse_file<T: BufRead>(reader: T) -> (Army, Army) {
    let mut lines = reader.lines().peekable();
    assert!(lines.next().unwrap().unwrap() == "Immune System:");
    let (mut lines, army1) = parse_army(lines);
    assert!(lines.next().unwrap().unwrap() == "");
    assert!(lines.next().unwrap().unwrap() == "Infection:");
    let (_lines, army2) = parse_army(lines);
    (army1, army2)
}

type Id = usize;

#[derive(Clone)]
struct Field {
    army1: Army,
    army2: Army,
}

impl Field {
    fn get_group(&self, id: Id) -> &Group {
        if id >= self.army1.len() {
            &self.army2[id - self.army1.len()]
        } else {
            &self.army1[id]
        }
    }

    fn get_group_mut(&mut self, id: Id) -> &mut Group {
        if id >= self.army1.len() {
            &mut self.army2[id - self.army1.len()]
        } else {
            &mut self.army1[id]
        }
    }

    fn num_groups(&self) -> Id {
        self.army1.len() + self.army2.len()
    }

    fn other_groups(&self, id: Id) -> ops::Range<Id> {
        if id < self.army1.len() {
            self.army1.len()..self.num_groups()
        } else {
            0..self.army1.len()
        }
    }

    fn damage_to(&self, id: Id, id2: Id) -> i32 {
        self.get_group(id).damage_to(self.get_group(id2))
    }

    fn cleanup(&mut self) {
        self.army1.retain(|g| g.units > 0);
        self.army2.retain(|g| g.units > 0);
    }

    #[used]
    fn print(&self) {
        println!("");
        println!("Immune System:");
        for (i, group) in self.army1.iter().enumerate() {
            println!("Group {} contains {} units", i + 1, group.units);
        }

        println!("Infection:");
        for (i, group) in self.army2.iter().enumerate() {
            println!("Group {} contains {} units", i + 1, group.units);
        }
    }

    #[used]
    fn id_str(&self, id: Id) -> String {
        format!("{} group {}",
                if id < self.army1.len() { "Immune System" } else { "Infection" },
                1 + if id < self.army1.len() { id } else { id - self.army1.len() })
    }
}

fn select_targets(field: &Field) -> HashMap<Id, Option<Id>> {
    let mut order = (0..field.num_groups()).collect::<Vec<_>>();
    order.sort_by_key(|&id| field.get_group(id).sort_key());

    let mut mapping = HashMap::new();
    let mut taken = vec![false; field.num_groups()];

    for id in order {
        let max_damage = field.other_groups(id)
                .filter(|&id2| !taken[id2])
                .map(|id2| {
                    let dmg = field.damage_to(id, id2);
                    // println!("{} would deal defending group {} {} damage", field.id_str(id), field.id_str(id2), dmg);
                    dmg
                })
                .max();

        let max_damage = match max_damage {
            Some(d) if d > 0 => d,
            _ => {
                mapping.insert(id, None);
                continue;
            }
        };

        let target = field.other_groups(id)
                .filter(|&id2| !taken[id2] && field.damage_to(id, id2) == max_damage)
                .min_by_key(|&id2| field.get_group(id2).sort_key()).unwrap();

        // println!("  chooses {}", field.id_str(target));

        mapping.insert(id, Some(target));
        taken[target] = true;
    }

    mapping
}

fn perform_attacks(field: &mut Field, mapping: &HashMap<Id, Option<Id>>) -> bool {
    let mut order = (0..field.num_groups()).collect::<Vec<_>>();
    order.sort_by_key(|&id| cmp::Reverse(field.get_group(id).initiative));

    let mut changed = false;

    for id in order {
        let group = field.get_group(id);
        if group.units == 0 {
            continue;
        }

        if let Some(&Some(target)) = mapping.get(&id) {
            let group2 = field.get_group(target);
            let res_units = cmp::max(0, group2.units - group.damage_to(group2) / group2.hp);

            if res_units < group2.units {
                changed = true;
            }

            field.get_group_mut(target).units = res_units;
        }
    }

    changed
}

fn simulate(mut field: Field) -> (i32, i32) {
    // println!("########################################################################");
    loop {
        // field.print();

        let targets = select_targets(&field);
        if !perform_attacks(&mut field, &targets) {
            break;
        }
        field.cleanup();

        if field.army1.len() == 0 || field.army2.len() == 0 {
            break;
        }
    }

    let collect = |v: &[Group]| v.iter().map(|g| g.units).sum::<i32>();
    (collect(&field.army1), collect(&field.army2))
}

pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
    let (army1, army2) = parse_file(reader);
    let field = Field { army1, army2 };

    let (r1, r2) = simulate(field.clone());
    let part1 = cmp::max(r1, r2);

    let mut part2 = 0;

    for boost in 1.. {
        let mut f2 = field.clone();
        for i in 0..f2.army1.len() {
            f2.army1[i].damage += boost;
        }

        let (r1, r2) = simulate(f2);
        // println!("{} {} {}", boost, r1, r2);
        if r1 > r2 && r2 == 0 {
            part2 = r1;
            break;
        }
    }

    Ok((part1.to_string(), part2.to_string()))
}