part two

diff --git a/09b.c b/09b.c
index a332dd4..3db03bf 100644 (file)
--- 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]);
 }