8
\$\begingroup\$

I saw this recent Puzzling question:

Add parentheses to make this true

And saw that one answer used a Python script to try all possibilities.

Your challenge is, given an expression (as a string) and an integer, is to make a program that can tell whether you can add parens to make the expression equal the integer.

For example, if the expression is 1 + 2 * 3 and the integer is 9, than you can add parens like (1 + 2) * 3, which equals 9, so the output should be truthy. But if the expression is 1 + 2 - 3 * 4 / 5 and the integer is 9999999999999, you can't add any amount of parens to make that equal 9999999999999, so the output should be falsey.

Note that the integer input may be positive or negative, but the expression will only contain positive integers. In fact, the expression will always match (\d+ [+*/-] )+ \d (regex). In other words, no parens, no exponents, just +, -, * and /. Standard operator order (* and /, then + and -).

More test cases:

1 + 2 - 3 * 4 / 9 and -1 -> truthy, ((1 + 2) - (3 * 4)) / 9
10 - 9 * 8 - 7 * 6 - 5 * 4 - 3 * 2 - 2 * 1 and 1, falsey, see linked question
10 + 9 - 8 * 7 + 6 - 5 * 4 + 3 - 2 * 1 and 82 -> truthy, (10 + (9 - 8)) * 7 + (6 - 5) * 4 + 3 - 2 * 1
34 + 3 and 15 -> falsey
1 + 2 + 5 + 7 and 36 -> falsey
1 / 10 * 3 + 3 / 10 * 10 and 6 -> truthy, (1/10*3+3/10)*10

Any questions?

You may output the expression with parenthesis if it is possible, for instance (10 + (9 - 8)) * 7 + (6 - 5) * 4 + 3 - 2 * 1 for the last test case. I would prefer this over just a truthy value, but it is up to you. Using 2(5) for multiplication is not allowed, only *.

\$\endgroup\$
  • \$\begingroup\$ / is float division , right? \$\endgroup\$ – Rod May 18 '17 at 13:32
  • \$\begingroup\$ @Rod yes, it is. \$\endgroup\$ – programmer5000 May 18 '17 at 13:32
  • 1
    \$\begingroup\$ You should have a test case that requires a non-integer intermediate result to be used. \$\endgroup\$ – feersum May 18 '17 at 13:50
  • \$\begingroup\$ You should add a test case where division by zero might occur, like 3 / 2 - 1 - 1 and 2 -> 3 / (2 - 1) - 1 \$\endgroup\$ – mbomb007 May 18 '17 at 18:19
3
\$\begingroup\$

Python 2, 286 285 282 bytes

from fractions import*
P=lambda L:[p+[L[i:]]for i in range(len(L))for p in P(L[:i])]or[L]
x,y=input()
x=x.split()
for p in P(['Fraction(%s)'%e for e in x[::2]]):
 try:print 1/(eval(''.join(sum(zip(eval(`p`.replace("['","'(").replace("']",")'")),x[1::2]+[0]),())[:-1]))==y)
 except:0

Try it online

Explanation:

This version will print all of the working expressions (with the Fraction objects).

from fractions import*
# Sublist Partitions (ref 1)
P=lambda L:[p+[L[i:]]for i in range(len(L))for p in P(L[:i])]or[L]
x,y=input()
x=x.split()
# Convert all numbers to Fractions for division to work
n=['Fraction(%s)'%e for e in x[::2]]
# Operators
o=x[1::2]
# Try each partition
for p in P(n):
    # Move parens to be inside strings
    n=eval(`p`.replace("['","'(").replace("']",")'"))
    # Alternate numbers and operators (ref 2)
    x=''.join(sum(zip(n,o+[0]),())[:-1])
    # Prevent division by zero errors
    try:
        # Evaluate and check equality
        if eval(x)==y:print x
    except:0

Try it online

References:

  1. Partitioning function

  2. Alternating zip

Saved 3 bytes thanks to Felipe Nardi Batista

\$\endgroup\$
  • \$\begingroup\$ 1- Can you use python3 (/ is float division) and drop all fractions uses? 2 - What about divisions by 0? \$\endgroup\$ – Rod May 18 '17 at 16:41
  • \$\begingroup\$ @Rod No, you can't. Float division is the reason it's required. \$\endgroup\$ – mbomb007 May 18 '17 at 16:44
  • \$\begingroup\$ What's the reason then? \$\endgroup\$ – Rod May 18 '17 at 16:46
  • \$\begingroup\$ oh, rounding issues \$\endgroup\$ – Rod May 18 '17 at 16:54
  • \$\begingroup\$ I fixed the division by zero problem. It still worked for any example where the solution came before the division by zero, but I did find a test case that broke it. It's the last test case in my test suite. \$\endgroup\$ – mbomb007 May 18 '17 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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