From 464433396dbb86c54b50aefa08b4ec188d82c609 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Sun, 5 Dec 2021 14:00:30 +0100 Subject: [PATCH] implement day 5 with hashmaps to gain a 20x speed increase --- 05a.c | 92 ++++++++++++++++++++++---------------------------- 05b.c | 106 ++++++++++++++++++++++++++-------------------------------- 2 files changed, 88 insertions(+), 110 deletions(-) diff --git a/05a.c b/05a.c index 3e5b008..cdebe38 100644 --- a/05a.c +++ b/05a.c @@ -1,66 +1,54 @@ #include -#include -#include +#include -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= 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 --- a/05b.c +++ b/05b.c @@ -1,72 +1,62 @@ #include -#include -#include +#include -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= 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); -- 2.20.1