My attempts to work through the 2021 Advent of Code problems.
git clone
Log | Files | Refs | README | LICENSE (2161B)

      1 #!/usr/bin/env python
      2 """Advent of Code 2021, day 7 (part 1): optimize 'crab submarine' alignment to
      3 minimize fuel"""
      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.
     22 from utils import get_puzzle_input, convert_int_line_to_series
     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()))
     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()
     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))
     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}")
     44 if __name__ == "__main__":
     45     main()