21
\$\begingroup\$

I see your BIDMAS and raise you a BADMIS

Challenge

Given a set of numbers with operators between them: "5 + 4 * 9 / 3 - 8", return all the possible results of the expression for every permutation of the order of basic operations: [/, *, +, -].

Rules

  • Standard loopholes forbidden
  • I/O
    • Input must be ordered with infix operations, but however that is easiest (string or array)
    • You are not required to support unary operators (e.g. "-3 * 8 / +2")
    • Integers can be replaced by floats for languages that implicitly parse type (e.g. 45 ⟶ 45.0)
    • Output must be all of the possible results of the expression, no specified format or order
  • All of the inputs are valid (e.g. do not need to deal with "7 / 3 + *"). This also means that you will never need to divide by zero.
  • Operators are all left-associative so "20 / 4 / 2" = "(20 / 4) / 2"
  • This is Code Golf so fewest number of bytes wins

Test Cases (With explanation)

  • "2 + 3 * 4" = [14, 20]
    • 2 + (3 * 4) ⟶ 2 + (12) ⟶ 14
    • (2 + 3) * 4 ⟶ (5) * 4 ⟶ 20
  • "18 / 3 * 2 - 1" = [11, 2, 6]
    • ((18 / 3) * 2) - 1 ⟶ ((6) * 2) - 1 ⟶ (12) - 1 ⟶ 11
    • (18 / 3) * (2 - 1) ⟶ (6) * (1) ⟶ 6
    • (18 / (3 * 2)) - 1 ⟶ (18 / (6)) - 1 ⟶ (3) - 1 ⟶ 2
    • 18 / (3 * (2 - 1)) ⟶ 18 / (3 * (1)) ⟶ 6
    • 18 / ((3 * 2) - 1) ⟶ 18 / 5 ⟶ 3.6

Test Cases (Without explanation)

  • "45 / 8 + 19 / 45 * 3" = [6.891666666666667, 18.141666666666666, 0.11111111111111113, 0.01234567901234568, 0.01234567901234568, 5.765740740740741]
  • "2 + 6 * 7 * 2 + 6 / 4" = [112 196 23 87.5]
\$\endgroup\$
  • 2
    \$\begingroup\$ Nice first challenge, though, by the way. \$\endgroup\$ – Shaggy Sep 8 at 22:31
  • \$\begingroup\$ Closely related \$\endgroup\$ – Arnauld Sep 9 at 16:12
  • \$\begingroup\$ Suggested test case 2 - 3 + 4 => [-5, 3] \$\endgroup\$ – Jo King Sep 10 at 2:26
  • \$\begingroup\$ Suggested test case: 2*3-6+2-9/6*8+5/2-9, giving 24 distinct results. \$\endgroup\$ – Arnauld Sep 10 at 9:56
4
\$\begingroup\$

JavaScript (V8),  118  112 bytes

Prints the results.

f=(s,x='',y=x,o='+-*/')=>[...o].map(v=>f(s.split(v).join(x+v+y),x+')',y+'(',o.replace(v,'')))|print(eval(y+s+x))

Try it online!

Or see the deduplicated results.

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

C# (Visual C# Interactive Compiler), 285 bytes

x=>{int c=0,j,t=1,i;for(;c++<25;t=c){var r="*+-/".ToList();for(i=j=1;j++<4;t=t/j+1)(r[j-1],r[t%j])=(r[t%j],r[j-1]);float k(float z,int p=4){char d;int l;float m;return i<x.Count&&(l=r.IndexOf(d=x[i][0]))<p?k((m=k(x[(i+=2)-1],l))*0+d<43?z*m:d<44?z+m:d<46?z-m:z/m,p):z;}Print(k(x[0]));}}

Try it online!

x=>{                                          //Lambda taking in a List<dynamic>
  int c=0,j,t=1,i;                            //A bunch of delcarations jammed together to save bytes
  for(;c++<25;t=c){                           //Loop 24 times (amount of permutations a set of length 4 can have)
    var r="/+*-".ToList();                    //Initialize r as list of operators
    for(i=j=1;j++<4;t=t/j+1)                    //Create the Tth permutation, saving result in r, also reset i to 1
      (r[j-1],r[t%j])=(r[t%j],r[j-1]);
    float k(float z,int p=4) {                //Define local function 'k', with z as current value accumalated and p as current precedence
      char d;int l;float m;                   //Some helper variables
      return i<x.Count                        //If this is not the last number
        &&(l=r.IndexOf(d=x[i][0]))<p?         //  And the current operator's precedence is higher than the current precedence
      k(                                      //  Recursive call with the accumalative value as
        (m=k(x[(i+=2)-1],l))                  //    Another recursive call with the next number following the current operator as seed value,
                                              //    And the next operator's precedence as the precedence value, and store that in variable 'm'
        *0+d<43?z*m:d<44?z+m:d<46?z-m:z/m,    //    And doing the appropriate operation to m and current value ('z')
        p)                                    //  Passing in the current precedence
    :z;                                       //Else just return the current number
    }
    Print(k(x[0]));                           //Print the result of calling k with the first number as starting value
  }
}
\$\endgroup\$
  • \$\begingroup\$ I have fixed it so you do not need to omit duplicates as it is not a fundamental part of the problem as pointed out. \$\endgroup\$ – Freddie R Sep 9 at 13:05
  • 1
    \$\begingroup\$ @Arnauld Fixed at the cost of 4 bytes, it was because my permutations algorithm was a bit wrong \$\endgroup\$ – Embodiment of Ignorance Sep 11 at 4:56
3
\$\begingroup\$

JavaScript (Node.js), 132 bytes

a=>(w=[],F=(b,a)=>b?[...b].map(q=>F(b.replace(q,""),a.replace(eval(`/[\\d.-]+( \\${q} [\\d.-]+)+/g`),eval))):w.push(a))("+-*/",a)&&w

Try it online!

This allows duplicated outputs.

JavaScript (Node.js), 165 161 155 153 152 137 bytes

a=>Object.keys((F=(b,a)=>b?[...b].map(q=>F(b.replace(q,""),a.replace(eval(`/[\\d.-]+( \\${q} [\\d.-]+)+/g`),eval))):F[a]=1)("+-*/",a)&&F)

Try it online!

Takes a string with spaces between operators and numbers.

a=>                                             // Main function:
 Object.keys(                                   //  Return the keys of the -
  (
   F=(                                          //   Index container (helper function):
    b,                                          //    Operators
    a                                           //    The expression
   )=>
    b                                           //    If there are operators left:
    ?[...b].map(                                //     For each operator:
     q=>
      F(                                        //      Recur the helper function - 
       b.replace(q,""),                         //       With the operator deleted
       a.replace(                               //       And all -
        eval(`/[\\d.-]+( \\${q} [\\d.-]+)+/g`), //        Expressions using the operator
        eval                                    //        Replaced with the evaluated result
       )
      )
    )
    :F[a]=1                                     //     Otherwise - set the result flag.
  )(
   "+-*/",                                      //    Starting with the four operators
   a                                            //    And the expression
  )
  &&F
 )
\$\endgroup\$
  • \$\begingroup\$ @JoKing Implemented the fix I've stated before, should output [3, -5] now. \$\endgroup\$ – Shieru Asakoto Sep 10 at 3:42
2
\$\begingroup\$

Perl 6, 92 90 88 bytes

{map {[o](@_)($_)},<* / + ->>>.&{$^a;&{S:g{[\-?<[\d.]>+]+%"$a "}=$/.EVAL}}.permutations}

Try it online!

Takes a string with a space after any operators and returns a set of numbers. This mostly works by substituting all instances of n op n with the eval'ed result for all permutations of the operators.

Explanation:

{                                                                                   }  # Anonymous code block
                    <* / + ->>>.&{                                    } # Map the operators to:
                                  $^a;&{                             }  # Functions that:
                                        S:g{                }      # Substitute all matches of:
                                            \-?<[\d.]>+]+        # Numbers
                                                         %$a     # Joined by the operator
                                                              =$/.EVAL   # With the match EVAL'd
 map {           },                                                    .permutations   # Map each of the permutations of these operators
      [o](@_)        # Join the functions
             ($_)    # And apply it to the input
\$\endgroup\$
  • \$\begingroup\$ You can remove the set, as the condition to eliminate duplicates has been removed. Nice code. \$\endgroup\$ – Freddie R Sep 9 at 13:12
2
\$\begingroup\$

Python 3, 108 bytes

f=lambda e,s={*"+-*/"}:[str(eval(p.join(g)))for p in s for g in zip(*map(f,e.split(p),[s-{p}]*len(e)))]or[e]

Try it online!

The function takes a single string as input and returns a list of possible results.

Ungolfed

def get_all_eval_results(expr, operators={*"+-*/"}):
    results = []
    for operator in operators:
        remaining_operators = operators - {operator}

        # Split expression with the current operator and recursively evaluate each subexpression with remaining operators
        sub_expr_results = (get_all_eval_results(sub_expr, remaining_operators) for sub_expr in expr.split(operator))

        for result_group in zip(*sub_expr_results):   # Iterate over each group of subexpression evaluation outcomes
            expr_to_eval = operator.join(result_group)  # Join subexpression outcomes with current operator
            results.append(str(eval(expr_to_eval)))   # Evaluate and append outcome to result list of expr
    return results or [expr]  # If results is empty (no operators), return [expr]

Try it online!

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

Jelly, 30 bytes

œṡ⁹¹jṪḢƭ€jŒVɗßʋFL’$?
Ḋm2QŒ!烀

Try it online!

A pair of links. The second one is the main link, and takes as its argument a Jelly list of floats/integers interspersed with the operators as characters. This is a flattened version of the way Jelly takes its input when run as a full program with command line arguments. The return value of the link is a list of list of single member lists, each of which is a possible value for the expression.

Explanation

Helper link

Takes a list of floats/integers alternating with operators (as characters) as its left argument and an operator as a character as its right argument; returns the input list after evaluating numbers separated by the relevant operator, working left to right.

œṡ⁹                  | Split once by the right argument (the operator currently being processed)
                   ? | If:
                  $  | - Following as a monad
                L    |   - Length
                 ’   |   - Decremented by 1
              ʋ      | Then, following as a dyad:
   ¹                 | - Identity function (used because of Jelly’s ordering of dyadic links at the start of a dyadic chain)
    j       ɗ        | - Join with the following as a dyad, using the original left and right arguments for this chain:
     ṪḢƭ€            |   - Tail of first item (popping from list) and head from second item (again popping from list); extracts the numbers that were either side of the operator, while removing them from the split list
         j           |   - Joined with the operator
          ŒV         |   - Evaluate as Python (rather than V because of Jelly’s handling of decimals with a leading zero)
            ß        | - Recursive call to this helper link (in case there are further of the same operator)
               F     | Else: Flatten

Main link

Takes a list of floats/integers alternating with operators (as characters)

Ḋ         | Remove first item (which will be a number)
 m2       | Every 2nd item, starting with the first (i.e. the operators)
   Q      | Uniquify
    Œ!    | Permutations
      烀 | For each permuted list of operators, reduce using the helper link and with the input list as the starting point
\$\endgroup\$
1
\$\begingroup\$

Python 2, 182 172 bytes

import re
def f(s,P=set('+-/*')):
 S=[eval(s)]
 for p in P:
	t=s
	while p+' 'in t:t=re.sub(r'[-\d.]+ \%s [-\d.]+'%p,lambda m:`eval(m.group())`,t,1)
	S+=f(t,P-{p})
 return S

Try it online!

Takes input with ints formatted as floats, as per "Integers can be replaced by floats for languages that implicitly parse type".

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

Julia 1.2, 88 (82) bytes

f(t)=get(t,(),[f.([t[1:i-1];t[i+1](t[i],t[i+2]);t[i+3:end]] for i=1:2:length(t)-2)...;])
julia> f([2, +, 3, *, 4])
2-element Array{Int64,1}:
 20
 14

julia> f([18, /, 3, *, 2, -, 1])
6-element Array{Float64,1}:
 11.0
  6.0
  2.0
  3.6
  6.0
  6.0

Takes a tape in the form of a vector of numbers and infix functions, evaluates each single function call and recursively passes each resulting tape back to itself until only a single number is left. Unfortunately, get(t, (), ...) doesn't work properly in Julia 1.0, so a newer version is needed.

Six bytes can be saved, if a bunch of nested arrays is acceptable as an output:

f(t)=get(t,(),f.([t[1:i-1];t[i+1](t[i],t[i+2]);t[i+3:end]] for i=1:2:length(t)-2))

Output:

julia> f([18, /, 3, *, 2, -, 1])
3-element Array{Array{Array{Float64,1},1},1}:
 [[11.0], [6.0]]
 [[2.0], [3.6]] 
 [[6.0], [6.0]] 
\$\endgroup\$
0
\$\begingroup\$

Perl 5 (-alp), 89 bytes

my$x;map{$x.=$`.(eval$&.$1).$2.$"while/\d+[-+*\/](?=(\d+)(.*))/g}@F;$_=$x;/[-+*\/]/&&redo

TIO

or unique values, 99 bytes

my%H;map{$H{$`.(eval$&.$1).$2}++while/\d+[-+*\/](?=(\d+)(.*))/g}@F;$_=join$",keys%H;/[-+*\/]/&&redo
\$\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.