aoc/year2015/
day22.rs

1//! # Wizard Simulator 20XX
2//!
3//! [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) is ideal
4//! for solving this problem. A node in the graph is our current state and each edge is
5//! represented by casting a 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.
10use crate::util::hash::*;
11use crate::util::heap::*;
12use crate::util::iter::*;
13use crate::util::parse::*;
14
15type Input = [i16; 2];
16
17#[derive(Clone, Copy, PartialEq, Eq, Hash)]
18struct State {
19    boss_hp: i16,
20    player_hp: i16,
21    player_mana: i16,
22    shield_effect: u8,
23    poison_effect: u8,
24    recharge_effect: u8,
25}
26
27pub fn parse(input: &str) -> Input {
28    input.iter_signed().chunk::<2>().next().unwrap()
29}
30
31pub fn part1(input: &Input) -> i16 {
32    play(*input, false)
33}
34
35pub fn part2(input: &Input) -> i16 {
36    play(*input, true)
37}
38
39fn play(input: Input, hard_mode: bool) -> i16 {
40    let [boss_hp, boss_damage] = input;
41    let start = State {
42        boss_hp,
43        player_hp: 50,
44        player_mana: 500,
45        shield_effect: 0,
46        poison_effect: 0,
47        recharge_effect: 0,
48    };
49
50    let mut todo = MinHeap::new();
51    let mut cache = FastSet::with_capacity(5_000);
52
53    todo.push(0, start);
54    cache.insert(start);
55
56    while let Some((spent, mut state)) = todo.pop() {
57        // Check winning condition
58        if apply_spell_effects(&mut state) {
59            return spent;
60        }
61
62        // Part two
63        if hard_mode {
64            if state.player_hp > 1 {
65                state.player_hp -= 1;
66            } else {
67                continue;
68            }
69        }
70
71        // Magic Missile
72        if state.player_mana >= 53 {
73            let mut next =
74                State { boss_hp: state.boss_hp - 4, player_mana: state.player_mana - 53, ..state };
75
76            if apply_spell_effects(&mut next) {
77                return spent + 53;
78            }
79            if boss_turn(&mut next, boss_damage) && cache.insert(next) {
80                todo.push(spent + 53, next);
81            }
82        }
83
84        // Drain
85        if state.player_mana >= 73 {
86            let mut next = State {
87                boss_hp: state.boss_hp - 2,
88                player_hp: state.player_hp + 2,
89                player_mana: state.player_mana - 73,
90                ..state
91            };
92
93            if apply_spell_effects(&mut next) {
94                return spent + 73;
95            }
96            if boss_turn(&mut next, boss_damage) && cache.insert(next) {
97                todo.push(spent + 73, next);
98            }
99        }
100
101        // Shield
102        if state.player_mana >= 113 && state.shield_effect == 0 {
103            let mut next =
104                State { player_mana: state.player_mana - 113, shield_effect: 6, ..state };
105
106            if apply_spell_effects(&mut next) {
107                return spent + 113;
108            }
109            if boss_turn(&mut next, boss_damage) && cache.insert(next) {
110                todo.push(spent + 113, next);
111            }
112        }
113
114        // Poison
115        if state.player_mana >= 173 && state.poison_effect == 0 {
116            let mut next =
117                State { player_mana: state.player_mana - 173, poison_effect: 6, ..state };
118
119            if apply_spell_effects(&mut next) {
120                return spent + 173;
121            }
122            if boss_turn(&mut next, boss_damage) && cache.insert(next) {
123                todo.push(spent + 173, next);
124            }
125        }
126
127        // Recharge
128        if state.player_mana >= 229 && state.recharge_effect == 0 {
129            let mut next =
130                State { player_mana: state.player_mana - 229, recharge_effect: 5, ..state };
131
132            if apply_spell_effects(&mut next) {
133                return spent + 229;
134            }
135            if boss_turn(&mut next, boss_damage) && cache.insert(next) {
136                todo.push(spent + 229, next);
137            }
138        }
139    }
140
141    unreachable!()
142}
143
144/// Applies spell effects to state and returns true if the player has won.
145#[inline]
146fn apply_spell_effects(state: &mut State) -> bool {
147    if state.shield_effect > 0 {
148        state.shield_effect -= 1;
149    }
150    if state.poison_effect > 0 {
151        state.poison_effect -= 1;
152        state.boss_hp -= 3;
153    }
154    if state.recharge_effect > 0 {
155        state.recharge_effect -= 1;
156        state.player_mana += 101;
157    }
158
159    state.boss_hp <= 0
160}
161
162/// Applies boss attack and returns true if the wizard survives.
163#[inline]
164fn boss_turn(state: &mut State, mut attack: i16) -> bool {
165    if state.shield_effect > 0 {
166        attack = (attack - 7).max(1);
167    }
168
169    state.player_hp -= attack;
170    state.player_hp > 0 && state.player_mana >= 53
171}
aoc/year2015/day22.rs

aoc/year2015/
day22.rs
