25
\$\begingroup\$

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:

+>>->+<->-<<<->>++<<
>+>-<+<->+-<>->+<-<+
+--+-++--++-+--+-++-
>>>>>>>>>+-<<<<<<<<<
\$\endgroup\$
13
  • 22
    \$\begingroup\$ here's a brainfuck NOP that doesn't use +-<> like you asked for: a \$\endgroup\$ Dec 7, 2015 at 13:46
  • 4
    \$\begingroup\$ @Eumel "The brainfuck interpreter in question has a doubly infinite tape of arbitrary precision cells." \$\endgroup\$ Dec 7, 2015 at 15:50
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Alex A.
    Dec 7, 2015 at 19:10
  • 2
    \$\begingroup\$ @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.) \$\endgroup\$ Dec 8, 2015 at 6:03
  • 2
    \$\begingroup\$ No, because it'd always produce the same output if the seed was constant \$\endgroup\$ Dec 8, 2015 at 6:12

7 Answers 7

17
\$\begingroup\$

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.

\$\endgroup\$
12
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – Falco
    Dec 8, 2015 at 11:50
  • \$\begingroup\$ 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. \$\endgroup\$ Dec 9, 2015 at 9:02
  • \$\begingroup\$ @n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ that's a neat idea. \$\endgroup\$ Dec 9, 2015 at 9:08
  • \$\begingroup\$ @n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Thanks, that actually saves three bytes here as well. \$\endgroup\$ Dec 9, 2015 at 14:49
4
\$\begingroup\$

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.

\$\endgroup\$
7
  • 4
    \$\begingroup\$ Would you mind adding an explanation, so people can actually convince themselves this is valid? :) \$\endgroup\$ Dec 7, 2015 at 15:53
  • \$\begingroup\$ How exactly does this work? If I call the function with a number it only returns +. \$\endgroup\$ Dec 7, 2015 at 19:57
  • \$\begingroup\$ @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. \$\endgroup\$ Dec 7, 2015 at 22:00
  • \$\begingroup\$ does that actually generate a valid no-op of length 100 in under a minute? \$\endgroup\$ Dec 7, 2015 at 22:07
  • \$\begingroup\$ @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. \$\endgroup\$ Dec 7, 2015 at 22:14
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Timeout for n=100 \$\endgroup\$
    – l4m2
    Oct 24, 2018 at 12:51
  • \$\begingroup\$ @l4m2 Didn't notice that requirement. Fixed. \$\endgroup\$
    – Bubbler
    Oct 24, 2018 at 23:44
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.