Это семнадцатый день Пришествия Кода. Сегодня мы будем моделировать траекторию полета снаряда в воде.

Как всегда, пожалуйста, попробуйте решить проблему, прежде чем искать решение. Для всех статей в этой серии ознакомьтесь с этим списком.

День 17

В качестве входных данных мы получаем координаты нашей цели по осям x и y, а для части 1 перед нами стоит задача определить причудливую траекторию, по которой мы хотим выстрелить снарядом как можно выше, но при этом поразить цель.

target area: x=277..318, y=-92..-53

Симуляция примитивная. Каждый тик снаряд движется в зависимости от его скорости x и y, а затем мы уменьшаем/увеличиваем эти скорости:

  • x скорость стремится к нулю; то есть отрицательная скорость x будет увеличиваться на единицу за каждый тик, положительная скорость x будет уменьшаться на единицу за каждый тик (нулевая скорость остается равной нулю)
  • y скорость уменьшается с каждым тиком (имитация гравитации)

Если бы мы выстрелили снарядом прямо вниз, он бы продолжал ускоряться, а если бы мы выстрелили прямо вверх, он замедлился бы, в какой-то момент достиг нулевой скорости, а затем начал бы падать и ускоряться.

Решение этой задачи для общих случаев становится весьма громоздким и не особо интересным с точки зрения программирования. Поэтому я сделаю несколько упрощений:

  • x координата цели всегда положительна
  • y координата цели всегда отрицательная
  • цель достаточно «широкая» (мы обсудим это позже)

Симметрия

Давайте рассмотрим, что происходит с положением y снаряда, когда мы стреляем в него. В какой-то момент он снова приземлится на ось (позиция y==0), потому что процесс симметричен (рассмотрите среднюю точку нулевой скорости, окружающие скорости будут ...4 3 2 1 0 1 2 3 4...). Это также означает, что снаряд будет иметь одинаковую скорость, пересекая ось.

Затем мы можем оптимистично предположить, что мы сможем найти соответствующую скорость x и рассмотреть нижнюю линию цели y_min. Наивысшая возможная скорость - это то, что снаряд достигнет y_min сразу после достижения y==0. Поэтому начальная скорость просто vy_max=-y_min-1 (на единицу меньше, чем скорость, которая позволила нам достичь y_min).

Когда у нас есть скорость, мы знаем, что достигли средней точки vy_max+1, где скорость достигнет нуля. Наконец, нам нужно выяснить фактическое расстояние.

Для y-позиции мы знаем, что позиция представляет собой сумму vy + vy-1 + vy-2..., которую мы можем переписать как vy*steps — (0+1+2...) и упростить сумму: vy*ticks-ticks*(ticks-1)/2. Формула для x очень похожа, за исключением того, что нам нужно остановиться в точке, где скорость достигает нуля, поэтому new_ticks=min(ticks,vx+1), а затем мы можем повторно использовать формулу: vx*new_ticks-new_ticks*(new_ticks-1)/2.

Зная скорость, можно вычислить по формуле:

Я упомянул упрощение. Есть шанс, что мы не найдем скорость x, которая также попадет в цель за то же количество тиков. Чтобы решить эту проблему для общего случая, нам пришлось бы просмотреть от y_min, и если мы все еще не находим совпадения, рассмотрим случаи, когда между y==0 и достижением цели есть одна (или несколько) промежуточных точек.

Нахождение всех скоростей, попадающих в цель

Правильный способ сделать это — начать с цели и использовать положение Y для определения возможных скоростей. Мы знаем, что расстояние ниже y==0 должно выражаться как vy+vy-1+vy-2..., и оттуда мы будем генерировать все соответствующие x скорости, которые приземляются на цель.

Тем не менее, это слишком много усилий для чего-то такого простого. Итак, грубая сила:

Мы знаем, что наша скорость по оси y должна быть не менее y_min, которая достигает нижней границы за один шаг, и не более vy_max, которую мы определили в части 1. Точно так же для скорости x максимум равен x_max, который достигает правой границы за один шаг (минимум можно было бы ограничить жестче, но в этом нет причин).

Приношу свои извинения за, возможно, разочаровывающее решение, но правильный-правильный подход настолько далек от простоты решения методом грубой силы, а проблемная область настолько мала, что я действительно не мог найти силы. Я надеюсь, что вы нашли его полезным, тем не менее.

Ссылки и технические примечания

Репозиторий ежедневных решений доступен по адресу: https://github.com/HappyCerberus/moderncpp-aoc-2021.

Посмотрите в этом списке статьи о других днях появления кода.

И, пожалуйста, не забудьте попробовать Пришествие кода на себе.

Спасибо за чтение

Спасибо, что прочитали эту статью. Вам понравилось?

Я также публикую видео на YouTube. У тебя есть вопросы? Напишите мне в Twitter или LinkedIn.