cleanup
[advent21.git] / 07b.c
diff --git a/07b.c b/07b.c
index 87ba2f0..2d361dd 100644 (file)
--- 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);
 }