Advent of Code 2021 Day 17 in Elixir - Trick Shot 풀이

문제 보기

포물선 형태로 탐사정을 발사했을 때 주어진 영역에 도달할 수 있도록 하는 초기 속도를 구하는 문제였다. 문제 1에서는 힙하게 가장 높은 곳까지 가는 초기 속도를, 문제 2에서는 주어진 영역(가로-세로 범위를 각각 x_s..x_e, y_s..y_e (0 < x_s < x_e, y_s < y_e < 0)라 하자)에 도달하는 모든 경우의 수를 구해야 했다. 단, 단위시간 기준으로 위치를 계산하므로, 궤적이 영역 안에 있더라도 주어진 영역을 지나쳐버리는 경우에는 도달하지 못한 것으로 본다.

가로 방향으로는 발사 후 1 단위시간마다 가로 방향 속도가 줄어들어 언젠가 0이 되어 앞으로 더 전진하지 못하므로, 속도가 0이 되기 전에 주어진 영역의 x좌표에 도달해야 한다. 여기서 주어진 영역에 도달하기 위한 가로 방향 최소 속도를 구할 수 있고, 최대 속도는 1 단위시간 안에 영역에 도달하는 x_e가 된다.

세로 방향으로는 중력의 영향으로 발사 후 1 단위시간마다 세로 방향 속도가 줄어드므로(0 이하로도 줄어든다), 당연하게도 위를 향해 발사하더라도 언젠가 아래로 다시 떨어지게 된다. 이 때 떨어지면서 반드시 y=0 지점을 지나고(고민 끝에 발견했다), 주어진 영역은 항상 y < 0이므로, y=0을 지난 이후 1 단위시간 내에 주어진 영역을 지나치면 안 된다. 여기서 주어진 영역에 도달하기 위한 세로 방향 최대 속도를 구할 수 있다. 속도의 최저값은 1 단위시간 안에 주어진 영역의 가장 아래를 스치는 y_s.

여차저차 해서 코드로 구현하면 다음과 같다. 주어진 영역과 탐사정의 위치를 비교해 지나쳤는지, 아직 도달하지 않았는지, 도달할 수 없는지 등을 확인하여 경우의 수를 계산해 간다. 도달 가능 여부를 확인할 수 있는 시점이 확실하지 않아서, 함수를 연속적으로 적용하여 필요한 만큼 값을 얻어올 수 있는 Stream.iterate를 사용했다. 스트림을 본격적으로 사용해본 건 아마 이게 처음 아닐까 싶다. 제법 편하다.

defmodule Day17 do
  def parse_input(file_name \\ "input/day17.txt") do
    file_name
    |> File.read!()
    |> String.trim_leading("target area: ")
    |> String.split(", ")
    |> Enum.map(fn range ->
      [s, e] =
        range
        |> String.slice(2..-1//1)
        |> String.split("..")
        |> Enum.map(&String.to_integer/1)
        |> Enum.sort()

      Range.new(s, e)
    end)
    |> List.to_tuple()
  end

  def run_q1() do
    {x_s..x_e, y_s..y_e} = parse_input()

    initial_y_velocity = 0
    min_x_velocity = find_min_x_velocity(x_s..x_e)
    {max_y_velocity, _} = step({x_s..x_e, y_s..y_e}, min_x_velocity, initial_y_velocity, 0)

    {max_y_velocity, max_y_velocity * (max_y_velocity + 1) / 2}
  end

  def run_q2() do
    {x_s..x_e, y_s..y_e} = parse_input()

    initial_y_velocity = y_s
    min_x_velocity = find_min_x_velocity(x_s..x_e)

    {_, candidate_count} = step({x_s..x_e, y_s..y_e}, min_x_velocity, initial_y_velocity, 0)

    candidate_count
  end

  defp step({_, y_s..y_e} = target, min_x_velocity, y_velocity, candidate_count) do
    result =
      simulate(target, min_x_velocity, y_velocity)
      |> Enum.reject(&(&1 == :never_reached))

    cond do
      Enum.any?(result, &(&1 == true)) ->
        feasibles = Enum.count(result, &(&1 == true))
        step(target, min_x_velocity, y_velocity + 1, candidate_count + feasibles)

      # y 영역이 모두 음수 지역에 있는데, 쏜 드론은 항상 y=0을 지남
      # 따라서 y 영역의 절대값이 큰 지점보다 속도가 빠른 경우 항상 지나침
      Enum.any?(result, &(&1 == :not_reached)) and
        y_velocity < abs(y_s) and y_velocity < abs(y_e) ->
        step(target, min_x_velocity, y_velocity + 1, candidate_count)

      Enum.all?(result, &(&1 == :over_reached)) ->
        {y_velocity - 1, candidate_count}

      true ->
        {y_velocity - 1, candidate_count}
    end
  end

  defp simulate({x_s..x_e, y_s..y_e}, min_x_velocity, y_velocity) do
    min_x_velocity..x_e
    |> Enum.map(fn x_velocity ->
      in_target_area?({x_s..x_e, y_s..y_e}, x_velocity, y_velocity)
    end)
  end

  defp find_min_x_velocity(x_s.._x_e) do
    0..x_s |> Enum.find_index(fn x_vel -> x_vel * (x_vel + 1) / 2 > x_s end)
  end

  defp x_velocity_step(x) when x > 0, do: x - 1
  defp x_velocity_step(x) when x < 0, do: x + 1
  defp x_velocity_step(0), do: 0

  defp in_target_area?({x_s..x_e, y_s..y_e}, x_velocity, y_velocity, with_log? \\ false) do
    Stream.iterate({x_velocity, y_velocity}, fn {x, y} -> {x_velocity_step(x), y - 1} end)
    |> Enum.reduce_while({0, 0}, fn {x_vel, y_vel}, {x, y} ->
      new_x = x + x_vel
      new_y = y + y_vel

      if with_log? do
        IO.inspect({new_x, new_y},
          label: "x=#{x_velocity}, y=#{y_velocity}, target=#{inspect({x_s..x_e, y_s..y_e})}"
        )
      end

      cond do
        new_x <= x_s and new_y < y_s and x_vel == 0 -> {:halt, :never_reached}
        new_x <= x_e and new_y < y_s -> {:halt, :not_reached}
        new_x > x_e -> {:halt, :over_reached}
        new_x in x_s..x_e and new_y in y_s..y_e -> {:halt, true}
        true -> {:cont, {new_x, new_y}}
      end
    end)
  end
end

여담. 문제가 점점 어려워지다보니 일단 돌아가도록 하려다 보니 점점 코드 정리를 소홀히 해가고 있다. 변수 이름도 대충 짓고 막...