year2015/
day22.rs

1use utils::prelude::*;
2
3/// RPG spell combinations.
4#[derive(Clone, Debug)]
5pub struct Day22 {
6    boss_health: u32,
7    boss_damage: u32,
8}
9
10impl Day22 {
11    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
12        let (boss_health, boss_damage) = parser::u32()
13            .with_prefix("Hit Points: ")
14            .then(parser::u32().with_prefix("\nDamage: "))
15            .parse_complete(input)?;
16
17        Ok(Self {
18            boss_health,
19            boss_damage,
20        })
21    }
22
23    #[must_use]
24    pub fn part1(&self) -> u32 {
25        self.min_mana(false)
26    }
27
28    #[must_use]
29    pub fn part2(&self) -> u32 {
30        self.min_mana(true)
31    }
32
33    fn min_mana(&self, hard_difficulty: bool) -> u32 {
34        let mut min = u32::MAX;
35
36        State {
37            boss_health: self.boss_health,
38            boss_damage: self.boss_damage,
39            hard_difficulty,
40            player_health: 50,
41            player_mana: 500,
42            spent_mana: 0,
43            shield_timer: 0,
44            poison_timer: 0,
45            recharge_timer: 0,
46        }
47        .player_turn(&mut min);
48
49        min
50    }
51}
52
53#[derive(Clone, Copy, Debug)]
54struct State {
55    boss_health: u32,
56    boss_damage: u32,
57    hard_difficulty: bool,
58    player_health: u32,
59    player_mana: u32,
60    spent_mana: u32,
61    shield_timer: u32,
62    poison_timer: u32,
63    recharge_timer: u32,
64}
65
66impl State {
67    fn player_turn(mut self, min_mana_to_win: &mut u32) {
68        if self.hard_difficulty {
69            if self.player_health <= 1 {
70                // Lose
71                return;
72            }
73            self.player_health -= 1;
74        }
75
76        self.apply_effects();
77        if self.boss_health == 0 {
78            // Win
79            *min_mana_to_win = self.spent_mana.min(*min_mana_to_win);
80            return;
81        }
82
83        // Poison
84        if self.player_mana >= 173 && self.poison_timer == 0 {
85            State {
86                player_mana: self.player_mana - 173,
87                spent_mana: self.spent_mana + 173,
88                poison_timer: 6,
89                ..self
90            }
91            .boss_turn(min_mana_to_win);
92        }
93
94        // Recharge
95        if self.player_mana >= 229 && self.recharge_timer == 0 {
96            State {
97                player_mana: self.player_mana - 229,
98                spent_mana: self.spent_mana + 229,
99                recharge_timer: 5,
100                ..self
101            }
102            .boss_turn(min_mana_to_win);
103        }
104
105        // Shield
106        if self.player_mana >= 113 && self.shield_timer == 0 {
107            State {
108                player_mana: self.player_mana - 113,
109                spent_mana: self.spent_mana + 113,
110                shield_timer: 6,
111                ..self
112            }
113            .boss_turn(min_mana_to_win);
114        }
115
116        // Magic missile
117        if self.player_mana >= 53 {
118            State {
119                boss_health: self.boss_health.saturating_sub(4),
120                player_mana: self.player_mana - 53,
121                spent_mana: self.spent_mana + 53,
122                ..self
123            }
124            .boss_turn(min_mana_to_win);
125        }
126
127        // Drain
128        if self.player_mana >= 73 {
129            State {
130                boss_health: self.boss_health.saturating_sub(2),
131                player_health: self.player_health + 2,
132                player_mana: self.player_mana - 73,
133                spent_mana: self.spent_mana + 73,
134                ..self
135            }
136            .boss_turn(min_mana_to_win);
137        }
138    }
139
140    #[inline]
141    fn boss_turn(mut self, min_mana_to_win: &mut u32) {
142        // Calculate a lower bound on the remaining mana required to defeat the boss by calculating
143        // the minimum number of additional spells the player must cast, multiplied by the cost of
144        // the cheapest spell. Return early unless this lower bound plus the already spent mana is
145        // less than the current record
146        let min_casts = self.boss_health / (3 + 3 + 4); // Poison + Poison + Magic Missiles
147        if self.spent_mana + (min_casts * 53) >= *min_mana_to_win {
148            return;
149        }
150
151        self.apply_effects();
152        if self.boss_health == 0 {
153            // Win
154            *min_mana_to_win = self.spent_mana.min(*min_mana_to_win);
155            return;
156        }
157
158        let armor = if self.shield_timer > 0 { 7 } else { 0 };
159        let boss_damage = self.boss_damage.saturating_sub(armor).max(1);
160        if self.player_health <= boss_damage || self.player_mana < 53 {
161            // Lose
162            return;
163        }
164        self.player_health -= boss_damage;
165
166        self.player_turn(min_mana_to_win)
167    }
168
169    #[inline]
170    fn apply_effects(&mut self) {
171        if self.shield_timer > 0 {
172            self.shield_timer -= 1;
173        }
174
175        if self.poison_timer > 0 {
176            self.poison_timer -= 1;
177            self.boss_health = self.boss_health.saturating_sub(3);
178        }
179
180        if self.recharge_timer > 0 {
181            self.recharge_timer -= 1;
182            self.player_mana += 101;
183        }
184    }
185}
186
187examples!(Day22 -> (u32, u32) []);
year2015/day22.rs

year2015/
day22.rs
