X-Git-Url: https://git.martlubbers.net/?a=blobdiff_plain;f=07b.c;h=2d361dd6da87321fee409058921cf45583accc91;hb=967152a3319e0207e16901ecc0344edaf8c8193e;hp=a71157891b437b1532395ef527a6d93dd691ae79;hpb=4f89ccfe471a725a5d081038c93841b4b3bd36d8;p=advent21.git

diff --git a/07b.c b/07b.c
index a711578..2d361dd 100644
--- a/07b.c
+++ b/07b.c
@@ -3,6 +3,16 @@
 #include <string.h>
 #include <limits.h>
 
+static inline int distance(int crabs[], int ncrabs, int pos)
+{
+	int dist = 0;
+	for (int i = 0; i<ncrabs; i++) {
+		int d = abs(crabs[i]-pos);
+		dist += (d*d+d)/2;
+	}
+	return dist;
+}
+
 int main()
 {
 	char *buf = NULL;
@@ -24,18 +34,17 @@ int main()
 		ncrabs++;
 	}
 
-	int lastdist = INT_MAX;
-	int dist = INT_MAX;
-	int i = minp;
-	do {
-		lastdist = dist;
-		dist = 0;
-		for (int j = 0; j<ncrabs; j++) {
-			int d = abs(crabs[j]-i);
-			for (int k = 1; k<=d; k++)
-				dist += k;
+	int middledist = INT_MAX;
+	int middle = (maxp+minp)/2;
+	while (middle != maxp && middle != minp) {
+		middledist = distance(crabs, ncrabs, middle);
+		if (distance(crabs, ncrabs, middle+1) > middledist) {
+			maxp = middle;
+			middle = (middle+minp)/2;
+		} else {
+			minp = middle;
+			middle = (middle+maxp)/2;
 		}
-		i++;
-	} while (dist < lastdist);
-	printf("%d\n", lastdist);
+	}
+	printf("%d\n", middledist);
 }