AoC 2021 Day 17

# Just like bull's-eyeing wamp rats in my T-16 back home


from copy import copy
from aoccore import Vector2D
from typing import List
from collections import defaultdict


class Rectangle:
    def __init__(self, pt0: Vector2D, pt1: Vector2D):
        self.x0 = pt0.x
        self.x1 = pt1.x
        self.y0 = pt0.y
        self.y1 = pt1.y

    def __repr__(self):
        return repr((self.x0, self.y0, self.x1, self.y1))

    def inside(self, pt: Vector2D):
        return (self.x0 <= pt.x <= self.x1) and (self.y0 <= pt.y <= self.y1)

    def below(self, pt: Vector2D):
        return (pt.x > max(self.x0, self.x1)) or (pt.y < min(self.y0, self.y1))


EXAMPLE = Rectangle(Vector2D(20, -10), Vector2D(30, -5))
INPUT = Rectangle(Vector2D(96, -144), Vector2D(125, -98))


def do_physics(point: Vector2D, velocity: Vector2D) -> tuple:
    """
    Simulates a basic physics engine, with fixed gravity and drag forces, represented by the 'phob' object
    :param point:
    :param velocity:
    :return:
    """
    phob = Vector2D(-1, -1)
    new_pt = point.add(velocity)
    vel = velocity.add(phob)
    vel.x = 0 if vel.x < 0 else vel.x  # clamp forward velocity at zero since drag is a function of forward velocity
    return new_pt, vel


def display(path: List[Vector2D], target: Rectangle):
    x_min = 0
    x_max = max([target.x0, target.x1] + [p.x for p in path]) + 10
    y_min = min([target.y0, target.y1] + [p.y for p in path]) - 10
    y_max = max([target.y0, target.y1] + [p.y for p in path]) + 10
    buffer = defaultdict(lambda: ' ')
    for x in range(target.x0, target.x1):
        for y in range(target.y0, target.y1):
            buffer[Vector2D(x, y)] = '#'
    for loc in path:
        buffer[loc] = '*'
        if target.inside(loc):
            buffer[loc] = '@'
    output = []
    for y in range(y_max, y_min - 1, -1):
        line = ''
        for x in range(x_min, x_max):
            line += buffer[Vector2D(x, y)]
        output.append(line)
    for line in output:
        print(line)


def trajectory(start: Vector2D, target: Rectangle, min_vel: Vector2D, max_vel: Vector2D, good_vis: List[Vector2D]):
    trajectories, final_path = [], []
    test_velocities = [Vector2D(x, y) for x in range(min_vel.x, max_vel.x + 1) for y in range(min_vel.y, max_vel.y + 1)]
    for stv in test_velocities:
        pt = copy(start)
        tv = copy(stv)
        pt_path = []
        while True:
            pt, tv = do_physics(pt, tv)
            pt_path.append(pt)
            if target.inside(pt):
                trajectories.append(pt_path)
                good_vis.append(stv)
                break
            if target.below(pt):
                break
        # display(pt_path, target)
    if not trajectories:
        min_vel = max_vel
        max_vel = Vector2D(max_vel.x + min_vel.x, max_vel.y + min_vel.y)
        max_height, good_vis = trajectory(start, target, min_vel, max_vel, good_vis)
        return max_height, good_vis
    max_height = max(p0.y for p in trajectories for p0 in p)
    for t in trajectories:
        if max_height in [pt.y for pt in t]:
            final_path = t[:]
            break
    # display(final_path, target)
    return max_height, good_vis


def targeting_solutions(start: Vector2D, target: Rectangle, min_vel: Vector2D, max_vel: Vector2D) -> List[Vector2D]:
    good_vis = []
    test_velocities = [Vector2D(x, y) for x in range(min_vel.x, max_vel.x + 1) for y in range(min_vel.y, max_vel.y + 1)]
    for stv in test_velocities:
        pt = copy(start)
        tv = copy(stv)
        while True:
            pt, tv = do_physics(pt, tv)
            if target.inside(pt):
                good_vis.append(stv)
                break
            if target.below(pt):
                break
    return good_vis


def part1(target: Rectangle):
    start = Vector2D(0, 0)
    for vy in range(0, 101, 10):
        max_height, vis = trajectory(start, target, Vector2D(0, vy), Vector2D(10, vy + 10), [])
        print('Max height:', max_height)


def part2(target: Rectangle):
    start = Vector2D(0, 0)
    max_vx = target.x1
    min_vy = target.y0
    good_vis = targeting_solutions(start, target, Vector2D(0, min_vy), Vector2D(max_vx + 1, 2 * abs(min_vy)))
    print('Good initial velocities', len(good_vis))