7
\$\begingroup\$

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.

\$\endgroup\$
8
  • 6
    \$\begingroup\$ Why isn't the second one [[0, 1], [0, 1]], [[0, 1], [0, 1]]? \$\endgroup\$ Aug 24, 2023 at 13:10
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – alephalpha
    Aug 24, 2023 at 13:41
  • 1
    \$\begingroup\$ @cairdcoinheringaahing [[0, 1], [0, 1]] is (0*1+1*y)*1+(0*1+1*y)*x=x+x*y. \$\endgroup\$
    – alephalpha
    Aug 24, 2023 at 13:43
  • 2
    \$\begingroup\$ "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? \$\endgroup\$
    – Jonah
    Aug 25, 2023 at 0:16
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – doug
    Aug 25, 2023 at 7:28

5 Answers 5

3
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ (or 82 bytes with newest JS features) \$\endgroup\$
    – Arnauld
    Aug 24, 2023 at 15:49
3
\$\begingroup\$

Charcoal, 115 112 bytes

FEθ⟦⟦ι⟧⟧«W⁺⟦⟧§§ι⁰±¹≔ΣEιE⊟λ⁺λ⟦ξν⟧ι⊞υι»≔⟦⟧θF⊟υ«≔⊟ιηF⌊υ«≔Eι⁺λ§κμζ≔⊟ζε≔θδFζ≔§⎇⁼λLδ⊞Oδ⟦⟧δλδF⁼εLδ⊞δ⁰§≔δε⁺§δε×↨κ⁰η»»⭆¹θ

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.

FEθ⟦⟦ι⟧⟧«

Double wrap each input polynomial and then loop over them.

W⁺⟦⟧§§ι⁰±¹≔ΣEιE⊟λ⁺λ⟦ξν⟧ι

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

⊞υι

Save the resulting list.

»≔⟦⟧θ

Start building up the output list.

F⊟υ«

Loop over the second polynomial's multidimensional index list.

≔⊟ιη

Remove the coefficient from the multidimensional index.

F⌊υ«

Loop over the first polynomial's multidimensional index list.

≔Eι⁺λ§κμζ

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

≔⊟ζε

Remove the innermost index.

≔θδ

Start traversing the dimensions of the output list.

Fζ

Loop over the earlier multidimensional indices.

≔§⎇⁼λLδ⊞Oδ⟦⟧δλδ

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

F⁼εLδ⊞δ⁰

Extend the innermost list if necessary.

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

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

»»⭆¹θ

Pretty-print the resulting list.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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