1use 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 #[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 #[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 let damage_per_turn = 4 + 6; let mana_per_turn = 53; spent + (boss_hp + (damage_per_turn - 1) - 6) / damage_per_turn * mana_per_turn
91}
92
93fn 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 if state.apply_spell_effects() {
116 return ControlFlow::Break(spent);
117 }
118
119 if hard_mode {
121 if state.player_hp > 1 {
122 state.player_hp -= 1;
123 } else {
124 continue;
125 }
126 }
127
128 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 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 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 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 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 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}