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 { 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, immune: Vec, } 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 { 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; 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(mut lines: iter::Peekable>) -> (iter::Peekable>, 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(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 { 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> { let mut order = (0..field.num_groups()).collect::>(); 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>) -> bool { let mut order = (0..field.num_groups()).collect::>(); 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::(); (collect(&field.army1), collect(&field.army2)) } pub fn main(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())) }