# Distribute the additions!

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

• Related.. This challenge is slightly simpler, because you don't have the additional logical identities. Commented Jun 30, 2021 at 15:08
• May we take input as P(1, M(3, 4)) instead of 1+(3*4))?
– user
Commented Jun 30, 2021 at 15:11
• @user Yes, I think it is already a consensus that this is a reasonable format for syntax-tree-style input. Commented Jun 30, 2021 at 15:13
• 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"? Commented Jun 30, 2021 at 17:34
• @WheatWizard Ahh, that's exactly what I'm doing when I encountered this problem in real world! I think it's OK. Commented Jun 30, 2021 at 17:41

# 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


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.

• You might find some one-character operators for :+ and :*...? Or have you used them up? Commented Jun 30, 2021 at 18:23
• @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. Commented Jun 30, 2021 at 18:52
• 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). – lynn Commented Jun 30, 2021 at 20:31 # 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! # 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*...+...).