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

diff --git a/07b.c b/07b.c
index 87ba2f0..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,17 +34,17 @@ int main()
 		ncrabs++;
 	}
 
-	int mindist = INT_MAX;
-	for (int i = minp; i<=maxp; i++) {
-		int 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;
 		}
-		if (dist < mindist)
-			mindist = dist;
 	}
-	printf("%d\n", mindist);
+	printf("%d\n", middledist);
 }