6
\$\begingroup\$

Challenge: Given an expressions made of additions and multiplications, output an expression that is a sum of products. The output must be equivalent to the input modulo the law of distribution. For example, \$1 + ((2 + 5\times 6) \times(3+4))\$ becomes \$1 + 2 \times 3 + 2 \times 4 + 5\times6\times3 + 5 \times 6 \times 4 \$. This is .

This task is useful in automatic theorem proving, since the conversion to disjunctive normal forms is exactly the same task. (Oops, that gives away a Mathematica builtin!)

Clarifications:

  • You can assume the numbers are whatever you want, integers, floats, or even just strings of symbols, as long as it's convenient.
  • You can use the law of distribution, commutativity and associativity of addition and multiplication. But you cannot use any other property of addition or multiplication. So e.g. \$3 \times (1 + 3) \to 3 + 3 \times 3\$ is not acceptable.
  • This means that answers are not unique, the test cases are just a reference.
  • Parentheses are optional, you won't need them anyway.
  • You can assume any reasonable input form.

Test cases:

2 -> 2 (Corner case, you can ignore this.)
1+3 -> 1+3
1+(3*4) -> 1+3*4
1+3*4 -> 1+3*4
(1+3)*4 -> 1*4+3*4
(1+2+3)*(4+5+6) -> 1*4+2*4+3*4+1*5+2*5+3*5+1*6+2*6+3*6
(1+2*(3+4))*((5+6)*7)+8 -> 1*5*7+1*6*7+2*3*5*7+2*3*6*7+2*4*5*7+2*4*6*7+8
\$\endgroup\$
8
  • \$\begingroup\$ Related.. This challenge is slightly simpler, because you don't have the additional logical identities. \$\endgroup\$
    – Trebor
    Jun 30 '21 at 15:08
  • \$\begingroup\$ May we take input as P(1, M(3, 4)) instead of 1+(3*4))? \$\endgroup\$
    – user
    Jun 30 '21 at 15:11
  • 1
    \$\begingroup\$ @user Yes, I think it is already a consensus that this is a reasonable format for syntax-tree-style input. \$\endgroup\$
    – Trebor
    Jun 30 '21 at 15:13
  • \$\begingroup\$ Can I define my own addition and multiplication functions and take input as the application of those. e.g. f(1*(2+3))="1*2+1*3"? \$\endgroup\$
    – Wheat Wizard
    Jun 30 '21 at 17:34
  • \$\begingroup\$ @WheatWizard Ahh, that's exactly what I'm doing when I encountered this problem in real world! I think it's OK. \$\endgroup\$
    – Trebor
    Jun 30 '21 at 17:41
3
\$\begingroup\$

Haskell, 139 bytes

data M=I Int|M:*M|M:+M deriving(Show,Read)
f(x:*y)|z:+w<-f y=f(x:*z):+f(x:*w)|z:+w<-f x=f(z:*y):+f(w:*y)
f(x:+y)=f x:+f y
f x=x
show.f.read

Try it online!

IO Format

Here our IO format uses the functions :+ for addition and :* for multiplication. We also require that numbers themselves are prefixed with I , and that all parentheses be explicit.

So for example

2 * (3 * (1 + 2))

is

I 2 :* (I 3 :* (I 1 :+ I 2))

We uses this format because we are parsing into a native haskell data type defined on the first line. If I could operate on the data type directly the code would be a lot shorter:

Haskell, 107 bytes

data M=I Int|M:*M|M:+M
f(x:*y)|z:+w<-f y=f(x:*z):+f(x:*w)|z:+w<-f x=f(z:*y):+f(w:*y)
f(x:+y)=f x:+f y
f x=x

Try it online!

Since this gets rid of all the parsing bits and just includes the manipulations.

\$\endgroup\$
3
  • \$\begingroup\$ You might find some one-character operators for :+ and :*...? Or have you used them up? \$\endgroup\$
    – Trebor
    Jun 30 '21 at 18:23
  • \$\begingroup\$ @Trebor Constructors must be named with a starting :, and : itself is already taken. I could make an alias but it can't be used in pattern matches and ends up making my code bigger. \$\endgroup\$
    – Wheat Wizard
    Jun 30 '21 at 18:52
  • 1
    \$\begingroup\$ Maybe this is I/O scumming to a degree that trivializes the challenge too much, but combining this input format with a “list-of-lists, sum-of-products” output format ([[1],[2,3],[4,5,6]] meaning 1 + 2×3 + 4×5×6) makes the implementation very short (f(x:*y)=(++)<$>f x<*>f y etc). \$\endgroup\$
    – Lynn
    Jun 30 '21 at 20:31
3
\$\begingroup\$

Python 3, 157 bytes

lambda e:"+".join(eval(re.sub("\d","A('\g<0>')",e)))
import re
class A(list):__mul__=lambda s,x:A(i+"*"+j for i in s for j in x);__add__=lambda s,x:A([*s]+x)

How it works :

We define a new object named A with the wanted properties for addition and multiplication.

  • each digit is stored as a list of string
  • an expression like 1+2 is converted into ['1', '2']
  • an expression like 1*2 is converted into ['1*2']
  • the sum is equivalent to the python list addition
  • the product is a double iteration over the 2 lists

Then we let python do the multiplication over addition priority

  • re.sub("\d","A('\g<0>')",e) we convert all the digits in our expression into instances of this object
  • "+".join(eval(...)) we evaluate and formate the result

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 118 bytes

{`\(([\d*]+)\)
$1
\(([\d*]+)\+([^()]+\))(\*([\d*]+|\([^()]+\)))
$1$3+($2$3
([\d*]+\*)\(([\d*]+)\+([^()]+\))
$1$2+$1($3

Try it online! Link includes test cases. Explanation:

{`

Perform all possible reductions.

\(([\d*]+)\)
$1

(a*b*...) becomes a*b*....

\(([\d*]+)\+([^()]+\))(\*([\d*]+|\([^()]+\)))
$1$3+($2$3

(a*b*...+c*d*...+...)*f*g*... becomes a*b*...*f*g*...+(c*d*...+...)*f*g*, where f*g*... could instead be (f*g*...+h*i*...+...).

([\d*]+\*)\(([\d*]+)\+([^()]+\))
$1$2+$1($3

a*b*...*(c*d*...+e*f*...+...) becomes a*b*...*c*d*...+a*b*...(e*f*...+...).

\$\endgroup\$

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.