advent_of_code_2021

day07_part1.py (2161B)

---

 #!/usr/bin/env python
 """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, the subs with positions less than or equal to x_m would each
 # spend the same amount of additional fuel to reach x_o, while the subs with
 # positions greater than x_o would each save that same amount of fuel (no need
 # to worry about any 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 (i.e., there are
 # more subs spending extra fuel than there are saving fuel). Since the same
 # logic applies to an x_o less than x_m, we have shown 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):
     """Given the positions of the 'crab submarines', find the minimum fuel use
     to line them up"""
     return float(calculate_fuel_use_to(positions, positions.median()))
 
 def calculate_fuel_use_to(start_positions, end_position):
     """Given a series that represents the (1-D) positions of a collection of 'crab
     submarines', find the fuel used to move to the given end position"""
     return start_positions.sub(end_position).abs().sum()
 
 def solve_puzzle(input_string):
     """Return the numeric solution to the puzzle"""
     return find_minimum_fuel_use(convert_int_line_to_series(input_string))
 
 def main():
     """Run when the file is called as a script"""
     assert solve_puzzle("16,1,2,0,4,2,7,1,2,14\n") == 37
     print("Fuel spent to align crabs:",
           f"{solve_puzzle(get_puzzle_input(7)):.0f}")
 
 if __name__ == "__main__":
     main()