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

year2015/
day22.rs
