advent_of_code_2021

day07_part2.py (2395B)

---

 #!/usr/bin/env python
 """Advent of Code 2021, day 7 (part 2): optimize 'crab submarine' alignment to
 minimize fuel"""
 
 # Well the actual code I wrote for part 1 isn't very useful here, but the
 # general approach works so that's cool I guess. It's probably faster to
 # evaluate the fuel use at every position than it is to deploy an optimizer to
 # solve the problem. HOWEVER, I'm using AoC to learn, so today I'm learning how
 # to use `scipy.optimize.minimize()`.
 
 from scipy.optimize import minimize
 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"""
     # Unlike part 1, we need to actually work to find the solution. What's
     # interesting is that an optimization procedure found that, for the example
     # input, a position of 4.7 had better fuel use (167.55) than the example
     # solution of 5 (168). The problem doesn't explicitly state that only
     # integer solutions are allowed, but we'll round the result. Knowing this,
     # we can loose up the tolerances quite a bit, which gives us a nice
     # speed boost.
     best_position_solution = minimize(
         lambda x: calculate_fuel_use_to(positions, x[0]),
         0, method='nelder-mead', options={'xatol': 0.1, 'fatol': 0.01}
     )
     if not best_position_solution.success:
         raise RuntimeError('optimizer failed to find solution')
     return calculate_fuel_use_to(positions,
                                  float(best_position_solution.x[0].round()))
 
 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"""
     # \sum_{i=1}^{n}i=\frac{n(n+1)}{2}
     return (
         start_positions
         .sub(end_position)
         .abs()
         .apply(lambda n: n*(n+1)/2)
         .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") == 168.0
     print("Actual fuel spent to align crabs:",
           f"{solve_puzzle(get_puzzle_input(7)):.0f}")
 
 if __name__ == "__main__":
     main()