2022 day23

1 files changed, 52 insertions, 5 deletions

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