day 18 part 2

1 files changed, 54 insertions, 0 deletions

diff --git a/22.18/main.cpp b/22.18/main.cpp
index f4fbcea..eaf7bab 100644
--- a/22.18/main.cpp
+++ b/22.18/main.cpp
@@ -1,4 +1,6 @@
+#include <algorithm>
 #include <cstdio>
+#include <deque>
 #include <string>
 #include <unordered_set>
 using namespace std;
@@ -28,6 +30,10 @@ struct Vec3
 			z + o.z,
 		};
 	}
+
+	bool operator<(const Vec3& o) const {
+		return x < o.x || y < o.y || z < o.z;
+	}
 };
 
 /* from nullprogram */
@@ -71,6 +77,53 @@ partOne(unordered_set<Vec3> const& map)
 }
 
 int
+partTwo(unordered_set<Vec3> const& map)
+{
+	Vec3 low = *map.begin();
+	Vec3 high = *map.begin();
+	for (auto &v : map) {
+		low = {
+			min(low.x, v.x),
+			min(low.y, v.y),
+			min(low.z, v.z),
+		};
+		high = {
+			max(high.x, v.x),
+			max(high.y, v.y),
+			max(high.z, v.z),
+		};
+	}
+	low = low + Vec3{-1, -1, -1};
+	high = high + Vec3{1, 1, 1};
+
+	int total = 0;
+	unordered_set<Vec3> visited;
+	deque<Vec3> frontier;
+	visited.insert(low);
+	frontier.push_back(low);
+	while (!frontier.empty()) {
+		Vec3 v = frontier.front();
+		frontier.pop_front();
+
+		for (int axis = 0; axis < 3; axis++) {
+			for (auto ad : {-1, 1}) {
+				Vec3 vd = v;
+				vd[axis] += ad;
+				if (vd < low || high < vd) continue;
+				if (visited.count(vd) == 1) continue;
+				if (map.count(vd) == 1) {
+					total += 1;
+				} else {
+					visited.insert(vd);
+					frontier.push_back(vd);
+				}
+			}
+		}
+	}
+	return total;
+}
+
+int
 main()
 {
 	int x, y, z;
@@ -80,4 +133,5 @@ main()
 		map.insert(v);
 	}
 	printf("%d\n", partOne(map));
+	printf("%d\n", partTwo(map));
 }