Day 24: Simulating army fights

2 files changed, 224 insertions, 2 deletions

diff --git a/inputs/24.txt b/inputs/24.txt
new file mode 100644
index 0000000..0c90bb1
--- /dev/null
+++ b/inputs/24.txt
@@ -0,0 +1,23 @@
+Immune System:
+2991 units each with 8084 hit points (weak to fire) with an attack that does 19 radiation damage at initiative 11
+4513 units each with 3901 hit points (weak to slashing; immune to bludgeoning, radiation) with an attack that does 7 bludgeoning damage at initiative 12
+5007 units each with 9502 hit points (immune to bludgeoning; weak to fire) with an attack that does 16 fire damage at initiative 2
+2007 units each with 5188 hit points (weak to radiation) with an attack that does 23 cold damage at initiative 9
+1680 units each with 1873 hit points (immune to bludgeoning; weak to radiation) with an attack that does 10 bludgeoning damage at initiative 10
+1344 units each with 9093 hit points (immune to bludgeoning, cold; weak to radiation) with an attack that does 63 cold damage at initiative 16
+498 units each with 2425 hit points (immune to fire, bludgeoning, cold) with an attack that does 44 slashing damage at initiative 3
+1166 units each with 7295 hit points with an attack that does 56 bludgeoning damage at initiative 8
+613 units each with 13254 hit points (immune to radiation, cold, fire) with an attack that does 162 radiation damage at initiative 15
+1431 units each with 2848 hit points (weak to radiation) with an attack that does 19 cold damage at initiative 1
+
+Infection:
+700 units each with 47055 hit points (weak to fire; immune to slashing) with an attack that does 116 fire damage at initiative 14
+2654 units each with 13093 hit points (weak to radiation) with an attack that does 8 radiation damage at initiative 19
+5513 units each with 18026 hit points (immune to radiation; weak to slashing) with an attack that does 6 slashing damage at initiative 20
+89 units each with 48412 hit points (weak to cold) with an attack that does 815 radiation damage at initiative 17
+2995 units each with 51205 hit points (weak to cold) with an attack that does 28 slashing damage at initiative 7
+495 units each with 21912 hit points with an attack that does 82 cold damage at initiative 13
+2911 units each with 13547 hit points with an attack that does 7 slashing damage at initiative 18
+1017 units each with 28427 hit points (immune to fire) with an attack that does 52 fire damage at initiative 4
+2048 units each with 29191 hit points (weak to bludgeoning) with an attack that does 22 bludgeoning damage at initiative 6
+1718 units each with 15725 hit points (immune to cold) with an attack that does 18 slashing damage at initiative 5
diff --git a/src/bin/day_24.rs b/src/bin/day_24.rs
index 0053f3d..d52f7d0 100644
--- a/src/bin/day_24.rs
+++ b/src/bin/day_24.rs
@@ -3,16 +3,215 @@ use advent_of_code_2018::*;
 
 use std::error::Error;
 use std::path::PathBuf;
+use std::str::FromStr;
+
+use std::collections::HashMap;
 
 // cargo watch -cs "cargo run --release --bin day_24"
 
+#[derive(Debug, Clone)]
+struct Army {
+    units: u32,
+    hp: u32,
+    weaknesses: Vec<String>,
+    immunities: Vec<String>,
+    damage_type: String,
+    damage: u32,
+    initiative: u32
+}
+
+impl Army {
+    fn effective_power(&self) -> u32 {
+        self.units * self.damage
+    }
+
+    fn actual_damage(&self, other: &Army) -> u32 {
+        let modifier = if other.weaknesses.contains(&self.damage_type) {
+            2
+        } else if other.immunities.contains(&self.damage_type) {
+            0
+        } else {
+            1
+        };
+        self.effective_power() * modifier
+    }
+}
+
+impl FromStr for Army {
+    type Err = Box<Error>;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        // 2991 units each with 8084 hit points (weak to fire) with an attack that does 19 radiation damage at initiative 11
+        let mut words = s.split_whitespace();
+        let units = words.next().unwrap().parse()?;
+        let hp = words.nth(3).unwrap().parse()?;
+        let _ = words.nth(1);
+        
+        let mut weaknesses = Vec::new();
+        let mut immunities = Vec::new();
+        
+        let mut bracket_handled = false;
+        while !bracket_handled {
+            let maybe_weak_or_immune = words.next().unwrap().trim_matches(|c: char| !c.is_alphabetic());
+            if maybe_weak_or_immune == "weak" {
+                let mut weakness = words.nth(1).unwrap();
+                weaknesses.push(weakness.trim_matches(|c: char| !c.is_alphabetic()).to_string());
+                while weakness.ends_with(',') {
+                    weakness = words.next().unwrap();
+                    weaknesses.push(weakness.trim_matches(|c: char| !c.is_alphabetic()).to_string());
+                }
+            }
+            else if maybe_weak_or_immune == "immune" {
+                let mut immunity = words.nth(1).unwrap();
+                immunities.push(immunity.trim_matches(|c: char| !c.is_alphabetic()).to_string());
+                while immunity.ends_with(',') {
+                    immunity = words.next().unwrap();
+                    immunities.push(immunity.trim_matches(|c: char| !c.is_alphabetic()).to_string());
+                }
+            }
+            else {
+                bracket_handled = true;
+            }
+        }
+        let damage = words.nth(4).unwrap().parse()?;
+        let damage_type = words.next().unwrap().to_string();
+        let initiative = words.nth(3).unwrap().parse()?;
+        
+        Ok(Army {
+            units, hp, weaknesses, immunities, damage_type, damage, initiative
+        })
+    }
+}
+
+
+
 fn main() -> Result<(), Box<Error>> {
     let input = read_file(&PathBuf::from("inputs/24.txt"))?;
 
-    println!("Input: {:?}", input);
-
+    let mut input_iter = input.iter();
+    let _ = input_iter.next();
+    let immune_army: Vec<Army> = input_iter.by_ref()
+        .take_while(|&line| line != "Infection:")
+        .map(|line| line.parse().unwrap())
+        .collect();
+    let infection_army: Vec<Army> = input_iter
+        .map(|line| line.parse().unwrap())
+        .collect();
 
+    let (unboosted_immune_army_size, unboosted_infection_army_size) = simulate(&immune_army, &infection_army, 0);
+    debug!(unboosted_immune_army_size);
+    debug!(unboosted_infection_army_size);
 
+    for boost in 0.. {
+        debug!(boost);
+        let (immune_army_size, infection_army_size) = simulate(&immune_army, &infection_army, boost);
+        debug!(immune_army_size);
+        debug!(infection_army_size);
+        if immune_army_size > 0 {
+            break;
+        }
+    }
 
     Ok(())
 }
+
+
+fn target_selection(targeting_army: &Vec<Army>, targeted_army: &Vec<Army>) -> HashMap<usize, usize> {
+    let mut targets = HashMap::new();
+    for (i, army) in targeting_army.iter().enumerate() {
+        let best_target = (0..targeted_army.len())
+            .filter(|potential_target| !targets.values().any(|targeted| targeted == potential_target))
+            .fold(None, |best_target, next| {
+                let next_actual_damage = army.actual_damage(&targeted_army[next]);
+                let last_best_actual_damage = best_target.map(|best_target| army.actual_damage(&targeted_army[best_target])).unwrap_or(0);
+                let next_effective_power = targeted_army[next].effective_power();
+                let last_best_effective_power = best_target.map(|best_target: usize| targeted_army[best_target].effective_power()).unwrap_or(0);
+                let next_initiative = targeted_army[next].initiative;
+                let last_best_initiative = best_target.map(|best_target| targeted_army[best_target].initiative).unwrap_or(0);
+                if next_actual_damage == 0 && last_best_actual_damage == 0 {
+                    None
+                } else if next_actual_damage > last_best_actual_damage {
+                    Some(next)
+                } else if next_actual_damage == last_best_actual_damage && next_effective_power > last_best_effective_power {
+                    Some(next)
+                } else if next_actual_damage == last_best_actual_damage && next_effective_power == last_best_effective_power && next_initiative > last_best_initiative {
+                    Some(next)
+                } else {
+                    best_target
+                }
+            });
+
+        if let Some(best_target) = best_target {
+            targets.insert(i, best_target);
+        }
+    }
+
+    targets
+}
+
+fn attack(aggressor: &Army, target: &mut Army) {
+    let damage =  aggressor.actual_damage(target);
+    let units_destroyed = damage / target.hp;
+    target.units = target.units.saturating_sub(units_destroyed);
+}
+
+
+fn simulate(immune_army: &[Army], infection_army: &[Army], boost: u32) -> (u32, u32) {
+    let mut infection_army = Vec::from(infection_army);
+    
+    let mut immune_army: Vec<Army> = immune_army.iter().map(|army| Army {
+        damage: army.damage + boost,
+        ..army.clone()
+    }).collect();
+
+    let mut watchdog_sum = immune_army.iter().map(|a| a.units).sum::<u32>() + infection_army.iter().map(|a| a.units).sum::<u32>();
+    while immune_army.len() > 0 && infection_army.len() > 0 {
+        immune_army.sort_by(|a, b| b.effective_power().cmp(&a.effective_power()).then(b.initiative.cmp(&a.initiative)));
+        infection_army.sort_by(|a, b| b.effective_power().cmp(&a.effective_power()).then(b.initiative.cmp(&a.initiative)));
+
+        let mut immune_targets = target_selection(&immune_army, &infection_army);
+        let mut infection_targets = target_selection(&infection_army, &immune_army);
+
+        while immune_targets.len() > 0 || infection_targets.len() > 0 {
+            let next_immune = immune_targets.keys()
+                .map(|&k| (k, immune_army[k].initiative.clone()))
+                .max_by_key(|(_, initiative)| *initiative);
+            let next_infection = infection_targets.keys()
+                .map(|&k| (k, infection_army[k].initiative.clone()))
+                .max_by_key(|(_, initiative)| *initiative);
+            match (next_immune, next_infection) {
+                (None, None) => {
+                    panic!("No targets left")
+                },
+                (Some((immune_key, immune_init)), Some((_infect_key, infect_init))) if immune_init > infect_init => {
+                    attack(&immune_army[immune_key], &mut infection_army[*immune_targets.get(&immune_key).unwrap()]);
+                    immune_targets.remove(&immune_key);
+                },
+                (Some((_immune_key, _immune_init)), Some((infect_key, _infect_init))) => {
+                    attack(&infection_army[infect_key], &mut immune_army[*infection_targets.get(&infect_key).unwrap()]);
+                    infection_targets.remove(&infect_key);
+                },
+                (Some((immune_key, _immune_init)), None) => {
+                    attack(&immune_army[immune_key], &mut infection_army[*immune_targets.get(&immune_key).unwrap()]);
+                    immune_targets.remove(&immune_key);
+                },
+                (None, Some((infect_key, _infect_init))) => {
+                    attack(&infection_army[infect_key], &mut immune_army[*infection_targets.get(&infect_key).unwrap()]);
+                    infection_targets.remove(&infect_key);
+                }
+            };
+        }
+
+        immune_army.retain(|a| a.units > 0);
+        infection_army.retain(|a| a.units > 0);
+
+        let new_watchdog_sum = immune_army.iter().map(|a| a.units).sum::<u32>() + infection_army.iter().map(|a| a.units).sum::<u32>();
+        if watchdog_sum == new_watchdog_sum {
+            // Stalemate! Everyone loses.
+            return (0, 0);
+        }
+        watchdog_sum = new_watchdog_sum;
+    }
+
+    (immune_army.iter().map(|a| a.units).sum(), infection_army.iter().map(|a| a.units).sum())
+}