advent_17_part1.py

def simulate(dx, dy, x1, x2, y1, y2):
  x, y = (0, 0)
  hit = False
  max_y = -999999
  while True:
    x += dx
    y += dy
    dy -= 1
    if dx < 0:
      dx += 1
    elif dx > 0:
      dx -= 1
    if x >= x1 and x <= x2 and y >= y1 and y <= y2:
      hit = True
    if x > x2 or y < y1:
      break # Overshot
    if y > max_y:
      max_y = y
  if not hit:
    max_y = -9999
  return hit, max_y

def find_best_dy(dx, x1, x2, y1, y2):
  dy = 999
  best_y = -99999
  best_dy = None
  last_y = None
  while dy > -999:
    hit, max_y = simulate(dx, dy, x1, x2, y1, y2)
    if last_y is not None:
      if last_y > max_y:
        # Value is increasing, no need to continue, we got the best value already
        break
    if hit:
      last_y = max_y
      if max_y > best_y:
        best_dy = dy
        best_y = max_y
    dy -= 1
  return best_dy, best_y

def find_trajectory(x1, x2, y1, y2):
  x1, x2 = sorted([x1, x2])
  y1, y2 = sorted([y1, y2])
  # Initial dx must be at most x2, otherwise it'll fall out of bounds.
  dx = x2
  best_solution = -999999
  best_dy = 0
  best_dx = 0
  while dx > 0:
    solution, max_y = find_best_dy(dx, x1, x2, y1, y2)
    if solution is not None and max_y > best_solution:
      best_solution = max_y
      best_dx = dx
      best_dy = solution
    dx -= 1
  print(best_dx, best_dy, best_solution)

find_trajectory(25, 67, -260, -200)