# Generating Brainf*** NOPs

Sometimes when writing brainfuck code, you feel the need to make it longer than needed to encourage debugging. You could do it by just plopping a >< in there, but what fun is that? You'll need something longer and less NOPey to confuse anybody reading your code.

## Quick introduction to Brainfuck

Brainfuck is an esoteric programming language created in 1993 by Urban Müller, and notable for its extreme minimalism. (Wikipedia)

Brainfuck is a language based on eight commands: +-><,.[]. The code is run on something like a Turing machine: an infinite tape on which values can be changed. In this challenge, we'll focus on the first four:

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


## Brainfuck NOPs

A brainfuck NOP is a sequence of brainfuck characters that, when executed from any state, leads to no change in the state. They consist of the four characters mentioned above.

## The Challenge

The challenge is to write a program or function that, when executed, generates a random brainfuck NOP of the given length.

## Input

You will receive as input a nonnegative even integer n. (NOPs are impossible for odd n.)

## Output

You will output a random brainfuck NOP of the length n.

## Rules

• The definition of NOP: when the output of the program is inserted at any point in a brainfuck program, the behavior of said program must not change in any way. In other words, it must not change the state of the interpreter.
• Note that for example +>-< is incorrect, since it changes the values of the two cells without changing them back. Please test your solution for these before posting.
• Also note that +>-<->+< is a NOP that can't be reduced to nothing just by removing >< <> +- -+. Thus, you can't use an algorithm that just inserts these inside each other.
• Every valid NOP of the length n must have a nonzero chance of appearing in the output. The distribution does not have to be uniform, though.
• The brainfuck interpreter in question has a doubly infinite tape of arbitrary precision cells. That is, you can go infinitely to the both directions, and increment/decrement each cell indefinitely.
• The program must finish within 1 minute for n = 100 on my machine, so no generating all possible NOPs and picking one.
• If given invalid input (non-integer, negative, odd, etc.) you may do anything you'd like, including crash.

## Scoring

This is , so the shortest answer in bytes wins.

## Examples

Here are all valid outputs for n = 4:

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


Here are a few possible outputs for n = 20:

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

• here's a brainfuck NOP that doesn't use +-<> like you asked for: a – undergroundmonorail Dec 7 '15 at 13:46
• I don't think non-simple NOPs exist, so you can probably remove that qualification. . has a side-effect, , overwrites a value which cannot be recovered without the use of []. But [] will end up setting a value to zero. This also overwrites a value (so we'd need another [] to recover it) unless we can be sure that the affected cell was zero to begin with. However, we'd have to search for such a cell with something like [>], and it's impossible to reliably return to the position we came from. – Martin Ender Dec 7 '15 at 14:52
• @Eumel "The brainfuck interpreter in question has a doubly infinite tape of arbitrary precision cells." – Martin Ender Dec 7 '15 at 15:50
• Please note that "Brainfuck" is no longer allowed in question titles on the system level. It appears you were able to circumvent the restriction by using non-ASCII characters. In the future, please abide by this restriction. – Alex A. Dec 7 '15 at 19:10
• @undergroundmonorail Well, it's Turing complete... so technically one could write a PRNG in it just like any other language. (Although seeding it might be hard.) – PurkkaKoodari Dec 8 '15 at 6:03

## CJam, 62 59 bytes

Thanks to nhahtdh for saving 3 bytes.

Because there is no requirement for any particular distribution as long as each no-op appears with finite probability, we can simplify this a lot by simply generating string containing a balanced number of -+ and <>, respectively, testing if it's a NOP and sorting it if it isn't.

Of course, for longer inputs, this will almost always result in sorted output, but you can test the code with some input like 8 to see that it can in principle produce any NOP of the given length.

ri_0a*\2/{;"-+<>":L2/mR}%smr:SL["Xa.Xm"3/2e*L]z:sers~0-S$S?  Try it online. • Yes... the arbitrary limit should have been n=1000 under 10 seconds. Computers are just way to fast today ^^ Because the algorithmic answer solves it in under a second even for n = 1000 – Falco Dec 8 '15 at 11:50 • For even larger n, I think it's possible to just sort the output if the balanced string is not NOP. The distribution is terribly skewed, but it's allowed by the question. – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Dec 9 '15 at 9:02 • @n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ that's a neat idea. – Martin Ender Dec 9 '15 at 9:08 • @n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Thanks, that actually saves three bytes here as well. – Martin Ender Dec 9 '15 at 14:49 ## CJam, 118 116 bytes This got slightly out of hand... especially the second half seems like it should be very golfable. ri2/_)mr:R-"<>"R*mr_'=fm0\{1$+}%+__&e]:\{mr1aa..+}*\@](\z:~\{~\("+-"*mr1$3$e=[{_,)mr_2$<@@>}*+]@@f{1$={(}@?\}W<}/


Test it here.

This handles N = 100 pretty much instantly. I don't have time to write the full breakdown of the code now, so here is the algorithm:

• Generate a random balanced string of < and > with random (even) length between 0 and N inclusive.
• Riffle the tape head positions into this array. E.g. "<>><" becomes [0 '< -1 '> 0 '> 1 '< 0].
• Get a list of all positions reached in the process.
• For each such position initialise an empty string. Also determine how many pairs of characters are left to reach a string of length N.
• For each remaining pair append +- to the string of a random position.
• Shuffle all of those strings.
• For each position determine how often that position occurs in the riffled array, and split the corresponding string into that many (random-length) chunks.
• In the riffled array, replace the occurrences of the position with its random chunks.

Done. This is based on the observation that:

• Any NOP must have an equal amount of < and > to return the tape head to the original position.
• The code will be a NOP as long as each tape cell is incremented as often as decremented.

By distributing random but balanced amounts of +s and -s between all the places where the tape head is on a given cell, we ensure that we find every possible NOP.

## Mathematica, 350 bytes

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)&


Way too long? Yes. Do I even care? Not until someone else posts a valid answer.

• Would you mind adding an explanation, so people can actually convince themselves this is valid? :) – Martin Ender Dec 7 '15 at 15:53
• How exactly does this work? If I call the function with a number it only returns +. – Martin Ender Dec 7 '15 at 19:57
• @MartinBüttner Fixed... Currently, it just generates random programs with an equal number of +-- and <-> pairs until one happens to be a NOP. Half of it is taken by a simple BF interpreter. – LegionMammal978 Dec 7 '15 at 22:00
• does that actually generate a valid no-op of length 100 in under a minute? – Martin Ender Dec 7 '15 at 22:07
• @MartinBüttner Yes. On average, I would say that it takes about 5 seconds. At first, I tried completely random programs, but it never terminated for length 100. – LegionMammal978 Dec 7 '15 at 22:14

# Python 3, 177 bytes

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='')


Try it online!

I used code from Bubbler's answer for the BF simulation.

# Python 3, 163 bytes

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='')


Try it online!

Full program that prints results to STDOUT. The line that runs BF code might be golfable.

Adopted Tyilo's approach; if the generated BF code is not a NOP, discard it altogether and fall back to '+-' repeated.

• Timeout for n=100 – l4m2 Oct 24 '18 at 12:51
• @l4m2 Didn't notice that requirement. Fixed. – Bubbler Oct 24 '18 at 23:44

# JavaScript (Node.js), 160 bytes

n=>[...s=c(i=n,t=c(n/2,r=[],f=_=>'+-'),f=_=>'+-<>'[Math.random()*4|0])].map(_=>_<'<'?(r[i]=_+1-~r[i]-1):(i+=_<'>'||-1))|r.some(eval)|i-n?t:s;c=n=>n?c(n-1)+f():r


Try it online!

# Wolfram Language (Mathematica), 224 bytes

(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)&


Try it online!

Here is the un-golfed (or rather, pre-golfed) version:

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]


We first pick a random number of <'s and >'s to use, and generate a random list with an equal number of each.

To fill in the rest of the characters, we pick a position in which to add a +, then find a position where the pointer points to the same location and add a - there.

Repeat until the list has length n`, and stringify the result.