aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorkaiwu <kaiwu2004@gmail.com>2023-01-10 17:49:55 +0800
committerkaiwu <kaiwu2004@gmail.com>2023-01-10 17:49:55 +0800
commit2b81cfc18ddc268a26ccb260760e14ed0384c99e (patch)
treedb7ca2e65678f88a21537258687336f8e99613e4 /src
parent6d7566a1462d9e610500ca8129a45f4307a0b9e0 (diff)
downloadadvent-of-code-2b81cfc18ddc268a26ccb260760e14ed0384c99e.tar.gz
advent-of-code-2b81cfc18ddc268a26ccb260760e14ed0384c99e.zip
2022 day16 part1
Diffstat (limited to 'src')
-rw-r--r--src/2022/day16/aoc.cpp46
1 files changed, 35 insertions, 11 deletions
diff --git a/src/2022/day16/aoc.cpp b/src/2022/day16/aoc.cpp
index 460b29a..05e1d47 100644
--- a/src/2022/day16/aoc.cpp
+++ b/src/2022/day16/aoc.cpp
@@ -9,12 +9,14 @@ namespace aoc2022 {
struct valve_m {
valve* v;
int m;
+
+ friend bool operator<(valve_m v1, valve_m v2) { return v1.m < v2.m ? true : v1.m > v2.m ? false : v1.v < v2.v; }
};
std::map<line_view, valve*> valves = {};
std::map<valve*, std::vector<valve_m>> diagram;
-size_t maxopened = 0;
+int maxopened = 0;
static valve* get(line_view lv) {
auto p = valves.insert({lv, nullptr});
@@ -59,26 +61,39 @@ void update_total(int* total, std::set<valve*>& opened) {
}
// m minutes left at v
-void flow(int m, valve* v, std::set<valve*> opened, int total, int* max) {
+void flow(int m, valve* v, std::map<valve_m, int>& visited, std::set<valve*> opened, int os, int total, int* max) {
+ update_total(&total, opened);
if (m == 0) {
if (*max < total) {
*max = total;
}
} else {
- update_total(&total, opened);
+ auto p = visited.insert({{v, m}, total});
+ if (!p.second) {
+ if (total <= p.first->second) {
+ return;
+ } else {
+ p.first->second = total;
+ }
+ }
std::cout << "at " << v->name << " when " << m << " minutes left, total is " << total << std::endl;
- if (opened.size() >= maxopened) {
- flow(m - 1, v, opened, total, max);
+ if (os >= maxopened) {
+ flow(m - 1, v, visited, opened, os, total, max);
} else {
- if (v->rate > 0 && opened.find(v) == opened.end()) {
- m -= 1;
+ if (opened.find(v) == opened.end()) {
+ if (v->rate > 0) {
+ os += 1;
+ m -= 1;
+ }
opened.insert(v);
}
// choose next
for (auto& n : diagram[v]) {
- if (m >= n.m && opened.find(n.v) == opened.end()) {
- flow(m - n.m, n.v, opened, total, max);
+ if (m >= n.m) {
+ auto v = visited;
+ flow(m - n.m, n.v, visited, opened, os, total, max);
+ visited = v;
}
}
}
@@ -102,7 +117,7 @@ std::pair<int, int> day16(line_view file) {
rank_neighbours(v, visited);
std::vector<valve_m> vs;
for (auto& kv : visited) {
- if (kv.first != v && kv.first->rate > 0) {
+ if (kv.first != v) {
vs.emplace_back(valve_m{kv.first, kv.second});
}
}
@@ -110,9 +125,18 @@ std::pair<int, int> day16(line_view file) {
diagram.insert({v, vs});
}
+ for (auto& kv : diagram) {
+ std::cout << kv.first->name << ": ";
+ for (auto& m : kv.second) {
+ std::cout << m.v->name << "(" << m.m << ") ";
+ }
+ std::cout << std::endl;
+ }
+
int max{INT32_MIN};
std::set<valve*> opened;
- flow(29, get("BB"), opened, 0, &max);
+ std::map<valve_m, int> visited;
+ flow(30, get("AA"), visited, opened, 0, 0, &max);
printf("%d\n", max);