19
\$\begingroup\$

Let me tell you about a simple number system. (which I made up just for this challenge)

This system contains the functions (), [], {}, and <>.

1. ()

When () is given no arguments, it evaluates to 0.

When () is given one or more arguments, it evaluates to the sum of the arguments.

2. []

When [] is given no arguments, it evaluates to -1.

When [] is given one or more arguments, it evaluates to the first argument minus the sum of the other arguments.

3. {}

When {} is given no arguments, it evaluates to 1.

When {} is given one or more arguments, it evaluates to the product of those arguments.

4. <>

When <> is given no arguments, it evaluates to 1.

When <> is given one or more arguments, it evaluates to the first argument integer divided by the product of the other arguments.

Your task

Given a string that contains a valid number (that means brackets are balanced, no division by 0s, etc.) in this simple number system, print its value.

Test cases

() -> 0
(()()) -> 0
([][]) -> -2
({}<>) -> 2
({}[]) -> 0
[] -> -1
[[][]] -> 0
[()<>] -> -1
{()} -> 0
{([]<>)} -> 0

Remember, this is , so the code with the fewest bytes wins.

\$\endgroup\$
  • 13
    \$\begingroup\$ I have a great name for this, which I totally just made up and did not get from anywhere else: Brain-flake! \$\endgroup\$ – ETHproductions Nov 19 '16 at 2:44
  • 4
    \$\begingroup\$ @ETHproductions no \$\endgroup\$ – Oliver Ni Nov 19 '16 at 2:45
  • \$\begingroup\$ Sort of related \$\endgroup\$ – DJMcMayhem Nov 19 '16 at 2:57
  • 2
    \$\begingroup\$ Is division float division or integer division? \$\endgroup\$ – xnor Nov 19 '16 at 3:19
  • 1
    \$\begingroup\$ @Oliver How should integer division work when one or both of the operands are negative? What are the 4 expected results for 5/3, 5/-3, -5/3 and -5/-3? \$\endgroup\$ – Martin Ender Nov 19 '16 at 13:12

10 Answers 10

2
\$\begingroup\$

Dyalog APL, 94 bytes

o←{(⊂(1⊃⍵),⍺⍺⊃⍵),2↓⍵}⋄u←{(⊃⍵,⍺⍺1)⍺⍺⍵⍵/1↓⍵}⋄⍎⍕'+/o' '-u+o' '×/o' '÷u×o' '(⊂⍬),'[')]}>'⍳⌽⍞],'⊂⍬'

uses ⎕IO←0

replaces )]}> with a function call that takes a stack, applies an operation on its top frame, deletes it, and appends the result to its next frame (monadic operator o is used for that; dyadic operator u handles the more complicated cases of - and ÷)

replaces ([{< with code that adds a frame to the stack ((⊂⍬),)

executes the resulting expression (reversed, to match APL's order of execution) with an initial stack of one empty frame (⊂⍬)

\$\endgroup\$
5
\$\begingroup\$

Haskell, 357 306 277 251 228 224 188 185 180 bytes

A token-based parser with an explicit stack. (%) takes a token stack and a character and either pushes (opcode,defaultnumber) or (0,number) for ({[<, or pops topmost numbers and one opcode and pushes the answer for )}]>. Opcodes are encoded by a ascii enumeration hack.

Kudos to @ChristianSievers for his great answer that I borrowed some ideas from.

One-liner!

s%c|elem c"([<{",g<-div(fromEnum c)25=(g,[0,0,1,-1,1]!!g):s|(a,(o,n):b)<-span((==0).fst)s=(0,[foldr1(flip$[(+),quot,(-),(*)]!!(o-1))$snd<$>a,n]!!(0^length a)):b
snd.head.foldl(%)[]

Now with less error-handling! Usage:

*Main> map (snd.head.foldl(%)[]) ["()","(()())","([][])","({}<>)","({}[])","[]","[[][]]","[()<>]","{()}","{([]<>)}"]
[0,0,-2,2,0,-1,0,-1,0,0]

Thanks @ChristianSievers for saving 14+3 bytes!

Thanks @Zgarb for saving some+4 bytes!

\$\endgroup\$
  • 1
    \$\begingroup\$ How about (0,[0,0,1,-1,1]!!o):s in the fifth line? \$\endgroup\$ – Christian Sievers Nov 23 '16 at 0:48
  • \$\begingroup\$ @ChristianSievers of course! \$\endgroup\$ – Angs Nov 23 '16 at 5:23
  • \$\begingroup\$ Switch the definitions of !, so you can do (s:_)!_=d s as the second case. Also, I think you could bind x<-p$d<$>init a,y<-d$last a in the last case of %. \$\endgroup\$ – Zgarb Nov 23 '16 at 13:18
  • \$\begingroup\$ @Zgarb thanks! I found a way to unify the evaluation even more. \$\endgroup\$ – Angs Nov 23 '16 at 14:23
  • 1
    \$\begingroup\$ On the third line of % you can drop parens around _:b and g c. \$\endgroup\$ – Zgarb Nov 23 '16 at 17:27
3
\$\begingroup\$

Python 2, 292 265 248 235 223 206 204 bytes

r=reduce
s=input()
for n in')]}>':s=s.replace(n,'),')
for a in'(*x:sum(x)','[a=-1,*x:a-sum(x)','{*x:r(int.__mul__,x,1)','<a=1,*x:r(int.__div__,x,a)':s=s.replace(a[0],'(lambda %s)('%a[1:])
print eval(s)[0]

Replaces all brackets with a lambda that does what the bracket does, then evaluates the resulting Python code. Requires its input surrounded by quotes, like '[<><>([]{})]'.

This program stores the type of bracket as the first character in each string in the for, and everything after the keyword lambda as the rest. It then uses the first character to substitute; the rest of it is combined into a lambda like (lambda*x:sum(x))().

Try it on Ideone!

\$\endgroup\$
3
\$\begingroup\$

PEG.js (ES6), 132 bytes

x=a:[([{<]b:x*[)\]}>]{var x='([<'.indexOf(a)
b.length^1||b.push(0)
return~~eval(b.length?b.join(('+-/'[x]||'*')+' '):~-('10'[x]||2))}

Should be fixed now.

Explanation

More readable:

x=a:[([{<]
  b:x*
  [)\]}>]
{
  var x='([<'.indexOf(a)
  b.length^1||b.push(0)
  return ~~eval(
    b.length?
      b.join(('+-/'[x]||'*')+' ')
    :~-('10'[x]||2))
  )
}

PEG.js is an extended version of Javascript specifically made for parsing. It's VERY strict, which is why I had to use var. In addition, there seems to be a bug with brackets inside strings, which bloated the code significantly.

To start, we define a rule x that matches any bracket a that may or may not contain multiple expressions that matches rule x.

For each match to rule x, we push a 0 to the array of the inner match b if b's length is 1.

If b's length > 0, then we find the index of a in ([< and get a character from +-/ using that index. If the result is undefined (meaning that a was {), then we turn the result into *. Finally, we tack on a space and join b with the result.

If b's length = 0, then we find the index of a in ([< and get a character from 10 using that index. If the result is undefined (meaning that a was { or <), then we turn the result into 2. Finally, we simply decrement.

At the end, we can just evaluate the expression and floor the result.

\$\endgroup\$
3
\$\begingroup\$

Perl, 113 + 2 = 115 bytes

Run with -lp (2 byte penalty).

/\W/,eval"sub $`\{\$#_?(shift)$&&$'1}"for qw'a+a:1- b-a:- c*c: d/c:';y/([{</a-d/;s/\W/0),/g;s/\pL\K/(/g;$_=eval

More readable (note: this "more readable version" won't actually run, because I put comments in places they aren't syntactically allowed):

              # -p option: read a line of input into $_ at program start
              # -l option: remove the final newline whenever reading
do {          # for each element of a list, given later:
  /\W/;       # place an initial identifier in $`, the next character in
              # $&, and the rest of the element in $'
  eval qq{    # then evaluate the following template, with substitutions:
    sub $` {  # define a subroutine named $`, that does this:
      \$#_ ?  # if there is more than one argument                   
      (shift) # then return the first argument $&-ed with
      $& &$'  # the result of a recursive call with the tail of the arguments
              # else (the "else" is a colon taken from $', not the template)
      1       # return (the remainder of $' applied to) 1
    }
  }
} for qw'     # specify the list by splitting the following on whitespace:        
  a+a:1-      # a(head,tail) = len(tail>1) ? head+a(tail) : 1-1
  b-a:-       # b(head,tail) = len(tail>1) ? head-a(tail) : -1
  c*c:        # c(head,tail) = len(tail>1) ? head*c(tail) : 1
  d/c:        # d(head,tail) = len(tail>1) ? head/c(tail) : 1
';
y/([{</a-d/;  # replace ( [ { < with a b c d in $_
s/\W/0),/g;   # replace whitespace, punctuation in $_ with the string "0),"
s/\pL\K/(/g;  # place a ( after (\K) each letter (\pL) in $_
$_=eval       # evaluate $_ as a Perl program, storing the result back in $_
              # -p option: print $_ to the user at program end
              # -l option: output a newline whenever printing

The basic idea is that we're converting an input like [()<>] to the Perl program b(a(0),d(0),0), via text processing; Perl's just fine with the trailing comma. Earlier, we defined the functions a, b, c, d to have the same effect as the (), [], {}, <> constructs from the language we're implementing; they each disregard their last argument (the 0 at the end), which is included to ensure that all input parses correctly, and work using the implementation commonly seen in functional programming where the head and tail are processed separately. Because b(e,f,g,0) means e-f-g, i.e. treats its first argument specially, whereas a treats its arguments symmetrically (a(e,f,g,0) means e+f+g), we implement a recursively and b via calling a. c and d have a similar relationship. All four of these functions are very similar, so we generate them at runtime rather than implementing them separately; we store a template that applies to all four functions in a string, then generate the functions by substituting characters into the template.

Because Perl / does floating-point division, the implemented {} does too. I'm assuming that either this is not a problem in its own right, or -Minteger (selecting a language variant where all arithmetic operations are integer operations) is free, because otherwise I'd have to spend extra bytes writing an integer division in Perl, which doesn't seem to be what the problem is fundamentally about. (I think you'd have to spend four bytes changing (shift) to int+(shift); I haven't tested this.)

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

Octave, 215 206 198 bytes

S='sum(x(:))-sum(x(2:end))';Y='(@(x)isempty(x)';c=']) ';[~,~,u]=unique(['()<>[]{}',input('')]);eval([{'sum([',c,[Y,'+fix((',S,')/prod(x(2:end))))(['],c,[Y,'*-1+',S,'*2)(['],c,'prod([',c}{u(9:end)}])

try it online

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

PHP, 315 300 285 258 250 244 bytes

for($s=$argv[1];$r=!$r;)foreach(["(+)1","[-]0","{*}2","</>2]as$p)if(preg_match("#$e$p[0]([-_\d]*)$e$p[2]#",$s,$m)){if(""==$v=strtok($m[1],_))$v=$p[3]-1;while(""<$n=strtok(_))eval("\$v$p[1]=$n;");$s=strtr($s,[$m[$r=0]=>_.$v]);}echo substr($s,1);

replaces sub-expressions with underscore+value; loop breaks when iteration made no replacement.

19 years since I first met C, 17 years working with PHP;
this is the first time that strtok makes sense ... helping to save 24 bytes!

breakdown

for($s=$argv[1];    // take input from argument
    $r=!$r;)        // toggle $r; loop until no replacement has taken place
    foreach(["(+)1","[-]0","{*}2","</>2]as$p) // loop through operations
        if(preg_match("#$e$p[0]([-_\d]*)$e$p[2]#",$s,$m))   // find a match
        {
            if(""==$v=strtok($m[1],_))  // init $v with first token from sub-match
                $v=$p[3]-1;             // if no token, init with default value
            while(""<$n=strtok(_))      // loop through tokens
                eval("\$v$p[1]=$n;");       // operate
            $s=strtr($s,[$m[$r=0]=>_.$v]);  // reset $r; replace match with underscore+value
        }
echo substr($s,1);  // print result
\$\endgroup\$
  • \$\begingroup\$ @Oliver not beating anyone here; but thanks for the fun! \$\endgroup\$ – Titus Nov 19 '16 at 17:59
2
\$\begingroup\$

ES6 (Javascript), 250, 171, 154, 149, 147 bytes

A pure Javascript version.

"Metaprogramming" (like most other answers here), converts input program text into a corresponding Javascript program, by applying a number of direct text substitutions to it (i.e. keeping the program structure as is).

Can probably be golfed further.

UPDATE (v2.1)

  • Minus two bytes (removed parenthesis in the ternary expression)
  • Golfed 5 more bytes off, by using variable for result extraction, and getting rid of extra "[]"

UPDATE (v2)

Just realised that pending commas in ES arrays are totally valid, so the whole comma normalization code could be removed. Also followed an excellent advice by @Titus, on optimizing the alphabet lookup.

UPDATE (v1)

Removed duplicate "replace" alias.

UPDATE (v1)

  • Use a better alphabet: ()=>1+ []=>0 {}=>2* <>=>2/ (each char can be directly re-used as a value or operator)

  • Replaced reduce() with replace() (alphabet mapping)

  • Merged constant inlining, open and closing bracket processing into one step

Golfed (v2.1)

s=>eval("o="+s.replace(/./g,r=>"2+1-3*3/"["()[]{}<>".indexOf(r)]).replace(/\d\D?|\D/g,r=>r[1]?r[0]-2+",":r*1?'([':`].reduce((r,a)=>r${r}a)),`)+"o

Golfed (v1)

(s,A="(2)+[1]-{3}*<3>/")=>eval(s[R="replace"](/./g,r=>A[A.indexOf(r)+1])[R](/\d\D?|\D/g,r=>r[1]?r[0]-2+",":(r[0]*1?'([':`].reduce((r,a)=>r${r}a)),`))[R](/,(\])|,$/g,"$1"))    

Golfed (v0)

([...s],A="(a)b[c]d{e}f<g>h",R="replace")=>eval(s.reduce((r,c)=>r+=A[A.indexOf(c)+1],'')[R](/ab|cd|ef|gh/g,r=>({d:-1,b:'0'}[r[1]]||1) + ',')[R](/[aceg]/g,"([")[R](/[bdfh]/g,r=>`].reduce((r,a)=>r${"+*-/"["bfdh".indexOf(r)]}a)),`)[R](/,(\])|,$/g,"$1"))

Explained (v0)

//BEGIN 

//s - input text, A - alphabet, R - "String.replace()" alias
E=([...s],A="(a)b[c]d{e}f<g>h",R="replace")=>eval(

//Replace input alphabet by a more friendly one, to avoid too much escaping and quoting
// () - ab, [] -cd, {} - ef, <> - gh
s.reduce((r,c)=>r+=A[A.indexOf(c)+1],'')

//Replace no-arg invocations with a corresponding constant value
// () => 0, [] => -1, {} => 1, <> => 1      
[R](/ab|cd|ef|gh/g,r=>({d:-1,b:'0'}[r[1]]||1) + ',')

//Replace opening brackets with "(["
[R](/[aceg]/g,"([")

//Replace closing brackets with "].reduce(...)),"
//An arithmetic operation to apply (+-*/) is chosen based on the bracket type 
//and is substituted into the template 
[R](/[bdfh]/g,r=>`].reduce((r,a)=>r${"+*-/"["bfdh".indexOf(r)]}a)),`)

//Strip excessive commas
[R](/,(\])|,$/g,"$1")
);

//END: eval() the result


Example:
E("{([]<>()<>{})(<><>)}")
=> eval("([([-1,1,0,1,1].reduce((r,a)=>r+a)),([1,1].reduce((r,a)=>r+a))].reduce((r,a)=>r*a))")
=> 4

Test

E=([...s],A="(a)b[c]d{e}f<g>h",R="replace")=>eval(s.reduce((r,c)=>r+=A[A.indexOf(c)+1],'')[R](/ab|cd|ef|gh/g,r=>({d:-1,b:'0'}[r[1]]||1) + ',')[R](/[aceg]/g,"([")[R](/[bdfh]/g,r=>`].reduce((r,a)=>r${"+*-/"["bfdh".indexOf(r)]}a)),`)[R](/,(\])|,$/g,"$1"))

T=(s,a)=>{
    console.log(s,r=E(s),r==a?"OK":"NOT OK");
}

T("()",0)
T("(()())",0) 
T("([][])",-2)
T("({}<>)",2) 
T("({}[])",0) 
T("[]",-1)
T("[[][]]",0) 
T("[()<>]",-1) 
T("{()}",0) 
T("{([]<>)}",0)

Test Output

() 0 OK
(()()) 0 OK
([][]) -2 OK
({}<>) 2 OK
({}[]) 0 OK
[] -1 OK
[[][]] 0 OK
[()<>] -1 OK
{()} 0 OK
{([]<>)} 0 OK
\$\endgroup\$
  • 1
    \$\begingroup\$ Could your v0 version go with s.reduce((r,c)=>r+="abcdefgh"["()[]{}<>".indexOf(c)],'') (-5)? if so, you could remember indexOf in a variable and take the operator from a third string literal. \$\endgroup\$ – Titus Nov 20 '16 at 18:17
2
\$\begingroup\$

Haskell, 184 179 172 161 160 159 151 148 145 bytes

s%(c:i)|elem c")}]>"=([1?(*),sum,1?quot,(-1)?(-)]!!mod(fromEnum c)5$s,i)|(r,j)<-[]%i=(s++[r])%j
[v]%e=(v,e)
(v?_)[]=v
(_?o)s=foldl1 o s
fst.([]%)

Recursive descent, threading the input because Haskell. As usual, the last line is not a definition, but states the function that solves the problem. So to test, put the lines except the last one in a file, load it and do something like this:

*Main> fst.([]%) $ "{([][][])([][])}"
6

Thanks to @Zgarb for inspiration and a lot of detailed hints, and to @Angs for inspiration from his solution and further hints.

It wasn't specified how division should behave with negative integers. Anyway, repeatedly using div seems wrong, as it is not the same as using div once with the product of the remaining values. Now using quot, I get the same results for <{}([][])[]>and <{}{([][])[]}>.

For nice, almost readable code look at the first version. The intermediate versions contain all kinds of nice and intimidating code and help understand this version.

\$\endgroup\$
  • \$\begingroup\$ I think you can save a couple of bytes by defining (!)=(,) and using ! instead of explicit tuples. \$\endgroup\$ – Zgarb Nov 23 '16 at 13:02
  • \$\begingroup\$ If you define m x and d x as 1#x and 0#x, you can merge the cases m[x] and d[x] into one, which I think saves some bytes too. \$\endgroup\$ – Zgarb Nov 23 '16 at 13:17
  • \$\begingroup\$ @Zgarb Thanks! I nearly missed the last pair, without which the ! trick doesn't pay out. Your second suggestion is evil, there goes my almost readable code... Clever! \$\endgroup\$ – Christian Sievers Nov 23 '16 at 13:46
  • \$\begingroup\$ Heh, I just realized that defining s%(c:i)=(s?c,i) and s?')'=sum s etc will be much shorter, since you can get rid of the repeated is. ..No wait, that probably won't work because of the s%(_:i) case. \$\endgroup\$ – Zgarb Nov 23 '16 at 13:50
  • 1
    \$\begingroup\$ Lose the backticks on elem and div, that should save some more bytes. \$\endgroup\$ – Zgarb Nov 23 '16 at 15:30
1
\$\begingroup\$

JavaScript (ES6), no eval, 156 bytes

f=s=>s==(s=s.replace(/(.) ?([- \d]*)[\]})>]/,(_,c,s)=>` `+(s?s.split` `.reduce((l,r)=>c<`<`?l- -r:c<`[`?l/r|0:c<`{`?l-r:l*r):c==`[`?-1:c==`(`?0:1)))?+s:f(s)

Explanation: The regexp finds the first unprocessed closing bracket, and matches the (presumably) corresponding opening bracket and any arguments in between. The arguments are split and reduced according to the operation (sadly '(' and '[' are not the optimal pair for + and -), or if there are no arguments then the appropriate value is calculated (again the matching of characters to values is suboptimal from my point of view). The result is then substituted in with a leading space so as to separate it from other results. The function then calls itself recursively until there are no more changes to make, in which case it returns the resulting value. Example:

[()<>]
[ 0<>]
[ 0 1]
 -1
\$\endgroup\$
  • \$\begingroup\$ f("([][])") => 0 (instead of 2) \$\endgroup\$ – zeppelin Nov 20 '16 at 20:16
  • \$\begingroup\$ Some other tests are also failing for me (you can give the test code in my answer a try), probably due to: f("[]")=>0, as "[]" is a part of every failing test. \$\endgroup\$ – zeppelin Nov 20 '16 at 20:21
  • \$\begingroup\$ @zeppelin Oops, that was due to some bad golfing. I've reverted to a previous version, but sadly that costs me a couple of bytes. \$\endgroup\$ – Neil Nov 20 '16 at 21:24

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.