2021 day9 part2

7 files changed, 64 insertions, 12 deletions

diff --git a/src/2021/day9/aoc.cpp b/src/2021/day9/aoc.cpp
index d8f6735..d4297ac 100644
--- a/src/2021/day9/aoc.cpp
+++ b/src/2021/day9/aoc.cpp
@@ -1,7 +1,7 @@
 #include "aoc.h"
 
 namespace aoc2021 {
-
+int heightmap::areas[grid * grid] = {0};
 std::pair<int, int> day9(line_view file) {
   heightmap hm;
   int r{0};
@@ -11,7 +11,7 @@ std::pair<int, int> day9(line_view file) {
     return true;
   });
 
-  return {hm.risks(), 0};
+  return {hm.risks(), hm.top3()};
 }
 
 }
diff --git a/src/2021/day9/aoc.h b/src/2021/day9/aoc.h
index 5e079fe..fef2af4 100644
--- a/src/2021/day9/aoc.h
+++ b/src/2021/day9/aoc.h
@@ -1,40 +1,72 @@
 #pragma once
 #include "common.h"
+#include <algorithm>
 
 namespace aoc2021 {
 
 struct heightmap {
   // 0 .. 99
-  char hs[100 * 100] = {0};
+  static const int grid = 100;
+  static int areas[grid * grid];
+  struct hchar {
+    char value = 0;
+    char checked = 0;
+  };
+
+  hchar hs[grid * grid];
 
   void load(int r, line_view lv) {
     const char* p = lv.line;
-    for(int i = 0; i < 100; i++) {
-      hs[100 * r + i] = *(p + i) - '0';
+    for(int i = 0; i < grid; i++) {
+      hs[grid * r + i].value = *(p + i) - '0';
     }
   }
 
   void low_point(int x, int y, int* d) const noexcept {
-    char l = x == 0 ? 10 : hs[100 * y + x - 1];
-    char r = x == 99 ? 10 : hs[100 * y + x + 1];
-    char t = y == 0 ? 10 : hs[100 * (y - 1) + x];
-    char b = y == 99 ? 10 : hs[100 * (y + 1) + x];
+    char l = x == 0 ? 10 : hs[grid * y + x - 1].value;
+    char r = x == grid - 1 ? 10 : hs[grid * y + x + 1].value;
+    char t = y == 0 ? 10 : hs[grid * (y - 1) + x].value;
+    char b = y == grid - 1 ? 10 : hs[grid * (y + 1) + x].value;
 
-    char n = hs[100 * y + x];
+    char n = hs[grid * y + x].value;
     if (n < l && n < r && n < t && n < b) {
       *d += n + 1;
     }
   }
+
+  void basin(int x, int y, int* area) {
+    if (hs[grid * y + x].value < 9 && hs[grid * y + x].checked == 0) {
+      *area += 1;
+      hs[grid * y + x].checked = 1;
+      std::pair<char, char> ps[4] = {{x-1, y}, {x+1, y}, {x, y-1}, {x, y+1}};
+      for (auto& p : ps) {
+        if (p.first >= 0 && p.first < grid && p.second >= 0 && p.second < grid) {
+          basin(p.first, p.second, area);
+        }
+      }
+    }
+  }
   
   int risks() const noexcept {
     int r{0};
-    for (int y = 0; y < 100; y++) {
-      for (int x = 0; x < 100; x++) {
+    for (int y = 0; y < grid; y++) {
+      for (int x = 0; x < grid; x++) {
         low_point(x, y, &r);
       }
     }
     return r;
   }
+
+  int top3() {
+    for (int y = 0; y < grid; y++) {
+      for (int x = 0; x < grid; x++) {
+        areas[y * grid + x] = 0;
+        basin(x, y, &areas[y * grid + x]);
+      }
+    }
+    std::sort(areas, areas + grid * grid, [](int x, int y){ return x > y;});
+    return areas[0] * areas[1] * areas[2];
+  }
 };
 
 std::pair<int, int> day9(line_view file);
diff --git a/src/2022/day5/README.md b/src/2022/day5/README.md
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/2022/day5/README.md
diff --git a/src/2022/day5/aoc.cpp b/src/2022/day5/aoc.cpp
new file mode 100644
index 0000000..bfaaaf4
--- /dev/null
+++ b/src/2022/day5/aoc.cpp
@@ -0,0 +1,11 @@
+#include "aoc.h"
+#include <algorithm>
+#include <vector>
+
+namespace aoc2022 {
+std::pair<int, int> day5(line_view file) {
+  return {0,0};
+}
+
+
+} // namespace aoc2022
diff --git a/src/2022/day5/aoc.h b/src/2022/day5/aoc.h
new file mode 100644
index 0000000..4b0d9d1
--- /dev/null
+++ b/src/2022/day5/aoc.h
@@ -0,0 +1,8 @@
+#include "common.h"
+
+
+namespace aoc2022 {
+
+std::pair<int, int> day5(line_view file);
+
+}
diff --git a/src/2022/day5/input b/src/2022/day5/input
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/src/2022/day5/input
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index d2963e7..72030bf 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -86,6 +86,7 @@ set(SOLUTION_FILES
   "2022/day2/aoc.cpp"
   "2022/day3/aoc.cpp"
   "2022/day4/aoc.cpp"
+  "2022/day5/aoc.cpp"
 )
 
 add_library(solution SHARED ${SOLUTION_FILES})