Skip to main content

aoc/year2015/
day22.rs

1//! # Wizard Simulator 20XX
2//!
3//! [A* algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm) is ideal for solving this
4//! problem. A node in the graph is our current state and each edge is represented by casting a
5//! spell to get to a new state.
6//!
7//! The key to optimizing is to cache previously seen states. As we receive states in strictly
8//! increasing order of mana spent if we see a state again then it cannot possibly be optimal
9//! and we can discard it. As an additional heuristic, for any given state, we know that we must
10//! spend a minimum mana on every turn, and that the game will last for at least as many
11//! turns as it requires for maximum damage to deplete the boss's hit points. This heuristic
12//! does not take into account the fact that maximum damage is only possible while Poison is
13//! still active, where re-casting Poison costs more mana but can end the game faster. That's
14//! okay because as long as the heuristic is consistent, underestimating is fine.
15use std::ops::ControlFlow;
16
17use crate::util::hash::*;
18use crate::util::heap::*;
19use crate::util::iter::*;
20use crate::util::parse::*;
21
22type Input = [i16; 2];
23
24#[derive(Clone, Copy, Eq, Hash, PartialEq)]
25struct State {
26    boss_hp: i16,
27    player_hp: i16,
28    player_mana: i16,
29    shield_effect: u8,
30    poison_effect: u8,
31    recharge_effect: u8,
32    spent: i16,
33}
34
35impl State {
36    /// Applies spell effects to state and returns true if the player has won.
37    #[inline]
38    fn apply_spell_effects(&mut self) -> bool {
39        if self.shield_effect > 0 {
40            self.shield_effect -= 1;
41        }
42        if self.poison_effect > 0 {
43            self.poison_effect -= 1;
44            self.boss_hp -= 3;
45        }
46        if self.recharge_effect > 0 {
47            self.recharge_effect -= 1;
48            self.player_mana += 101;
49        }
50
51        self.boss_hp <= 0
52    }
53
54    /// Applies boss attack and returns true if the wizard survives.
55    #[inline]
56    fn boss_turn(&mut self, mut attack: i16) -> bool {
57        if self.shield_effect > 0 {
58            attack = (attack - 7).max(1);
59        }
60
61        self.player_hp -= attack;
62        self.player_hp > 0 && self.player_mana >= 53
63    }
64}
65
66pub fn parse(input: &str) -> Input {
67    input.iter_signed().chunk::<2>().next().unwrap()
68}
69
70pub fn part1(input: &Input) -> i16 {
71    let ControlFlow::Break(spent) = play(*input, false);
72    spent
73}
74
75pub fn part2(input: &Input) -> i16 {
76    let ControlFlow::Break(spent) = play(*input, true);
77    spent
78}
79
80fn heuristic(spent: i16, boss_hp: i16) -> i16 {
81    // Assume that Poison is still active. This can deal the boss up to 6 damage prior to the next
82    // time we can cast. Beyond that, we must spend mana every turn. The minimum is 53 for Magic
83    // Missile, and we need to survive at least as many turns as what the boss will survive even
84    // if we have maximum damage per turn (the most damage possible is 6 from Poison and 4 from
85    // Magic Missile from here on out). Since this is a heuristic, it does not matter that it
86    // underestimates actual costs needed to keep Poison active, or that the boss will survive
87    // longer than the minimum number of turns for every time we cast a different spell.
88    let damage_per_turn = 4 + 6; // Poison still active and cast Magic Missile
89    let mana_per_turn = 53; // Magic Missile is cheapest to cast
90    spent + (boss_hp + (damage_per_turn - 1) - 6) / damage_per_turn * mana_per_turn
91}
92
93/// The search always ends with a win, so the never type `!` rules out `Continue`.
94fn play(input: Input, hard_mode: bool) -> ControlFlow<i16, !> {
95    let [boss_hp, boss_damage] = input;
96    let start = State {
97        boss_hp,
98        player_hp: 50,
99        player_mana: 500,
100        shield_effect: 0,
101        poison_effect: 0,
102        recharge_effect: 0,
103        spent: 0,
104    };
105
106    let mut todo = MinHeap::new();
107    let mut cache = FastSet::with_capacity(5_000);
108
109    todo.push(heuristic(0, boss_hp), start);
110    cache.insert(start);
111
112    while let Some((_, mut state)) = todo.pop() {
113        let spent = state.spent;
114        // Check winning condition.
115        if state.apply_spell_effects() {
116            return ControlFlow::Break(spent);
117        }
118
119        // Part two
120        if hard_mode {
121            if state.player_hp > 1 {
122                state.player_hp -= 1;
123            } else {
124                continue;
125            }
126        }
127
128        // Apply spell effects and boss turn, returning the winning mana spent if the boss dies.
129        let mut try_cast = |mut next: State| {
130            if next.apply_spell_effects() {
131                return ControlFlow::Break(next.spent);
132            }
133            if next.boss_turn(boss_damage) && cache.insert(next) {
134                todo.push(heuristic(next.spent, next.boss_hp), next);
135            }
136            ControlFlow::Continue(())
137        };
138
139        // Magic Missile
140        if state.player_mana >= 53 {
141            let next = State {
142                boss_hp: state.boss_hp - 4,
143                player_mana: state.player_mana - 53,
144                spent: spent + 53,
145                ..state
146            };
147            try_cast(next)?;
148        }
149
150        // Drain
151        if state.player_mana >= 73 {
152            let next = State {
153                boss_hp: state.boss_hp - 2,
154                player_hp: state.player_hp + 2,
155                player_mana: state.player_mana - 73,
156                spent: spent + 73,
157                ..state
158            };
159            try_cast(next)?;
160        }
161
162        // Shield
163        if state.player_mana >= 113 && state.shield_effect == 0 {
164            let next = State {
165                player_mana: state.player_mana - 113,
166                shield_effect: 6,
167                spent: spent + 113,
168                ..state
169            };
170            try_cast(next)?;
171        }
172
173        // Poison
174        if state.player_mana >= 173 && state.poison_effect == 0 {
175            let next = State {
176                player_mana: state.player_mana - 173,
177                poison_effect: 6,
178                spent: spent + 173,
179                ..state
180            };
181            try_cast(next)?;
182        }
183
184        // Recharge
185        if state.player_mana >= 229 && state.recharge_effect == 0 {
186            let next = State {
187                player_mana: state.player_mana - 229,
188                recharge_effect: 5,
189                spent: spent + 229,
190                ..state
191            };
192            try_cast(next)?;
193        }
194    }
195
196    unreachable!()
197}