Представьте себе путь, состоящий из <и >и заканчивая в @, например ,
><>@
Ходок начинается в самой левой камере. Он пройдёт путь следующим образом:
- Если ходок находится в
@камере, он достиг цели и готово. - Если бродяга находится в
>камере, весь путь циклически сдвигается на один шаг вправо , унося бродягу с собой . - Если ходок находится в
<камере, весь путь циклически сдвигается на один шаг влево , унося ходока с собой . - После этого ходок делает один шаг. Если он находится на любом конце пути, он отходит от конца. В противном случае он продолжает двигаться в том направлении, в котором он двигался на последнем шаге (не обращая внимания на вращение), первоначально идя прямо.
Давайте поработаем над приведенным выше примером. Положение ходока обозначено ^:
><>@ --rotate--> @><>
^ ^
step right (first step):
@><> --rotate--> ><>@
^ ^
step right:
><>@ --rotate--> @><>
^ ^
step left (dead end):
@><> --rotate--> ><>@
^ ^
step left:
><>@ --rotate--> @><>
^ ^
step left:
@><> Goal reached!
^
Ходящий посетил 6 ячеек в процессе (включая начальную ячейку, а также @и подсчитывал каждую ячейку так часто, как она посещалась).
Вот небольшой пример, где ходок перемещается по краям с помощью вращения:
>>@ --rotate--> @>>
^ ^
step right (first step):
@>> --rotate--> >@>
^ ^
step right (dead end):
>@> Goal reached!
^
На этот раз ходок посетил 3 камеры.
Мы можем легко превратить это в целочисленную последовательность:
- Вам дано положительное целое число N , например
9. - Вы вычисляете двоичное представление этого целого числа, например
1001. - Затем включите
1в>и0в ,<и добавить@:><<>@. - Мы связываем с N количество ячеек, посещаемых ходоком, в числе, построенном таким образом.
Первые несколько элементов полученной последовательности:
2, 3, 3, 4, 6, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6,
6, 10, 6, 10, 8, 8, 6, 10, 8, 8, 6, 6, 6, 6, 7, 7
Это может показаться совершенно произвольным, но результирующая последовательность на самом деле имеет большую структуру:
Для справки, вы можете найти первые 2048 номеров последовательности в этой папке .
Соревнование
Вы догадались: вы должны вычислить вышеуказанную последовательность. Вы можете сделать это одним из трех способов:
- Вы можете создать бесконечную последовательность (пока позволяет память) либо путем непрерывного вывода (разделенных нечисловыми символами) значений, либо с помощью некоторой формы бесконечного генератора в языках, которые их поддерживают. Если вы печатаете бесконечный поток в STDOUT, вам не нужно печатать числа по одному, но убедитесь, что каждое число будет напечатано через конечное время (и по порядку). Если вы используете эту опцию, вы не должны принимать никаких данных.
- Вы можете взять целое число N в качестве входных данных и получить N- й член последовательности.
- Вы можете взять целое число N в качестве входного и производят все до в N - й член последовательности, либо в виде списка или строку , используя однозначный разделитель.
Поскольку я не хочу наказывать языки, которые не могут легко конвертировать между базами, вместо целого числа N вы можете вместо этого взять двоичное представление N , используя 0s и 1s как обычно (в виде списка или строки), с наибольшим -существенный бит первый.
Вы можете написать программу или функцию, принимая ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и выводя результат через STDOUT (или ближайшую альтернативу), возвращаемое значение функции или параметр функции (out).
Применяются стандартные правила игры в гольф .
Фон
На самом деле это вычисляет количество «тиков» прямого интерпретатора моего эзотерического языка программирования, который Лабиринт должен интерпретировать как «путь» как исходный код. В этом случае «ходок» - это просто указатель команд (который имеет позицию и направление), @команда завершает программу <и >является командами изменения исходного кода.
Ответы:
Желе , 10 байт
Эта функция принимает одно целое число в виде списка ее двоичных цифр в качестве входных данных.
Алгоритм эквивалентен одному из ответов @ Agawa001 .
Попробуйте онлайн! или сгенерируйте первые 2048 номеров .
Фон
Перечислите позиции под траекторией от 0 до L , получая в общей сложности L + 1 позиций. L совпадает с количеством двоичных цифр числа N, которое кодирует путь. В этих обозначениях ходунок начинается в положении 0 , цели в положении L .
С каждым шагом, который делает ходок, он приближается на один шаг к цели (в направлении, в котором он сейчас идет). Кроме того, с каждым шагом сдвига, в зависимости от того, идет ли он с направлением сдвига или против него, он либо увеличивает, либо уменьшает свою позицию на 2 по модулю L + 1 , или он остается в текущей позиции.
Чтобы изменить направление, он должен приземлиться в положении L - 1 (лицом к L ) или в положение 1 (лицом к 0 ), а затем сместиться в своем направлении. Следующий шаг, который он сделает, вернет его на прежнюю позицию в противоположном направлении.
Если L четно, L-1 нечетно, поэтому он не может перейти из своей начальной позиции в L-1 напрямую. Единственный способ добраться до него - пройти через L , перенести на 0 и сделать следующий шаг, чтобы приземлиться на 1 , а затем продвинуться вправо. Это требует продвижения 2L позиций, что можно сделать не менее чем за L шагов.
Однако после того, как предпримет L шагов без изменения направления, он достигнет цели. Добавляя одну для начальной ячейки, мы получаем L + 1 посещенных ячеек в этом случае.
Если L нечетно, L-1 четно, поэтому он может достичь этой позиции, сдвинув (L-1) / 2 раза вправо. Если в это время положение L - 1 находится ниже 1 , он переместится в положение L , развернется и встанет в положение L - 1 (влево).
Это может произойти или не произойти, прежде чем он достигнет своей цели, поэтому есть два случая для анализа:
Если в двоичном расширении N меньше (L + 1) / 2 вхождений, 1 , L шагов будет недостаточно для направления поворота. Поскольку эти L- этапы приводят ходока к его цели, добавляя один для начальной ячейки, в этом случае мы получаем L + 1 посещенных ячеек.
Если в двоичном расширении N имеется по крайней мере (L + 1) / 2 вхождения 1 , для перехода к ((L + 1) / 2) -ому вхождению потребуются I шаги, где I - начальная позиция этого вхождения из 1 .
Таким образом, после шагов I ходок находится в положении L - 1 , обращенном влево. Чтобы снова повернуть направление, ему придется идти вперед влево до положения 1 . Однако, как и в четном случае, поскольку (L - 1) - 1 нечетно, для этого потребуется пройти 0 и предпринять не менее L шагов.
Поскольку начальное расстояние до цели в левом направлении равно 1 , после того, как я предпринял I шаги, ходок оказывается на расстоянии I + 1 от цели после смены направления. Поскольку I <L , у нас есть I + 1 ≤ L , поэтому следующие шаги I + 1 приведут его к цели.
Это дает в общей сложности I + I + 1 = 2I + 1 принятых шагов. Добавляя одну для начальной ячейки, мы получаем в общей сложности 2I + 1 + 1 = 2 (I + 1) посещенных ячеек.
Как это устроено
источник
Matlab (оценка = 230, n = inf)
infесли хотите сохранить бесконечность).h=1000000000000000000000000000000000000000000000000000;w(h,h+1)чтобы убедиться.Алгоритм следует математическому подходу, который я объясню позже, и он подтверждает список ссылок Мартина, основываясь на этой программе:
Поскольку алгоритм проверяет 2048 первых тестовых случаев, я буду слепо предполагать, что это будет для любого тестового случая, поэтому мой алгоритм работает в отношении нескольких свойств, которые я обнаружил в этом процессе, без необходимости сдвигать и перемещать указатель:
1 - если удвоенное число единиц в двоичном переводе не превышает длину последовательности,
Lпоэтому выводL+12 - если длина последовательности четная, а предыдущее условие не установлено, поэтому вывод такой же
L+13- в противном случае выходной сигнал в два раза больше
L/2индекса 1.источник
a=dec2bin(input(''));c=find(a=='1');g=nnz(a)+1;if nnz(c)<g/2|mod(g,2);g,else,2*c(g/2),end, что дает только один элемент последовательности.Python,
122119113110108107103 байтаПринимает ввод как список двоичных цифр. Вспомогательная функция для проверки:
Кредит Линн за сохранение 7 байтов.
источник
p-d-1in[-2,w]сохраняет один байт.d*=2*(1!=d-p>~w)-1спасает еще четыре! ° v °Python 2, 99 байт
Порт Python от Agawa001 блестящий ответ.
Читаемая версия:
источник
MATL,
31, 25 байтЭто всего лишь MATL-версия алгоритма Agawa001, за исключением того, что он принимает целочисленный вход N и возвращает N-й член в последовательности. Было сложно идти в ногу со всеми элементами в стеке! Мне пришлось прибегнуть к использованию буфера обмена, чтобы не сойти с ума. Вы можете попробовать это онлайн!
Может быть превращен в цикл печати первых N терминов путем добавления
:"@до кода и]Dпосле.Спасибо Луису Мендо за сохранение 6 целых байтов!
источник
Юлия 0,4, 4̷4̷ 42 байта
Эта функция принимает одно целое число в виде списка ее двоичных цифр в качестве входных данных.
Алгоритм эквивалентен одному из ответа @ Agawa001 и моего ответа Jelly .
Попробуйте онлайн!
Как это устроено
find(x)возвращает основанные на 1 индексы всех ненулевых элементов x . Мы пытаемся получить доступ к результирующему массиву по индексу k / 2 и, в случае успеха, перезаписать k двойным выбранным индексом.Это не удастся, если и только если выполняется одно из следующих условий:
k / 2 - нецелое число с плавающей точкой, поэтому InexactError вызывается.
Массив индекса содержит менее k / 2 элементов, поэтому возникает ошибка BoundsError .
В любом случае перезапись k не удастся, поэтому будет возвращено ее первоначальное значение.
источник
JavaScript (ES6), 65 байт
Принимает двоичную строку. Использует проверку отказов от различных других ответов.
источник
Python 2, 74 байта
Эта функция принимает одно целое число в виде списка ее двоичных цифр в качестве входных данных.
Алгоритм эквивалентен одному из ответа @ Agawa001 и моего ответа Jelly .
Проверьте это на Ideone .
Как это устроено
nextпытается найти первое целое число 2i, для которогоk==2*sum(x[:i])возвращается значение true. Посколькуx[:i]содержит i элементов, это дает основанный на 1 индекс (k / 2) -го 1 .nextпотерпит неудачу, если k / 2 нецелое или если x содержит меньше k / 2 единиц. В этом случае возвращается значение по умолчанию k .источник
> <> , 63 байта
С того момента, как я увидел пример шаблона в этом задании, я знал, какой язык использовать :)
Используя N, чтобы получить N- й член.
Предполагается, что ввод в двоичном виде в стеке. Вместо того, чтобы перемещать ходунки, это решение основано главным образом на перемещении ленты под ходунки.
Попробуйте онлайн!
источник