1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#include "aoc.h"
#include <string.h>
#include <vector>
namespace aoc2015 {
static spell bosskill = {"bosskill", 0, 1, 8, 0, 0, 0, 0};
static spell spells[5] = {
{"Magic Missile", 53, 1, 4, 0, 0, 0, 0},
{"Drain", 73, 1, 2, 2, 0, 0, 0},
{"Shield", 113, 6, 0, 0, 0, 7, 0},
{"Poison", 173, 6, 3, 0, 0, 0, 0},
{"Recharge", 229, 5, 0, 0, 101, 0, 0},
};
// spells wizard w can pick
std::vector<spell*> can_spell(const wizard& w) {
std::vector<spell*> is;
for (int i = 0; i < 5; i++) {
spell* s = w.wp->spells[i];
if (s != nullptr && s->tick == 0 && w.mana >= s->costs) {
is.push_back(s);
}
}
return is;
}
char * indent(int t) {
static char idn[60] = {0};
memset(idn, 0, 60);
for (int i = 0; i < ((t+1) / 2) * 2; i++) {
idn[i] = ' ';
}
return idn;
}
void start_of_each_turn (int t, wizard& me, wizard& boss) {
// printf("%sT[%d] boss[%d] player[%d] armor[%d] mana[%d]\n", indent(t), t, boss.points, me.points, me.armor, me.mana);
for (int i = 0; i < 5; i++) {
spell* s = boss.spells[i];
if (s->tick > 0) {
// printf("%sT[%d] %s has tick %d\n", indent(t), t, s->name, s->tick);
if (strcmp(s->name, "Magic Missile") == 0 && t % 2 == 0) {
boss.points -= s->damage;
}
if (strcmp(s->name, "Drain") == 0 && t % 2 == 0) {
boss.points -= s->damage;
me.points += s->heals;
}
if (strcmp(s->name, "Shield") == 0) {
me.armor = 7;
}
if (strcmp(s->name, "Poison") == 0) {
boss.points -= s->damage;
}
if (strcmp(s->name, "Recharge") == 0) {
me.mana += s->payback;
}
s->tick -= 1;
}
else {
if (strcmp(s->name, "Shield") == 0) {
me.armor = 0;
}
}
}
}
void save_ticks(int ticks[], spell* spells[]) {
for(int i = 0; i < 5; i++) {
ticks[i] = spells[i]->tick;
}
}
void undo_ticks(int ticks[], spell* spells[]) {
for(int i = 0; i < 5; i++) {
spells[i]->tick = ticks[i];
}
}
void fight(int turn, wizard me, wizard boss, int cost, std::vector<int>& costs) {
start_of_each_turn(turn, me, boss);
if (turn > 18) return; // !!! THIS IS IMPORTANT !!!
if (turn % 2 == 1) { // my turn
// me.points -= 1; // part 2
if (me.points > 0) {
auto ss = can_spell(me);
for(auto& s : ss) {
// printf("%sT[%d] choose %s =============\n", indent(turn), turn, s->name);
s->tick = s->turns;
me.mana -= s->costs;
int ticks[5] = {0};
save_ticks(ticks, boss.spells);
fight(turn+1, me, boss, cost + s->costs, costs);
undo_ticks(ticks, boss.spells);
me.mana += s->costs;
s->tick = 0;
}
}
} else { // boss turn
if (boss.points <= 0) { // boss lose
// printf("%sT[%d] player win %d\n", indent(turn), turn, cost);
costs.push_back(cost);
}
else {
me.points -= bosskill.damage - me.armor;
fight(turn+1, me, boss, cost, costs);
}
}
}
std::pair<int, int> day22(wizard me, wizard boss) {
me.wp = &boss;
boss.wp = &me;
me.spells[0] = &bosskill;
for (int i = 0; i < 5; i++) {
boss.spells[i] = spells + i;
}
std::vector<int> costs;
fight(1, me, boss, 0, costs);
int min{INT32_MAX};
for(auto& c : costs) {
if (c < min) {
min = c;
}
}
return {min, 0};
}
}
|
