Этот конкурс был опубликован в рамках конкурса LotM в апреле 2018 года , а также ко второму дню рождения Brain-flak
Я думал о том, каким будет наиболее эффективный способ кодирования программ мозговых атак. Очевидная вещь, которую нужно сделать, поскольку существует только 8 допустимых символов, состоит в том, чтобы сопоставить каждый символ с 3-битной последовательностью. Это, конечно, очень эффективно, но все равно очень избыточно. В коде мозгового штурма есть некоторые особенности, которые мы могли бы использовать для сокращения кодировки.
Нилады, которые все представлены в 2 совпадающих скобках, действительно действуют как единая единица информации, а не как 2. Если бы мы заменили каждую скобку однобайтовым символом, это сделало бы кодировки намного меньше без потери каких-либо данных.
Этот менее очевиден, но завершающие байты монад также избыточны. Думаю, вы могли догадаться, что
'?'
символы представляют в следующем фрагменте?{(({}?<>?<>?
Если мы предположим, что введенный код является допустимым кодом «мозгового штурма», то для каждого из этих вопросительных знаков будет только один вариант. Это означает, что мы можем однозначно использовать символ закрывающей монады для представления каждой закрывающей скобки. Это дает дополнительное преимущество, заключающееся в сохранении небольшого набора символов, что очень помогло бы, если бы мы хотели использовать кодировку Хаффмана. Поскольку символ закрытой монады , скорее всего, будет наиболее распространенным символом с большим отрывом, он может быть представлен одним битом, что чрезвычайно эффективно.
Эти два трюка позволят нам сжать код мозгового штурма с помощью следующего алгоритма:
Замените все закрывающие скобки монады на
|
. Или, другими словами, замените каждую закрывающую скобку, которой не предшествует ее открывающее совпадение, с чертой. Так...(({})<(()()())>{})
станет
(({}|<(()()()||{}|
Замените каждую ниладу закрывающей скобкой. Поэтому в сопоставленных скобках, в которых нет ничего, используется следующее сопоставление:
() --> ) {} --> } [] --> ] <> --> >
Теперь наш последний пример становится:
((}|<()))||}|
Удалить висячие
|
символы. Поскольку мы знаем, что общее количество баров должно равняться общему количеству({[<
символов, если в конце отсутствуют бары, мы можем вывести их. Итак, пример как:({({})({}[()])})
станет
({(}|(}[)
Ваша задача на сегодня - переломить этот процесс.
Получив цепочку сжатых мозговых злаков, содержащих только символы (){}[]<>|
, разверните ее в исходный код мозговых злаков. Вы можете предположить, что входные данные всегда будут расширяться до действительных умственных способностей. Это означает, что ни один префикс ввода никогда не будет содержать больше, |
чем ({[<
символы.
Ввод не будет содержать завершающие |
символы. Они должны быть выведены из контекста.
Как обычно, вы можете отправить либо полную программу, либо функцию, а форматы ввода / вывода допустимы. А поскольку это код-гольф , ваш код будет оцениваться по длине исходного кода в байтах, чем меньше оценка, тем лучше.
Контрольные примеры
Вот несколько тестов. Если вам нужно больше, вы можете сгенерировать свои собственные тестовые сценарии с помощью этого сценария Python и Brain-Flak Wiki , откуда и происходит большинство этих тестовых примеров.
#Compressed code
#Original code
())))
(()()()())
([([}()||||(>||{(})|>|}{((<}|||>}|}>}
([([{}(())])](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}
({(}|(}[)|||}
({({})({}[()])}{})
(((()))||(](((}}||(}([(((}))||||(]((}}|}|}}|||]||]|[))||(}))|}(}|(}]]|}
((((()()()))([]((({}{}))({}([((({}()())))]([](({}{}){}){}{})))[]))[])[()()])({}()()){}({})({}[][]){}
источник
Ответы:
Brain-Flak ,
952 916818 байтЭкономия 360 байт путем вычисления противоположных скобок относительно, а не с нуля (например,
')'
='(' + 1
вместо(((5 * 2) * 2) * 2) + 1
)Сохранено 34 байта с некоторыми прямыми заменами от DJMcMayhem
Сохранено 10 байтов путем наложения
>]}
кода обработкиСохранено 118 байт за счет дедупликации рулонов
Экономия 40 байтов за счет использования пустого стека для упрощения первого броска
Сохранение 48 байтов путем пометки EOF -1, что позволяет более краткий код броска
Сохранено 36 байтов, используя логику равенства акций вместо моей
Экономия 98 байт благодаря Джо Кингу, который нашел более эффективный способ создания выходных данных.
Попробуйте онлайн!
Первый раз игра в гольф в Brain-Flak, так что, возможно, есть некоторые действительно большие улучшения, но это работает. Много копий / вставок для обработки каждого типа скобок, и большое благодаря автоматическому целочисленному генератору и фрагменту Roll отсюда .
Объяснение здесь , TIO форматирует его легче
Бонусный ответ:
Сжатый Brain-Flak 583 байта
Попробуйте онлайн!
(Обратите внимание, что приведенная выше ссылка не работает, потому что TIO не имеет интерпретатора Compressed Brain-Flak. Вы можете найти транспортер для Brain-Flak здесь )
Я проверил, что это действительно так, перенеся его в Brain-Flak с помощью этого инструмента, который теперь достаточно эффективен, поэтому время ожидания маловероятно.
источник
<>(<()>)
на(<>)
. Кроме того, вы можете изменить(<>{}<>)(<()>)
на(<(<>{}<>)>)
Сетчатка 0.8.2 ,
10398 байтПопробуйте онлайн! Ссылка включает в себя тестовые случаи. Редактировать: 5 байт по вдохновению от @MartinEnder. Объяснение:
Поставьте
;
после каждой закрывающей скобки и замените их на открытые скобки, а также измените|
s на;
s.Подсчитайте количество непревзойденных открытых скобок и добавьте столько
;
s.Скопируйте каждую открывающую скобку в соответствие
;
.Переверните скопированные скобки и удалите
;
s.источник
|
что-то вроде!
. Это не будет даже стоить байт , если перевести>-}
на<-{
(который я думаю , что даетz
для|
).z
но я все равно придумал способ сэкономить еще несколько байтов.TIS ,
670666 байт-4 байта для прыжка вперед, чтобы вернуться назад
Код:
Планировка:
Попробуйте онлайн!
Я сомневаюсь, что это самое маленькое, но я не вижу способа сделать его меньше. К сожалению, все
NOP
s кажутся необходимыми для синхронизации, и я не могу поместить стек там, где@14
сейчас находится из-за чтения изANY
in@11
.Структура этого решения следующая:
Увидев открытую фигурную скобку, открытое отправляется по левому столбцу для вывода, а закрытое отправляется по правому столбцу в стек.
Увидев закрывающую фигурную скобку, оба открытия и закрытия отправляются по левому столбцу для вывода.
После просмотра канала стек извлекается и отправляется на вывод.
После EOF
@1
начнется чтение из@2
, а не из входного потока из@0
.@2
производит бесконечный поток труб, поэтому стек будет осушен.Как только вход и стек исчерпаны, программа останавливается.
Предупреждение: из-за ограничений TIS размер стека ограничен 15. Если что-то вложено глубже, эта реализация приведет к неверному результату.
источник
JavaScript (ES6), 107 байт
Принимает ввод как массив символов. Возвращает строку.
Попробуйте онлайн!
источник
Haskell,
127121 байтПопробуйте онлайн!
Отредактируйте: -6 байт, используя функцию @ Laikoni, чтобы найти подходящую скобку .
источник
Рубин , 104 байта
Это полная программа, которая выводит на консоль.
(i<5?a:$>)<<r[-i]
должен быть одним из самых крутых гольфов, которые я когда-либо делал.Попробуйте онлайн!
Рубин , 106 байт
Это мое первое решение. Анонимная лямбда-функция, которая принимает и возвращает строки.
Попробуйте онлайн!
источник
Brain-Flak ,
606 548 496 418 394390 байтПопробуйте онлайн!
Я начал это с игры в гольф с ответом Камиля Дракари , но это отошло от меня до такой степени, что я решил опубликовать его как отдельный ответ.
Объяснение:
И конечно ...
Сжатый Brain-Flak, 285 байт:
источник
Java 10, 424 байта
Это довольно долго, но я не мог понять, как сократить его дальше. Это хороший вызов, хотя.
Попробуйте это онлайн здесь .
Безголовая версия:
источник
Python 2,
188184180177174173 байтаСохранено 4 байта благодаря DJMcMayhem.
Попробуйте онлайн!
источник
s
пустым. В противном случае вы получите дополнительные символы в неправильном конце.Python 3 , 122 байта
Попробуйте онлайн!
источник
Haskell , 152 байта
Попробуйте онлайн! или проверьте все контрольные примеры .
p
реализует рекурсивный синтаксический анализатор, который может оказаться слишком сложным для простой грамматики.источник
m
чтобы найти подходящую скобку.Python 2 , 244 байта
Попробуйте онлайн!
Потребовалось больше часа или двух, чтобы это заработало ...
источник