From b66bca1e31050058cb9fd9124b635408b3453144 Mon Sep 17 00:00:00 2001
From: Mart Lubbers <mart@martlubbers.net>
Date: Thu, 9 Dec 2021 08:50:24 +0100
Subject: [PATCH] part two

---
 09b.c | 89 ++++++++++++++++++++++++++++++-----------------------------
 1 file changed, 46 insertions(+), 43 deletions(-)

diff --git a/09b.c b/09b.c
index a332dd4..3db03bf 100644
--- a/09b.c
+++ b/09b.c
@@ -2,69 +2,62 @@
 #include <stdlib.h>
 #include <string.h>
 #include <stdbool.h>
-#include <limits.h>
 #include <uthash.h>
 
 struct point { int x; int y; };
 struct entry { struct point key; UT_hash_handle hh; };
 
-#define push(x, y) {\
-	if ((x) >= 1 && (y) >= 1 && (x) <= maxx+1 && (y) <= maxy+1)\
-		stack[sp++] = (struct point){x, y};\
-	}
+bool havevisited(struct entry **visited, int x, int y)
+{
+	struct entry *e = NULL;
+	struct point p;
+	memset(&p, 0, sizeof(p));
+	p.x = x;
+	p.y = y;
+	HASH_FIND(hh, *visited, &p, sizeof(struct point), e);
+	return e;
+}
 
-int basin(int grid[102][102], int maxx, int maxy, int x, int y)
+void addvisited(struct entry **visited, struct point p)
+{
+	struct entry *e = calloc(1, sizeof(struct entry));
+	e->key = p;
+	HASH_ADD(hh, *visited, key, sizeof(struct point), e);
+}
+
+int basin(struct entry **visited, int grid[102][102], int x, int y)
 {
-	printf("calculate basin for: %d,%d -- ", x, y);
 	struct point stack[1000];
 	memset(stack, 0, sizeof stack);
-	struct entry *visited = NULL;
 
 	int sp = 0;
 	int size = 0;
 	stack[sp++] = (struct point){.x=x, .y=y};
 
 	struct point p;
-	struct entry *e;
 	memset(&p, 0, sizeof p);
 	while(--sp >= 0) {
 		p = stack[sp];
-		HASH_FIND(hh, visited, &p, sizeof(struct point), e);
-		if (e)
+		if (havevisited(visited, p.x, p.y))
 			continue;
-
-		e = calloc(1, sizeof(struct entry));
-		e->key = p;
-		HASH_ADD(hh, visited, key, sizeof(struct point), e);
+		addvisited(visited, p);
 
 		if (grid[p.y][p.x] == 9)
 			continue;
 		size++;
 
-		push(p.x+1, p.y);
-		push(p.x-1, p.y);
-		push(p.x, p.y+1);
-		push(p.x, p.y-1);
+		if (!havevisited(visited, p.x+1, p.y))
+			stack[sp++] = (struct point){.x=p.x+1, .y=p.y};
+		if (!havevisited(visited, p.x-1, p.y))
+			stack[sp++] = (struct point){.x=p.x-1, .y=p.y};
+		if (!havevisited(visited, p.x, p.y+1))
+			stack[sp++] = (struct point){.x=p.x, .y=p.y+1};
+		if (!havevisited(visited, p.x, p.y-1))
+			stack[sp++] = (struct point){.x=p.x, .y=p.y-1};
 	}
-	printf(" %d\n", size);
 	return size;
 }
 
-void insert(int tl[3], int s)
-{
-	if (s > tl[0] && s <= tl[1])
-		tl[0] = s;
-	if (s > tl[1] && s <= tl[2]) {
-		tl[0] = tl[1];
-		tl[1] = s;
-	}
-	if (s > tl[2]) {
-		tl[0] = tl[1];
-		tl[1] = tl[2];
-		tl[2] = s;
-	}
-}
-
 int main()
 {
 	int grid[102][102];
@@ -85,13 +78,23 @@ int main()
 	}
 
 	int tl[3] = {0};
-	for (int cy = 1; cy<y; cy++)
-		for (int cx = 1; cx<maxx+1; cx++)
-			if (grid[cy][cx] < grid[cy+1][cx] &&
-					grid[cy][cx] < grid[cy-1][cx] &&
-					grid[cy][cx] < grid[cy][cx+1] &&
-					grid[cy][cx] < grid[cy][cx-1])
-				insert(tl, basin(grid, maxx, y, cx, cy));
-	printf("%d %d %d\n", tl[0], tl[1], tl[2]);
+	struct entry *visited = NULL;
+	for (int cy = 1; cy<y; cy++) {
+		for (int cx = 1; cx<maxx+1; cx++) {
+			if (!havevisited(&visited, cx, cy)) {
+				int s = basin(&visited, grid, cx, cy);
+				if (s >= tl[0]) {
+					tl[2] = tl[1];
+					tl[1] = tl[0];
+					tl[0] = s;
+				} else if (s >= tl[1]) {
+					tl[2] = tl[1];
+					tl[1] = s;
+				} else if (s > tl[2]) {
+					tl[2] = s;
+				}
+			}
+		}
+	}
 	printf("%d\n", tl[0]*tl[1]*tl[2]);
 }
-- 
2.20.1