diff options
| -rw-r--r-- | src/2022/day16/aoc.cpp | 45 |
1 files changed, 23 insertions, 22 deletions
diff --git a/src/2022/day16/aoc.cpp b/src/2022/day16/aoc.cpp index 6298483..015aa6f 100644 --- a/src/2022/day16/aoc.cpp +++ b/src/2022/day16/aoc.cpp @@ -111,22 +111,22 @@ struct valve_mm { } }; -std::vector<valve_m> cango(valve* v, int m, const std::map<valve*, int>& opened) { +std::vector<valve_m> cango(valve* v, int m0, int m, const std::map<valve*, int>& opened) { std::vector<valve_m> t; for (auto& vm : diagram[v]) { - if (!is_open(vm.v, opened) && m > vm.m) { + if (!is_open(vm.v, opened) && m > vm.m && m == m0) { t.emplace_back(vm); } } return t; } -void flow(valve_m vs[2], std::map<valve_mm, int> visited, std::map<valve*, int> opened, int os, int total, int* max) { - auto m = std::min(vs[0].m, vs[1].m); +void flow(int m, valve_m vs[2], std::map<valve_mm, int>& visited, std::map<valve*, int> opened, int os, int total, + int* max) { update_total(&total, opened, m); - if (vs[0].m == 0 || vs[1].m == 0) { + if (m == 0) { if (*max < total) { - printf("when (%d, %d) max is %d\n", vs[0].m, vs[1].m, total); + printf("max is %d\n", total); *max = total; } } else { @@ -137,30 +137,28 @@ void flow(valve_m vs[2], std::map<valve_mm, int> visited, std::map<valve*, int> } p.first->second = total; } - // std::cout << os << " opened when " << vs[0].m << "/" << vs[1].m << " minutes left, total is " << total << - // std::endl; + std::cout << os << " opened, " << m << "/" << vs[0].m << "/" << vs[1].m << " m left, total " << total << std::endl; if (os >= maxopened) { - vs[0].m -= vs[0].m > 0 ? 1 : 0; - vs[1].m -= vs[1].m > 0 ? 1 : 0; - flow(vs, visited, opened, os, total, max); + flow(m - 1, vs, visited, opened, os, total, max); } else { for (auto i = 0; i < 2; i++) { - if (!is_open(vs[i].v, opened)) { + if (vs[i].m == m && !is_open(vs[i].v, opened)) { if (vs[i].v->rate > 0) { os += 1; vs[i].m -= 1; } // std::cout << vs[i].v->name << " opened with " << vs[i].m << " minutes left" << std::endl; - opened.insert({vs[i].v, vs[i].m}); + opened.insert({vs[i].v, m}); } } if (os >= maxopened) { - // vs[0].m -= vs[0].m > 0 ? 1 : 0; - // vs[1].m -= vs[1].m > 0 ? 1 : 0; - flow(vs, visited, opened, os, total, max); + flow(m - 1, vs, visited, opened, os, total, max); } else { - auto ns0 = cango(vs[0].v, vs[0].m, opened); - auto ns1 = cango(vs[1].v, vs[1].m, opened); + auto ns0 = cango(vs[0].v, vs[0].m, m, opened); + auto ns1 = cango(vs[1].v, vs[1].m, m, opened); + if (ns0.size() == 0 && ns1.size() == 0) { + flow(m - 1, vs, visited, opened, os, total, max); + } if (ns0.size() == 0 && ns1.size() > 0) { for (auto& n : ns1) { valve_m vx[2]; @@ -169,7 +167,8 @@ void flow(valve_m vs[2], std::map<valve_mm, int> visited, std::map<valve*, int> vx[1].m -= n.m; vx[1].v = n.v; - flow(vx, visited, opened, os, total, max); + auto v = visited; + flow(m - 1, vx, v, opened, os, total, max); } } if (ns0.size() > 0 && ns1.size() == 0) { @@ -180,7 +179,8 @@ void flow(valve_m vs[2], std::map<valve_mm, int> visited, std::map<valve*, int> vx[0].m -= n.m; vx[0].v = n.v; - flow(vx, visited, opened, os, total, max); + auto v = visited; + flow(m - 1, vx, v, opened, os, total, max); } } if (ns0.size() > 0 && ns1.size() > 0) { @@ -194,7 +194,8 @@ void flow(valve_m vs[2], std::map<valve_mm, int> visited, std::map<valve*, int> vx[0].v = n0.v; vx[1].m -= n1.m; vx[1].v = n1.v; - flow(vx, visited, opened, os, total, max); + auto v = visited; + flow(m - 1, vx, v, opened, os, total, max); } } } @@ -249,7 +250,7 @@ std::pair<int, int> day16(line_view file) { {get("AA"), 26}, }; std::map<valve_mm, int> visited; - flow(vs, visited, opened, 0, 0, &m2); + flow(26, vs, visited, opened, 0, 0, &m2); printf("%d %d\n", m1, m2); return {m1, 0}; |