[jon.kiparsky]

Hoping to keep you all on your toes, Simown and I plan to issue a new code challenge every other week through 2013.

This time, the challenge is this: Given a list of integers and a single integer argument output a parenthesized expression that sums to the individual integer provided, with the basic arithmetic operations (+, -, /, *)


For example:
1 parenthesize([1, 20, 2], 11) => (1 + (20 / 2))
2 parenthesize([1, 2, 3, 4], 10) => (1 + 2 + 3 + 4)

In order to make things interesting, we'll be running this one as a round of Code Golf. That is, you're looking to do this in the smallest number of characters (not counting whitespace).

Rules:
-- The function signature is not added to the count, and it must have 2 and only 2 parameters (the list of numbers and the integer)
-- It must be a single top-level function (nested helper functions are fine)
-- "import" and "import ... as" are acceptable
-- Your function must handle the case when the expression is not parenthesizable.
-- There must be outer brackets on every expression e.g. (5 + 4 + 3), (6 * (2 + 1))
-- Order of arithmetic operations are PEDMAS or BODMAS/BIDMAS basically anything in BRACKETS first then DIVISION then MULTIPLICATION then ADDITION then SUBTRACTION
-- And for those wondering, the Simown constraint is in effect.

Any questions leave a comment here and we'll get back to you. Remember, you have 2 weeks to complete this challenge before the next one is posed.

And as always, please post your solutions in spoiler tags as a courtesy to those who are still working on it.

That's it! Happy Challenging!

This post has been edited by Simown: 19 January 2013 - 02:29 PM
Reason for edit:: Fixing some terminology

[sepp2k]

What exactly do you mean by "fully parenthesized"? I would have thought it means "every invocation of an operator needs to be surrounded by one pair of parentheses", but your second example output doesn't match that interpretation.

[Simown]

Ah, indeed. It should be "a parenthesized expression that sums to the integer provided", perhaps not "fully parenthesized" - I wrote this, blame me .

In the second example addition is commutative so it sums to 10. I guess this would also be a valid solution:

parenthesize([1, 2, 3, 4], 10) => ((1 + 2) + (3 + 4))

Probably extra brackets is pushing it, however valid:

parenthesize([1, 2, 3, 4], 10) => ((((((1 + 2) + (3 + 4))))))

This post has been edited by Simown: 18 January 2013 - 06:08 PM

[jon.kiparsky]

Good question.

For purposes of the challenge, we'd accept "sufficiently parenthesized". As in, the output must be an arithmetically correct expression composed of the basic operations and at least enough parentheses to parse the expression correctly.

Note that this certainly allows for the fully parenthesized form, which I think is going to be the shortest source code. In fact, I think it would be a fun extra challenge to produce a minimally parenthesized form, using as few brackets as possible.

EDIT: Ninja'd. And no, we hadn't consulted about this case.

This post has been edited by jon.kiparsky: 18 January 2013 - 06:05 PM

[Simown]

Haha, sorry. I sneaked in and edited your initial post too. That's what you get for being unable to sleep. I'll leave you to it

This post has been edited by Simown: 18 January 2013 - 06:08 PM

[Nallo]

Two questions:

jon.kiparsky, on 19 January 2013 - 12:50 AM, said:

...with the basic arithmetic operations (+, -, %, *)

...
Rules:
-- It must be a single top-level function
...

-You meant arithmetic operations (+, -, /, *), not (+, -, %, *), right?

-A single top level function, hmm. Are import statements outside allowed? I mean I can make an import statement inside a function, but not an from ... import ... as ...

[Simown]

Yeah, "/", I'm not sure where "%" came from, but it's sometimes used in place of division written, over here anyway, it's confusing because of modulus I know - I'll change it.

Import statements are fine. As long as one can run parenthesise([x,y,z], a) it's acceptable. That constraint was just to prevent anyone submitting things where you had to run more than a single function.

[jon.kiparsky]

Nallo, on 19 January 2013 - 04:17 PM, said:

-You meant arithmetic operations (+, -, /, *), not (+, -, %, *), right?

Yes, correct.
I'll have the proofreader whipped soundly.

[Nallo]

I assume we can change the order in which the operands are supplied. So that

parenthesize([5, 5, 2, 2], 5) => ((5 / 2) + (5 / 2))

would be valid. If so here is my first entry. I may make an other one later as I see room for improvement. Excluding the def parenthesize(v, i): line and all (even the required) whitespace I am at 216 characters now:

Spoiler

Requires Python 3.x. In Python 2.6/2.7 I would need from __future__ import division which I wanted to avoid. Usually Python 2.x is better for code golf but that import is a deal breaker.

Algorithm:
-generate all fully parethesized expressions as strings
-eval them and see if one gives the required result

The try except block is needed to handle zero division errors.

def parenthesize(v, i):
    v = [str(x) for x in v]
    def m(v):
        l = len(v)
        if l == 1:
            yield v[0]
        else:
            for i in range(l):
                w = v[:]
                a = w.pop(i)
                for j in range(l-1):
                    u = w[:]
                    b = u[j]
                    for o in "+-*/":
                        u[j] = "("+a+o+b+")"
                        for t in m(u):
                            yield t
    for t in m(v):
        try:
            if eval(t) == i:
                return t
        except:
            pass
    return ""

Edit:
On second thought: The rules didn't tell what to return when we cannot reach a solution. I returned an empty string but if returning None in such case is fine I can kill a return statement from my program. After all Python functions return None as default :-) Would be another 8 characters source code less.

This post has been edited by Nallo: 20 January 2013 - 09:13 AM

[NathanMullenax]

Does the function have to generate every possible expression?

For instance, parenthesize( [1,2,3,4], 10 ) could be represented several different ways e.g., (4+1*2*3) or (1+2+3+4).

Should the function assume division is exact or are we assuming integer division?

Example:

parenthesize( [2,3,5], 5 ) => (2/3 + 5) or (5/(3/2))
Are these valid solutions?

I suck at awk, so I wrote a non-whitespace counting perl script (if anyone else needs one).

#!/usr/bin/perl
use strict;
open F, "<", $ARGV[0] or die $!;
my $score =0;
while( <F> )
{
    my $l = $_;
    $l =~ s/\s//g;
    $score += length($l);
}
print "$ARGV[0] contains $score non-whitespace characters.";

[AdamSpeight2008]

This is a very similar challenge to this C# Challenge.

[NathanMullenax]

Here's a 509-character (sans signature) solution. It's not elegant, short, or readable, but my approach was to generate all possible expressions in reverse Polish notation and then convert to infix. If you remove the last return, all solutions will be generated. In retrospect, I probably should have used eval to make it shorter.

This solution assumes that division is to be interpreted as /exact/ division; it would be slightly shorter if I removed the remainder-check from the division case.

Spoiler

from itertools import permutations as P

K = "+-*/"
L = len
S = str

def cs( s, n ):
    m = []
    l = L(s)
    for i in range(0, l**n):
        p = i
        t = []
        while L(t) < n:
            t +=[ s[p%l] ]
            p /= l
        m+=[t]
    return m

def R( N, Z ):
    for O in Z:
        a = N.pop()
        b = N.pop()
        if O=='+':
            N+=[ a+b ]
        elif O=='-':
            N+=[ a-b ]
        elif O=='*':
            N+=[ a*b ]
        elif O=='/':
            if b==0:
                return []
            N+=[ 1.*a/b ]
    return N[0]

def parenthesize( N, t ):
    for p in P(N):
        rs = cs( K, L(N)-1 )
        for r in rs:
            if R( list(p), r )==t:
                l = list(p)            
                e = S(l.pop()) + r[0] + S(l.pop()) 
                for O in r[1:]:
                    a = l.pop()
                    if O=='+':
                        e += '+%s' % a 
                    elif O=='-':
                        e += '-%s' % a  
                    elif O=='*':
                        e =  '(%s)*%s'% (e, a)
                    elif O=='/':
                        e = '(%s)/%s'% (e, a)
                print '(%s)' %  e 
                return         

This post has been edited by NathanMullenax: 25 January 2013 - 01:54 PM

[Simown]

NathanMullenax, on 20 January 2013 - 08:29 PM, said:

Does the function have to generate every possible expression?

For instance, parenthesize( [1,2,3,4], 10 ) could be represented several different ways e.g., (4+1*2*3) or (1+2+3+4).

The function only needs to return a single correct parenthesised expression that adheres to all the rules in the first post.

NathanMullenax, on 20 January 2013 - 08:29 PM, said:

Should the function assume division is exact or are we assuming integer division?


Example:

parenthesize( [2,3,5], 5 ) => (2/3 + 5) or (5/(3/2))
Are these valid solutions?

Assume division is exact for this challenge, e.g. a valid solution would be:

parenthesize([5, 2, 5, 2], 5) => ((5/2) + (5/2))

I understand that it gets a bit difficult when you are dealing with 2/7ths or even 1/3, I think you can safely assume it won't be tested with fractions where possible rounding/precision errors might occur.

AdamSpeight2008, on 20 January 2013 - 08:50 PM, said:

This is a very similar challenge to this C# Challenge.

Thanks? Forgive me for not noticing it was a similar challenge to one posted over a year ago in C#, this challenge is also similar to one jon.kiparsky brought up before, I forget which exactly. Should be easy for you to think up a nice a solution then, I guess.

This post has been edited by Simown: 20 January 2013 - 02:10 PM

[Nallo]

I suck at perl and awk, so here is my non-whitespace counter in python 2.x. Also ignores the function definition line (if it's "def parenthesize"):

#!/usr/bin/python
import sys
FUNCTION_LINE = "def parenthesize"

filename = sys.argv[1]
f = open(filename, "r")
lines = (line for line in f
              if FUNCTION_LINE not in line)
chars = (char for line in lines
              for char in line
              if not char.isspace())
print len(list(chars))
f.close()