Implement a BrainFlump interpreter
BrainFlump is the latest alternate memory model brainfuck-esque turing tarpit.
It operates on a memory model we call a "Dump", which is simply an un-ordered collection of integers, with a pointer indicating the current item to operate on. As it is "unordered", when moving to the next item, one is simply chosen at random (chosen uniformly between the items that are not the currently selected item) and the operation pointer is moved to that item.
Commands
+ #Increment the item at the pointer
- #Decrement the item at the pointer
: #Add a 0 to the dump, and move the pointer to it
; #Move the pointer to a random item that is not the pointer's current position
( #Skip to the matching ) if the item at the pointer is 0
) #Skip to the matching ( if the item at the pointer is not 0
, #Read a single character from STDIN and push its ascii value to the dump
#This also moves the pointer to the new item
. #Print the current item at the pointer modulo 127 as an ASCII character
Other notes
- When the
; command is used if the dump contains only 1 item, a new 0 is pushed to the dump, and the pointer is moved to it
- The
. command does not pop the item from the dump
- When the
, command is used if STDIN has been exhausted, a new 0 is pushed to the dump, and the pointer is moved to it
- Any item in the dump who's value is
0 is not considered to exist, unless it is the item at the pointer, therefore to "pop" an item from the dump, you simply set its value to 0
- Nested loops are supported
- The random number generator used for the interpreter does not have to be cryptographically secure, but must chose with uniformity.
- BrainFlump does not support floating point numbers or negative integers. Attempting to decrement a number below
0 has no effect.
- The maximum value of an item in the dump is
255
Examples/Testcases
brainf**k emulation
++++++(;++++++++;-);.
This should output 0
Explanation
++++++ #Increment the first item to 6
( #While the item under the pointer is not 0
; #Move to another item in the dump
# Note the first time this loop runs,
# this will insert a new item
++++++++ #Increment the new item by 8
; #Switch to another item in the dump
# Note there are only 2 items currently,
# So this will switch to the only other
# item, the one we initially incremented to 6
- #Decrement the item
) #Repeat the loop if the item is not 0
; #Switch to the other item
# Note this switches the pointer back to
# The item we have been incrementing by
# 8 each loop
. #Output as ASCII character
This is effectively a 6*8 operation, followed by an output, and is nearly identical to brainf**k's ++++++[>++++++++<-]>. program, which also outputs 0.
Note, however, that brainf**k-esque dump manipulation is only deterministically possible if there are never more than 2 items in the dump.
Random output
+:++:+++:++++:+++++:;.
This will actually always output an unprintable character, however which character is output will be random each time, selected from: SOH, STX, EST, EOT, ENQ, ie ASCII characters 1-5. In a correctly implemented interpreter, this output should be uniformly random between the 5 possibilities.
Explanation
+ #Increment first item to 1
: #Add new item and move to it
++ #Increment new item to 2
: #Add new item and move to it
+++ #Increment new item to 3
: #Add new item and move to it
++++ #Increment new item to 4
: #Add new item and move to it
+++++ #Increment new item to 5
: #Add new item and move to it
# Note this last item is added because ; will
# always switch to an item that is *not* the
# currently selected item
; #Switch randomly to an item in the dump
. #Output as ASCII character
To give a little more info on this, by the time the ; command is reached, the dump should look like this:
1 2 3 4 5 0
^
As ; always switches to a different item, the result will be the pointer at one of the non-zero items.
cat
,(.,)
Nice and simple, and identical to brainf**k's cat program.
For scoring purposes, you should use this gist as input when testing.
When will it end?
++++(,:+++++;++(;++++++;--):++++;---)
This program doesn't output anything, but runs for a non-deterministic amount of time.
Explanation
++++ #Increment first item to 4
( #Start loop
, #Read char from STDIN to new item in dump
:+++++ #Push 5 to dump
;++ #Switch to random item in dump and add 2
( #Start loop
;++++++ #Switch to random item in dump and add 6
;-- #Switch to random item in dump and subtract 2
) #End loop
:++++ #Push 4 to dump
;--- #Switch to random item in dump and subtract 3
)
This one is a little tricky, as ; will never switch to a 0 (Remember items with a value of 0 are considered to not exist)
The inner loop will only exit if ;-- switches to a number <= 2
The outer loop will only exit if ;--- switches to a number <= 3
Due to the inherent randomness of the language, this should always terminate... eventually.
For scoring purposes, you should use the exact string Hello, World! as input when testing.
Scoring
This is fastest-code meaning the interpreter that on average runs the fastest, wins!
Scoring will be determined by running each of the 4 test-cases above 100 times, and determining an average runtime (due to the inherent randomness of the language, a high number of runs should be made to minimise anomalous results).
Then once you have an average for each testcase, sum the 4 times, and that is your final score. Lower is better
