library(tidyverse)

z = readLines("data/day17.txt") %>% str_extract_all("-?[0-9]{1,3}") %>% .[[1]] %>% as.numeric()
x1 = z[1]
x2 = z[2]
y1 = z[3]
y2 = z[4]

# Part 1
y_target = abs(min(y1, y2)) - 1
y_target * (y_target + 1) / 2

# Part 2
# Which bounds do I have to search?
quadratic_pos = function(a, b, cv) {
  subv = c(
    (-b + sqrt(b^2 - (4*a*cv))) / (2 * a),
    (-b - sqrt(b^2 - (4*a*cv))) / (2 * a)
  )

  subv[subv > 0]
}

min_vx_rest = ceiling(quadratic_pos(1, 1, -(2 * x1)))
max_vx_rest = floor(quadratic_pos(1, 1, -(2 * x2)))

vel_bounds_y = c(y1, y_target)
yt = seq(vel_bounds_y[1], vel_bounds_y[2]) %>% map_dfr(function(vy) {
  # Offsets
  offset = 0
  fvy = vy
  if(vy == 0) {
    offset = 1
    fvy = -1
  } else if(vy > 0) {
    offset = (2 * vy) + 1
    fvy = -fvy - 1
  }

  # Solve the range of ts where this velocity works
  min_t = ceiling(quadratic_pos(-1, 2 * fvy + 1, -2 * y2))
  max_t = floor(quadratic_pos(-1, 2 * fvy + 1, -2 * y1))

  if(min_t <= max_t) {
    tibble(
      y = vy,
      t = (min_t:max_t) + offset
    )
  } else { return(NULL) }
}) %>% unique()

tx = unique(yt$t) %>% map_dfr(function(t) {
  #
  # dist = (1/2) * (t) * (2*vx - (t - 1))
  # 2 * dist = t * (2vx - (t - 1))
  # (2 * dist) / t = 2vx - t + 1
  # ((2 * dist) / t) + t - 1 = 2vx
  # (((2 * dist) / t) + t - 1) / 2 = vx

  # Solutions where the range of values are in the target
  min_vx_move = ceiling((((2 * x1) / t) + t - 1) / 2)
  max_vx_move = floor((((2 * x2) / t) + t - 1) / 2)

  # This is going to include illegal values (where there were some
  # negative velocities) -- clip those. Those occur when t > the velocity
  xrange = min_vx_move:max_vx_move %>% .[. >= t]

  # We are excluding cases where the item came to rest before t
  if(min_vx_rest < t) {
    xrange = c(xrange, min_vx_rest:min(t, max_vx_rest)) %>% unique()
  }

  tibble(
    t = t,
    x = xrange)
}) %>% unique()

answers = yt %>%
  inner_join(tx) %>%
  select(-t) %>%
  unique()

nrow(answers)