19
\$\begingroup\$

This challenge was posted as part of the April 2018 LotM challenge


Brain-Flak is a turing-tarpit language which has gained quite a lot of fame here on PPCG. The memory of the language is composed by two stacks, but a "hidden" third stack was discovered by Wheat Wizard, leading to some interesting new ways of thinking Brain-Flak programs.

So, what about giving that poor hidden third stack more visibility? Let's create a language where the third stack has the recognition it deserves! Here I present you Third-Flak.

The language

In Third-Flak there is only one stack, called the third stack. Operators work on the third stack in the same way they do in Brain-Flak, but here there are no [],{},<> nilads and no {...} monad (so the only admissible characters in a Third-Flak program are ()[]<>). Here is what each operator does (examples will be given representing the third stack with a list where the last element is the top of the stack):

  • () is the only two-characters operator in Third-Flak. It increases the top of the third stack by 1. Example: [1,2,3][1,2,4]

  • (,[,<: all opening parentheses that are not covered by the previous case push a 0 to the third stack. Example: [1,2,3][1,2,3,0]

  • ) pops two elements from the third stack and pushes back their sum. Example: [1,2,3][1,5]

  • ] pops two elements from the third stack and pushes back the result of subtracting the first from the second. Example: [1,2,3][1,-1]

  • > pops an element from the third stack. Example [1,2,3][1,2]

And here are the other rules of the language:

  • At the beginning of execution the third stack contains only a single 0.

  • It is forbidden to have empty [] or <> inside a program (they would be noops anyway if following the semantics of Third-Flak, but they actually have a different meaning in Brain-Flak that is not possible to recreate here).

  • Parentheses always need to be balanced, except for the fact that trailing closing parentheses at the end of the program can be missing. As an example, [()<(() is a valid Third-Flak program (and the third stack at the end of the program would be [1,0,1]).

  • A program can only contain the six allowed characters ()[]<>. Programs are guaranteed to be non-empty.

Note: it is implied by the previous rules that you won't have to deal with situations where you need to pop from an empty stack.

The challenge

Simple, write an interpreter for Third-Flak. Your program must take as input a Third-Flak program and return as output the state of the third stack at the end of the program.

Your output format is flexible as long as it is possible to unambiguously read from it the state of the third stack and the same number is always encoded in the same way (This is just a way of saying that any output format that's not a blatant way to try to cheat is fine).

Your output choice may restrict the range of numbers you can manage as long as this does not trivialize the challenge (since this would be a default loophole).

Test cases

For each test case the first line is the input, and the second line the output stack represented as a space separated list of numbers where the top of the stack is the last element.

[()<(()
0 1 0 1

[((((()()()()()))
0 0 0 5

((([()][()][()])))
-3

[<<(((()()()())(((((
0 0 0 0 0 4 0 0 0 0 0

[()]<(([()])><[()]
-1 0 -1

(())(()()())(())(())(()()())(())(())(()()())(())(()()()()())(()())(()()()()())(())(()()())(())(()()()()())(())(())(())(())(()()()()())(())(())(()()())(())(())(()()())(())(()()()()())(()())(()()()()())(())(()()())(())(()()()()())(())(())(())(())(())(())(()())(())(())(())(()())(()()()())(())(()()()()())(()())(()())(()())(()()())(())(()())(())(()()()()())(()())(()()()()())(())(())(())(())(())(()())(())(())(())(()()()()())(())(())(()()()()())(())(())(()()()()())(())(())(()())(())(()())(())(()())(())(()())(())(()())(()())(()())(()())(()())(()())(()())(()())(())(()()()()())(())(())(()()())(())(())(()()())(())(()()()()())(()())(()()()()())(())(()()())(())(())(()()())(()())(())(()()()()())(())(())(()()())(())(())(()()())(())(()()()()())(()())(()()()()())(())(())(())(()()())(())(())(()()())(())(())(()()())(())(()()()()())(()())(()()()()())(()()())(())(()()())(())(())(())(()())(()()())(()())(())(()()()()())(()())(())(()()())(())(()()()()())(())(())(())(()()())(())(())(())(()())(())(()())(()()()())(())(())(()()()()())(()())(()())(())(()()())(())(())(())(())(()()())(()())(())(())(()()()()())(())(())(()()()()())(())(())(()()()()())(())(())(()())(())(()())(())(()())(())(()())(()())(()())(()())(())(()()()()())(()())(())(()()())(())(()()()()())(()()()()())(())(()()())(())(())(()())(())(()()()()())(())(()()()()())(())(())(())(()()()()())(())(())(()())(())(()())(())(()())(())(()())(())(()())(()())(()())(()())(())(()()()()())(()())(())(()()())(())(())(()())(())(()()()()())(()())(()()()()())(())(()()())(())(())(()()()()())(())(()()()()())(())(())(())(()())(())(()()()()())(())(())(()())(())(()())(())(()())(()())(()())(()())(())(()()()()())(()())(())(()()()()())(())(()()())(())(())(()())(())(()()()()())(()())(()()()()())(())(()()())(())(())(())(()())(()()()())(())(())(()())(())(()()()()())(())(())(()()()()())(())(())(()()()()())(())(())(()())(())(()())(())(()())(())(()())(())(()())(()())(()())(()())(()())(()())(())(()()())(())(())(()())(())(()()()()())(()())(()()()()())(()()())(())(())(()())(())(())(()()()()())(()()()())(()())(()())(()()())(())(()())(())(()()()()())(()())(()()()()())(())(())(())(()()()())(()()()())(()()
718 2
\$\endgroup\$
  • \$\begingroup\$ Is the stack initialised with a 0? Otherwise [()] breaks the rule that we don't need to worry about popping from an empty stack \$\endgroup\$ – Jo King Apr 24 '18 at 4:52
  • 1
    \$\begingroup\$ @JoKing Yep: "At the beginning of execution the third stack contains only a single 0". Maybe I should highlight that part a bit, I was afraid it would have been too easy to miss. \$\endgroup\$ – Leo Apr 24 '18 at 5:00
  • \$\begingroup\$ Oops, I don't know how I missed that \$\endgroup\$ – Jo King Apr 24 '18 at 5:01
  • 7
    \$\begingroup\$ Crossed out e is still e. \$\endgroup\$ – Sriotchilism O'Zaic Apr 24 '18 at 5:47
  • 2
    \$\begingroup\$ If anyone can't see that, the crossed out e is here. \$\endgroup\$ – user202729 Apr 24 '18 at 5:56
21
\$\begingroup\$

Brain-Flak, 276 bytes

{({}<>)<>}<>{(((()()()()()){})((({}){})())(({})({}{}([{}])(<>))))((()()(){[()]<{}>}{}){()<{{}}>}{}<<>({}({})())>{()(<{}>)}{}<>)<>}<>{(([{}]()<>)){{}({}())((){[()](<({}())((){[()](<({}())((){[()](<{}([{}]{})>)}{}){(<{}{}>)}{}>)}{}){(<{}({}{})>)}{}>)}{}){(<{}{}({}())>)}}{}<>}<>

Try it online!

You had to know this was coming.

\$\endgroup\$
4
\$\begingroup\$

Retina 0.8.2, 64 48 46 bytes

\(\)
_
[([<]
¶
+1`¶(.*)\)|(.*)¶\2]|¶.*>
$1
%`_

Try it online! Outputs the stack from bottom to top. Only works with non-negative integers, and the last test case is too slow, so the link only includes three test cases. Explanation: The stack implicitly precedes the program, so it starts off as the empty string, which represents a single zero. The () nilad is turned into a _ which is used to count in unary, while the other open brackets are turned into newlines which push a zero on to the stack as they are encountered. The close brackets are then processed one at a time so that the stack will be correct; the ) deletes the previous newline, adding the top two elements together, the ] deletes the top element and matches it from the previous element on the stack thus subtracting it, and the > just deletes the top element. Finally the stack is converted to decimal. Edit: Saved 2 bytes thanks to @Leo.

\$\endgroup\$
  • \$\begingroup\$ What's the $3 for? (great answer, anyway!) \$\endgroup\$ – Leo Apr 24 '18 at 10:21
  • \$\begingroup\$ @Leo That's a left-over from a previous golf. Thanks for spotting it! \$\endgroup\$ – Neil Apr 24 '18 at 10:49
4
\$\begingroup\$

Python 3, 145 144 132 122 116 109 104 bytes

-7 bytes thanks to Leo!

And - 5 thanks to Lynn!

s=[0]
for i in input().replace('()',' '):s+=i in']>) 'and(i<'!'or(2-ord(i)%5)*s.pop())+s.pop(),
print(s)

Try it online!

Pretty standard implementation. Not so readable now though. I'm disappointed I couldn't figure out a shorter way to check between start and end brackets though.

Some attempts at one-liners:

  • 124 bytes (anonymous function):

    lambda c:[s.append(i in']>) 'and(i<'!'or~-']>)'.index(i)*s.pop())+s.pop())or s for s in[[0]]for i in c.replace('()',' ')][0]
    
  • 115 bytes (full program):

    s=[0];[s.append(i in']>) 'and(i<'!'or~-']>)'.index(i)*s.pop())+s.pop())for i in input().replace('()',' ')];print(s)
    

Append is annoyingly longer than plain assignment

\$\endgroup\$
  • \$\begingroup\$ ~-']>)'.index(i) can be (2-ord(i)%5) to save 4 bytes. \$\endgroup\$ – Lynn Apr 24 '18 at 16:57
2
\$\begingroup\$

Ruby, 98 91 bytes

->s{a=[i=0];s.chars{|c|a<<("([<"[c]?s[i,2]["()"]?1:0:a.pop*~-"]>)".index(c)+a.pop);i+=1};a}

Try it online!

My initial code worked similarly in spirit to Jo King's Python answer, so that before looping through the source chars we replaced all () substrings by another character, as a distinct operator.

However, at least in Ruby, it turned out golfier not to do this, but rather go for a slightly more cumbersome approach. Here, we maintain an additional indexer i keeping track of our position in the source string, and whenever an opening bracket is encountered, we do a lookahead checking if our current+next chars s[i,2] form the () operator. In that case we push 1 instead of 0 on top of the stack, and let the closing ) do its job in the next step.

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

05AB1E, 25 bytes

΄()1:v"0+0\0->"žuykè.V})

Try it online!

Explanation

Î                           # initialize the stack with 0 and the input
 „()1:                      # replace any occurrence of "()" in the input with 1
      v                }    # for each char y in this string
                žuyk        # get its index in the string "()[]<>{}"
       "0+0\0->"    è       # use this to index into the string "0+0\0->"
                     .V     # eval
                        )   # wrap the stack in a list
\$\endgroup\$
1
\$\begingroup\$

SOGL V0.12, 34 bytes

0,Ƨ() Iŗ{"(<[”č0ŗΖ)+ŗ ] -ŗΖ>Xŗ!!}⁰

Try it Here!

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

R, 182 177 bytes

function(P){for(k in utf8ToInt(gsub("\\(\\)",7,P))%%8){if(k%in%0:4)F=c(0,F)
if(k==7)F[1]=F[1]+1
if(k==1)F=c(F[2]+F[3],F[-3:0])
if(k==5)F=c(F[2]-F[1],F[-2:0])
if(k==6)F=F[-1]}
F}

Try it online!

Returns the stack, where the top of the stack is first and the bottom of the stack is last.

Swaps () with 7 and then computes the code points mod 8 to get distinct numeric values, which are easier and golfier to work with than strings.

It's golfier to work with the beginning of a vector in R, so we construct the stack that way.

Then it sees a ), or when k==1, it adds an extra zero to the top of the stack since it's golfier to add it and remove it.

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

CJam, 29 bytes

0q")]>([<""+-;U"er"U+"/')*~]p

Try it online!

0q                              Push 0, input
  ")]>([<""+-;U"er              Translate )]>([< to +-;UUU
                  "U+"/')*      Replace U+ by )
                          ~     Eval as CJam code
                           ]p   Wrap and pretty-print stack
\$\endgroup\$
1
\$\begingroup\$

Ceylon, 285 266 bytes

function f(variable String c){variable Integer[]s=[0];value o=>[s[0]else nothing,s=s.rest][0];void u(Integer i)=>s=[i,*s];while(c!=""){if(c[0:2]=="()"){u(1);c=c.rest;}switch(c[0])case(')'){u(o+o);}case(']'){u(-o+o);}case('>'){noop(o);}else{u(0);}c=c.rest;}return s;}

Try it online!

(Saved 19 bytes due to a suggestion by Leo.)

Formatted and commented:

// Interpreter for ThirdFlak
// Question:    https://codegolf.stackexchange.com/q/163242/2338
// This answer: https://codegolf.stackexchange.com/a/163403/2338
//
// This function takes the code as a string, and returns the value
// of the stack as a sequence of Integers.
function f(variable String c) {
    // stack, in the beginning just a single 0.
    // Top element of the stack is the first, because push + pop is easier this way.
    variable Integer[] s = [0];
    // pop – used like an Integer variable (not a function – this saves the `()`), but has side effects.
    value o =>
        // `s[0]` is the first element of the stack. We tell the compiler
        // that it is non-null (otherwise we'll get an error at run time)
        // using the `else nothing`. `s.rest` is `s` without its first element.
        // Both together are wrapped into a 2-tuple, of which we then take just
        // the first element, to have both together in an expression instead
        // the longer way using an accessor block with a temporary variable and a return.
        // value o {
        //   value r = s[0] else nothing;
        //   s = s.rest;
        //   return r;
        // }
        [s[0] else nothing, s = s.rest][0];
    // push
    void u(Integer i) =>
        // a tuple enumeration, using the spread argument.
        s = [i, *s];
    // the main loop
    while (c != "") {
        if (c[0:2] == "()") {
            // »`()` is the only two-characters operator in Third-Flak. It increases the top of the third stack by 1.«
            // As `)` alone adds the two top elements together, we can just push a one here, and let the handling for `)` do the rest.
            u(1);
            c = c.rest;
        }
        switch (c[0])
        case (')') {
            // »`)` pops two elements from the third stack and pushes back their sum.«
            u(o + o);
        }
        case (']') {
            // »`]` pops two elements from the third stack and pushes back the result of subtracting the first from the second.«
            // As the o written first is the first one, we can't write this as a subtraction.
            u(-o + o);
        }
        case ('>') {
            // »`>` pops an element from the third stack.«
            // `o;` alone is not a valid statement, so we pass it to the `noop` function.
            noop(o);
        }
        else {
            // all other valid code characters are `(`, `[`, `<`, which all just push a 0.
            u(0);
        }
        c = c.rest;
    }
    return s;
}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I don't really know Ceylon, but maybe you could remove the first case of the switch and use the else part to manage all opening brackets :) \$\endgroup\$ – Leo Apr 25 '18 at 23:30
  • \$\begingroup\$ Hmm, I guess that could work ... it would change the behavior for invalid input, but that is not a problem. \$\endgroup\$ – Paŭlo Ebermann Apr 26 '18 at 18:27

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.