My attempts to work through the 2021 Advent of Code problems.
Log | Files | Refs | README | LICENSE

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()
```