7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Does factorial count as an operation? \$\endgroup\$ – Eelvex Mar 9 '11 at 8:25
  • \$\begingroup\$ 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. \$\endgroup\$ – J B Mar 9 '11 at 8:49
  • \$\begingroup\$ BTW, is this code golf at all? \$\endgroup\$ – J B Mar 9 '11 at 20:50
  • \$\begingroup\$ @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. \$\endgroup\$ – dmckee Mar 11 '11 at 19:23
  • \$\begingroup\$ I assume "4+4" is invalid since it repeats a number and doesn't use 2,3,5? \$\endgroup\$ – barrycarter Mar 14 '11 at 3:10
2
\$\begingroup\$

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']
\$\endgroup\$
  • \$\begingroup\$ Gotta love itertools. \$\endgroup\$ – st0le Mar 9 '11 at 5:54
  • \$\begingroup\$ ZeroDivisionError: integer division or modulo by zero \$\endgroup\$ – J B Mar 9 '11 at 20:10
3
\$\begingroup\$

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]]
\$\endgroup\$
1
\$\begingroup\$

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"
\$\endgroup\$
1
\$\begingroup\$

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.