# Multiply multivariate polynomials

We already have a challenge about multiplying multiply single-variable polynomials. This challenge is about multiply two polynomials with multiple variables

Your task is given two multi-variable polynomials (for instance given as nested lists) to return their product.

## Examples

(x²+x+1)*(x²+x+1)=x⁴+2x³+3x²+2x+1
(x+y)*(x+y)=x²+2xy+y²
(x+y+z)*(x-y+z) = x²-y²+2xz +z²
a*a=a²


when representing polynomials as nested lists1:

[1,1,1], [1,1,1]                                     -> [1, 2, 3, 2, 1]
[[0,1],[1]], [[0,1],[1]]                             -> [[0, 0, 1], [0, 2], [1]]
[[[0,1],[1]],[[1]]], [[[0,1],[-1]],[[1]]]            -> [[[0, 0, 1], [0], [-1]], [[0, 2]], [[1]]]
[[],[[[[[[[[[1]]]]]]]]]], [[],[[[[[[[[[1]]]]]]]]]] -> [[], [], [[[[[[[[[1]]]]]]]]]]


(non-golfed) solution in Python

## Rules

• You can Input/Output the polynomials in any convenient format (as long as each output can only represent one polynomial)
• Input and Output have to use the same format for polynomials
• You can assume that all coefficients are integers
• If you take input as lists you can assume that all numbers in both inputs appear in the nesting depth
• You are allowed to omit zero coefficients in the output (as long as the output value are unambiguous)
• You can use the empty list to represent zero/the zero polynomial
• If your language has a built-in for multi-variable polynomial multiplication consider adding a non-built-in solution as well
• This is the shortest solution wins

1short explanation of the nested list format used in the examples (you are free to use a different IO format):

Each list represents a single variable polynomial with its coefficients begin either integers or other lists representing polynomials in one less variable. The coefficients are multiplied with the polynomial variable to the power of their index:

[[[0,1],[1]],[[1]]] -> "[[0,1],[1]]"*1+"[[1]]"*z -> ("[0,1]"*1+"[1]"*y)*1+"[1]"*1*z -> (x*1+1*y)*1+1*1*z -> x+y+z


The variables are assigned by nesting layer. I use x for the innermost variable y for the next level, then z.

• Why isn't the second one [[0, 1], [0, 1]], [[0, 1], [0, 1]]? Aug 24 at 13:10
• This is Nekomata's × function (multidimensional convolution). Unfortunately it doesn't work on the version on ATO, so I won't post an answer for it. Aug 24 at 13:41
• @cairdcoinheringaahing [[0, 1], [0, 1]] is (0*1+1*y)*1+(0*1+1*y)*x=x+x*y. Aug 24 at 13:43
• "Each list is a single variable polynomial with its coefficients begin either integers or polynomials in one less variable" Fwiw, even with the worked example I am having trouble figuring out how this works. Specifically, how do you figure out which variables go with x, versus with y or z? Aug 25 at 0:16
• @Jonah - I think the idea is that a polynomial is represented as a tree where the entries at depth 1 represent the last variable, at depth 2 the second to last, etc. At each level the siblings left to right represent successive powers of the variable at that level (you can imagine interior nodes having a value of the power it represents) and the leaves contain the coefficients. So descending the tree you pick up various powers of each variable and at the leaf you have the coefficient for the term represented by that path.
– doug
Aug 25 at 7:28

# JavaScript (Node.js), 80 bytes

f=(x,y,s=[])=>x>f&&x.map((p,i)=>y.map(q=>f(p,q,s[i++]||=[])||(s[i-1]-=-p*q)))&&s


Attempt This Online!

# JavaScript (Node.js), 84 bytes

f=(x,y,s=[])=>x>f&&x.map((p,i)=>y.map(q=>f(p,q,s[i]=s[i++]||[])||(s[i-1]-=-p*q)))&&s


Try it online!

• (or 82 bytes with newest JS features) Aug 24 at 15:49

# Charcoal, 115 112 bytes

ＦＥθ⟦⟦ι⟧⟧«Ｗ⁺⟦⟧§§ι⁰±¹≔ΣＥιＥ⊟λ⁺λ⟦ξν⟧ι⊞υι»≔⟦⟧θＦ⊟υ«≔⊟ιηＦ⌊υ«≔Ｅι⁺λ§κμζ≔⊟ζε≔θδＦζ≔§⎇⁼λＬδ⊞Ｏδ⟦⟧δλδＦ⁼εＬδ⊞δ⁰§≔δε⁺§δε×↨κ⁰η»»⭆¹θ


Attempt This Online! Link is to verbose version of code. Explanation: Charcoal doesn't really like multidimensional indexing. I should really find time to test this out on my multidimensional indexing branch to see whether it offers a significant saving.

ＦＥθ⟦⟦ι⟧⟧«


Double wrap each input polynomial and then loop over them.

Ｗ⁺⟦⟧§§ι⁰±¹≔ΣＥιＥ⊟λ⁺λ⟦ξν⟧ι


Replace each polynomial with a list of its elements and their multidimensional indices.

⊞υι


Save the resulting list.

»≔⟦⟧θ


Start building up the output list.

Ｆ⊟υ«


Loop over the second polynomial's multidimensional index list.

≔⊟ιη


Remove the coefficient from the multidimensional index.

Ｆ⌊υ«


Loop over the first polynomial's multidimensional index list.

≔Ｅι⁺λ§κμζ


Get the multidimensional index of the product of the two terms.

≔⊟ζε


Remove the innermost index.

≔θδ


Start traversing the dimensions of the output list.

Ｆζ


Loop over the earlier multidimensional indices.

≔§⎇⁼λＬδ⊞Ｏδ⟦⟧δλδ


Get the inner list at the current multidimensional index, extending the current list if necessary.

Ｆ⁼εＬδ⊞δ⁰


Extend the innermost list if necessary.

§≔δε⁺§δε×↨κ⁰η


Add on the resulting coefficient to the element at the innermost index.

»»⭆¹θ


Pretty-print the resulting list.

# K (ngn/k), 60 55 bytes

{(.p),','!p:+/'(*p)@=*|p:(*/;+/)@''++',/,/:\:/,''(x;y)}


Try it online!

-5 : Save a lambda

Here multinomials are represented by lists of terms where each term is a pair of coefficients and list of powers of each variable in reverse order.

Thus,

(x-y+z) -> [[[1,[0,0,1]],[-1,[0,1,0]],[1,[0,0,1]]]


or in K notation:

((1;0 0 1)
(-1;0 1 0)
(1;1 0 0))


Cleaning up terms with zero coefficients is left to an auxiliary function.

# Python3, 490 bytes:

def U(p,l=1,o=1):
if type(p)!=list or[]==p:yield(p if p!=[]else 0,o);return
for i,a in enumerate(p):yield from U(a,l+1,{l:i}if o==1 else{**o,l:o.get(l,0)+i})
def G(p,l=1):
r={}
for c,D in p:
if l in D:r[V]=r.get(V:=D.pop(l),[])+[(c,D)]
return[G(r[i],l+1)if i in r else 0 for i in range(max(r)+1)]if r else c
def M(a,b):
r={}
for c,p in U(a):
for C,P in U(b):r[K]=r.get(K:=str({**p,**{A:p.get(A,0)+B for A,B in P.items()}}),0)+c*C
return G([(b,eval(a))for a,b in r.items() if b])


Try it online!

# Wolfram Language (Mathematica), 12 bytes

Expand[1##]&


Try it online. The inevitable built-in. 1## multiplies together all arguments to a function, regardless of the types of those objects. (So this function works for more than two polynomials as well.)