commit 42fc3fccad6918c9bc395c900d4e6e16d9824917
parent 27a578641f255001ee97eddc804b0c29e1abb81b
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Tue, 7 Dec 2021 15:22:07 -0500
Solution to day 7, part 2
Diffstat:
| A | day07_part2.py | | | 56 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 56 insertions(+), 0 deletions(-)
diff --git a/day07_part2.py b/day07_part2.py
@@ -0,0 +1,56 @@
+#!/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()
