1 files changed, 327 insertions, 0 deletions
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()))
+}