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.  As an additional heuristic, for any given state, we know that we must
10//! spend a minimum mana on every turn, and that 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; but
14//! that's okay: as long as the heuristic is consitent, underestimating is fine.
15use crate::util::hash::*;
16use crate::util::heap::*;
17use crate::util::iter::*;
18use crate::util::parse::*;
19
20type Input = [i16; 2];
21
22#[derive(Clone, Copy, PartialEq, Eq, Hash)]
23struct State {
24    boss_hp: i16,
25    player_hp: i16,
26    player_mana: i16,
27    shield_effect: u8,
28    poison_effect: u8,
29    recharge_effect: u8,
30    spent: i16,
31}
32
33impl State {
34    /// Applies spell effects to state and returns true if the player has won.
35    #[inline]
36    fn apply_spell_effects(&mut self) -> bool {
37        if self.shield_effect > 0 {
38            self.shield_effect -= 1;
39        }
40        if self.poison_effect > 0 {
41            self.poison_effect -= 1;
42            self.boss_hp -= 3;
43        }
44        if self.recharge_effect > 0 {
45            self.recharge_effect -= 1;
46            self.player_mana += 101;
47        }
48
49        self.boss_hp <= 0
50    }
51
52    /// Applies boss attack and returns true if the wizard survives.
53    #[inline]
54    fn boss_turn(&mut self, mut attack: i16) -> bool {
55        if self.shield_effect > 0 {
56            attack = (attack - 7).max(1);
57        }
58
59        self.player_hp -= attack;
60        self.player_hp > 0 && self.player_mana >= 53
61    }
62}
63
64pub fn parse(input: &str) -> Input {
65    input.iter_signed().chunk::<2>().next().unwrap()
66}
67
68pub fn part1(input: &Input) -> i16 {
69    play(*input, false)
70}
71
72pub fn part2(input: &Input) -> i16 {
73    play(*input, true)
74}
75
76fn heuristic(spent: i16, boss_hp: i16) -> i16 {
77    // Assume that Poison is still active; this can deal the boss up to 6 damage prior to the next
78    // time we can cast.  Beyond that, we must spend mana every turn; the minimum is 53 for Magic
79    // Missile; and we need to survive at least as many turns as what the boss will survive even
80    // if we have maximum damage per turn (the most damage possible is 6 from Poison and 4 from
81    // Magic Missile from here on out).  Since this is a heuristic, it does not matter that it
82    // underestimates actual costs needed to keep Poison active, or that the boss will survive
83    // longer than the minimum number of turns for every time we cast a different spell.
84    let damage_per_turn = 4 + 6; // Poison still active and cast Magic Missile
85    let mana_per_turn = 53; // Magic Missile is cheapest to cast
86    spent + (boss_hp + (damage_per_turn - 1) - 6) / damage_per_turn * mana_per_turn
87}
88
89fn play(input: Input, hard_mode: bool) -> i16 {
90    let [boss_hp, boss_damage] = input;
91    let start = State {
92        boss_hp,
93        player_hp: 50,
94        player_mana: 500,
95        shield_effect: 0,
96        poison_effect: 0,
97        recharge_effect: 0,
98        spent: 0,
99    };
100
101    let mut todo = MinHeap::new();
102    let mut cache = FastSet::with_capacity(5_000);
103
104    todo.push(heuristic(0, boss_hp), start);
105    cache.insert(start);
106
107    while let Some((_, mut state)) = todo.pop() {
108        let spent = state.spent;
109        // Check winning condition
110        if state.apply_spell_effects() {
111            return spent;
112        }
113
114        // Part two
115        if hard_mode {
116            if state.player_hp > 1 {
117                state.player_hp -= 1;
118            } else {
119                continue;
120            }
121        }
122
123        // Magic Missile
124        if state.player_mana >= 53 {
125            let mut next = State {
126                boss_hp: state.boss_hp - 4,
127                player_mana: state.player_mana - 53,
128                spent: spent + 53,
129                ..state
130            };
131
132            if next.apply_spell_effects() {
133                return spent + 53;
134            }
135            if next.boss_turn(boss_damage) && cache.insert(next) {
136                todo.push(heuristic(next.spent, next.boss_hp), next);
137            }
138        }
139
140        // Drain
141        if state.player_mana >= 73 {
142            let mut next = State {
143                boss_hp: state.boss_hp - 2,
144                player_hp: state.player_hp + 2,
145                player_mana: state.player_mana - 73,
146                spent: spent + 73,
147                ..state
148            };
149
150            if next.apply_spell_effects() {
151                return spent + 73;
152            }
153            if next.boss_turn(boss_damage) && cache.insert(next) {
154                todo.push(heuristic(next.spent, next.boss_hp), next);
155            }
156        }
157
158        // Shield
159        if state.player_mana >= 113 && state.shield_effect == 0 {
160            let mut next = State {
161                player_mana: state.player_mana - 113,
162                shield_effect: 6,
163                spent: spent + 113,
164                ..state
165            };
166
167            if next.apply_spell_effects() {
168                return spent + 113;
169            }
170            if next.boss_turn(boss_damage) && cache.insert(next) {
171                todo.push(heuristic(next.spent, next.boss_hp), next);
172            }
173        }
174
175        // Poison
176        if state.player_mana >= 173 && state.poison_effect == 0 {
177            let mut next = State {
178                player_mana: state.player_mana - 173,
179                poison_effect: 6,
180                spent: spent + 173,
181                ..state
182            };
183
184            if next.apply_spell_effects() {
185                return spent + 173;
186            }
187            if next.boss_turn(boss_damage) && cache.insert(next) {
188                todo.push(heuristic(next.spent, next.boss_hp), next);
189            }
190        }
191
192        // Recharge
193        if state.player_mana >= 229 && state.recharge_effect == 0 {
194            let mut next = State {
195                player_mana: state.player_mana - 229,
196                recharge_effect: 5,
197                spent: spent + 229,
198                ..state
199            };
200
201            if next.apply_spell_effects() {
202                return spent + 229;
203            }
204            if next.boss_turn(boss_damage) && cache.insert(next) {
205                todo.push(heuristic(next.spent, next.boss_hp), next);
206            }
207        }
208    }
209
210    unreachable!()
211}
aoc/year2015/day22.rs

aoc/year2015/
day22.rs
