26
2
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.
- Note that for example
- 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 code-golf, 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:
+>>->+<->-<<<->>++<<
>+>-<+<->+-<>->+<-<+
+--+-++--++-+--+-++-
>>>>>>>>>+-<<<<<<<<<
18here's a brainfuck NOP that doesn't use
+-<>
like you asked for:a
– undergroundmonorail – 2015-12-07T13:46:21.8231I 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 – 2015-12-07T14:52:15.273<
at the start of a BF programm gives different results depending on interpreter, is it safe to say we start at position 100 so we definetly dont run ito that error? – Eumel – 2015-12-07T15:48:07.5134@Eumel "The brainfuck interpreter in question has a doubly infinite tape of arbitrary precision cells." – Martin Ender – 2015-12-07T15:50:30.913
2
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. – 2015-12-07T19:10:50.067@undergroundmonorail, that's not an operation, just a comment taking zero execution time. A compiler would strip it out. – Hand-E-Food – 2015-12-07T22:12:49.010
1I'd love to see someone post an answer to this in brainfuck – Patrick Roberts – 2015-12-08T04:59:21.410
@hand-e-food you're no fun – undergroundmonorail – 2015-12-08T05:39:05.930
@patrick brainfuck can't do random – undergroundmonorail – 2015-12-08T05:39:25.883
2@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 – 2015-12-08T06:03:44.580
Just seed it with 0, what's wrong with settling for pseudo-random? That satisfies the requirement, does it not? – Patrick Roberts – 2015-12-08T06:12:16.490
1No, because it'd always produce the same output if the seed was constant – undergroundmonorail – 2015-12-08T06:12:56.050
1You could execute the code and pipe in the current date/time as an input to be used as the seed. – Hand-E-Food – 2015-12-08T21:47:40.737