implement day 5 with hashmaps to gain a 20x speed increase

diff --git a/05a.c b/05a.c
index 3e5b008..cdebe38 100644 (file)
--- a/05a.c
+++ b/05a.c
@@ -1,66 +1,54 @@
 #include <stdio.h>
-#include <stdlib.h>
-#include <stdbool.h>
+#include <uthash.h>
 
-struct line { enum {horz, vert} d; int x1; int y1; int x2; int y2; };
+#define SWAP(x, y) { x ^= y; y ^= x; x ^= y; }
 
-#define max(x, y) ((x)>(y) ? (x) : (y))
-#define min(x, y) ((x)<(y) ? (x) : (y))
-#define between(a, a1, a2) ((a) >= min(a1, a2) && (a) <= max(a1, a2))
+struct point { int x; int y; };
+struct entry { struct point key; int i; UT_hash_handle hh; };
 
-int parse_lines(struct line lines[], int *maxx, int *maxy)
+void mark_point(int x, int y, struct entry **entries, int *r)
 {
-       int i = 0;
-       char buf[1000];
-       while (fgets(buf, 1000, stdin) != NULL) {
-               char *p = &buf[0];
-               lines[i].x1 = strtol(p, &p, 10);
-               p++;
-               lines[i].y1 = strtol(p, &p, 10);
-               p+=4;
-               lines[i].x2 = strtol(p, &p, 10);
-               p++;
-               lines[i].y2 = strtol(p, &p, 10);
-               if (lines[i].x1 == lines[i].x2)
-                       lines[i].d = vert;
-               else if (lines[i].y1 == lines[i].y2)
-                       lines[i].d = horz;
-               else
-                       continue;
-               *maxx = max(*maxx, lines[i].x1);
-               *maxx = max(*maxx, lines[i].x2);
-               *maxy = max(*maxy, lines[i].y1);
-               *maxy = max(*maxy, lines[i].y2);
-               i++;
+       struct entry *p;
+       struct point s = { .x=x, .y=y };
+       HASH_FIND(hh, *entries, &s, sizeof(struct point), p);
+       if (p) {
+               if (p->i++ == 1)
+                       *r = *r+1;
+       } else {
+               p = malloc(sizeof(struct entry));
+               p->key = s;
+               p->i = 1;
+               HASH_ADD(hh, *entries, key, sizeof(struct point), p);
        }
-       return i;
-}
-
-bool online(int x, int y, struct line line)
-{
-       switch (line.d) {
-       case vert:
-               return x == line.x1 && between(y, line.y1, line.y2);
-       case horz:
-               return y == line.y1 && between(x, line.x1, line.x2);
-       }
-       return false;
 }
 
 int main()
 {
-       struct line lines[1000];
-       int maxx = 0, maxy = 0;
-       int nlines = parse_lines(lines, &maxx, &maxy);
+       char buf[1000];
+       struct entry *entries = NULL;
        int r = 0;
-       for (int x = 0; x<=maxx; x++) {
-               for (int y = 0; y<=maxy; y++) {
-                       int matches = 0;
-                       for (int line = 0; line<nlines && matches < 2; line++)
-                               if (online(x, y, lines[line]))
-                                       matches++;
-                       r = matches >= 2 ? r+1 : r;
-               }
+       while (fgets(buf, 1000, stdin) != NULL) {
+               char *ptr = &buf[0];
+               int x1 = strtol(ptr, &ptr, 10);
+               ptr++;
+               int y1 = strtol(ptr, &ptr, 10);
+               ptr+=4;
+               int x2 = strtol(ptr, &ptr, 10);
+               ptr++;
+               int y2 = strtol(ptr, &ptr, 10);
+               if (x1 > x2)
+                       SWAP(x1, x2);
+               if (y1 > y2)
+                       SWAP(y1, y2);
+
+               //Vertical
+               if (x1 == x2)
+                       for (int y = y1; y<=y2; y++)
+                               mark_point(x1, y, &entries, &r);
+               //Horizontal
+               else if (y1 == y2)
+                       for (int x = x1; x<=x2; x++)
+                               mark_point(x, y1, &entries, &r);
        }
        printf("%d\n", r);
 }

diff --git a/05b.c b/05b.c
index 208f870..f8dd141 100644 (file)
--- a/05b.c
+++ b/05b.c
@@ -1,72 +1,62 @@
 #include <stdio.h>
-#include <stdlib.h>
-#include <stdbool.h>
+#include <uthash.h>
 
-struct line { enum {horz, vert, diag} d; int x1; int y1; int x2; int y2; };
+#define SWAP(x, y) { x ^= y; y ^= x; x ^= y; }
 
-#define max(x, y) ((x)>(y) ? (x) : (y))
-#define min(x, y) ((x)<(y) ? (x) : (y))
-#define between(a, a1, a2) ((a) >= min(a1, a2) && (a) <= max(a1, a2))
+struct point { int x; int y; };
+struct entry { struct point key; int i; UT_hash_handle hh; };
 
-int parse_lines(struct line lines[], int *maxx, int *maxy)
+void mark_point(int x, int y, struct entry **entries, int *r)
 {
-       int i = 0;
-       char buf[1000];
-       while (fgets(buf, 1000, stdin) != NULL) {
-               char *p = &buf[0];
-               lines[i].x1 = strtol(p, &p, 10);
-               p++;
-               lines[i].y1 = strtol(p, &p, 10);
-               p+=4;
-               lines[i].x2 = strtol(p, &p, 10);
-               p++;
-               lines[i].y2 = strtol(p, &p, 10);
-               if (lines[i].x1 == lines[i].x2)
-                       lines[i].d = vert;
-               else if (lines[i].y1 == lines[i].y2)
-                       lines[i].d = horz;
-               else if (abs(lines[i].y2-lines[i].y1) == abs(lines[i].x2-lines[i].x1))
-                       lines[i].d = diag;
-               else
-                       continue;
-               *maxx = max(*maxx, lines[i].x1);
-               *maxx = max(*maxx, lines[i].x2);
-               *maxy = max(*maxy, lines[i].y1);
-               *maxy = max(*maxy, lines[i].y2);
-               i++;
+       struct entry *p;
+       struct point s = {.x=x, .y=y};
+       HASH_FIND(hh, *entries, &s, sizeof(struct point), p);
+       if (p) {
+               if (p->i++ == 1)
+                       *r = *r+1;
+       } else {
+               p = malloc(sizeof(struct entry));
+               p->key = s;
+               p->i = 1;
+               HASH_ADD(hh, *entries, key, sizeof(struct point), p);
        }
-       return i;
-}
-
-bool online(int x, int y, struct line line)
-{
-       int slope;
-       switch (line.d) {
-       case horz:
-               return y == line.y1 && between(x, line.x1, line.x2);
-       case vert:
-               return x == line.x1 && between(y, line.y1, line.y2);
-       case diag:
-               slope = (line.y2 - line.y1) / (line.x2 - line.x1);
-               return y-line.y1 == slope*(x-line.x1)
-                       && between(y, line.y1, line.y2) && between(x, line.x1, line.x2);
-       }
-       return false;
 }
 
 int main()
 {
-       struct line lines[1000];
-       int maxx = 0, maxy = 0;
-       int nlines = parse_lines(lines, &maxx, &maxy);
+       char buf[1000];
+       struct entry *entries = NULL;
        int r = 0;
-       for (int x = 0; x<=maxx; x++) {
-               for (int y = 0; y<=maxy; y++) {
-                       int matches = 0;
-                       for (int line = 0; line<nlines && matches < 2; line++)
-                               if (online(x, y, lines[line]))
-                                       matches++;
-                       r = matches >= 2 ? r+1 : r;
+       while (fgets(buf, 1000, stdin) != NULL) {
+               char *ptr = &buf[0];
+               int x1 = strtol(ptr, &ptr, 10);
+               ptr++;
+               int y1 = strtol(ptr, &ptr, 10);
+               ptr+=4;
+               int x2 = strtol(ptr, &ptr, 10);
+               ptr++;
+               int y2 = strtol(ptr, &ptr, 10);
+
+               //Diagonal
+               if (abs(y2-y1) == abs(x2-x1)) {
+                       int dx = x1 > x2 ? -1 : 1;
+                       int dy = y1 > y2 ? -1 : 1;
+                       for (; x1 != x2; x1 += dx, y1+= dy)
+                               mark_point(x1, y1, &entries, &r);
+                       mark_point(x1, y1, &entries, &r);
+               } else {
+                       if (x1 > x2)
+                               SWAP(x1, x2);
+                       if (y1 > y2)
+                               SWAP(y1, y2);
+                       //Vertical
+                       if (x1 == x2)
+                               for (int y = y1; y<=y2; y++)
+                                       mark_point(x1, y, &entries, &r);
+                       //Horizontal
+                       else if (y1 == y2)
+                               for (int x = x1; x<=x2; x++)
+                                       mark_point(x, y1, &entries, &r);
                }
        }
        printf("%d\n", r);