13 Replies - 5237 Views - Last Post: 20 January 2013 - 02:31 PM Rate Topic: -----

#1 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7572
  • View blog
  • Posts: 12,717
  • Joined: 19-March 11

Python Challenge: Parens Code Golf

Post icon  Posted 18 January 2013 - 05:50 PM

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


Is This A Good Question/Topic? 2
  • +

Replies To: Python Challenge: Parens Code Golf

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2089
  • View blog
  • Posts: 3,181
  • Joined: 21-June 11

Re: Python Challenge: Parens Code Golf

Posted 18 January 2013 - 05:55 PM

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.
Was This Post Helpful? 1
  • +
  • -

#3 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Python Challenge: Parens Code Golf

Posted 18 January 2013 - 06:00 PM

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

Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7572
  • View blog
  • Posts: 12,717
  • Joined: 19-March 11

Re: Python Challenge: Parens Code Golf

Posted 18 January 2013 - 06:04 PM

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

Was This Post Helpful? 1
  • +
  • -

#5 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Python Challenge: Parens Code Golf

Posted 18 January 2013 - 06:07 PM

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

Was This Post Helpful? 0
  • +
  • -

#6 Nallo  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 163
  • View blog
  • Posts: 255
  • Joined: 19-July 09

Re: Python Challenge: Parens Code Golf

Posted 19 January 2013 - 02:17 PM

Two questions:

View Postjon.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 ...
Was This Post Helpful? 1
  • +
  • -

#7 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Python Challenge: Parens Code Golf

Posted 19 January 2013 - 02:28 PM

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.
Was This Post Helpful? 0
  • +
  • -

#8 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7572
  • View blog
  • Posts: 12,717
  • Joined: 19-March 11

Re: Python Challenge: Parens Code Golf

Posted 19 January 2013 - 02:36 PM

View PostNallo, on 19 January 2013 - 04:17 PM, said:

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



Yes, correct.
I'll have the proofreader whipped soundly.
Was This Post Helpful? 1
  • +
  • -

#9 Nallo  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 163
  • View blog
  • Posts: 255
  • Joined: 19-July 09

Re: Python Challenge: Parens Code Golf

Posted 20 January 2013 - 05:14 AM

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


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

Was This Post Helpful? 1
  • +
  • -

#10 NathanMullenax  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 83
  • View blog
  • Posts: 176
  • Joined: 23-September 12

Re: Python Challenge: Parens Code Golf

Posted 20 January 2013 - 01:29 PM

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.";

Was This Post Helpful? 1
  • +
  • -

#11 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2241
  • View blog
  • Posts: 9,412
  • Joined: 29-May 08

Re: Python Challenge: Parens Code Golf

Posted 20 January 2013 - 01:50 PM

This is a very similar challenge to this C# Challenge.
Was This Post Helpful? 0
  • +
  • -

#12 NathanMullenax  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 83
  • View blog
  • Posts: 176
  • Joined: 23-September 12

Re: Python Challenge: Parens Code Golf

Posted 20 January 2013 - 02:06 PM

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

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

Was This Post Helpful? 1
  • +
  • -

#13 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Python Challenge: Parens Code Golf

Posted 20 January 2013 - 02:07 PM

View PostNathanMullenax, 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.

View PostNathanMullenax, 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.


View PostAdamSpeight2008, 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

Was This Post Helpful? 1
  • +
  • -

#14 Nallo  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 163
  • View blog
  • Posts: 255
  • Joined: 19-July 09

Re: Python Challenge: Parens Code Golf

Posted 20 January 2013 - 02:31 PM

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()


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1