2021 day9

4 files changed, 91 insertions, 0 deletions

diff --git a/src/2021/day9/README.md b/src/2021/day9/README.md
index 205cc78..ab98176 100644
--- a/src/2021/day9/README.md
+++ b/src/2021/day9/README.md
@@ -20,3 +20,41 @@ The risk level of a low point is 1 plus its height. In the above example, the ri
 
 Find all of the low points on your heightmap. What is the sum of the risk levels of all low points on your heightmap?
 
+--- Part Two ---
+Next, you need to find the largest basins so you know what areas are most important to avoid.
+
+A basin is all locations that eventually flow downward to a single low point. Therefore, every low point has a basin, although some basins are very small. Locations of height 9 do not count as being in any basin, and all other locations will always be part of exactly one basin.
+
+The size of a basin is the number of locations within the basin, including the low point. The example above has four basins.
+
+The top-left basin, size 3:
+
+2199943210
+3987894921
+9856789892
+8767896789
+9899965678
+The top-right basin, size 9:
+
+2199943210
+3987894921
+9856789892
+8767896789
+9899965678
+The middle basin, size 14:
+
+2199943210
+3987894921
+9856789892
+8767896789
+9899965678
+The bottom-right basin, size 9:
+
+2199943210
+3987894921
+9856789892
+8767896789
+9899965678
+Find the three largest basins and multiply their sizes together. In the above example, this is 9 * 14 * 9 = 1134.
+
+What do you get if you multiply together the sizes of the three largest basins?
diff --git a/src/2021/day9/aoc.cpp b/src/2021/day9/aoc.cpp
index 7a3c895..d8f6735 100644
--- a/src/2021/day9/aoc.cpp
+++ b/src/2021/day9/aoc.cpp
@@ -2,4 +2,16 @@
 
 namespace aoc2021 {
 
+std::pair<int, int> day9(line_view file) {
+  heightmap hm;
+  int r{0};
+  per_line(file, [&r, &hm](line_view lv){
+    hm.load(r, lv);
+    r++;
+    return true;
+  });
+
+  return {hm.risks(), 0};
+}
+
 }
diff --git a/src/2021/day9/aoc.h b/src/2021/day9/aoc.h
index cd205cd..5e079fe 100644
--- a/src/2021/day9/aoc.h
+++ b/src/2021/day9/aoc.h
@@ -3,4 +3,40 @@
 
 namespace aoc2021 {
 
+struct heightmap {
+  // 0 .. 99
+  char hs[100 * 100] = {0};
+
+  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';
+    }
+  }
+
+  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 n = hs[100 * y + x];
+    if (n < l && n < r && n < t && n < b) {
+      *d += n + 1;
+    }
+  }
+  
+  int risks() const noexcept {
+    int r{0};
+    for (int y = 0; y < 100; y++) {
+      for (int x = 0; x < 100; x++) {
+        low_point(x, y, &r);
+      }
+    }
+    return r;
+  }
+};
+
+std::pair<int, int> day9(line_view file);
+
 }
diff --git a/src/2021/day9/input0 b/src/2021/day9/input0
new file mode 100644
index 0000000..6dee4a4
--- /dev/null
+++ b/src/2021/day9/input0
@@ -0,0 +1,5 @@
+2199943210
+3987894921
+9856789892
+8767896789
+9899965678