Генерация Brainf *** NOPs

26

Иногда при написании кода для мозгового отвращения вы чувствуете необходимость сделать его длиннее, чем необходимо, чтобы стимулировать отладку. Вы могли бы сделать это, просто положив ><туда, но что это весело? Вам нужно что-то более длинное и меньшее NOPey, чтобы сбить с толку любого, кто читает ваш код.

Краткое введение в Brainfuck

Brainfuck - это эзотерический язык программирования, созданный в 1993 году Урбаном Мюллером и отличающийся чрезвычайным минимализмом. (Википедия)

Brainfuck является язык , основанный на восьми команд: +-><,.[]. Код запускается на чем-то похожем на машину Тьюринга: бесконечную ленту, на которой можно изменять значения. В этом задании мы сосредоточимся на первых четырех:

+    increment the value at the pointer
-    decrement the value at the pointer
>    move the pointer right
<    move the pointer left

Brainfuck NOPs

Мозговой NOP - это последовательность персонажей, которые при исполнении из любого состояния не приводят к изменению состояния. Они состоят из четырех символов, упомянутых выше.

Соревнование

Задача состоит в том, чтобы написать программу или функцию, которая при исполнении генерирует случайный NOP для мозгового отрыва заданной длины.

вход

В качестве входных данных вы получите неотрицательное четное число n. (НОПы для странного невозможны n.)

Выход

Вы выведете случайный NOP мозгового траха длины n.

правила

  • Определение NOP: когда выходные данные программы вставляются в любую точку программы «мозгового штурма», поведение указанной программы не должно меняться каким-либо образом. Другими словами, он не должен изменять состояние переводчика.
    • Обратите внимание, что, например, +>-<это неверно, так как он изменяет значения двух ячеек, не возвращая их обратно. Пожалуйста, проверьте ваше решение для них перед публикацией.
    • Также обратите внимание, что +>-<->+<это NOP, который нельзя уменьшить до нуля, просто удалив >< <> +- -+. Таким образом, вы не можете использовать алгоритм, который просто вставляет их друг в друга.
  • Каждый действительный NOP длины nдолжен иметь ненулевой шанс появления в выходных данных. Распределение не обязательно должно быть равномерным.
  • У рассматриваемого интерпретатора мозгового удара есть вдвойне бесконечная лента произвольных прецизионных ячеек. То есть вы можете бесконечно идти в обоих направлениях и увеличивать / уменьшать каждую ячейку до бесконечности.
  • Программа должна завершиться в течение 1 минуты для n= 100 на моем компьютере, поэтому не нужно создавать все возможные NOP и выбирать один.
  • Если задан неверный ввод (нецелое, отрицательное, нечетное и т. Д.), Вы можете делать все, что захотите, включая сбой.

счет

Это , поэтому выигрывает самый короткий ответ в байтах.

Примеры

Вот все допустимые результаты для n= 4:

++--    +-+-    +--+    --++    -+-+    -++-
>><<    ><><    ><<>    <<>>    <><>    <>><
><+-    ><-+    <>+-    <>-+
>+-<    >-+<    <+->    <-+>
+><-    -><+    +<>-    -<>+
+-><    -+><    +-<>    -+<>

Вот несколько возможных выходных данных для n= 20:

+>>->+<->-<<<->>++<<
>+>-<+<->+-<>->+<-<+
+--+-++--++-+--+-++-
>>>>>>>>>+-<<<<<<<<<
PurkkaKoodari
источник
18
Вот NOP, который не использует, +-<>как вы просили:a
подземный
1
Я не думаю, что существуют непростые NOP, поэтому вы можете удалить эту квалификацию. .имеет побочный эффект, ,перезаписывает значение, которое не может быть восстановлено без использования []. Но в []итоге установим значение на ноль. Это также перезаписывает значение (поэтому нам понадобится другое []для его восстановления), если только мы не можем быть уверены, что затронутая ячейка была нулевой для начала. Однако нам пришлось бы искать такую ​​камеру с чем-то вроде этого [>], и невозможно надежно вернуться к той позиции, с которой мы пришли.
Мартин Эндер
4
@Eumel "У рассматриваемого интерпретатора мозгового удара есть вдвойне бесконечная лента произвольных прецизионных ячеек".
Мартин Эндер
2
Обратите внимание, что «Brainfuck» больше не допускается в заголовках вопросов на системном уровне. Похоже, вы смогли обойти ограничение, используя не-ASCII символы. В будущем, пожалуйста, соблюдайте это ограничение.
Алекс А.
2
@undergroundmonorail Ну, это Тьюринг завершен ... так что технически можно написать PRNG на нем, как и на любом другом языке. (Хотя посев может быть трудным.)
PurkkaKoodari

Ответы:

13

CJam, 62 59 байт

Спасибо nhahtdh за сохранение 3 байта.

Поскольку нет никакого требования к какому-либо конкретному распределению, если каждый неоператор появляется с конечной вероятностью, мы можем упростить это много, просто генерируя строку, содержащую сбалансированное число -+и <>, соответственно, проверяя, является ли она NOP, и сортируя ее, если она нет.

Конечно, для более длинных входных данных это почти всегда приводит к сортировке выходных данных, но вы можете проверить код с некоторыми входными 8данными, например, чтобы убедиться, что он в принципе может генерировать любой NOP заданной длины.

ri_0a*\2/{;"-+<>":L2/mR}%smr:SL["Xa.Xm"3/2e*L]z:sers~0-S$S?

Попробуйте онлайн.

Мартин Эндер
источник
1
Да ... произвольный предел должен был быть n = 1000 за 10 секунд. Компьютеры - просто способ быстро сегодня ^^ Потому что алгоритмический ответ решает его за секунду даже для n = 1000
Falco
Для еще большего n, я думаю, можно просто отсортировать вывод, если сбалансированная строка не NOP. Распределение ужасно искажено, но это допускается вопросом.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ это хорошая идея.
Мартин Эндер
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Спасибо, это также экономит три байта.
Мартин Эндер
16

CJam, 118 116 байтов

Это немного вышло из-под контроля ... особенно вторая половина кажется, что это должно быть очень пригодным для игры в гольф.

ri2/_)mr:R-"<>"R*mr_'=fm0\{1$+}%+__&e`]:\{mr1aa..+}*\@](\z:~\{~\("+-"*mr1$3$e=[{_,)mr_2$<@@>}*+]@@f{`1$`={(}@?\}W<}/

Проверьте это здесь.

Это обрабатывает N = 100почти мгновенно. У меня нет времени, чтобы написать полную разбивку кода сейчас, поэтому вот алгоритм:

  • Создание случайной сбалансированной строки <и >со случайной (даже) между длиной 0и Nвключительно.
  • Перемешайте положения головки ленты в этот массив. Например "<>><"становится [0 '< -1 '> 0 '> 1 '< 0].
  • Получить список всех позиций, достигнутых в процессе.
  • Для каждой такой позиции инициализируйте пустую строку. Также определите, сколько пар символов осталось, чтобы достичь строки длины N.
  • Для каждой оставшейся пары добавьте +-строку случайной позиции.
  • Перемешайте все эти строки.
  • Для каждой позиции определите, как часто эта позиция встречается в рифленом массиве, и разбейте соответствующую строку на такое количество фрагментов (произвольной длины).
  • В рифленом массиве замените вхождения позиции случайными кусками.

Выполнено. Это основано на наблюдении, что:

  • Любой NOP должен иметь одинаковое количество <и >возвращать головку ленты в исходное положение.
  • Код будет NOP, если каждая ячейка ленты увеличивается так же часто, как уменьшается.

Распределяя случайные, но сбалансированные количества +s и -s между всеми местами, где головка ленты находится в данной ячейке, мы гарантируем, что мы найдем все возможные NOP.

Мартин Эндер
источник
4

Mathematica, 350 байт

Quiet@(For[a="+",If[{##4}=={},#3!=0||Union@#!={0},Switch[#4,"+",#0[ReplacePart[#,#2->#[[#2]]+1],#2,#3,##5],"-",#0[ReplacePart[#,#2->#[[#2]]-1],#2,#3,##5],">",#0[#~Append~0,#2+1,#3+1,##5],"<",If[#2<2,#0[#~Prepend~0,1,#3-1,##5],#0[#,#2-1,#3-1,##5]]]]&@@{{0},1,0}~Join~Characters@a,a=""<>RandomSample@Flatten@RandomChoice[{{"+","-"},{">","<"}},#/2]];a)&

Слишком долго? Да. Меня это вообще волнует? Нет, пока кто-то еще не отправит правильный ответ.

LegionMammal978
источник
4
Не могли бы вы добавить объяснение, чтобы люди могли убедить себя, что это действительно так? :)
Мартин Эндер
Как именно делает эту работу? Если я вызываю функцию с номером, она только возвращается +.
Мартин Эндер
@ MartinBüttner Фиксированный ... В настоящее время, он просто генерирует случайные программы с одинаковым числом +- -и <- >пар , пока не случится быть NOP. Половина из них берется простым BF-интерпретатором.
LegionMammal978
действительно ли это генерирует действительный запрет на операцию длиной менее 100 минут?
Мартин Эндер
@ MartinBüttner Да. В среднем, я бы сказал, что это занимает около 5 секунд. Сначала я пробовал совершенно случайные программы, но они никогда не заканчивались для длины 100.
LegionMammal978
2

Python 3 , 177 байт

from random import*
n=int(input())
r=[0]*n*3
p=0
a=[43,45]
s=choices(a+[60,62],k=n)
for c in s:p+=~c%2*(c-61);r[p]+=c%2*(44-c)
if any(r+[p]):s=a*(n//2)
print(*map(chr,s),sep='')

Попробуйте онлайн!

Я использовал код из ответа Bubbler для симуляции BF.

Tyilo
источник
2

Python 3 , 163 байта

from random import*
n=int(input())
p=0;d=[0]*n;a=choices(b'+-<>',k=n)
for c in a:d[p]+=c%2*(44-c);p+=~c%2*(c-61)
if p|any(d):a=n//2*b'+-'
print(*map(chr,a),sep='')

Попробуйте онлайн!

Полная программа, которая печатает результаты в STDOUT. Линия с кодом BF может быть пригодна для игры в гольф.

Принял подход Tyilo; если сгенерированный код BF не является NOP, откажитесь от него и вернитесь к '+-'повторному.

фонтанчик для питья
источник
Тайм-аут для n = 100
l4m2
@ l4m2 Не заметил этого требования. Исправлена.
Bubbler
1

Wolfram Language (Mathematica) , 224 байта

(s=RandomSample[##&@@@Table["<"">",(r=RandomInteger)[#/2]]];While[(g=Length@s)<#,s=Insert[s=Insert[s,"+",i=r@g+1],"-",RandomChoice@@Select[GatherBy[0~Range~++g,Count[#,"<"]-Count[#,">"]&@Take[s,#]&],!FreeQ[#,i]&]+1]];""<>s)&

Попробуйте онлайн!

Вот версия без гольфа (или, скорее, перед игрой в гольф):

Function[{n},
 k = RandomInteger[n/2];
 s = RandomSample[## & @@@ Table["<" ">", k]];
 While[Length[s] < n,
   s = Insert[s, "+", i = RandomInteger[Length[s]] + 1];
   p = GatherBy[Range[0, Length[s]], 
     Count[#, "<"] - Count[#, ">"]& @ Take[s, #]&];
   j = RandomChoice @@ Select[p, ! FreeQ[#, i] &]];
   s = Insert[s, "-", j + 1];
   ];
 ""<>s]

Сначала мы выбираем случайное число <«и >» для использования, и генерируем случайный список с равным числом каждого.

Чтобы заполнить остальные символы, мы выбираем позицию, в которую нужно добавить +, затем находим позицию, в которой указатель указывает на то же место, и добавляем -туда.

Повторяйте, пока список не nстанет длинным, и зафиксируйте результат.

Миша лавров
источник