Робот-черепашка сначала смотрит на север. За один шаг может двинуться на N (N >= 1) клеток туда, куда смотрит, после чего сразу поворачивается на 90 грд. по часовой стрелке.
Входная программа — ряд целых чисел любой длины. Например: 1,7,3,4,5,1. (1 на север, 7 на восток, 3 на юг, 4 на запад, 5 на север, 1 на восток). Каждый шаг — не менее 1.
Написать код, который бы возвращал ближайший номер шага (от начала программы), на котором черепашка проедется по собственному пути. То есть, по клетке, на которой она уже была. Стоимость алгоритма по процу — не более O(N), стоимость алгоритма по памяти — постоянная ( O(1) ).
Нарисовал картинку, из которой видно одно свойство алгоритма — если черепашка когда-либо наезжает на собственный путь на неком шаге M, то этот наезд всегда происходит на ту линию, которая была построена на шаге M-3, либо M-5. Всё.
1. Это наколеночное решение, выведенное умозрительно, без доказательств.
2. История про робота-черепашку — боян 40-летней давности (или больше), над которым бились все великие бородатые изобретатели алгоритмов, поэтому любое своё решение просто психологически идёт в корзину.
Свойства шагательного алгоритма таковы, что черепашка либо поедет по постоянно раскручивающейся спирали (конечной, если конечно значение целого числа в программе), либо (сделав хоть один ход, не выносящий её за "очертания" спирали, обязательно на себя наедет, максимум продлив себе "жизнь" закручиванием спирали.
Картинка, из которой видны свойства шагательного алгоритма (красным показаны линии, на которые совершается наезд). Зелёная точка — возможные альтернативы развития событий для рассмотрения разных вариантов.
Здравствуйте, pkl, Вы писали: pkl>Обсудите (-;
Берем две черепашки: одна "бежит" в 2 раза быстрее другой (выполняет 2 шага за раз).
Когда черепашки пересекутся, тогда и будет найдено решение.
Здравствуйте, syrompe, Вы писали:
S>Здравствуйте, pkl, Вы писали: pkl>>Обсудите (-; S>Берем две черепашки: одна "бежит" в 2 раза быстрее другой (выполняет 2 шага за раз). S>Когда черепашки пересекутся, тогда и будет найдено решение.
По-моему этот алгоритм ищет петли в пути, а здесь петель нет.
Здравствуйте, syrompe, Вы писали:
S>Берем две черепашки: одна "бежит" в 2 раза быстрее другой (выполняет 2 шага за раз). S>Когда черепашки пересекутся, тогда и будет найдено решение.
Нда ужжж. Это алгоритм для поиска цикла в односвязном списке . Сходу я тогда это решение не придумал, но вот теперь знаю, соответственно стал неимоверно круче как программист . Вот только этот алгоритм тут неприменим, ибо черепашки не пересекутся. Соответственно маловероятно, что здесь алгоритм будет тривиальным. Возможно решение связано с обновлением структуры данных из фиксированного числа элементов на каждом шаге, связанного с расстоянием до ближайшей границы. Возможно за день и написал бы неспешно, но алгоритм будет явно нетривиальным и запутанным.
Здравствуйте, pkl, Вы писали:
pkl>Обсудите (-;
Так ты вроде и ответил. Берешь для каждой точки прямые заданные направлениями на предыдущий и последующий шаги и смотришь пересекла ли черепашка их через 4 точки, если пересекла, то смотришь пересекла ли свой путь (отрезок между текущей точкой и предыдущей/последующей, если нет, то нет).
Здравствуйте, pkl, Вы писали: pkl>По-моему этот алгоритм ищет петли в пути, а здесь петель нет.
"Написать код, который бы возвращал ближайший номер шага (от начала программы), на котором черепашка проедется по собственному пути."
А это разве не петля в итоге?
Здравствуйте, syrompe, Вы писали:
S>Здравствуйте, pkl, Вы писали: pkl>>По-моему этот алгоритм ищет петли в пути, а здесь петель нет.
S>"Написать код, который бы возвращал ближайший номер шага (от начала программы), на котором черепашка проедется по собственному пути." S>А это разве не петля в итоге?
Нет, пройтись по собственному пути означает наступить на клетку, где уже проходил.
Здравствуйте, pkl, Вы писали:
pkl>Здравствуйте, syrompe, Вы писали:
S>>Здравствуйте, pkl, Вы писали: pkl>>>По-моему этот алгоритм ищет петли в пути, а здесь петель нет.
S>>"Написать код, который бы возвращал ближайший номер шага (от начала программы), на котором черепашка проедется по собственному пути." S>>А это разве не петля в итоге? pkl>Нет, пройтись по собственному пути означает наступить на клетку, где уже проходил.
Ага, понял...
Значит метод сей действительно не катит.
если надо чтобы она максимальное расстояние прошла по спиралям то можно через micrsoft solver foundation сделать модель и потом по этой модели будет CSP или MLIP решальщик с Goal(Max...) который вычислит максимальное расстояние в пределах прямоугольника, еще на каждую клетку повесить надо необходимые constraint перемещения и все, за бесплатно ясное дело всех деталей раскрывать смысла нет.
Здравствуйте, pkl, Вы писали:
pkl>Робот-черепашка сначала смотрит на север. За один шаг может двинуться на N (N >= 1) клеток туда, куда смотрит, после чего сразу поворачивается на 90 грд. по часовой стрелке.
pkl>Входная программа — ряд целых чисел любой длины. Например: 1,7,3,4,5,1. (1 на север, 7 на восток, 3 на юг, 4 на запад, 5 на север, 1 на восток). Каждый шаг — не менее 1.
pkl>Обсудите (-;
Очевидно, четные и нечетные значения отвечают за движение по разным осям. Выделяем, допустим, четные. Тогда среди них четные и нечетные отвечают за движение в противоположных направлениях. Присвой им разные знаки и сложи. Пересечение возможно только там где меняется знак суммы. Аналогично с последовательностью нечетных проделай. Необходимое условию для перечения что бы сумма нечетных ( или четных если проверяем перемену знака нечетных)была меньше максимума суммы по этому направлению.
Здравствуйте, pkl, Вы писали:
pkl>Робот-черепашка сначала смотрит на север. За один шаг может двинуться на N (N >= 1) клеток туда, куда смотрит, после чего сразу поворачивается на 90 грд. по часовой стрелке.
pkl>Входная программа — ряд целых чисел любой длины. Например: 1,7,3,4,5,1. (1 на север, 7 на восток, 3 на юг, 4 на запад, 5 на север, 1 на восток). Каждый шаг — не менее 1.
pkl>Написать код, который бы возвращал ближайший номер шага (от начала программы), на котором черепашка проедется по собственному пути. То есть, по клетке, на которой она уже была. Стоимость алгоритма по процу — не более O(N), стоимость алгоритма по памяти — постоянная ( O(1) ).
Нужна очередь фиксированного размера 2 и еще один булевая переменная A (false изначально)
Шаг: заталкиваем длину хода L_n в хвост очереди, сравниваем ее с тем, что выскочило с головы очереди (длиной шага L_n-2).
Если A == true и L_n >= L_n-2 то все, приехали, на этом ходе черепашка наехала на свой след (или пересекла его)
Иначе, Если L_n <= L_n-2, то спираль начинает схлопываться (неважно, если она до этого уже схлопывалась), устанавливаем A=true;
Переходим на следующий шаг (или выходим, если это был последний. Тогда пересечений не было)
Как-то так.
Применительно к эхотагу — ИМХО вся соль алгоритмостроения заключается в том, чтобы свести объем информации, с которой приходится иметь дело, к минимуму. Можно влет выдавать решения для известных алгоритмических задач, можно натаскаться на алгоритмы, произведенные от них. Можно ли научиться это делать для абстрактной алгоритмической задачи в вакууме —
Здравствуйте, batu, Вы писали:
B>Здравствуйте, pkl, Вы писали:
pkl>>Робот-черепашка сначала смотрит на север. За один шаг может двинуться на N (N >= 1) клеток туда, куда смотрит, после чего сразу поворачивается на 90 грд. по часовой стрелке.
pkl>>Входная программа — ряд целых чисел любой длины. Например: 1,7,3,4,5,1. (1 на север, 7 на восток, 3 на юг, 4 на запад, 5 на север, 1 на восток). Каждый шаг — не менее 1.
pkl>>Обсудите (-; B>Очевидно, четные и нечетные значения отвечают за движение по разным осям. Выделяем, допустим, четные. Тогда среди них четные и нечетные отвечают за движение в противоположных направлениях. Присвой им разные знаки и сложи. Пересечение возможно только там где меняется знак суммы. Аналогично с последовательностью нечетных проделай. Необходимое условию для перечения что бы сумма нечетных ( или четных если проверяем перемену знака нечетных)была меньше максимума суммы по этому направлению.
Не совсем так, так ты найдешь когда раскручивающаяся спираль перейдет в закручивающуюся, но там может быть ещё немало шагов после этого
Здравствуйте, pkl, Вы писали:
pkl>Робот-черепашка сначала смотрит на север. За один шаг может двинуться на N (N >= 1) клеток туда, куда смотрит, после чего сразу поворачивается на 90 грд. по часовой стрелке.
pkl>Входная программа — ряд целых чисел любой длины. Например: 1,7,3,4,5,1. (1 на север, 7 на восток, 3 на юг, 4 на запад, 5 на север, 1 на восток). Каждый шаг — не менее 1.
pkl>Написать код, который бы возвращал ближайший номер шага (от начала программы), на котором черепашка проедется по собственному пути. То есть, по клетке, на которой она уже была. Стоимость алгоритма по процу — не более O(N), стоимость алгоритма по памяти — постоянная ( O(1) ).
Почему бы просто не сравнивать текущий ход с ходом, который был последним ровно в противоположном направлении? Если текущий ход меньше или равен ходу предыдущему ходу в противоположном направлении, то черепашка наступила на клетку, где она уже была.
Здравствуйте, zero-gravity, Вы писали:
pkl>>Написать код, который бы возвращал ближайший номер шага (от начала программы), на котором черепашка проедется по собственному пути. То есть, по клетке, на которой она уже была. Стоимость алгоритма по процу — не более O(N), стоимость алгоритма по памяти — постоянная ( O(1) ).
ZG>Почему бы просто не сравнивать текущий ход с ходом, который был последним ровно в противоположном направлении? Если текущий ход меньше или равен ходу предыдущему ходу в противоположном направлении, то черепашка наступила на клетку, где она уже была.
Это необходимое условие. Но не достаточное. Черепашка на шахматной доске: A1-(8 клеток)->A8-->H8-(4 клетки)->H4 (ход меньше, но игра пока продолжается, хоть и не долго)
Здравствуйте, pkl, Вы писали:
pkl>Обсудите (-;
Ха, интересная задачка, у меня таких небыло, в принципе, наверное такие задачи для гейм девелоперов дают.
Есть еще данные, что бы проверить решение ?
Спасибо
насколько я понимаю, необходимо хранить прямоугольник, в который умещается вся траектория черепашки (bounding-box), и на каждом шаге проверять пересечение нового отрезка пути с этим прямоугольником, а если пересечения нет то раздвигать границы этого прямоугольника в случае необходимости.
Здравствуйте, ioj, Вы писали:
ioj>Здравствуйте, pkl, Вы писали:
pkl>>Обсудите (-;
ioj>насколько я понимаю, необходимо хранить прямоугольник, в который умещается вся траектория черепашки (bounding-box), и на каждом шаге проверять пересечение нового отрезка пути с этим прямоугольником, а если пересечения нет то раздвигать границы этого прямоугольника в случае необходимости.
Да Вы правы! На сколько я понял из постановки задачи они прямоугольники какие — то фигуры (неявно если внимательно присмотреться ) там уже есть, осталось банально найти первое пересечение, ну а тут есть разные подходы и теории , так как это на собеседовании то должно быть быстро и не гора кода, что тоже не маловажно.
ioj>>насколько я понимаю, необходимо хранить прямоугольник, в который умещается вся траектория черепашки (bounding-box), и на каждом шаге проверять пересечение нового отрезка пути с этим прямоугольником, а если пересечения нет то раздвигать границы этого прямоугольника в случае необходимости. TLL>Да Вы правы! На сколько я понял из постановки задачи они прямоугольники какие — то фигуры (неявно если внимательно присмотреться ) там уже есть, осталось банально найти первое пересечение, ну а тут есть разные подходы и теории , так как это на собеседовании то должно быть быстро и не гора кода, что тоже не маловажно.
только, заметим, что, как это очень часто бывает, незаметно теряется логарифм.
(Потому что размер прямоугольника потенциально неограничен, и нужен логарифмическое место для его хранения -- а не O(1) как изначально утверждалось).
