Day 24

3 files changed, 353 insertions, 1 deletions

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