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
|
#pragma once
#include "common.h"
#include <vector>
namespace aoc2015 {
struct ingredient {
line_view name;
int capacity;
int durability;
int flavor;
int texture;
int calories;
friend std::ostream& operator<<(std::ostream& o, const ingredient& i) {
o << i.name << " " << i.capacity << " " << i.durability << " " << i.flavor << " " << i.texture << " " << i.calories;
return o;
}
};
struct recipe {
std::vector<ingredient> ingredients;
int score(const std::vector<int>& is, int* cals) {
int capacity = 0;
int durability = 0;
int flavor = 0;
int texture = 0;
int calories = 0;
for (size_t i = 0; i < ingredients.size(); i++) {
capacity += is[i] * ingredients[i].capacity;
durability += is[i] * ingredients[i].durability;
flavor += is[i] * ingredients[i].flavor;
texture += is[i] * ingredients[i].texture;
calories += is[i] * ingredients[i].calories;
}
if (capacity < 0 || durability < 0 || flavor < 0 || texture < 0) {
return 0;
}
if (cals != nullptr && calories != *cals) {
return 0;
}
return capacity * durability * flavor * texture;
}
// backtrace
void measure(int total, size_t index, std::vector<int>& combos, int* best, int* cals) {
if (index == ingredients.size() - 1) { // last ingredient
combos.push_back(total);
int s = score(combos, cals);
// std::cout << "{" << s << " -> ";
// for (auto i : {0, 1, 2, 3}) {
// std::cout << ingredients[i].name << ": " << combos[i] << " ";
// }
// std::cout << "}" << std::endl;
if (s > 0 && s > *best) {
*best = s;
}
combos.pop_back();
return;
}
for (int x = 1; x < total; x++) {
combos.push_back(x);
measure(total - x, index + 1, combos, best, cals);
combos.pop_back();
}
}
int get_number(const char* p) {
int d{0};
int sign{1};
if (*p == '-') {
sign = -1;
p++;
}
while ((*p) >= '0' && (*p) <= '9') {
d = d * 10 + *p - '0';
p++;
}
return sign * d;
}
void parse(line_view line) {
static const char* cs[] = {"capacity", "durability", "flavor", "texture", "calories"};
const char* p0 = line.contains(":");
ingredient x{{line.line, p0}, 0, 0, 0, 0, 0};
int* xs[] = {&x.capacity, &x.durability, &x.flavor, &x.texture, &x.calories};
for (size_t i = 0; i < ARRAY_SIZE(cs); i++) {
const char* p = line.contains(cs[i]);
*xs[i] = get_number(p + strlen(cs[i]) + 1);
}
// std::cout << x << std::endl;
ingredients.push_back(x);
}
};
int day15(line_view, int* cals = nullptr);
} // namespace aoc2015
|
