diff options
| -rw-r--r-- | src/2017/day22/README.md | 84 | ||||
| -rw-r--r-- | src/2017/day22/aoc.cpp | 90 | ||||
| -rw-r--r-- | src/2017/day22/aoc.h | 11 | ||||
| -rw-r--r-- | test/test_2017.cpp | 2 |
4 files changed, 184 insertions, 3 deletions
diff --git a/src/2017/day22/README.md b/src/2017/day22/README.md index 56b870e..ae4f649 100644 --- a/src/2017/day22/README.md +++ b/src/2017/day22/README.md @@ -84,4 +84,88 @@ By this time, 41 bursts of activity caused an infection (though most of those no After a total of 10000 bursts of activity, 5587 bursts will have caused an infection. Given your actual map, after 10000 bursts of activity, how many bursts cause a node to become infected? (Do not count nodes that begin infected.) +--- Part Two --- +As you go to remove the virus from the infected nodes, it evolves to resist your attempt. +Now, before it infects a clean node, it will weaken it to disable your defenses. If it encounters an infected node, it will instead flag the node to be cleaned in the future. So: + +Clean nodes become weakened. +Weakened nodes become infected. +Infected nodes become flagged. +Flagged nodes become clean. +Every node is always in exactly one of the above states. + +The virus carrier still functions in a similar way, but now uses the following logic during its bursts of action: + +Decide which way to turn based on the current node: +If it is clean, it turns left. +If it is weakened, it does not turn, and will continue moving in the same direction. +If it is infected, it turns right. +If it is flagged, it reverses direction, and will go back the way it came. +Modify the state of the current node, as described above. +The virus carrier moves forward one node in the direction it is facing. +Start with the same map (still using . for clean and # for infected) and still with the virus carrier starting in the middle and facing up. + +Using the same initial state as the previous example, and drawing weakened as W and flagged as F, the middle of the infinite grid looks like this, with the virus carrier's position again marked with [ ]: + +. . . . . . . . . +. . . . . . . . . +. . . . . . . . . +. . . . . # . . . +. . . #[.]. . . . +. . . . . . . . . +. . . . . . . . . +. . . . . . . . . +This is the same as before, since no initial nodes are weakened or flagged. The virus carrier is on a clean node, so it still turns left, instead weakens the node, and moves left: + +. . . . . . . . . +. . . . . . . . . +. . . . . . . . . +. . . . . # . . . +. . .[#]W . . . . +. . . . . . . . . +. . . . . . . . . +. . . . . . . . . +The virus carrier is on an infected node, so it still turns right, instead flags the node, and moves up: + +. . . . . . . . . +. . . . . . . . . +. . . . . . . . . +. . .[.]. # . . . +. . . F W . . . . +. . . . . . . . . +. . . . . . . . . +. . . . . . . . . +This process repeats three more times, ending on the previously-flagged node and facing right: + +. . . . . . . . . +. . . . . . . . . +. . . . . . . . . +. . W W . # . . . +. . W[F]W . . . . +. . . . . . . . . +. . . . . . . . . +. . . . . . . . . +Finding a flagged node, it reverses direction and cleans the node: + +. . . . . . . . . +. . . . . . . . . +. . . . . . . . . +. . W W . # . . . +. .[W]. W . . . . +. . . . . . . . . +. . . . . . . . . +. . . . . . . . . +The weakened node becomes infected, and it continues in the same direction: + +. . . . . . . . . +. . . . . . . . . +. . . . . . . . . +. . W W . # . . . +.[.]# . W . . . . +. . . . . . . . . +. . . . . . . . . +. . . . . . . . . +Of the first 100 bursts, 26 will result in infection. Unfortunately, another feature of this evolved virus is speed; of the first 10000000 bursts, 2511944 will result in infection. + +Given your actual map, after 10000000 bursts of activity, how many bursts cause a node to become infected? (Do not count nodes that begin infected.) diff --git a/src/2017/day22/aoc.cpp b/src/2017/day22/aoc.cpp index b2e2dfb..3e9a907 100644 --- a/src/2017/day22/aoc.cpp +++ b/src/2017/day22/aoc.cpp @@ -1,6 +1,94 @@ #include "aoc.h" +#include <set> namespace aoc2017 { -std::pair<int64_t, int64_t> day22(line_view) { return {0, 0}; } +static int radias = 12; // demo 25/2 = 12 input +enum facing { + f_up, + f_down, + f_right, + f_left, +}; + +struct vpos { + int x; + int y; + facing f; +}; + +static vpos turn_right(vpos p) { + facing fs[4] = {f_right, f_left, f_down, f_up}; + return {p.x, p.y, fs[(int)p.f]}; +} + +static vpos turn_left(vpos p) { + facing fs[4] = {f_left, f_right, f_up, f_down}; + return {p.x, p.y, fs[(int)p.f]}; +} + +static vpos move(vpos p) { + vpos vs[4] = { + {p.x, p.y - 1, p.f}, + {p.x, p.y + 1, p.f}, + {p.x + 1, p.y, p.f}, + {p.x - 1, p.y, p.f}, + }; + return vs[(int)p.f]; +} + +vpos burst(std::set<node22>& infected, vpos p, int* c) { + auto it = infected.find({p.x, p.y}); + bool is_infected = it != infected.end(); + // If the current node is infected, it turns to its right. Otherwise, it turns to its left. (Turning is done in-place; + // the current node does not change.) + vpos px = is_infected ? turn_right(p) : turn_left(p); + + // If the current node is clean, it becomes infected. Otherwise, it becomes + // cleaned. (This is done after the node is considered for the purposes of changing direction.) The virus carrier + if (!is_infected) { + infected.insert({p.x, p.y}); + *c += 1; + } else { + infected.erase(it); + } + + // moves forward one node in the direction it is facing. + px = move(px); + return px; +} + +static void load(std::set<node22>& is, int r, line_view lv) { + const char* p = lv.line; + int x = 0; + while (*(p + x) != '\n') { + if (*(p + x) == '#') { + node22 n{x - radias, r - radias}; + is.insert(n); + } + x++; + } +} + +std::pair<int64_t, int64_t> day22(line_view file) { + std::set<node22> infected; + + int r{0}; + per_line(file, [&r, &infected](line_view lv) { + load(infected, r++, lv); + return true; + }); + + vpos p{0, 0, f_up}; + int t0{0}; + for (int i = 0; i < 10000; i++) { + p = burst(infected, p, &t0); + } + + // for (auto& n : infected) { + // printf("%d,%d\n", n.x, n.y); + // } + return {t0, 0}; +} + } // namespace aoc2017 diff --git a/src/2017/day22/aoc.h b/src/2017/day22/aoc.h index 6c9c549..2011f47 100644 --- a/src/2017/day22/aoc.h +++ b/src/2017/day22/aoc.h @@ -3,5 +3,14 @@ #include <vector> namespace aoc2017 { + +struct node22 { + int x; + int y; + + node22(int x0, int y0): x(x0), y(y0) {} + bool operator<(const node22& n) const noexcept { return x < n.x ? true : x > n.x ? false : y < n.y; } +}; + std::pair<int64_t, int64_t> day22(line_view); -} +} // namespace aoc2017 diff --git a/test/test_2017.cpp b/test/test_2017.cpp index 39af2d4..26d6a9b 100644 --- a/test/test_2017.cpp +++ b/test/test_2017.cpp @@ -213,7 +213,7 @@ TEST_CASE("Fractal Art", "[2017]") { TEST_CASE("Sporifica Virus", "[2017]") { line_view lv = load_file("../src/2017/day22/input"); auto p = aoc2017::day22(lv); - REQUIRE(0 == p.first); + REQUIRE(5246 == p.first); REQUIRE(0 == p.second); } |