Foobar приносит оружие в охрану Оптимизация боя

Question

Я обдумываю задачу «Привести ружье в охрану» от Google Foobar (также определено в конце вопроса для удобства).

Я пришел к К такому же выводу в статье привязывается, что лучше всего решать проблему, отражая комнату. Однако в статье предлагается сначала создать коробку с зеркальными комнатами, где высота и ширина определяются максимальным количеством раз, которое мы можем отразить комнату вверх и в стороны в пределах дистанции стрельбы (ceil((player_position + laser distance) / room_size)). Затем мы удалим все части, которые по диагонали находятся за пределами поля.

Однако это может привести к неэффективности, так как мы должны генерировать гораздо больше точек, чем позволяет расстояние до пистолета. По мере увеличения дальности стрельбы эта неэффективность будет возрастать.

Однако я не могу найти способ обойти эту проблему. Каков оптимальный способ получения баллов за проблему?

============================ ===

Ой-ой - вас загнал в угол один из элитных гвардейцев командира Лямбда! К счастью, вы схватили лучевое оружие с заброшенного сторожевого поста, когда бежали по станции, так что у вас есть шанс выбраться наружу. Но лучевое оружие потенциально опасно как для вас, так и для элитной стражи: его лучи отражаются от стен, а это означает, что вам нужно быть очень осторожным при стрельбе, чтобы не отразить выстрел в себя!

К счастью , лучи могут пройти только определенное максимальное расстояние, прежде чем станут слишком слабыми, чтобы нанести ущерб. Вы также знаете, что если луч попадает в угол, он отскакивает в том же направлении. И, конечно, если луч попадает в вас или в охранника, он немедленно останавливается (хотя и болезненно).

Напишите решение функции (размеры, your_position, guard_position, distance), которое дает массив из 2 целых чисел ширину и высоту комнаты, массив из 2 целых чисел ваших координат x и y в комнате, массив из 2 целых чисел координат x и y охранника в комнате, и возвращает целое число количества различных направлений, которые вы можете стрелять, чтобы поразить элитного охранника, учитывая максимальное расстояние, которое может пройти луч.

Комната имеет целочисленные размеры [1

Например, если вы и элитный стражник находились в комнате с размерами [3 , 2], your_position [1, 1], guard_position [2, 1] и максимальной дальностью выстрела 4, вы можете стрелять в семи разных направлениях, чтобы поразить элитного охранника (заданного в виде векторных пеленгов от вашего местоположения): [1 , 0], [1, 2], [1, -2], [3, 2], [3, -2], [-3, 2] и [-3, -2]. Как указано в c примерах, выстрел по азимуту [1, 0] - это горизонтальный выстрел по прямой линии на расстоянии 1, выстрел по пеленгу [-3, -2] отскакивает от левой стены, а затем от нижней стены, прежде чем попасть в элитный стражник с общей дистанцией выстрела sqrt (13), и выстрел по пеленгу [1, 2] отскакивает только от верхней стены, прежде чем поразить элитного охранника с общим расстоянием выстрела sqrt (5).

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

Python случаев

Input: solution.solution ([3,2], [ 1,1], [2,1], 4) Вывод: 7

Вход: solution.solution ([300,275], [150,150], [185,100], 500) Вывод: 9

Answer 1

ceil((player_position + laser distance) / room_size) недостаточно

Для следующего случая, когда:

solution([20, 20], [2, 2], [2, 4], 5)

вам все равно нужно создать отражение для левой стороны

Я обнаружил что эта формула работает лучше:

x_reflect = max(int(float(your_position[0] + distance) / dimensions[0]), abs(int(floor(float(your_position[0] - distance) / dimensions[0]))))
y_reflect = max(int(float(your_position[1] + distance) / dimensions[1]), abs(int(floor(float(your_position[1] - distance) / dimensions[1]))))

Я бы написал это как комментарий, но мне не хватает очков

Answer 2

Создание следующей комнаты - это просто ее отражение в выбранном направлении. Затем у нас есть две новые точки: одна для охранника и одна для нас самих. Мы можем сделать это как итерацию, комнату за комнатой, с постоянным пространством и временем. Метод, который сработал для меня, хотя и не был тривиальным для программирования, заключался в том, чтобы иметь sh строку (от origin-us до вновь отраженного охранника), поскольку нам нужно иметь возможность определить, находится ли новая точка на строке, которую мы уже выстрелил и поразил охранника, а также некоторые другие проверки. это хотя бы один опубликованный код, который выглядит намного более компактным, чем то, что я предлагал, чего я не понял. Похоже, это обобщение преобразований, но я не мог уследить за этим.