commit 94d6acb1df097d280e1405d008bc70da9156f374 (patch)
parent 9c87944e409e9e96ea2ad8a4b8c7ba581c97efa3
Author: Alex Karle <alex@alexkarle.com>
Date: Tue, 7 Dec 2021 00:30:16 -0500
day7: Add comments with rough proof of correctness
Diffstat:
2 files changed, 24 insertions(+), 3 deletions(-)
diff --git a/7/a.py b/7/a.py
@@ -1,8 +1,18 @@
#!/usr/bin/env python3
+# In a "all fuel is equal" situation, the optimal solution will
+# be the median, since it's effectively the closest to the "middle"
+# one can get. I forget the proof, but it works. Something like
+#
+# T = |x1 - m| + ... + |xi - m|
+#
+# If m is the median, there are i/2 points on each side. If m
+# was NOT the median, it might get "closer" to a subset of points
+# but the "larger" split will be >i/2 points, and it is getting
+# "farther" from those points. The # of points farther > # closer,
+# so it's a less optimal positioning.
import sys
crabs = []
-
for l in sys.stdin:
crabs = [int(x) for x in l.split(",")]
diff --git a/7/b.py b/7/b.py
@@ -1,11 +1,22 @@
#!/usr/bin/env python3
+# In the "non-linear fuel cost" situation, we suddenly know
+# the median is definitely not optimal. Consider 1,2,100. A
+# median of 2 means you'd incur a huge penalty (100 + 99..)
+# for the 100 term, 4851 to be exact (plus 1 more for the 1)
+#
+# A better solution is to optimize for the least number of
+# far-out points by using the average. We see 34 is would
+# give us 3300 instead, which is significantly better.
import sys
-crabs = []
+def cost(a, b):
+ # Distance 3 = 1 + 2 + 3 = sum(range(abs)))
+ return sum(range(abs(a - b) + 1))
+crabs = []
for l in sys.stdin:
crabs = [int(x) for x in l.split(",")]
avg = int(sum(crabs) / len(crabs))
-print(sum([sum(range(abs(x - avg) + 1)) for x in crabs]))
+print(sum([cost(x, avg) for x in crabs]))
