Golunar / Одинарный способ кодирования всех действительных Brainfuck программ, но это не перечисление, так как большинство натуральных чисел не соответствуют действительной программе.
Для этой задачи предположим, что лента бесконечно вдвойне бесконечна и без комментариев, т. Е. Программа Brainfuck действительна тогда и только тогда, когда она состоит только из символов <>+-.,[]
и все левые и правые скобки совпадают.
Например, пустая программа ,[+][-].
,[>+<[--].]
и +[+[+][+[+]+]+]+.
является действительной программой Brainfuck, в то время как ][
, и a[]
нет.
задача
Напишите программу или функцию, которая принимает действительную программу Brainfuck в качестве входных данных и возвращает натуральное число ( 1 , 2 , 3 ,…) со следующими ограничениями:
Сгенерированный вывод должен быть разным для всех действительных программ Brainfuck.
Для каждого натурального числа n должна существовать действительная программа Brainfuck, которая, если она предоставляется в качестве входных данных, генерирует выходные данные n .
Дополнительные правила
Если программа Brainfuck имеет длину 100 или менее байтов, ваша программа или функция должны завершиться в течение одной минуты.
Это означает, что вы не можете перебирать все действительные программы Brainfuck до тех пор, пока не сопоставите ввод.
Применяются стандартные правила игры в гольф .
Ответы:
Python 3,
443158155154134131128124117116115 байтовНесколько байтов благодаря Sp3000 и Митчу Шварцу: D
Как это работает:
Это отображает все действительные программы BF на все возможные, действительные или недействительные программы BF, которые не начинаются с
[
, в соотношении один к одному. После этого новая программа просто преобразуется в восьмеричное.Вот формула сопоставления:
[
символов. Третья часть - самый большой постфикс, состоящий только из]
символов. Вторая часть - это середина.]
скобки в третьей части, которые совпадают со[
скобками во второй части. Они также могут быть пересчитаны позже.Если вы не понимаете это объяснение, вы можете найти расширенное объяснение в чате, начиная здесь .
Для справки, вот первые 20 программ:
Вот первые 1000 программ: http://pastebin.com/qykBWhmD
Вот программа, которую я использовал для их создания: http://ideone.com/e8oTVl
Вот
Hello, World!
:источник
Python 2, 157 байт
По-прежнему выглядит неплохо для игры в гольф, но я публикую это сейчас. Он использует рекурсию с небольшим кэшированием. Досадно,
D.get
что для кеширования не происходит короткое замыкание, поэтому я не могу сохранить 9 байтов таким образом ...Сопоставление сначала определяет длину, затем лексикографический порядок над порядком
"][><.-,+"
(см. Примеры вывода ниже). Основная идея - сравнить префиксы.Переменная
o
отслеживает количество[
открытых скобок для текущего префикса, в то время как переменнаяd
принимает одно из трех значений, указывающих:d = 1
: Текущий префикс лексикографически раньше, чемs
. Добавьте все программы с этим префиксом и длиной<= s
,d = -1
: Текущий префикс лексикографически позже, чемs
. Добавьте все программы с этим префиксом и длиной< s
.d = 0
: Текущий префикс является префиксомs
, поэтому мы можем изменить егоd
на 1 или -1 позже.Например, если у нас есть
s = "[-]"
и наш текущий префиксp = "+"
, так какp
это позже, чемs
лексикографически, мы знаем только добавить программы, начиная сp
которых строго короче, чемs
.Чтобы дать более подробный пример, предположим, что у нас есть программа ввода
s = "-[]"
. Первое рекурсивное расширение делает это:Обратите внимание , как мы на самом деле не использовать префиксы в рекурсии - все , что мы заботимся о них захватывается через переменные
d
,o
и сокращение ввода программыs
. Вы заметите много повторений выше - именно здесь происходит кэширование, позволяющее нам обрабатывать программы из 100 символов в срок.Когда
s
пусто, мы смотрим(d>=0 and o==0)
, который решает, возвращать ли 1 (считать эту программу, потому что она лексикографически ранняя / равная и программа действительна), или 0 (не считать эту программу).Любая ситуация с
o < 0
немедленным возвратом0
, так как любые программы с этим префиксом имеют больше]
s, чем[
и, следовательно, являются недействительнымиПервые 20 выходов:
Используя тот же пример Hello World, что и ответ @ TheNumberOne:
источник
Python 2, 505 (не в гольф)
Мне нравилось разрабатывать этот подход, но я могу не беспокоить его, потому что он не конкурентоспособен по сравнению с другими подходами. Я публикую это для разнообразия и возможного эстетического интереса. Это включает в себя рекурсию и немного математики.
Функция
f(n)
подсчитывает количество действительных программ длины мозгаn
.h(x)
карты программа длиныn
до[0..f(n)-1]
, иg(x)
это биективная функция ранжирования в вопросе.Основная идея заключается в том, что непустая программа может запускаться
[
либо с одним из 6 не[]
символов. В первом случае мы можем перебирать возможные местоположения сопоставления]
и повторяться на закрытой части и на хвосте (где хвост означает подстроку, следующую за]
). В последнем случае мы можем выполнить рекурс на хвосте (где хвост означает выпадение первого символа). Это рассуждение можно использовать как для подсчета, так и для вычисления ранга.Более короткие программы всегда будут иметь более низкий рейтинг, чем более длинные программы, и шаблон скобок является второстепенным определяющим фактором. Не-
[]
символы сортируются в соответствии с "+ - <>,". (что произвольно).Например, у
n=4
нас есть эти случаи:где
z
обозначает не[]
символьный иx
обозначает любой символ, при условии, что]
он должен совпадать с начальным[
. Программы ранжируются в соответствии с этим порядком и рекурсивно поx
подразделам, причем левый раздел имеет приоритет над правым разделом в последних случаях. Расчет ранга аналогичен системам счисления со смешанным основанием иf
важен для вычисления текущего «основа».источник
Этот ответ является формальным доказательством ответа TheNumberOne , перечисления действительных программ Brainf ** k , где может быть немного трудно понять тонкости, почему перечисление является правильным. Нетрудно понять, почему не существует какой-либо недопустимой программы, которая отображается на число, которое не включено в допустимую программу.
В этом ответе заглавные буквы используются для обозначения программ, а строчные переменные используются для функций и целых чисел. ~ является оператором конкатенации.
Предложение 1:
Пусть функция f будет программой, описанной в этом ответе. Тогда для каждой программы U существует действительная программа V такая, что f (U) = f (V)
Определение 1:
Пусть g (X) будет номером того,
[
что появляется в программе X, и пусть h (X) будет номером того,]
что появляется.Определение 2:
Определите P (x), чтобы быть этой функцией:
Определение 3:
Для программы X обозначим X1 как самый большой префикс
[
символов, X2 - его центр, а X3 - самый большой суффикс]
символов.Доказательство предложения 1:
Если g (U) = h (U), то U - правильная программа, и мы можем взять V = U. (тривиальный случай).
Если g (U) <h (U), то мы можем создать V, добавив n = h (U) - g (U)
[
символов. Очевидно, что f (V) = f (U), поскольку все[
символы в префиксе удалены.Теперь рассмотрим g (U)> h (U). Определить T = U2 ~ U3. если g (T) <= h (T), то мы можем построить V, удалив n = g (U) - h (U)
[
символов.Таким образом, мы можем предположить, что h (T) <g (T). Построим V = T ~ P (g (T) - h (T)).
Нам нужно три небольших факта, чтобы продолжить:
Утверждение 1: g (U2) = g (T)
U3
[
по своему определению не содержит символов. Поскольку T = U2 ~ U3, все его[
символы находятся в первой части.Утверждение 2: h (U3) <g (T)
Это следует из того, что h (T) <g (T) и h (U3) <h (U3 ~ U2) = h (T).
Утверждение 3: h (V3) = g (U2) - h (U2)
Теперь покажем, что f (V) = f (U).
Это завершает доказательство. QED
Давайте сделаем уникальность также.
Предложение 2:
Пусть U, V две разные, действительные программы. Тогда f (U)! = F (V)
Это довольно просто по сравнению с предыдущим предложением.
Предположим, что U2 = V2. Но тогда единственный способ, которым U и V могут различаться, - это добавление или удаление n
[
и]
символов к U1 и U3 соответственно. Тем не менее, это изменяет вывод f, так как f будет подсчитывать количество непревзойденных]
символов в суффиксе.Таким образом, U2! = V2.
Очевидно, это приводит к противоречию. Поскольку U2 и V2 буквально содержатся в выходных данных f (U) и f (V) соответственно, они не могут отличаться, кроме как на «краю», месте, где U2 соединяется с U3. Но первый и последний символы U2 и V2 не могут быть
[
или]
по определению, в то время как это единственные символы, разрешенные в U1, U3, V1, V3 соответственно и соответственно снова. Таким образом, мы получаем U2 = V2. QEDисточник