65
\$\begingroup\$

Say I have an expression:

9 * 8 + 1 - 4

This expression can be interpreted in six different ways, depending on operator precedence:

(((9 * 8) + 1) - 4) = 69 (* + -)
((9 * 8) + (1 - 4)) = 69 (* - +)
((9 * (8 + 1)) - 4) = 77 (+ * -)
(9 * ((8 + 1) - 4)) = 45 (+ - *)
((9 * 8) + (1 - 4)) = 69 (- * +)
(9 * (8 + (1 - 4))) = 45 (- + *)

Say I'm a developer, and I don't feel like memorizing precedence tables, etc., so I'm just going to guess.

In this case, the largest margin of error would be 45-77, which is a difference of 32. This means that my guess will only be off by a maximum of 32.

The challenge

Given an expression consisting of numbers and +, -, *, / (integer division) and %, output the absolute difference of the largest and smallest possible value for that expression, based on the precedence of operators.

Specifications

  • The input expression will not contain parenthesis and every operator is left-associative.
  • The input expression will only contain nonnegative integers. However, subexpressions may evaluate to negatives (e.g. 1 - 4).
  • You can take the expression in any reasonable format. For example:
    • "9 * 8 + 1 - 4"
    • "9*8+1-4"
    • [9, "*", 8, "+", 1, "-", 4]
    • [9, 8, 1, 4], ["*", "+", "-"]
  • The input will contain at least 1 and at most 10 operators.
  • Any expression that contains a division or modulo by 0 should be ignored.
  • You can assume that modulo will not be given negative operands.

Test Cases

9 * 8 + 1 - 4             32
1 + 3 * 4                  3
1 + 1                      0
8 - 6 + 1 * 0              8
60 / 8 % 8 * 6 % 4 * 5    63
\$\endgroup\$
  • 1
    \$\begingroup\$ @AndersKaseorg It looks like you're treating % as having two different precedences in your second example. \$\endgroup\$ – Esolanging Fruit Jul 9 '17 at 0:38
  • 1
    \$\begingroup\$ Three of the 'six' are identical, as are another two. That leaves three actual cases, not six. \$\endgroup\$ – user207421 Jul 9 '17 at 12:13
  • 3
    \$\begingroup\$ how % operator works on negative numbers? The way like C or Python or something else? \$\endgroup\$ – tsh Jul 9 '17 at 14:33
  • 8
    \$\begingroup\$ Just saying, you don't have to add the "and I'm lazy" part to your description. Just saying you're a developer is enough. :) \$\endgroup\$ – Gryphon Jul 9 '17 at 16:57
  • 1
    \$\begingroup\$ @tsh Any behavior. Do whatever you want. You can make demons fly out of my nose. \$\endgroup\$ – Esolanging Fruit Jul 10 '17 at 7:11

13 Answers 13

27
\$\begingroup\$

Python 2, 171 156 bytes

lambda a:max(e(a))-min(e(a))
u=')%s('
def e(a,t=u):
 try:b=[eval(a)]
 except:b=[]
 return sum([e('(%s)'%a.replace(o,t%o),u%t)for o in"+-*/%"if' '+o in a],b)

Try it online!

How it works

We surround each operator with a different number of outward-facing pairs of parentheses to simulate different precedences (in all possible ways), and wrap enough inward-facing pairs of parentheses around the entire string, to get an expression we can eval. For example, with

+)+(
*))*((
-)))-(((

we get

9 * 8 + 1 - 4(((9 ))*(( 8 )+( 1 )))-((( 4))) = 77.

\$\endgroup\$
  • \$\begingroup\$ You can save 2 bytes by moving the or outside the sum to remove a layer of square brackets: sum([...],[])or[eval(a)] instead of sum([...]or[[eval(a)]],[]) \$\endgroup\$ – Strigoides Jul 9 '17 at 6:29
  • \$\begingroup\$ @Strigoides I had been thinking that wasn’t equivalent, because the sum may be empty without its argument being empty—however, it’s actually fine because the eval must fail in that case. Thanks. \$\endgroup\$ – Anders Kaseorg Jul 9 '17 at 7:24
8
\$\begingroup\$

Jelly, 126 bytes

"Operator Precedence? Parentheses? Pah, who needs that?" - challenges of using Jelly for an operator precedence challenge.

⁾[]i$€Ḥæ%3+\¬œp¹Ḋ€
ǵḟØDO%9µÐṀṪɓœṣ⁹,ṚÑj@¥/
ǵVṾµ1ĿFḟØDḟ”-Lµ?ÐL
5Ḷx@€“]“[”ż⁸j/€,@y³Fɓ³i@€Ṁ’x@“[“]”jÇ
“+_×:%”Œ!Ç€µṾL_L’ỊµÐfV€ṢIS

Try it online!

Input is taken as a string, e.g. "1+2_3×4:5%6". Note multiplication uses "×" instead of "*", division uses ":" instead of "/", and subtraction uses "_" instead of "-".

How it Works The program is divided into three parts: generating all expressions of different operator precedence, evaluating them, and returning the difference between the maximum and minimum.

All expressions are generated with the code:

5Ḷx@€“]“[”ż⁸j/€,@y³Fɓ³i@€Ṁ’x@“[“]”jÇ (4) helper link: returns all outputs given a permutation. Input e.g. "_+:×%"
5Ḷx@€“]“[”           - repeat outer brackets to get ["",""],["]","["],["]]","[["],["]]]","[[["],["]]]]","[[[["]
          ż⁸j/€      - insert the operations in to get "_","]+[","]]:[[","]]]×[[[","]]]]%[[[["
               ,@    - turn this into a mapping equivalent to "_"↦"_","+"↦"]+[",":"↦"]]:[[","×"↦"]]]×[[[","%"↦"]]]]%[[[["
                 y³F - use this mapping to get the right number of outward brackets on each operation. e.g. "1]+[3]]]×[[[4"
ɓ³i@€Ṁ’x@“[“]”j      - add the right number of brackets to the end to get e.g."[[[1]+[3]]]×[[[4]]]"
               Ç     - this calls the link which evaluates the expression
“+_×:%”Œ!Ç€                          (5a) main link. Input e.g. "1+3×4"
“+_×:%”                                 - the string "+_×:%"
       Œ!                               - all permutations
         ǀ                             - apply link (4) to each permutation

The links are evaluated with this (I could probably improve with a different structure):

⁾[]i$€Ḥæ%3+\¬œp¹Ḋ€      (1) Helper link: Outputs a list of expressions within brackets, e.g. "[[[1]+[3]]]×[[[4]]]"↦"[[1]+[3]]","[[4]]"
⁾[]i$€Ḥæ%3                 - map "[" to 2, "]" to -2, and any other character to 0.
          +\¬              - cumulative sum negated: 1s at characters not in brackets (includes opening brackets), 0s otherwise (includes closing brackets)
             œp¹           - partition the input, not including borders, based on the sum to get "[[[1]+[3]]","[[[4]]"
                Ḋ€         - remove opening brackets
ǵḟØDO%9µÐṀṪɓœṣ⁹,ṚÑj@¥/ (2) Return the input to this link with one of the expressions from (1) evaluated
ǵVṾµ1ĿFḟØDḟ”-Lµ?ÐL     (3) link called from part 1: Evaluates expressions
 µ  µ          µ?          - if:
     1ĿFḟØDḟ”-L            - the input contains no operators within brackets:         
  VṾ                         - evaluate this one expression with normal Jelly calculation and return to string
                           - otherwise:
Ç                            - evaluate one subexpression using link (2)
                  ÐL       - repeat this until a single output is determined

The difference between the maximum and minimum is computed with the code in link (5):

µṾL_L’ỊµÐfV€ṢIS (5b) determine difference between minimum and maximum
µ      µÐf        - filter out outputs involving division or modulo by 0. Determined with:
 ṾL_L’Ị           - actual numbers have their unevaled form Ṿ no more than one byte longer than the non-unevaled form.
          V€      - evaluate each of these valid numbers to get integers from strings
            Ṣ     - sort
             IS   - return the sum of all difference between consecutive elements.
\$\endgroup\$
  • 4
    \$\begingroup\$ Probably the longest Jelly answer (without embedded data) I've ever seen. Well done! \$\endgroup\$ – Keyu Gan Jul 10 '17 at 1:51
  • \$\begingroup\$ @KeyuGan If you want longer Jelly answers, look at this answer. I can't think of any other long Jelly answers without compression. \$\endgroup\$ – fireflame241 Jul 10 '17 at 1:57
6
\$\begingroup\$

Python 2, 235 234 233 226 bytes

-1 byte (and a fix) thanks to Anders Kaseorg!

-7 bytes thanks to Step Hen!

from itertools import*
def f(e,a=()):
 for o in permutations("+-*/%"):
	l=e[:]
	for c in o:
	 for i in range(len(l),0,-1):
		if l[i-1]==c:l[i-2:i+1]=["("+l[i-2]+l[i-1]+l[i]+")"]
	try:a+=eval(*l),
	except:0
 print max(a)-min(a)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Function submissions must be reusable. You can fix that problem by letting a be a tuple instead of a list, and even save 1 byte by doing so (a=(), a+=eval(*l),). \$\endgroup\$ – Anders Kaseorg Jul 9 '17 at 1:11
  • \$\begingroup\$ Huh, TIL. Thanks for the tip! \$\endgroup\$ – notjagan Jul 9 '17 at 1:14
  • 1
    \$\begingroup\$ Since you're in Python 2, you can save some bytes by alternating spaces and tabs for indentation (in this case, 2 spaces -> tab, three spaces -> tab + space, four spaces -> two tabs) Try it online! \$\endgroup\$ – Stephen Jul 9 '17 at 2:11
4
\$\begingroup\$

Haskell 582 bytes

This didn't go nearly as well as I hoped it would...

import Data.List
f x=case x of '+'->(+);'-'->(-);'*'->(*);'/'->div;_->rem
e _ s[]=s
e 1 s(')':x:a)|0<-(read$e 0""a),(x=='%'||x=='/')=""|""<-(e 0""s)=""|""<-(e 0""a)=""|0<3=show$(f x)(read$e 0""s)$read$e 0""a
e 1 s")"=e 0""s
e n s(')':a)=e(n-1)(s++")")a
e 0 s('(':a)=e 1 s a
e n s('(':a)=e(n+1)(s++"(")a
e n s(x:a)=e n(s++[x])a
n?s=take n$cycle s
a!b=e 0""(9?"("++(concat$zipWith(++)a(b++[[]]))++9?")")
c#b|l<-[read x|x<-map(c!)(a b),x/=""]=maximum l-minimum l
a c=transpose$map(\x->map((\(Just q)->q).lookup x)$map(\a->zipWith(\x y->(y,x?")"++y:x?"("))[1..5]a)$permutations"+-*%/")c

Try It Online!

Trying to golf a long program just makes me write bad code :(

I tried to use Anders' algorithm in Haskell, but it got out of my control

The function e is like a specific case of eval. (#) takes a list of strings representing integers and a string of operators and returns the difference between the maximum and minimum possible values. e.g

(#) ["9","8","1","4"] "*+-" => 32
\$\endgroup\$
  • 1
    \$\begingroup\$ If you renamed # to ##, you could rename e to (#), like so: (n#s)(x:a)=... \$\endgroup\$ – Esolanging Fruit Jul 10 '17 at 9:13
  • \$\begingroup\$ If you alias the following three commonly used functions you can save a further 6 bytes. r=read;j=zipWith;o=map and then replace those functions with the letter aliases. \$\endgroup\$ – maple_shaft Jul 10 '17 at 13:46
  • \$\begingroup\$ Also I am counting 594 bytes, not 582. \$\endgroup\$ – maple_shaft Jul 10 '17 at 13:48
3
\$\begingroup\$

Pyth, 45 bytes

KS.nm.x.vj\ u.nm+*H/kHckHGd]s.iFQY.p_{eQ-eKhK

I'm sure that a lot more optimization can be done, but I like it so far.

Takes input like this: [9, 8, 1, 4], ["*", "+", "-"].

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Can you add an explanation? \$\endgroup\$ – Jim Jul 10 '17 at 16:14
2
\$\begingroup\$

Mathematica, 186 164 159 bytes

eMax@#-Min@#&[Fold[#//.{m___,x_,#2[[0]],y_,n___}:>{m,x~Last@#2~y,n}&,e,#]&/@Permutations@{"+"@Plus,"-"[#-#2&],"*"@Times,"/"@Quotient,"%"@Mod}/. 0/0|1/0->{}]

\[Function] takes 3 bytes.

Some alternatives (keeps bytecount the same)

#2-#&@MinMax[...] to replace Max@#-Min@#&[...]

Head@#2 to replace #2[[0]]

Try it online at http://sandbox.open.wolframcloud.com : enter ( .... )[{60, "/", 8, "%", 8, "*", 6, "%", 4, "*", 5}] with .... replaced by code above for test case 60 / 8 % 8 * 6 % 4 * 5. Press Shift + enter to evaluate.

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

Javascript, 280 bytes

Note: The integer division rounds using the floor function, which means that negative numbers round away from zero.

This solution is based on this answer.

b=>(Math.max(...(f=(a,h="(",i=")",r=[...a[d="replace"](/[^-+*/%]|(.)(?=.*\1)/g,"")])=>(r[0]?(r.map((c,j)=>s=s.concat(f(h+a[d](RegExp("\\"+(n=r.concat()).splice(j,1),"g"),i+c+h)+i,h+"(",i+")",n)),s=[]),s):(a=eval(`(${a})`[d](/\(/g,"Math.floor(")))==a&&1/a?a:r))(b))-Math.min(...f(b)))

Example code snippet:

g=

b=>(Math.max(...(f=(a,h="(",i=")",r=[...a[d="replace"](/[^-+*/%]|(.)(?=.*\1)/g,"")])=>(r[0]?(r.map((c,j)=>s=s.concat(f(h+a[d](RegExp("\\"+(n=r.concat()).splice(j,1),"g"),i+c+h)+i,h+"(",i+")",n)),s=[]),s):(a=eval(`(${a})`[d](/\(/g,"Math.floor(")))==a&&1/a?a:r))(b))-Math.min(...f(b)))

for(k=0;k<5;k++)
  v=["9*8+1-4","1+3*4","1+1","8-6+1*0","60/8%8*6%4*5"][k],
  console.log(`g(${v}) = ${g(v)}`)

\$\endgroup\$
  • \$\begingroup\$ How hard would it be to make it compliant by replacing the a/b case with a/b|0? \$\endgroup\$ – trlkly Jul 10 '17 at 11:45
  • \$\begingroup\$ @trlkly a/b|0 stops the divide/modulo 0 error check, but Math.floor(a/b) worked \$\endgroup\$ – Herman L Jul 10 '17 at 12:43
2
\$\begingroup\$

Haskell, 254 bytes

import Data.List.Split
import Data.List
f s=(-)<$>maximum<*>minimum$permutations(zip"+-*/%"[p(+),p(-),p(*),c$div,c$mod])>>=(s!)
p=((pure.).)
c o a b=[o a b|b/=0]
s![]=[read s]
s!((x,o):y)=case splitOn[x]s>>=(!y)of[]->[];l->l?o
[a]?_=[a]
(a:b)?o=b?o>>=o a

Try it online!

Input is a whole string, such as 4+5 * 2. It generates all permutations of operations, and for each permutation splits the string recursively. It filters divisions by 0 with the list monad.

\$\endgroup\$
  • \$\begingroup\$ (%) is modulus operator. It is remainder of a division operation between the left argument and the right argument. \$\endgroup\$ – maple_shaft Jul 10 '17 at 13:57
1
\$\begingroup\$

Python 2, 262 256 254 bytes

from itertools import*
def r(s,o):
 try:
  while o in s:i=s.index(o)-1;s[i:i+3]=[`eval(''.join(s[i:i+3]))`]
  return s
 except:0
def f(s):
 u=[int(v[0])for v in [reduce(r,O,s.split(' '))for O in permutations('*/%+-')]if v!=None];return abs(max(u)-min(u))

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Save some bytes by also using tabs: Try it online! \$\endgroup\$ – Stephen Jul 9 '17 at 2:12
  • 1
    \$\begingroup\$ Save one byte by changing in [ to in[ (space isn't needed) \$\endgroup\$ – Zacharý Jul 9 '17 at 15:12
1
\$\begingroup\$

PHP, 316 bytes

<?for(;$t++<54322;)count_chars($t,3)!=12345?:$p[]=$t;foreach($p as$x){for(list($z,$q)=$_GET,$b=1,$i=0;$y=strtr($x,12345,"/%*+-")[$i++];)while(-1<$k=array_flip($q)[$y]){$n=$k+1;if($b&=$z[$n]||ord($y)%10<6)eval("\$z[$k]=$z[$k]$y$z[$n]^0;");($s=array_splice)($z,$n,1);$s($q,$k,1);}$b?$r[]=$z[0]:0;}echo max($r)-min($r);

Try it online!

Expanded
for(;$t++<54322;)
  count_chars($t,3)!=12345?:$p[]=$t;
foreach($p as$x){
  for(list($z,$q)=$_GET,$b=1,$i=0;$y=strtr($x,12345,"/%*+-")[$i++];)
    while(-1<$k=array_flip($q)[$y]){
      $n=$k+1;
      if($b&=$z[$n]||ord($y)%10<6)
        eval("\$z[$k]=$z[$k]$y$z[$n]^0;");
      ($s=array_splice)($z,$n,1);
      $s($q,$k,1);
    }
  $b?$r[]=$z[0]:0;
}
echo max($r)-min($r);
\$\endgroup\$
  • \$\begingroup\$ The lase case is 63. Your mistake due to giving the same operator a different precedence in different parts of one expression \$\endgroup\$ – H.PWiz Jul 10 '17 at 0:28
0
\$\begingroup\$

Python 3, 284 bytes

Edit: seems like something's wrong with evaluating the last example. I'll look into it tomorrow.

Another Python answer. Couldn't outgolf everyone else, but I spent too long on this to not put it up.

from itertools import*
def f(n,o):
 z=[]
 for p in permutations("+-*/%"):
  try:
   p,x,a=[*p],n[:],o[:]
   while(p):
    for i,d in enumerate(a):
     if d==p[0]:x[i+1]=str(eval(x[i]+d+x[i+1]));x.pop(i);a.pop(i)
    p.pop(0)
   z+=x
  except:0
 z=[*map(float,z)];return max(z)-min(z)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ while(p) can become while p for one byte saved. \$\endgroup\$ – Zacharý Jul 9 '17 at 15:10
0
\$\begingroup\$

Clojure (+ combinatorics), 342 377 + 41 = 418 bytes

+35 bytes because of a bug.

(fn[x y](let[l filter s first z #(l(fn[y]y)%)r(sort(z(for[e(q/permutations[+ - * quot mod])](try(loop[t e m y a x](if(=[]t)(s a)(let[j(s t)i(reverse(keep-indexed #(if(= j %2)%)m))](recur(rest t)(l #(not= j %)m)(loop[d 0 h a](if(=(count i)d)h(let[c(nth i d)f(inc c)](recur(inc d)(vec(z(assoc h c(j(nth h c)(nth h f))f nil)))))))))))(catch Exception _ nil)))))](-(last r)(s r))))

Try it online!

For this function to work, you have to use the clojure.math.combinatorics library (41 bytes):

(use '[clojure.math.combinatorics :as q])

Nuances:

This function is an anonymous function, which means you must do this to use it:

((fn[x y]...) numbers operators)

Also, I'm using the word quot instead of / (since Clojure does fraction division by default), and mod instead of %.

Ungolfed program:

(defn precedence [numbers operators]
  (let [results
        (sort
          (for [permute (c/permutations [+ - * / mod])]
            (loop [p-temp permute
                  o-temp operators
                  n-temp numbers]
              (if (empty? o-temp) (first n-temp)
                (let [first-p (first p-temp)
                      indices (reverse (keep-indexed #(when (= first-p %2) %) o-temp))]
                  (recur
                    (rest p-temp)
                    (filter #(not= first-p %) o-temp)
                    (loop [ind 0
                          n-through n-temp]
                      (if (= ind (count indices)) n-through
                        (let [current-ind (nth indices ind)]
                          (recur
                            (inc ind)
                            (vec
                              (filter #(not (nil? %))
                                (assoc n-through
                                  current-ind (first-p (nth n-through current-ind) (nth n-through (inc current-ind)))
                                  (inc current-ind) nil)))))))))))))]
    (- (last results) (first results))))
\$\endgroup\$
  • \$\begingroup\$ I think you can just say "Closure + Combinatorics" and not have to score the use statement. \$\endgroup\$ – Esolanging Fruit Jul 10 '17 at 5:04
  • \$\begingroup\$ @Challenger5 I believe you'd better write it in the description, because by default, The characters used to import the library will likely be counted codegolf.meta.stackexchange.com/questions/10225/… \$\endgroup\$ – Keyu Gan Jul 10 '17 at 8:20
  • \$\begingroup\$ @KeyuGan You're right - I misunderstood that Meta consensus. I think the require needs to be included in the code and its length should be added to the byte count. \$\endgroup\$ – Esolanging Fruit Jul 10 '17 at 9:05
  • \$\begingroup\$ @Challenger5 So I need to add 41 bytes into my bytecount, right? OK. \$\endgroup\$ – Qwerp-Derp Jul 10 '17 at 10:15
  • \$\begingroup\$ @Qwerp-Derp Yes, but the import is part of your code, and you can golf it. \$\endgroup\$ – Esolanging Fruit Jul 11 '17 at 2:13
0
\$\begingroup\$

JavaScript (ES6), 210 bytes

Input as an array of numbers and operators

k=>(m=n=-k,r=(o,k,j=0)=>{for(o||(m=m>k?m:k,n=n<k?n:k);q=o[j++];(q>'%'&q<'/'||z)&&r(o.slice(0,j-1)+o.slice(j),h))for(h=[...k],z=1;i=h.indexOf(q)+1;h.splice(i-2,3,eval(a=h[i-2]+q+h[i])|0))z*=h[i]})('+-*/%',k)|m-n

Less golfed

k=>(
  m = n = NaN,
  r =(o, k, j=0) => {
    // try all operators in o
    for(;q = o[j]; j++)
    {  
      // q : current operator, 
      // look for q inside the expression to evaluate
      for(h = [...k], z = 1; i = h.indexOf(q) + 1;)
      {
        a = h[i - 2]
        b = h[i]
        z *= b // trace if any second operand is zero
        // subst subexpression with its value
        h.splice(i - 2, 3, eval(a + q + b) | 0)
      }
      // now all subexp involving current operator are evaluated
      // the result is ok if current operator is not % or /
      //  OR if no second operand was zero
      (q > '%' & q < '/' || z) && 
        // try again recursively
        // using the remaining operators and the remaining expression
        r(o.slice(0, j) + o.slice(j+1), h) 
    }
    // if no more operators to try, check max and min
    // k is an array with 1 element, can be used like a single number
    o || (
      m = m > k ? m : k, 
      n = n < k ? n : k
    )
  },
  r('+-*/%', k),
  m-n
)

Test

var F=
k=>(m=n=-k,r=(o,k,j=0)=>{for(o||(m=m>k?m:k,n=n<k?n:k);q=o[j++];(q>'%'&q<'/'||z)&&r(o.slice(0,j-1)+o.slice(j),h))for(h=[...k],z=1;i=h.indexOf(q)+1;h.splice(i-2,3,eval(a=h[i-2]+q+h[i])|0))z*=h[i]})('+-*/%',k)|m-n

function update() {
  var input = I.value.match(/\d+|\S/g)
  var result = F(input)
  O.textContent = I.value + ' -> ' + result + ' (max:'+m+' min:'+n+')'
}

update()
<input id=I value="60 / 8 % 8 * 6 % 4 * 5" oninput='update()'>
<pre id=O></pre>

\$\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.