advent_of_code_2021

day17_part2.py (4514B)

---

 #!/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()