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
|
#pragma once
#include "common.h"
#include <map>
#include <set>
#include <vector>
namespace aoc2015 {
struct guest {
line_view name;
std::map<guest*, int> points;
int point(guest* other) {
auto it = points.find(other);
return it != points.end() ? it->second : 0;
}
};
struct party {
std::vector<guest*> guests;
guest* the(line_view lv) {
for (auto g : guests) {
if (g->name == lv) {
return g;
}
}
guests.emplace_back(new guest{lv, {}});
return guests.back();
}
int happiness(std::vector<guest*> gs) const noexcept {
int h = 0;
int size = gs.size();
for (int i = 0; i < size; i++) {
guest* g1 = gs[i];
guest* g2 = i < size - 1 ? gs[i + 1] : gs[0];
h += g1->point(g2);
h += g2->point(g1);
}
return h;
}
int happiness(const char* p) {
int h{0};
while (*p != ' ') {
h = h * 10 + *p - '0';
p++;
}
return h;
}
// backtrace
typedef std::vector<guest*>* arrange_t;
typedef std::vector<std::vector<guest*>> combo_t;
void arrange(guest* g, std::set<guest*>& gs, arrange_t arrangement, combo_t& combos) const noexcept {
if (arrangement->size() == guests.size()) {
combos.push_back(*arrangement);
return;
}
for (auto& kv : g->points) {
if (gs.find(kv.first) != gs.end()) {
continue;
} else {
gs.insert(kv.first);
arrangement->push_back(kv.first);
arrange(kv.first, gs, arrangement, combos);
arrangement->pop_back();
gs.erase(kv.first);
}
}
}
std::pair<int, int> arrange() const noexcept {
combo_t combos;
for (auto g : guests) {
arrange_t arrangement = new std::vector<guest*>;
std::set<guest*> gs;
arrange(g, gs, arrangement, combos);
break;
}
int hmax = INT32_MIN;
int hmin = INT32_MAX;
for (auto c : combos) {
int h = happiness(c);
/*
std::cout << "[" << h << ":";
for (auto x : c) {
std::cout << x->name << " -> ";
}
std::cout << "]" << std::endl;
*/
if (hmax < h) {
hmax = h;
}
if (hmin > h) {
hmin = h;
}
}
return {hmin, hmax};
}
void parse(line_view lv) {
const char* p = lv.line;
const char* p1 = lv.contains("would");
const char* p2 = lv.contains("to");
guest* g1 = the({p, p1 - 1});
guest* g2 = the({p2 + 3, p + lv.length - 2});
int point = happiness(p1 + 11);
if (*(p1 + 6) == 'l') {
point = -point;
}
// std::cout << g1->name << " -> " << g2->name << ":" << point << std::endl;
g1->points.insert({g2, point});
}
void add(const char* x, int h) {
guest* ng = new guest{x, {}};
for (auto g : guests) {
g->points.insert({ng, h});
ng->points.insert({g, h});
}
guests.push_back(ng);
}
};
std::pair<int, int> day13(line_view file, const char* = nullptr);
} // namespace aoc2015
|
