cleanup

[advent21.git] / 07a.c

diff --git a/07a.c b/07a.c
index 8e3d256..92730a2 100644 (file)
--- a/07a.c
+++ b/07a.c
@@ -3,6 +3,14 @@
 #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++)
+               dist += abs(crabs[i]-pos);
+       return dist;
+}
+
 int main()
 {
        char *buf = NULL;
@@ -24,13 +32,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++)
-                       dist += abs(crabs[j]-i);
-               if (dist < mindist)
-                       mindist = dist;
+       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;
+               }
        }
-       printf("%d\n", mindist);
+       printf("%d\n", middledist);
 }