day07_part1.py (2161B)

1 #!/usr/bin/env python 2 """Advent of Code 2021, day 7 (part 1): optimize 'crab submarine' alignment to 3 minimize fuel""" 4 5 # How do we know that the median minimizes sum(abs(start_positions - 6 # end_position))? Let's do a quick and dirty proof in the Advent of Code 7 # universe. 8 # Suppose that we've already moved all the crab submarines to the median 9 # position, x_m, but there's actually a better position--that's greater than 10 # x_m--which we'll call x_o. If we had moved the submarines to position x_o 11 # instead of x_m, the subs with positions less than or equal to x_m would each 12 # spend the same amount of additional fuel to reach x_o, while the subs with 13 # positions greater than x_o would each save that same amount of fuel (no need 14 # to worry about any subs between x_m and x_o for now). 15 # However, by the definition of the median, the majority of subs have 16 # positions less than or equal to x_m, which means moving to x_o will 17 # necessarily cost the crab sub fleet more fuel than it saves (i.e., there are 18 # more subs spending extra fuel than there are saving fuel). Since the same 19 # logic applies to an x_o less than x_m, we have shown by contradition that x_m 20 # must be the best position. 21 22 from utils import get_puzzle_input, convert_int_line_to_series 23 24 def find_minimum_fuel_use(positions): 25 """Given the positions of the 'crab submarines', find the minimum fuel use 26 to line them up""" 27 return float(calculate_fuel_use_to(positions, positions.median())) 28 29 def calculate_fuel_use_to(start_positions, end_position): 30 """Given a series that represents the (1-D) positions of a collection of 'crab 31 submarines', find the fuel used to move to the given end position""" 32 return start_positions.sub(end_position).abs().sum() 33 34 def solve_puzzle(input_string): 35 """Return the numeric solution to the puzzle""" 36 return find_minimum_fuel_use(convert_int_line_to_series(input_string)) 37 38 def main(): 39 """Run when the file is called as a script""" 40 assert solve_puzzle("16,1,2,0,4,2,7,1,2,14\n") == 37 41 print("Fuel spent to align crabs:", 42 f"{solve_puzzle(get_puzzle_input(7)):.0f}") 43 44 if __name__ == "__main__": 45 main()