commit e13970376c770cdd6c5fe6a2a50f3a99a4e01387
parent 726e9f7efd14ce878e96b649fe4ffc41fa8cb4d4
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Tue, 7 Dec 2021 13:25:09 -0500
I feel like I owe folks an explanation of why this solution is correct
Diffstat:
1 file changed, 16 insertions(+), 1 deletion(-)
diff --git a/day07_part1.py b/day07_part1.py
@@ -1,7 +1,22 @@
#!/usr/bin/env python
-"""Advent of Code 2021, day 7 (part 2): optimize 'crab submarine' alignment to
+"""Advent of Code 2021, day 7 (part 1): optimize 'crab submarine' alignment to
minimize fuel"""
+# How do we know that the median minimizes sum(abs(start_positions -
+# end_position))? Let's do a quick and dirty proof in the Advent of Code
+# universe.
+# Suppose that we've already moved all the crab submarines to the median
+# position, x_m, but there's actually a better position that's greater than
+# x_m, which we'll call x_o. If we had moved the submarines to position x_o
+# instead of x_m, all of the subs with positions less than or equal to x_m
+# would spend the same amount of additional fuel, and all of the subs with
+# positions greater than or equal to x_o would save that same amount of fuel
+# (we can forget about the subs between x_m and x_o for now). However, by the
+# definition of the median, the majority of subs have positions less than or
+# equal to x_m, which means moving to x_o will necessarily cost the crab sub
+# fleet more fuel than it saves. The same logic applies to an x_o less than
+# x_m, so we have proven by contradition that x_m must be the best position.
+
from utils import get_puzzle_input, convert_int_line_to_series
def find_minimum_fuel_use(positions):
