commit 805a0082908f673dccd443df9cea48490d59899e
parent 95669e57118d046bdd93359d61c8749f7a65ca83
Author: Eamon Caddigan <eamon.caddigan@gmail.com>
Date: Fri, 17 Dec 2021 12:52:32 -0500
Solution for day 17
Diffstat:
| A | day17_part2.py | | | 98 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 98 insertions(+), 0 deletions(-)
diff --git a/day17_part2.py b/day17_part2.py
@@ -0,0 +1,98 @@
+#!/usr/bin/env python
+"""Advent of Code 2021, day 17 (part 2): Trick Shot
+Find the starting x and y velocities that end inside a target area"""
+
+# No part 1 file for today; I solved it with my phone calculator while I was
+# feeding my baby. Once I realized that any positive y velocity of _n_ would
+# have a velocity of -n when it returned to the vertical position y=0, it was
+# easy to work out without code.
+#
+# I am coding part 2, but it seems like a simple problem so late in the AoC. I
+# will admit that I made one naive assumption that was incorrect: since the
+# updating process for x and y are independent, I thought that x and y would be
+# independent for the solution, but I didn't consider that both the x and y
+# position need to be inside the target area _on the same step_. Oops.
+#
+# The initial x velocity is bounded by that which will stop moving forward
+# immediately upon reaching the trench, and that which finishes its first step
+# at the far end of the trench. The initial y velocity is bounded by the one
+# that solved part 1, and that which finishes its first step at the low end of
+# the trench. I'll use more lax bounds than this because it's so quick it
+# doesn't hurt.
+
+from typing import List, Tuple
+import re
+from utils import get_puzzle_input
+
+EXAMPLE_INPUT = \
+"""target area: x=20..30, y=-10..-5
+"""
+
+def parse_input(input_string: str) -> Tuple[Tuple[int, int], Tuple[int, int]]:
+ """Given the puzzle input, return the min and max of x and the min and max
+ of y as tuples"""
+ match = re.match(r"^target area: x=(?P<x1>\d+)..(?P<x2>\d+), " + \
+ r"y=(?P<y1>-?\d+)..(?P<y2>-?\d+)",
+ input_string)
+ if match is None:
+ raise RuntimeError("improperly foratted input string")
+
+ return (tuple(sorted([int(x) for x in match.group('x1', 'x2')])),
+ tuple(sorted([int(x) for x in match.group('y1', 'y2')])))
+
+def update_x(x_position: int, x_velocity: int) -> Tuple[int, int]:
+ """Given an x position and velocity, return an updated position and
+ velocity"""
+ # x position increases by velocity and the velocity increments or
+ # decrements by 1 toward 0. This code is a little hacky, but the expression
+ # `(n>0)*2-1` evaluates to 1 if n is positive, and -1 if it's negative,
+ # providing a concise `sign` function.
+ return (x_position + x_velocity,
+ ((x_velocity > 0) * 2 - 1) * max(0, abs(x_velocity) - 1))
+
+def update_y(y_position: int, y_velocity: int) -> Tuple[int, int]:
+ """Given a y position and velocity, return an updated position and
+ velocity"""
+ # y position increases by velocity and the velocity decreases by 1
+ return (y_position + y_velocity, y_velocity - 1)
+
+# XXX: These are pretty hacky in that they assume that x will be entirely
+# greater than 0 and y will be entirely less than 0.
+
+def test_xy(x_velocity: int, y_velocity: int,
+ x_bounds: Tuple[int, int], y_bounds: Tuple[int, int]) -> bool:
+ """Return True iff a probe with initial starting position of (0, 0), and
+ velocity vector of (`x_velocity`, `y_velocity`) would finish any step
+ inside the area bounded by `x_bound` and `y_bounds`."""
+ x_position, y_position = (0, 0)
+ while x_position <= x_bounds[1] and y_position >= y_bounds[0]:
+ if x_bounds[0] <= x_position <= x_bounds[1] and \
+ y_bounds[0] <= y_position <= y_bounds[1]:
+ return True
+ x_position, x_velocity = update_x(x_position, x_velocity)
+ y_position, y_velocity = update_y(y_position, y_velocity)
+ return False
+
+def find_xy(x_bounds: Tuple[int, int],
+ y_bounds: Tuple[int, int]) -> List[Tuple[int, int]]:
+ """Given the specified boundaries, return a list of all the starting x and
+ y velocities that would finish a step inside of them"""
+ in_bounds_velocities = []
+ for x_velocity in range(x_bounds[1]+1):
+ for y_velocity in range(y_bounds[0], -y_bounds[0]+1):
+ if test_xy(x_velocity, y_velocity, x_bounds, y_bounds):
+ in_bounds_velocities.append((x_velocity, y_velocity))
+ return in_bounds_velocities
+
+def solve_puzzle(input_string: str) -> int:
+ """Return the numeric solution to the puzzle"""
+ return len(find_xy(*parse_input(input_string)))
+
+def main() -> None:
+ """Run when the file is called as a script"""
+ assert solve_puzzle(EXAMPLE_INPUT) == 112
+ print("Total distinct initial velocities:",
+ solve_puzzle(get_puzzle_input(17)))
+
+if __name__ == "__main__":
+ main()
