# Obtain a number from 4 numbers using any combination of mathematical operations

Given 4 numbers n1, n2, n3, n4, and a goal n5, obtain n5 using n1 through n4 combined with any operations.

Eg. Given four numbers 2,3,4,5 and the goal as 8, output (one of many) is `2-3+4+5`

EDIT: This is a variation of a game played at my son's school. Paranthesis, powers, unary operations (log, factorial) are allowed; the expressions tend to get complicated. However, unary operations can be applied only once on a number. Essentially, the tree should be:

```                          goal
/\
/  \
/    \
expression1   expression2
/\                /\
/  \              /  \
/    \            /    \
term1  term2     term3  term4
```

where term#i is either
1. one of the numbers, or 2. one of the numbers with an unary operation.

-
 Does factorial count as an operation? – Eelvex Mar 9 '11 at 8:25 Can output need parentheses? (it seems like a valid way to combine with the operations, but neither your example nor the current posted answers support that) For example solving 5 with 10,1,1,0. – J B Mar 9 '11 at 8:49 BTW, is this code golf at all? – J B Mar 9 '11 at 20:50 @CMR: You are expected to tag a question with a type-of-challange tag; either code-golf or code-challenge (and possibly others eventually). Given the nature of the answers so-far, I'm going to apply [code-golf], and you should change it if that is not what you meant. – dmckee♦ Mar 11 '11 at 19:23 I assume "4+4" is invalid since it repeats a number and doesn't use 2,3,5? – barrycarter Mar 14 '11 at 3:10
show 1 more comment

## Python (159)

```from itertools import*
f=lambda*l:[a+f+b+g+c+h+d for f,g,h in product('+-/*',repeat=3)for a,b,c,d in permutations(map(str,l[:4]))if eval(a+f+b+g+c+h+d)==l[4]]
```

Example:

```>>> f(2,3,4,5,8)
['2+4+5-3', '2+5+4-3', '4+2+5-3', '4+5+2-3', '5+2+4-3', '5+4+2-3', '2+5+4/3',
'3+5+2/4', '5+2+4/3', '5+3+2/4', '2+4-3+5', '2+5-3+4', '4+2-3+5', '4+5-3+2',
'5+2-3+4', '5+4-3+2', '3+5-2/4', '4+5-3/2', '5+3-2/4', '5+4-3/2', '2+4/3+5',
'3+2/4+5', '5+2/4+3', '5+4/3+2', '2+4*5/3', '2+5*4/3', '2-3+4+5', '2-3+5+4',
'4-3+2+5', '4-3+5+2', '5-3+2+4', '5-3+4+2', '3-2/4+5', '4-3/2+5', '5-2/4+3',
'5-3/2+4', '2/4+3+5', '2/4+5+3', '4/3+2+5', '4/3+5+2', '3/5+2*4', '3/5+4*2',
'5/3*2*4', '5/3*4*2', '2*4+3/5', '4*2+3/5', '2*4-3/5', '4*2-3/5', '4*5/3+2',
'5*4/3+2']
```
-
 Gotta love itertools. – st0le Mar 9 '11 at 5:54 ZeroDivisionError: integer division or modulo by zero – J B Mar 9 '11 at 20:10

## Python - 146 chars

``````from itertools import*
f=lambda*l:[s for s in((3*"%s%%s"+"%s")%a%o for o in product(*['+-/*']*3)for a in permutations(l[:4]))if eval(s)==l[4]]
``````
-

# Ruby1.9.1 - 158 chars

``````g=->a,&b{a.permutation.each &b}
f=->*a{t=a.pop
g.(a){|n|g.(['+','-','*','/']*3){|k|s=[n[0],k[9],n[1],k[10],n[2],k[11],n[3]].join ''
return s if eval(s)==t}}}
``````

Lambda function `f` returns the first solution it finds. eg.

``````f[2,3,4,5,8] #gives "2-3+4+5"
``````
-

## Perl

Not golfed as this is a code-challenge and not code-golf.

Aiming for complete solution; uses reverse polish notation.

Enjoy cryptic variable names and weird coding style ;)

```#!perl -l
use strict;
use warnings;
use Math'Combinatorics;
use Math'RPN;

my @do=qw(add sub mul div mod pow);
my @uo=qw(sqrt sin cos tan log exp);

sub u(@){my%h;\$h{"@\$_"}=\$_ for@_;values%h}

sub ms (\$\$\$) {
my(\$c,\$d,\$f)=@_; my @r;
my \$o = new Math'Combinatorics count => \$c, data => \$d, frequency => \$f;
while (my @x = \$o->next_multiset) {push @r, [@x]}
@r;
}

my \$r = shift;
my \$a = ~~@ARGV;

my @p = u permute @ARGV;
my @d = ms \$a-1, \@do, [(~~@do) x @do];
my @u = ms \$a, \@uo, [(~~@uo)x@uo];
my @t;

push @t, [unpack "(A)\$a", sprintf "%0\${a}b", \$_] for 0..2**\$a-1;

my @pu = ();

for my \$pp (@p) {
for my \$uoo (@u) {
for my \$tt (@t) {
my @opu = ();
for my \$g (0..\$a-1) {
push @opu, \$pp->[\$g];
push @opu, \$uoo->[\$g] if \$tt->[\$g];
}
push @pu, \@opu;
}
}
}

@pu = u @pu;

for my \$ppu (@pu) {
for my \$doo (@d) {
my @e = (@\$ppu,@\$doo); my \$z;
eval {\$z=rpn(@e)};
\$z = \$r-1 if \$@;
print "@e = \$z" if \$z==\$r;
}
}
```

usage example:

```> perl ./mc.pl 14 3 4 4
4 sqrt 3 4 add mul = 14
4 sqrt 4 3 add mul = 14
4 exp 3 exp 4 exp mod mod = 14
4 exp 3 exp 4 sqrt mul mod = 14
```
-