7
\$\begingroup\$

Brainf**k is the most famous esoteric programming language and is the inspiration for hundreds of other esoteric languages. In fact, there are quite a few languages that are so heavily based off of Brainf**k that the only difference is the characters used. Your challenge is to interpret one of these languages.

Brainf**k

Brainf**k uses these commands:

> Move pointer to the right
< Move pointer to the left
+ Increment the memory cell under the pointer
- Decrement the memory cell under the pointer
. Output the character signified by the cell at the pointer
, Input a character and store it in the cell at the pointer
[ Jump past the matching ] if the cell under the pointer is 0
] Jump back to the matching [ if the cell under the pointer is nonzero

Trivial Brainf**k Substitution

There are lots of esolangs that are identical to Brainf**k in that they use the same commands, just with different characters/strings signaling the commands. For example, take Ook!:

Brainf**k | Ook         | Command
-----------------------------------------------------
>         | Ook. Ook?   | Move the pointer to the right
<         | Ook? Ook.   | Move the pointer to the left
+         | Ook. Ook.   | Increment the memory cell under the pointer
-         | Ook! Ook!   | Decrement the memory cell under the pointer
.         | Ook! Ook.   | Output the character signified by the cell at the pointer
,         | Ook. Ook!   | Input a character and store it in the cell at the pointer 
[         | Ook! Ook?   | Jump past the matching Ook? Ook! if the cell under the pointer is 0
]         | Ook? Ook!   | Jump back to the matching Ook! Ook? if the cell under the pointer is nonzero

Ook is exactly like Brainf**k, except for the syntax.

TrivialBrainfuckSubstitution is a function defined as:

TrivialBrainfuckSubstitution(string1, string2, string3, string4, string5, string6, string7, string8)

Each string provided substitutes the corresponding Brainf**k character - so string1 will be a substitution for >, string2 will be a substitution for <, so on and so forth.

For example, Ook! is equivalent to TrivialBrainfuckSubstitution("Ook. Ook?", "Ook? Ook.", "Ook. Ook.", "Ook! Ook!", "Ook! Ook.", "Ook. Ook!", "Ook! Ook?", "Ook? Ook!").

Alphuck is equivalent to TrivialBrainfuckSubstitution("a", "c", "e", "i", "j", "o", "p", "s").

The challenge

Implement TrivialBrainfuckSubstitution.

To elaborate: Given eight strings representing the eight substitutions and a ninth string representing a program, interpret the program as a trivial Brainf** substitution.

Rules

  • TrivialBrainfuckSubstitution may take function arguments or command line arguments. These are the only ways it may take the first eight arguments.
  • TrivialBrainfuckSubstitution can take the ninth argument from standard input, a file, or a literal ninth argument.
  • TrivialBrainfuckSubstitution must be able to take any ASCII characters as substitutions. It does not have to handle Unicode, and you can assume there are no duplicate elements provided.
  • Note that the actual function in your code need not be named TrivialBrainfuckSubstitution. This is just the title of the function; the actual name in the code can be f, or x, or a lambda, or whatever you like.
  • Your interpreter should not require any spaces between command substitutions. However, it should not break if they are present. To rephrase, it should ignore unrecognized commands, just like normal Brainf**k.
  • You may assume that all substitutions are the same length. I.e. you may assume that AB, A, and B are never in the same substitution set.

Challenge-specific Brainf**k semantics

In your newly-created Brainf**k language:

  • You do not need to be able to go left from the start of the tape. (You can choose to allow this.)
  • The tape should have a minimum length of 30000. (If you want it can be longer or allocated dynamically.)
  • The maximum value of the tape elements must be the maximum value for an integer in your (host) language.
  • Input can be read from standard input or a file.
  • An attempt to read EOF (End Of File) should not cause any undefined behavior. EOF must simply be stored as would any other character read.

Test cases

Test case 1
Test case 2

Winner

As with , the shortest submission wins. I won't ever accept an answer unless one is 50 bytes shorter than all others.

Also, as this challenge is somewhat more difficult than others (while certainly not the hardest), I kindly ask that you include an ungolfed version and explanation with your answer.

\$\endgroup\$
  • \$\begingroup\$ We need to (1) replace the 8 strings, (2) interpret BF. Nothing of substance has been added, what did I miss? \$\endgroup\$ – Jonathan Allan Jun 7 '17 at 19:40
  • \$\begingroup\$ @JonathanAllan Well, it is a lot harder than it sounds to replace the strings, given the requirements. Did you look at Challenge-specific Brainf**k semantics? And if nothing of substance was added, then why are there hundreds of languages based off Brainf**k, that plenty of people use? \$\endgroup\$ – MD XF Jun 7 '17 at 19:42
  • 3
    \$\begingroup\$ Because it's an easy starting point for people implementing esolangs since the spec of Brainfuck is very easy to understand. \$\endgroup\$ – a spaghetto Jun 7 '17 at 19:44
  • 3
    \$\begingroup\$ @MDXF you can't close an esolang as a duplicate \$\endgroup\$ – Stephen Jun 7 '17 at 19:45
  • 3
    \$\begingroup\$ The only other difference I see is in cell capacity of the interpreted BF program. If others think I've made a mistake it wont take long to get reopened. \$\endgroup\$ – Jonathan Allan Jun 7 '17 at 19:50
5
\$\begingroup\$

APL (Dyalog), 49 bytes

Prompts for program as text, then for a list of eight PCRE patterns. Note that this allows for substitutions of differing lengths, and even mapping multiple substitutions to each BF command, at the cost of having to escape some characters. Outputs to STDERR.

⎕CY'dfns'
bf(⎕,'.')⎕R(,¨'><+-.,[] ')⊢⍞

Try it online! (runs first two test cases, as the third is faulty)

⎕CY'dfns'Copy the dfns workspace

 prompt for text input (the symbol is mnemonic: a quote character in a console)

 yield that (serves to separate the substitution patterns from the input)

()⎕R()Replace:

⎕,'.' input (mnemonic: console) followed by PCRE for "any character"

… with:

'><+-.,[] ' the BF symbols followed by a BF no-op space

 ravel each (to make them into character vectors/strings instead of scalars)

bf evaluate as BF.


As of posting, this is way more than 50 bytes shorter than the other two solutions.

\$\endgroup\$
  • \$\begingroup\$ ...this is way more than 50 bytes shorter than the other two solutions. You can't compare APL with Python. :P \$\endgroup\$ – totallyhuman Aug 2 '17 at 11:05
  • \$\begingroup\$ @totallyhuman Why is that? Both are interpreted high-level programming languages for general-purpose programming. \$\endgroup\$ – Adám Aug 2 '17 at 11:06
  • \$\begingroup\$ APL has an interpret as BF built-in. :P And APL is much terser. \$\endgroup\$ – totallyhuman Aug 2 '17 at 11:08
  • 1
    \$\begingroup\$ @totallyhuman No OP prohibition on built-ins (also, it isn't; I imported it). The whole point of code-golf is to find the tersest language! \$\endgroup\$ – Adám Aug 2 '17 at 11:10
  • 5
    \$\begingroup\$ @Adám The point of code golf is very much in the eye of the beholder. For me pushing any given language is what's interesting, especially when it comes to languages where terseness was never the point. Comparison between languages is not as important imo. \$\endgroup\$ – algmyr Aug 3 '17 at 0:51
6
\$\begingroup\$

Python 2, 447 bytes

import re,sys
def f(b,r,a,i,n,f,u,c,k):
 d,e,g,m=[0]*30000,0,0,''
 for n in re.finditer('|'.join(r'(?P<%s>%s)'%m for m in[(j,re.escape(l))for j,l in zip('rlidoswen',[r,a,i,n,f,u,c,k,'.'])]),b):
  m+=' '*g+{'r':'e+=1','l':'e-=1','i':'d[e]+=1','d':'d[e]-=1','o':'sys.stdout.write(chr(d[e])),','s':'d[e]=ord(sys.stdin.read(1))','w':'while d[e]:','e':'pass'}.get(n.lastgroup,'')+'\n';g+=n.lastgroup=='w';g-=n.lastgroup=='e'
 try:exec m
 except:d[e]=-1

Try it online!

The first argument b is the code and the arguments r a i n f u c k are > < + - . , [ ] respectively.

Well... Lemme know if I missed out on anything.


Explanation

This implements a golfed tokenizer.

import re, sys

def trivial_brainfuck_substitution(code, r, a, i, n, f, u, c, k):  # define function with arguments
    tape, index, loop, result = [0]*30000, 0, 0, ''                # initialize tape, pointer, loop state and the final code

    for i in re.finditer(                                                    # iterate over matches of the regex...
                 '|'.join(                                                   # which is the next list joined by '|'
                     r'(?P<%s>%s)' % m for m in                              # construct a regex with a named group
                         [(j, re.escape(l)) for j, l in                      # a tuple of...
                             zip('rlidoswen', [r, a, i, n, f, u, c, k,'.'])  # the group name and the command
                         ]
                  ),
             code):                                                          # in the given code

        result += (' ' * loop +                                         # a space for the current amount of loops
                      {
                          'r': 'index += 1',                            # move to next cell
                          'l': 'index -= 1',                            # move to previous cell
                          'i': 'tape[index] += 1',                      # increment current cell
                          'd': 'tape[index] -= 1',                      # decrement current cell
                          'o': 'sys.stdout.write(chr(tape[index]))',    # output current cell's value as ASCII character
                          's': 'tape[index] = ord(sys.stdin.read(1))',  # store ASCII number of input in current cell
                          'w': 'while tape[index]:',                    # start a while loop
                          'e': 'pass'                                   # end a while loop
                      }.get(i.lastgroup, '') + '\n'                     # get respective command or an empty string for a no-op
                  )

        loop += i.lastgroup == 'w'  # increment the loop counter
        loop -= i.lastgroup == 'e'  # decrement the loop counter

    try:
        exec result       # execute the generated code as Python code
    except:               # except on a TypeError, thrown when no input is found
        tape[index] =- 1  # store -1 in current cell
\$\endgroup\$
  • 2
    \$\begingroup\$ double space -> tab \$\endgroup\$ – Stephen Aug 1 '17 at 18:11
  • 1
    \$\begingroup\$ If variable argument functions are allowed, you can shorten this down to 420 bytes pastebin.com/DP7JFU05 \$\endgroup\$ – sagiksp Aug 1 '17 at 19:13
  • \$\begingroup\$ @StepHen Oh yeah... I always forget that. Thanks! \$\endgroup\$ – totallyhuman Aug 1 '17 at 20:07
  • \$\begingroup\$ @sagiksp B-But b,r,a,i,n,f,u,c,k... ;-; I thought it was funny. :P Will change, thanks! \$\endgroup\$ – totallyhuman Aug 1 '17 at 20:08
  • 1
    \$\begingroup\$ +1 for b,r,a,i,n,f,u,c,k \$\endgroup\$ – ATaco Aug 1 '17 at 22:35
5
\$\begingroup\$

Python 2, 373 372 381 380 375 bytes

-1 Thanks to @StepHen

-1 Thanks to @RohanJhunjhunwala

-5 More thanks to @RohanJhunjhunwala's suggestion and cleaning up some repeated code

+9 Cause @totallyhuman made a valid point about raw_input() requiring a new line

import sys
def f(c,r,l,i,d,p,n,b,j):
 t,x,a,h,s,o,v=[0]*30000,0,0,[],0,'',[r,l,i,d,p,n,b,j," "]
 w=map(len,v)
 while a<len(c):
	for u in range(9):
	 if v[u]==c[a:w[u]+a]:break
	if s<1or u>5:
	 exec"x+=1|x-=1|t[x]+=1|t[x]-=1|o+=chr(t[x])|t[x]=ord(sys.stdin.read(1))|if t[x]and s<1:h+=[a]\nelse:s+=1|if s<1:a=h.pop()-w[6]\nelse:s-=1|".split("|")[u]
	x%=30000
	a+=w[u]
 return o

Try it online!

Works on the first two test cases, but it looks like the third one is messed up since it has 9 strings instead of 8, and two are the same. It also works on some other Hello World! Brainfuck programs.


Explanation

import sys
def TrivialBrainfuckSubstitution(code, greater, less, plus, minus, period, comma, leftbracket, rightbracket):
    tape, index, slot, loopindex, skip, output = [0]*8**5, 0, 0, [], 0, ''                  # Set up variables for the tape, tape index, code index, list of loop indices we're in, skipping indicator, and output string
    values = [greater, less, plus, minus, period, comma, leftbracket, rightbracket," "]     # Create a list of all possible values to find in the code
    lengths = map(len, values)                                          # Create a list with the lengths of all of the elements in value
    while slot < len(code):                                             # While we havent reached the end of the string
        for u in range(9):                                              # For each value in the value list
            if value[u] == code[slot:lengths[u] + slot]:break           # If the u-th element of values is equal to the same length chuck of the code from the current index
        if skip < 1 or u > 5:                                           # If we're not skipping operations or if we found a leftbracket or rightbracket
            if u == 0:                                                  # If the option was a greater
                index += 1                                              # Increment the tape counter
            elif u == 1:                                                # Else if it was a less
                index -= 1                                              # Decrement the tape counter
            elif u == 2:                                                # Else if it was a plus
                tape[index] += 1                                        # Increment the current tape cell
            elif u == 3:                                                # Else if it was a minus
                tape[index] -= 1                                        # Decrement the current tape cell
            elif u == 4:                                                # Else if it was a period
                output += chr(tape[index])                              # Append the character value of the current tape cell to the output string
            elif u == 5:                                                # Else if it was a comma
                tape[index] = ord(sys.stdin.read(1))                    # Store only a single character of input into the tape cell
            elif u == 6:                                                # Else if it was a leftbracket
                if tape[index] and skip < 1:                            # If the current cell is non-zero and we aren't currently skipping over a loop
                    loopindex += [index]                                # Append the current index to the loopindex list
                else:                                                   # Else we're trying to skip to the end of a loop
                    skip += 1                                           # Increment the skip counter (a count of the number of rightbrackets we need to skip to continue executing)
            elif u == 7:                                                # Else if it was a rightbracket
                if skip < 1:                                            # If we're executing code normally
                    slot = loopindex.pop() - lengths[6]                 # Move to the index we stored when we hit the leftbracket, but push forward enough so we hit it with the next character
                                                                        # Simultaneously remove the last value from the loopindex list since we just used it
                else:                                                   # Else we're trying to move past some loop
                    skip -= 1                                           # Decrement the skip counter since we found another rightbracket
        index = index % 30000                                           # Map the index back to 0-29999
        slot += lengths[u]                                              # Move past the current operator
 return output                                                          # Return the output string we generated

I took a different approach than totallyhuman did, so that I didn't need to import and modules. It does however use the same trick with passing strings to exec to have it do all the work. Effectively, at the start of each loop, it looks at the current index and sees if the text that follows can be matched to any of the operators that were given. If it can't, then the counter will end at an index associated with a non-valid character in this language.

The hardest part for me was getting a refined way of matching loop starts and ends. I eventually settled on a counter that gets incremented every time it sees a loop start operator, and decrements every time it sees a loop end. So in order to have the now parsed option executed, we have to be not skipping over code (indicated by a skip counter of 0) or it's the loop start or loop end characters (or a bad character, but nothing happens with that, so it's okay).

That counter index is then used to take the index-th slot of an array of strings that is created by splitting that massive string you see at all of the |s. That line of code is then executed by exec which will do a handful of checks and variable mutations. At the end of the loop we skip past the operator we just found and keep going. Finally, return the output string we've been adding onto this entire time.

On of the key pieces to this was how skipping back to loops was handled. Every time a loop was started, it appended its index to the back of a list, and every time a loop ended, it set the code index to the last value of that list (minus the length of the loop end operator so that when it was pushed "past" the loop end operator we would be at the loop start operator again).

\$\endgroup\$
  • \$\begingroup\$ 8**8 (or similar) is might a golfier way of making a number bigger than thirty thousand (have not confirmed) \$\endgroup\$ – Rohan Jhunjhunwala Aug 2 '17 at 23:43
  • \$\begingroup\$ @RohanJhunjhunwala I guess I could replace the instantiation portion with 8^5 (simply because that's a bit closer to 30k than 8^8), but leave the index one at 30k. I'm afraid to make that one over 30k since technically moving right from the 30000th cell should keep you there. \$\endgroup\$ – Arnold Palmer Aug 3 '17 at 0:24
  • \$\begingroup\$ I think thats the minimum capacity, and moving it right can cause undefined behavior after that. I would reach out to the op, but does python support 3e4? \$\endgroup\$ – Rohan Jhunjhunwala Aug 3 '17 at 1:47
  • \$\begingroup\$ @RohanJhunjhunwala I don't know if that's allowed since it says "The tape can have a maximum length of 30000". I'll ask the OP though. And python does, but you can't multiply a list by a float, so it can't be used in that context \$\endgroup\$ – Arnold Palmer Aug 3 '17 at 1:52
  • \$\begingroup\$ @RohanJhunjhunwala The OP said you can't go past the 30000th slot, but what you said combined with the OP's comment made me realize I could refactor a bit of code to shave some bytes, so thanks! \$\endgroup\$ – Arnold Palmer Aug 3 '17 at 2:13
1
\$\begingroup\$

PHP, 275 222 234 238 239 235 233 236 230 229 224 223 bytes

for($p=_.strtr($argv[9],array_flip(array_slice($argv,$m=1,8)));~$c=$p[$i+=$c<7];eval(['$m++','$m--','$$m++','$$m--','echo chr($$m)','$$m=ord(fgetc(STDIN))'][$c].';'))for($n=$d=[6=>!$$m,-1][$c];$n;)$n+=[6=>1,-1][$p[$i+=$d]];

Takes dictionary from arguments 1..8, code from argument 9, input from STDIN.

The tape has 2^64 cells and starts almost in the middle, but does not wrap.
Insert ,$m=($m+3e4)%3e4 after eval(...) for a wrapping 30K tape.
(or replace '$m--' with '$m+=29999' and insert ,$m%=3e4 after eval(...) - that´s 3 bytes shorter)

Requires PHP 5.5 or later. Run with -nr or try it online.

breakdown

for(
# translate code to 0..7, init $m (memory pointer)
    $p=_.strtr($argv[9],array_flip(array_slice($argv,$m=1,8)));
# loop through code
    ~$c=$p[
    # 1. previous instruction was not 7: increment $i (instruction pointer)
        $i+=$c<7
    ];
    # 3. instructions 0..5: eval
    eval(['$m++','$m--','$$m++','$$m--','echo chr($$m)','$$m=ord(fgetc(STDIN))'][$c].';')
)
    # 2. instructions 6,7:
        for(
        # init $n: instruction 6 and cell is 0: 1, instruction 7: -1, else: 0 or NULL
            $n=$d=[6=>!$$m,-1][$c];
        # loop while $n (bracket count) is truthy
            $n;
        )
            # 2. if bracket, increment / decrement bracket count
            $n+=[6=>1,-1][$p[
            # 1. increment / decrement IP
                $i+=$d
            ]];
\$\endgroup\$
  • \$\begingroup\$ PHP Notice: Undefined variable: f in /home/runner/.code.tio on line 1 PHP Notice: Undefined variable: m in /home/runner/.code.tio on line 1 PHP Fatal error: Uncaught Error: Unsupported operand types in /home/runner/.code.tio:1 Stack trace: #0 {main} thrown in /home/runner/.code.tio on line 1 \$\endgroup\$ – MD XF Aug 2 '17 at 23:45
  • \$\begingroup\$ @MDXF I´m not incapable of testing, I just was too tired at 2 AM. It requires PHP 7. -n makes PHP ignore Notices (Prepend error_reporting(22519); to emulate that). There are three bugs apart from that; but I will update that post. \$\endgroup\$ – Titus Aug 3 '17 at 9:21
  • \$\begingroup\$ @MDXF fixed and completed \$\endgroup\$ – Titus Aug 3 '17 at 12:10
1
\$\begingroup\$

CJam, 183 bytes

q:Iea):C;:O];{O{_,C<=}#_)O0=,(e&)C>:C}g]:C,{_C=6-We>"M+:M M(\:M;a+aL+:L "S/=~}/];0a3e4*{TC="(+ 1m> ))+ )(+ _W=co );I0ae|(\:I;i+ _W={L{1=T=}=0=:T;}| _W={L{0=T=}=1=:T;}& "S/=~T):TC,<}g;

183 bytes of pure, sweet CJam.

This first 8 command-line arguments are the commands, the 9th is the code.

Try it online!

Ungolfed and commented

e# Variables:
e# I  Input
e# C  Code
e# O  Command aliases
e# L  Loop open-close index pairs ([] by default, not set up here)
e# T  Instruction pointer (0 by defualt, not set)

q:I   e# Read the input and store it in I.
ea    e# Read the command-line args.
):C;  e# Remove the last, store it in C, and delete.
:O    e# Store the rest in O.
];    e# And clear everything off the stack.


e# Now we translate the code into numbers for each command:
e# -1 no-op
e# 0  >
e# 1  <
e# 2  +
e# 3  -
e# 4  .
e# 5  ,
e# 6  [
e# 7  ]

{          e# Do:
 O{_,C<=}#  e# Find the index of the alias such that C starts with (or -1 if C doesn't start with a valid command)
 _          e# Copy it
 )          e# Increment it
 O0=,(      e# Get the alias length-1
 e&)        e# Logical AND and increment the result
 C>         e# Slice that many characters from the beginning of C
 :C         e# Store the newly sliced code back into C
}g         e# While (C is not empty)
]:C        e# Save the resulting list of commands back into C


e# Next, we find the pairs of matching loops

,{                         e# For i in C
 _C=                        e# Copy i and push C[i]
 6-We>                      e# max(-1, i-6)
 "M+:M M(\:M;a+aL+:L "S/=~  e# Split this string on spaces, and eval result[max(-1, i-6)]
                            e# For 0 ([), push the index to M (M is a temporarily used list)
                            e# For 1 (]), pop and index from M, pair it with the current index, and add that pair to L
                            e# For -1, do nothing
}/                         e# End for
];                         e# Clear the stack


e# The final step is to interpret

0a3e4*  e# Create a tape containing 30000 0's
{       e# Do
 TC=     e# Get the current instruction

 e# This string contains the commands, space separated, so they can be easily evaled
 "(+ 1m> ))+ )(+ _W=co );I0ae|(\:I;i+ _W={L{1=T=}=0=:T;}| _W={L{0=T=}=1=:T;}& "
 S/=~    e# Split by spaces, get result[command], and eval
 T):T    e# Increment the instruction pointer
 C,<     e# Check if it's less than the length of the C
}g      e# While TOS is truthy
;       e# Delete the tape so it doesn't get implicitly printed
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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