Этот вопрос является первым из нескольких заданий на День Рождения Brain-flak, предназначенных для празднования первого Дня Рождения Brain-Flak! Вы можете найти больше информации о Дне Рождения Brain-Flak здесь
Прошлым летом у нас был целочисленный метагольф Brain-flak , и с тех пор полученные им ответы были очень полезны для сообщества Brain-Flak. Главное, что делает Integer Metagolf настолько эффективным, - это метод, называемый жестким кодированием.
В Brain-Flak время выполнения очень дорого. Самый короткий известный фрагмент умножения:
({}<>)({<({}[()])><>({})<>}{}<><{}>)
Обнаружен Мегатом
Однако есть очень простой способ создать умножение времени компиляции. Например, следующий код умножится на 5:
(({})({})({})({}){})
Это работает, потому что последовательные выражения добавляются вместе. Каждый ({})
ничего не делает со стеком ( {}
выталкивает и (..)
толкает его обратно) и оценивает все, что находится на вершине стека. Все эти выражения вместе суммируют до пяти раз больше, чем было на вершине стека.
Для любого n
следующего строкового выражения создаст фрагмент, который будет умножать вершину стека на n
:
"("+"({})"*(n-1)+"{})"
Это работает путем создания n
выражений, которые все оценивают до вершины стека. Первый на n-1
самом деле ничего не меняет, а последний удаляет вершину стека до нажатия.
Для составных чисел вы можете объединить несколько меньших выражений вместе, чтобы сохранить байты. Например, вы можете умножить на 25, умножив на 5 дважды:
(({})({})({})({}){})(({})({})({})({}){})
Это довольно просто, и для некоторых чисел это работает довольно хорошо, однако есть лучшие способы сделать это. Например, один метод, который я придумал, использует двоичное представление числа. ( Вот реализация Python ) Этот новый метод намного эффективнее, чем простое строковое выражение, показанное ранее, но это еще не конец, есть много интересных способов умножения с жестким кодом и, вероятно, тонна, которую еще никто не обнаружил.
Поэтому я думаю, что пришло время посмотреть, как хорошо мы можем получить.
Краткий обзор Brain-Flak
Вот описание всего, что вам нужно знать о Brain-Flak для этой задачи.
Brain-Flak имеет «нилады» и «монады». Нилады - это круглые скобки, в которых ничего нет. Каждый нилад делает что-то и возвращает значение. Для этого вызова нам нужны две нилады: {}
и <>
. {}
выскакивает вершина активного стека и возвращает его значение. <>
переключает активный стек и активный в стек, так что активный стек становится неактивным, а неактивный стек становится активным, он возвращает ноль.
Монады - это круглые скобки с содержимым внутри. Они принимают один аргумент, сумму всего внутри них, иногда выполняют действие, а затем возвращают значение. Три из них мы имеем дело с являются (...)
, <...>
и [...]
. Самая важная монада для этой задачи (...)
берет значение изнутри и выталкивает его в активный стек. Затем он возвращает аргумент. <...>
и [...]
обе являются "инертными" монадами, то есть они не выполняют никаких действий, а скорее изменяют значение, которое им передают. <...>
всегда возвращает ноль независимо от переданного аргумента. Между тем [...]
всегда возвращает время аргумента -1
.
Примеры программ с пояснениями
Если вы никогда не программировали в Brain-Flak, было бы неплохо взглянуть на некоторые примеры программ, используя описанные операции.
({}{})
Это добавляет две верхние цифры в стеке. Каждый {}
выталкивает значение из стека и (...)
возвращает свою сумму обратно.
({}[{}])
Точно так же это вычитает второй элемент в стеке из первого. Как и перед каждым {}
всплывающим значением, но [..]
после второго оно добавляется. Еще раз (...)
толкает сумму.
({}<{}>)
Это удаляет второе значение в стеке, сохраняя верхнее значение без изменений. Он работает так же, как последние два, за исключением того, что второе значение заглушается, <...>
так что push только отталкивает первое значение назад.
(({}))
Это делает вторую копию значения на вершине стека. Он делает это, выталкивая вершину стека с {}
получением его значения, первый (..)
затем возвращает его обратно, оценивая его значение. Второй (...)
получает значение, возвращаемое первым, и также помещает его в стек. создание второй копии.
задача
Получив целое число, n
создайте чистый фрагмент стека Brain-Flak, который умножает вершину текущего стека на n
.
Вам разрешено использовать следующие операции Brain-Flak
(...) -> Push Monad, Pushes the result of its contents
<...> -> Zero Monad, Returns zero
[...] -> Negative Monad, Returns the opposite of its contents result
{} -> Pop nilad, Pops the TOS and returns its value
<> -> Switch nilad, Switches the active and inactive stack
Другие операции запрещены с целью вызова.
счет
Ваша оценка будет кумулятивной длины всех программ от n=2
до n=10000
. Обязательно включите ссылку на вывод вашей программы для проверки.
источник
[...]
, так что это начало.Ответы:
Руби, 669856
Это быстрый базовый ответ. Первые 1000 мин-программ найдены здесь . (Я попытался опубликовать все из них, но это перегрузило максимальный размер пастбина.) Я могу добавить объяснение кода позже.
Примеры:
источник