Find operations required to get result

Question

So task is simple, given array of numbers and result, you need to find what operations you need to use on numbers from array , to obtain requested result.

Let's make it simple for start, and allow only basic operations such as: addition, subtraction, multiplication and division.

Example:

Input  : [5,5,5,5,5] 100
Output : 5*5*5-5*5

To give some advantage to languages like Java, request is to implement function, not entire program, and result can be return via parameter or print to console.

Code is scored based on amount bytes, and as it's golf code challenge, lowest score wins.

Another requirment is You can get additional -10 points if for array contains only digids, support solutions where you could construct numbers from following digits. Ie

Input  : [1,2,3,4,5] 0
Output : 12-3-4-5

Note that, provided outputs are proposed outputs, some cases might have more than one solution. It's up to you will you provide one or more solutions for given task.

EDIT: Result has to be valid from mathematical point of view, hence division is rational division, not integer, and operation precedence is same as in classical math (first multiplication and division then addition and subtraction).

Answer 1

Pyth, 23 bytes

Due to security reasons, * and / won't evaluate online, but they theoretically work.

fqeQvTms.ihQd^"+-*/"lth

Test suite with only + and -.

Answer 2

Oracle SQL 11.2, 322 304 270 bytes

SELECT o FROM(SELECT REPLACE(SUBSTR(:1,1,1)||REPLACE(SYS_CONNECT_BY_PATH(a||SUBSTR(:1,LEVEL*2+1,1),','),','),'_')o,LEVEL l FROM(SELECT SUBSTR('+-*/_',LEVEL,1)a FROM DUAL CONNECT BY LEVEL<6)CONNECT BY LEVEL<LENGTH(:1)/2)WHERE:2=dbms_aw.eval_number(o)AND l>LENGTH(:1)/2-1;

:1 is the list of digits
:2 is the result searched

Un-golfed :

SELECT o
FROM   (
         SELECT REPLACE(SUBSTR(:1,1,1)||REPLACE(SYS_CONNECT_BY_PATH(a||SUBSTR(:1,LEVEL*2+1,1),','),','),'_')o,LEVEL l 
         FROM ( -- Create one row per operator 
                SELECT SUBSTR('+-*/_',LEVEL,1)a FROM DUAL CONNECT BY LEVEL<6
              ) CONNECT BY LEVEL<LENGTH(:1)/2  -- Create every combination of operators, one per ','
)
WHERE :2=dbms_aw.eval_number(o)  -- filter on result = evaluation
  AND l>LENGTH(:1)/2-1           -- keep only expressions using every digits

Answer 3

TSQL(sqlserver 2016) 310 294 280 bytes

What a wonderful opportunity to write ugly code:

Golfed:

DECLARE @ varchar(max)= '5,5,5'
DECLARE @a varchar(20) = '125'

,@ varchar(max)='';WITH D as(SELECT @a a UNION ALL SELECT STUFF(a,charindex(',',a),1,value)FROM STRING_SPLIT('*,+,./,-,',',')x,d WHERE a like'%,%')SELECT @+=a+','''+REPLACE(a,'.','')+'''),('FROM D WHERE a not like'%,%'EXEC('SELECT y FROM(values('+@+'null,null))g(x,y)WHERE x='+@b)

Try it online

Readable:(insertion of decimal point(.) and removal of the same is necessary in order for sql to accept that 4/5 is not 0 - well removal is for the people testing it)

DECLARE @a varchar(max)= '5,5,5'
DECLARE @b varchar(20) = '5'

,@ varchar(max)=''
;WITH D as
(
  SELECT @a a
  UNION ALL
  SELECT STUFF(a,charindex(',',a),1,value)
  FROM STRING_SPLIT('*,+,./,-,',',')x,d
  WHERE a like'%,%'
)
SELECT @+=a+','''+REPLACE(a,',','')+'''),('
FROM D
WHERE a not like'%,%'

EXEC('SELECT y FROM(values('+@+'null,null))g(x,y)WHERE x='+@b)

This solution can also handle these types of input:

Input :[1,2,3,4,5] 0 Output : 12-3-4-5

Answer 4

JavaScript (ES6), 165 147 bytes

a=>o=>(c=[],i=c=>{for(j=0;!((c[j]?++c[j]:c[j]=1)%5);)c[j++]=0},eval(`while(eval(e=(a+'').replace(/,/g,(_,j)=>'+-*/'.charAt(c[~-j/2])))!=o)i(c);e`))

Nested eval... lovely.

f=a=>o=>(c=[],i=c=>{for(j=0;!((c[j]?++c[j]:c[j]=1)%5);)c[j++]=0},eval(`while(eval(e=(a+'').replace(/,/g,(_,j)=>'+-*/'.charAt(c[~-j/2])))!=o)i(c);e`))
console.log(f([5,5,5,5,5])(100))
console.log(f([1,2,3,4,5])(0))
console.log(f([3,4])(0.75))
console.log(f([3,4,5,6])(339))

Answer 5

Python 3, 170 155 bytes

from itertools import*
def f(n,o):print({k for k in[''.join(map(str,sum(j,())))[1:]for j in[zip(x,n)for x in product('+-*/',repeat=len(n))]]if eval(k)==o})

Create a generator with all possible orders of the operators, combine that with the numbers, then eval until we get the answer.

https://repl.it/C2F5

Answer 6

Python, 195 186 bytes

Here's an atrocious way of doing it.

def x(i,r):
 t=""
 from random import choice as c
 while True:
  for j in i:
   t+=str(j)
   if c([0,1]):t+="."+c("+-/*")
  t=t.strip("+-*/.")+"."
  v=eval(t)
  if v == r:print t
  t=""

The function x accepts an argument of a list and a result - x([1,2,3,4,5], 15) for example.

The program begins a loop where we begin randomly selecting if we should append "+", "-", "*", or "/" between each number, or if we should concatenate them together. This seemed like a more concise option than actually going through permutations and trying every combination to find every result, and although it takes longer to run and is much less efficient. (Fortunately that's not a concern in this context!)

It also appends "." to each number to avoid doing integer-rounded operations like 6/4 = 1. It then evals our expression and determines if the result equal to what we are expecting, and if so, outputs the expression.

This program never exits - it will keep continually outputting results until killed.

EDIT 1: Remove unnecessary newlines where one-line if statements can be used.

Answer 7

Matlab, 234 238 258 bytes

I'm assuming based on the limitations of the other answers that the number order of the input array is maintained by fiat.

n=length(x)-1
k=n*2+2
p=unique(nchoosek(repmat('*-+/',1,n),n),'rows')
p=[p char(' '*~~p(:,1))]'
c=char(x'*~~p(1,:))
o=p(:,r==cellfun(@eval,mat2cell(reshape([c(:) p(:)]',k,[]),k,0|p(1,:))))
reshape([repmat(x',size(o,2),1) o(:)]',k,[])'

This code takes a string of numbers x, say x = '12345' and a result r, say r = 15 and returns all of the strings of expressions you can evaluate to get r from x using the four operators.

I've used two different length-equivalent ways of avoiding using ones(length())-type or repmat(length())-type expressions: ~~p(1,:) which returns not-not values in p (i.e., a list of 1s the samelength as the first dimension of p) and 0|p(:,1) which returns 0 or is-there-a-value-in-p (i.e., a list of 1s the same length as the second dimension of p).

Matlab doesn't have an nchoosek with replacement method, so I've duplicated the operators the correct number of times, computed the whole space of nchoosek for that larger selection of operators, and then used a unique call to pare the result down to what it should be (removing equivalent combinations like '***+' and '***+'). I add a trailing space to match the length of the input vector for concatenation purposes and then compose the operator strings with the input strings into the columns of a matrix. I then evaluate the expressions columnwise to get results and find the order of operators that corresponds to those columns with results that match our input r.

Test: x = '12345', r = 15:

1*2*3+4+5 
1+2+3+4+5 
1-2*3+4*5 

If I had to take an array of double precision values, I'd need x = num2str(x,'%d'); in order to convert the digits to a string, adding 21 (20 without the ;) to my score. *The extra bytes were semicolons I left in purely so that anyone running this code won't see their command prompt blow up with long arrays. Since my edit produces a giant pile of warnings about logicals and colon-operands now anyway, I've removed the semicolons in the new version.

Edit 2: Forgot to replace a 2*n+2 with k.

Old answer:

n=length(x)-1;
p=unique(nchoosek(repmat(['*','-','+','/'],1,n),n),'rows');
l=length(p);
p=[p repmat(' ',l,1)]';
c=reshape([repmat(x',l,1) p(:)]',n*2+2,[]);
o = p(:,r == cellfun(@eval, mat2cell(c,n*2+2,ones(l,1))));
reshape([repmat(x',size(o,2),1) o(:)]',n*2+2,[])'

Answer 8

JavaScript (ES6), 88 bytes

a=>o=>eval(`while(eval(e=(a+'').replace(/,/g,_=>'+-*/'.charAt(Math.random()*5)))!=o);e`)

Threw in a little randomness to the mix. Much easier than systematically iterating through the combinations.

Test Suite

f=a=>o=>eval(`while(eval(e=(a+'').replace(/,/g,_=>'+-*/'.charAt(Math.random()*5)))!=o);e`)
console.log(f([5,5,5,5,5])(100))
console.log(f([1,2,3,4,5])(0))
console.log(f([3,4])(0.75))
console.log(f([3,4,5,6])(339))

Answer 9

PHP, 108 bytes

for(;$i=$argc;eval("$s-$argv[1]?:die(\$s);"))for($s="",$x=$p++;--$i>1;$x/=4)$s.="+-*/"[$s?$x&3:4].$argv[$i];

takes input from command line arguments in reverse order. Run with -r.

breakdown

for(;                   # infinite loop:
    $i=$argc;               # 1. init $i to argument count
    eval("$s-$argv[1]?:"    # 3. if first argument equals expression value,
        ."die(\$s);")       #    print expression and exit
    )
    for($s="",              # 2. create expression:
        $x=$p++;            #    init map
        --$i>1;                 # loop from last to second argument
        $x/=4)                  # C: shift map by two bits
        $s.="+-*/"[$s?$x&3:4]   # A: append operator (none for first operand)
            .$argv[$i];         # B: append operand

Answer 10

Perl 5 with -pa, 46 bytes

$"="{,\\*,/,+,-}";$x=<>;($_)=grep$x==eval,<@F>

Try it online!