diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/2022/day23/README.md | 18 | ||||
| -rw-r--r-- | src/2022/day23/aoc.cpp | 57 |
2 files changed, 70 insertions, 5 deletions
diff --git a/src/2022/day23/README.md b/src/2022/day23/README.md index 078d6cf..ea32e83 100644 --- a/src/2022/day23/README.md +++ b/src/2022/day23/README.md @@ -193,3 +193,21 @@ In this region, the number of empty ground tiles is 110. Simulate the Elves' process and find the smallest rectangle that contains the Elves after 10 rounds. How many empty ground tiles does that rectangle contain? +--- Part Two --- +It seems you're on the right track. Finish simulating the process and figure out where the Elves need to go. How many rounds did you save them? + +In the example above, the first round where no Elf moved was round 20: + +.......#...... +....#......#.. +..#.....#..... +......#....... +...#....#.#..# +#............. +....#.....#... +..#.....#..... +....#.#....#.. +.........#.... +....#......#.. +.......#...... +Figure out where the Elves need to go. What is the number of the first round where no Elf moves? diff --git a/src/2022/day23/aoc.cpp b/src/2022/day23/aoc.cpp index 1d60f78..1b09a2b 100644 --- a/src/2022/day23/aoc.cpp +++ b/src/2022/day23/aoc.cpp @@ -86,35 +86,72 @@ static struct elf_test { elf_move m; } moves[5] = {{eight, nomove}, {north_three, north}, {south_three, south}, {west_three, west}, {east_three, east}}; -bool duplicate(elf e, const std::vector<elf>& elfs) { - return false; +bool duplicate(elf e, const std::map<elf, int>& dups) { + auto it = dups.find(e); + return it != dups.end() && it->second > 1; } -std::vector<elf> round(int i, const std::vector<elf>& elfs, const std::set<elf>& elves) { +std::vector<elf> round(int i, const std::vector<elf>& elfs, const std::set<elf>& elves, size_t* n) { std::vector<elf> next; + *n = 0; + for (auto& e : elfs) { if (moves[0].p(e, elves)) { next.emplace_back(moves[0].m(e)); + *n += 1; } else { + bool can_move{false}; for (int x = 0; x < 4; x++) { int index = (i + x) % 4 + 1; if (moves[index].p(e, elves)) { next.emplace_back(moves[index].m(e)); + can_move = true; break; } } + if (!can_move) { + next.emplace_back(e); + } + } + } + + std::map<elf, int> dups; + for (auto& e : next) { + auto kv = dups.insert({e, 1}); + if (!kv.second) { + kv.first->second += 1; } } // check duplicate of next for(size_t i = 0; i < next.size(); i++) { - if (duplicate(next[i], next)) { + if (duplicate(next[i], dups)) { next[i] = elfs[i]; // stay put } } return next; } +int count(const std::vector<elf>& elfs, const std::set<elf>& elvs) { + int minx{INT32_MAX}, miny{INT32_MAX}; + int maxx{INT32_MIN}, maxy{INT32_MIN}; + + for (auto& e: elfs) { + minx = std::min(e.x, minx); + miny = std::min(e.y, miny); + maxx = std::max(e.x, maxx); + maxy = std::max(e.y, maxy); + } + + int n{0}; + for (int y = miny; y <= maxy; y++) { + for (int x = minx; x <= maxx; x++) { + if (elvs.find(elf{x, y}) == elvs.end()) n++; + } + } + return n; +} + std::pair<int, int> day23(line_view file) { int height{0}; std::vector<elf> elfs; @@ -131,6 +168,16 @@ std::pair<int, int> day23(line_view file) { std::set<elf> elves{elfs.begin(), elfs.end()}; - return {0, 0}; + size_t n{0}; + int r{0}; + while (r < 10 /*true*/) { + elfs = round(r++, elfs, elves, &n); + if (n == elfs.size()) break; + elves.clear(); + elves = std::set<elf>{elfs.begin(), elfs.end()}; + } + + int n1 = count(elfs, elves); + return {n1, r}; } } // namespace aoc2022 |