Day 17

Setup

input = File.read!("day17.txt")
# input = "target area: x=117..7310, y=-9546..-89"

IO.puts(input)

%{"a_x" => a_x, "a_y" => a_y, "b_x" => b_x, "b_y" => b_y} =
  Regex.named_captures(
    ~r/target area: x=(?<a_x>-?\d+)\.\.(?<b_x>-?\d+), y=(?<a_y>-?\d+)\.\.(?<b_y>-?\d+)/,
    input
  )

a = %{x: String.to_integer(a_x), y: String.to_integer(a_y)}
b = %{x: String.to_integer(b_x), y: String.to_integer(b_y)}

[a: a, b: b]

target area: x=288..330, y=-96..-50

[a: %{x: 288, y: -96}, b: %{x: 330, y: -50}]

Task 1

Lemma 1

The horizontal velocity there can be ignored, as we can always find a horizontal velocity that will reach the target area and will reduce the velocity to $$0$$, which mean that all further movement will happen only in one dimension. That velocity is:

$$ v_x = \lceil \frac{-1 + \sqrt{1 + 8b_x}}{2} \rceil $$

Proof:

Which came from the fact that distance traveled by the projectile is sum of the arithmetic sequence with $$r = -1$$, so the distance traveled is:

$$ sx = \frac{2v{x0} - t + 1}{2}t $$

Where $$t$$ is travel time. As $$vx(t) = v{x0}$$ then $$vx(t) = 0 \implies t = v{x0}$$, so after substituting $$t$$ we get:

$$ sx = \frac{2v{x0} - v{x0} + 1}{2}v{x0} \ sx = \frac{v{x0} + 1}{2}v{x0} \ s_x = \frac{v{x0}^2 + v_{x0}}{2} $$

As we want to find the nearest column where we want to stop movement in $$OX$$ then we are looking at $$s_x = b_x$$:

$$ bx = \frac{v{x0}^2 + v{x0}}{2} \ 2b_x = v{x0}^2 + v{x0} \ 0 = v{x0}^2 + v_{x0} - 2b_x $$

The soultions for these equation are in form of:

$$ v_{x0} = \frac{-1 \mp \sqrt{1 + 8b_x}}{2} $$

As we assume that $$b_x \gt 0$$, then the solutions will always be trivial. Additionally we do not care about negative roots, so we can take only:

$$ v_{x0} = \frac{-1 + \sqrt{1 + 8b_x}}{2} $$

As this can be fractional and we want $$v_x0 \in \mathbb{Z}$$ and assume that target is big enough to have at least one point that we can land on, then we can simply round velocity up:

$$ v_x = \lceil \frac{-1 + \sqrt{1 + 8b_x}}{2} \rceil\ $$

$$\blacksquare$$

Lemma 2

TODO

As

$$ v_{y0} = \frac{2a_y - t + t^2}{2t} $$

Left to prove that $$v_0$$ will have highest possible value for $$t = -2a_y$$. Then above equation reduces like that:

$$ v{y0} = \frac{2a_y + 2a_y + 4a_y^2}{4a_y} \ v{y0} = \frac{4ay + 4a_y^2}{4a_y} \ v{y0} = 1 + a_y $$

v_y = -min(a.y, b.y) - 1

{v_y, v_y * (v_y + 1) / 2}

{95, 4560.0}

Task 2

solveq_pos = fn a, b, c ->
  [
    (-b - :math.sqrt(b * b - 4 * a * c)) / (2 * a),
    (-b + :math.sqrt(b * b - 4 * a * c)) / (2 * a)
  ]
  |> Enum.filter(&(&1 > 0))
end

v_xmin_rest = ceil(hd(solveq_pos.(1, 1, -2 * min(a.x, b.x))))
v_xmax_rest = floor(hd(solveq_pos.(1, 1, -2 * max(a.x, b.x))))

v_ymax = -min(a.y, b.y) - 1
v_ymin = min(a.y, b.y)

{xmin, xmax} = Enum.min_max([a.x, b.x])
{ymin, ymax} = Enum.min_max([a.y, b.y])

offset = fn
  0 -> {1, -1}
  v_y when v_y > 0 -> {2 * v_y + 1, -v_y - 1}
  v_y -> {0, v_y}
end

v_y_pairs =
  for v_y <- v_ymin..v_ymax,
      {offset, fv_y} = offset.(v_y),
      tmin <- solveq_pos.(-1, 2 * fv_y + 1, -2 * ymax),
      tmax <- solveq_pos.(-1, 2 * fv_y + 1, -2 * ymin),
      ceil(tmin) <= floor(tmax),
      t <- ceil(tmin)..floor(tmax),
      do: {v_y, t + offset}

v_x_pairs =
  for t <- Enum.uniq(Enum.map(v_y_pairs, &elem(&1, 1))),
      v_xmin_move = ceil((2 * xmin / t + t - 1) / 2),
      v_xmax_move = floor((2 * xmax / t + t - 1) / 2),
      xrange = Enum.filter(v_xmin_move..v_xmax_move, &(&1 >= t)),
      xrange =
        if(v_xmin_rest < t,
          do: Enum.concat(xrange, v_xmin_rest..min(t, v_xmax_rest)),
          else: xrange
        ),
      v_x <- MapSet.new(xrange),
      do: {t, v_x}

pairs =
  for {v_y, t} <- v_y_pairs,
      {^t, v_x} <- v_x_pairs,
      into: MapSet.new(),
      do: {v_x, v_y}

MapSet.size(pairs)

3344