From 90ea69871badd76ada4faffbe02fe1a615f025ee Mon Sep 17 00:00:00 2001
From: Mart Lubbers <mart@martlubbers.net>
Date: Wed, 15 Dec 2021 15:16:37 +0100
Subject: [PATCH] day 15 part two donE

---
 15b.c | 71 +++++++++++++++++++++--------------------------------------
 1 file changed, 25 insertions(+), 46 deletions(-)

diff --git a/15b.c b/15b.c
index 65d8081..26881a3 100644
--- a/15b.c
+++ b/15b.c
@@ -1,14 +1,13 @@
 #include <stdio.h>
-#include <stdbool.h>
-#include <stdlib.h>
 #include <limits.h>
-#include <string.h>
-#include <search.h>
+#include <uthash.h>
 
-#define min(a, b) ((a) < (b) ? (a) : (b))
-#define MFAC 1
+#define MFAC 5
 
 struct point { int x; int y; };
+#define pnt(px, py) ((struct point){.x=(px), .y=(py)})
+struct q { struct point key; UT_hash_handle hh; };
+int dist[100*MFAC][100*MFAC];
 
 int grid[100][100] = {0};
 int maxx = 0;
@@ -24,21 +23,11 @@ int get_grid(int x, int y)
 	return r;
 }
 
-int dist[100*MFAC][100*MFAC];
-
-int mindist(const void *l, const void *r)
-{
-	struct point lp = *(const struct point *)l;
-	struct point rp = *(const struct point *)r;
-	return dist[rp.y][rp.x]-dist[lp.y][lp.x];
-}
-
-struct point *is_in_q(struct point *q, size_t nq, int x, int y)
+int qcmp(const void *l, const void *r)
 {
-	for (size_t i = 0; i<nq; i++)
-		if (q[i].x == x && q[i].y == y)
-			return q+i;
-	return NULL;
+	const struct q *lp = (const struct q *)l;
+	const struct q *rp = (const struct q *)r;
+	return dist[lp->key.y][lp->key.x]-dist[rp->key.y][rp->key.x];
 }
 
 int main()
@@ -54,52 +43,42 @@ int main()
 		}
 	}
 
-	struct point q[100*MFAC*100*MFAC];
-	size_t qp = 0;
-	struct point prev[100*MFAC][100*MFAC];
+	struct q *q = NULL;
 
-//	grid[0][0] = 0;
 	for (int y = 0; y<maxy*MFAC; y++) {
 		for (int x = 0; x<maxx*MFAC; x++) {
 			dist[y][x] = INT_MAX;
-			prev[y][x] = (struct point){.x=-1, .y=-1};
-			q[qp++] = (struct point){.x=x, .y=y};
+			struct q *i = malloc(sizeof(struct q));
+			i->key = pnt(x, y);
+			HASH_ADD(hh, q, key, sizeof(struct point), i);
 		}
 	}
 	dist[0][0] = 0;
+	HASH_SRT(hh, q, qcmp);
 
-	while (qp > 0) {
-//		printf("size of q: %lu\n", qp);
-		qsort(q, qp, sizeof(struct point), mindist);
-		qp--;
-		struct point u = q[qp];
+	while (q != NULL) {
+		struct point u = q->key;
+		HASH_DELETE(hh, q, q);
 		for (int dy = -1; dy <= 1; dy++) {
 			for (int dx = -1; dx <= 1; dx++) {
 				//Skip diagonal neigbours
-				if (dx == dy)
+				if (abs(dx) == abs(dy))
 					continue;
 				//check if v is in Q
-				struct point *v = is_in_q(&q[0], qp, u.x+dx, u.y+dy);
+				struct q *v;
+				HASH_FIND(hh, q, &pnt(u.x+dx, u.y+dy), sizeof(struct point), v);
 				if (v == NULL)
 					continue;
 				//Update dist if necessary
-				int alt = dist[u.y][u.x] + get_grid(v->x, v->y);
-				if (alt < dist[v->y][v->x]) {
-					dist[v->y][v->x] = alt;
-					prev[v->y][v->x] = u;
+				int alt = dist[u.y][u.x] + get_grid(v->key.x, v->key.y);
+				if (alt < dist[v->key.y][v->key.x]) {
+					dist[v->key.y][v->key.x] = alt;
+					HASH_DELETE(hh, q, v);
+					HASH_ADD_INORDER(hh, q, key, sizeof(struct point), v, qcmp);
 				}
 			}
 		}
 	}
 
-	printf("path: ");
-	struct point u = {.y=maxy*MFAC-1, .x=maxx*MFAC-1};
-	do {
-		u = prev[u.y][u.x];
-		printf("%d,%d ", u.x, u.y);
-	} while (u.x!= 0 && u.y != 0);
-
-	printf("\n");
-
 	printf("%d\n", dist[maxy*MFAC-1][maxx*MFAC-1]);
 }
-- 
2.20.1