From 885b0ea5b8f96bb2ed4424f387b244ef2d67a61e Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
Date: Mon, 24 Dec 2018 18:02:57 +0100
Subject: Day 24
---
2018/input/24.txt | 23 ++++
2018/src/day24.rs | 327 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
2018/src/main.rs | 4 +-
3 files changed, 353 insertions(+), 1 deletion(-)
create mode 100644 2018/input/24.txt
create mode 100644 2018/src/day24.rs
(limited to '2018')
diff --git a/2018/input/24.txt b/2018/input/24.txt
new file mode 100644
index 0000000..2fa319e
--- /dev/null
+++ b/2018/input/24.txt
@@ -0,0 +1,23 @@
+Immune System:
+1614 units each with 8016 hit points (immune to slashing; weak to radiation) with an attack that does 48 fire damage at initiative 9
+3730 units each with 5611 hit points (immune to bludgeoning; weak to fire) with an attack that does 14 radiation damage at initiative 16
+1627 units each with 9770 hit points (weak to cold) with an attack that does 55 fire damage at initiative 3
+4665 units each with 9782 hit points (weak to fire) with an attack that does 18 radiation damage at initiative 10
+281 units each with 5764 hit points (immune to fire; weak to radiation) with an attack that does 187 slashing damage at initiative 19
+524 units each with 9344 hit points with an attack that does 158 cold damage at initiative 15
+5013 units each with 9768 hit points with an attack that does 15 cold damage at initiative 14
+1143 units each with 1822 hit points (weak to radiation) with an attack that does 15 fire damage at initiative 18
+136 units each with 6830 hit points (weak to radiation) with an attack that does 420 slashing damage at initiative 7
+665 units each with 7973 hit points (weak to bludgeoning; immune to slashing) with an attack that does 119 fire damage at initiative 11
+
+Infection:
+515 units each with 8712 hit points (immune to radiation; weak to slashing, fire) with an attack that does 30 cold damage at initiative 1
+5542 units each with 56769 hit points with an attack that does 16 bludgeoning damage at initiative 4
+1663 units each with 10437 hit points (immune to slashing, fire, radiation) with an attack that does 12 radiation damage at initiative 12
+574 units each with 50124 hit points (weak to slashing, radiation) with an attack that does 171 fire damage at initiative 8
+1190 units each with 10652 hit points with an attack that does 16 cold damage at initiative 17
+3446 units each with 23450 hit points with an attack that does 12 fire damage at initiative 5
+5887 units each with 14556 hit points (weak to slashing) with an attack that does 4 radiation damage at initiative 2
+1761 units each with 41839 hit points (weak to cold) with an attack that does 35 cold damage at initiative 20
+4194 units each with 16090 hit points (immune to fire; weak to slashing) with an attack that does 6 fire damage at initiative 6
+2127 units each with 27065 hit points (weak to cold, slashing) with an attack that does 24 slashing damage at initiative 13
diff --git a/2018/src/day24.rs b/2018/src/day24.rs
new file mode 100644
index 0000000..e52b4d9
--- /dev/null
+++ b/2018/src/day24.rs
@@ -0,0 +1,327 @@
+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);
+ }
+
+ 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);
+ }
+ }
+
+ 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()))
+}
diff --git a/2018/src/main.rs b/2018/src/main.rs
index aac9302..85021fe 100644
--- a/2018/src/main.rs
+++ b/2018/src/main.rs
@@ -29,8 +29,9 @@ mod day20;
mod day21;
mod day22;
mod day23;
+mod day24;
-static NUM_DAYS: i32 = 23;
+static NUM_DAYS: i32 = 24;
fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
match day {
@@ -57,6 +58,7 @@ fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
21 => day21::main(reader),
22 => day22::main(reader),
23 => day23::main(reader),
+ 24 => day24::main(reader),
_ => Err(Error::new(ErrorKind::Other, "Invalid day"))
}
}
--
cgit v1.2.3-70-g09d2