Multiply Two Integer Polynomials

Question

Your task is to take two single-variable integer polynomial expressions and multiply them into their unsimplified first-term-major left-to-right expansion (A.K.A. FOIL in the case of binomials). Do not combine like terms or reorder the result. To be more explicit about the expansion, multiply the first term in the first expression by each term in the second, in order, and continue in the first expression until all terms have been multiplied by all other terms. Expressions will be given in a simplified LaTeX variant.

Each expression will be a sequence of terms separated by + (with exactly one space on each side) Each term will conform to the following regular expression: (PCRE notation)

-?\d+x\^\d+

In plain English, the term is an optional leading - followed by one or more digits followed by x and a nonnegative integer power (with ^)

An example of a full expression:

6x^3 + 1337x^2 + -4x^1 + 2x^0

When plugged into LaTeX, you get \$6x^3 + 1337x^2 + -4x^1 + 2x^0\$

The output should also conform to this format.

Since brackets do not surround exponents in this format, LaTeX will actually render multi-digit exponents incorrectly. (e.g. 4x^3 + -2x^14 + 54x^28 + -4x^5 renders as \$4x^3 + -2x^14 + 54x^28 + -4x^5\$) You do not need to account for this and you should not include the brackets in your output.

Example Test Cases

5x^4
3x^23

15x^27

---

6x^2 + 7x^1 + -2x^0
1x^2 + -2x^3

6x^4 + -12x^5 + 7x^3 + -14x^4 + -2x^2 + 4x^3

---

3x^1 + 5x^2 + 2x^4 + 3x^0
3x^0

9x^1 + 15x^2 + 6x^4 + 9x^0

---

4x^3 + -2x^14 + 54x^28 + -4x^5
-0x^7

0x^10 + 0x^21 + 0x^35 + 0x^12

---

4x^3 + -2x^4 + 0x^255 + -4x^5
-3x^4 + 2x^2

-12x^7 + 8x^5 + 6x^8 + -4x^6 + 0x^259 + 0x^257 + 12x^9 + -8x^7

Rules and Assumptions

• You may assume that all inputs conform to this exact format. Behavior for any other format is undefined for the purposes of this challenge.
  • It should be noted that any method of taking in the two polynomials is valid, provided that both are read in as strings conforming to the above format.
• The order of the polynomials matters due to the expected order of the product expansion.
• You must support input coefficients between \$-128\$ and \$127\$ and input exponents up to \$255\$.
  • Output coefficents between \$-16,256\$ and \$16,384\$ and exponents up to \$510\$ must therefore be supported.
• You may assume each input polynomial contains no more than 16 terms
  • Therefore you must (at minimum) support up to 256 terms in the output
• Terms with zero coefficients should be left as is, with exponents being properly combined
• Negative zero is allowed in the input, but is indistinguishable from positive zero semantically. Always output positive zero. Do not omit zero terms.

Happy Golfing! Good luck!

Answer 1

R, 159 153 148 bytes

function(P,Q,a=h(P),b=h(Q))paste0(b[1,]%o%a[1,],"x^",outer(b,a,"+")[2,,2,],collapse=" + ")
h=function(s,`/`=strsplit)sapply(el(s/" . ")/"x.",strtoi)

Try it online!

I really wanted to use outer, so there's almost surely a more efficient approach.

Answer 2

Haskell, 131 122 bytes

(%)=drop
f s=do(a,t)<-reads s;(i,u)<-reads$2%t;(a,i):f(3%u)
p!q=3%do(a,i)<-f p;(b,j)<-f q;" + "++shows(a*b)"x^"++show(i+j)

Try it online!

f parses a polynomial from a string, ! multiplies two of them and formats the result.

H.PWiz saved 9 bytes. Thanks!

Ungolfed

type Monomial = (Int, Int) -- a^i
type Polynomial = [Monomial]

parse :: String -> Polynomial
parse s = do (a, s')  <- reads s
             (i, s'') <- reads (drop 2 s')
             (a, i) : parse (drop 3 s'')

(!) :: String -> String -> String
p!q = drop 3 (concat terms)
  where terms    = [term (a*b) (i+j) | (a,i) <- p', (b,j) <- q']
        term a i = concat [" + ", show a, "x^", show i]
        p'       = parse p
        q'       = parse q

Answer 3

Ruby, 102 100 98 bytes

->a,b{a.scan(w=/(.*?)x.(\d+)/).map{|x|b.scan(w).map{|y|(eval"[%s*(z=%s;%s),z+%s]"%y+=x)*"x^"}}*?+}

Try it online!

How?

First step: get all the numbers from both polynomials: scan returns the numbers as an array of pairs of strings. Then, do a cartesian product of the 2 lists. Now we have all the numbers where we need them, but still in the wrong order.

Example: if we multiply 3x^4 by -5x^2, we get the numbers as [["3","4"],["-5","2"]], the first idea was to zip and flatten this list, and then put the numbers into an expression to be evaluated as [3*-5, 4+2]. Actually, we don't need to reorder the numbers, we could do it inside the expression by using a temporary variable: the expression becomes [3*(z=4,-5),z+2].

After evaluating these expressions, we get the coefficient and exponent, we need to join them using "x^", and then join all the tems using "+".

Answer 4

Haskell, 124 121 bytes

import Data.Lists
f!x=map f.splitOn x
z=read!"x^"!"+"
a#b=drop 3$do[u,v]<-z a;[p,q]<-z b;" + "++shows(u*p)"x^"++show(v+q)

Note: TIO lacks Data.Lists, so I import Data.Lists.Split and Data.List: Try it online!

Edit: -3 bytes thanks to @Lynn.

Answer 5

Pyth - 39 bytes

LmsMcdK"x^"%2cb)j" + "m++*FhdKsedCM*FyM

Try it online.

Answer 6

JavaScript (Babel Node), 118 bytes

Takes input as (a)(b).

a=>b=>(g=s=>[...s.matchAll(/(-?\d+)x.(\d+)/g)])(a).flatMap(([_,x,p])=>g(b).map(([_,X,P])=>x*X+'x^'+-(-p-P))).join` + `

Try it online!

Answer 7

SNOBOL4 (CSNOBOL4), 192 176 bytes

	P =INPUT
	Q =INPUT
	D =SPAN(-1234567890)
P	P D . K ARB D . W REM . P	:F(O)
	B =Q
B	B D . C ARB D . E REM . B	:F(P)
	O =O ' + ' K * C 'x^' W + E	:(B)
O	O ' + ' REM . OUTPUT
END

Try it online!

	P =INPUT				;* read P
	Q =INPUT				;* read Q
	D =SPAN(-1234567890)			;* save PATTERN for Digits (or a - sign); equivalent to [0-9\\-]+
P	P D . K ARB D . W REM . P	:F(O)	;* save the Koefficient and the poWer, saving the REMainder as P, or if no match, goto O
	B =Q					;* set B = Q
B	B D . C ARB D . E REM . B	:F(P)	;* save the Coefficient and the powEr, saving the REMainder as B, or if no match, goto P
	O =O ' + ' K * C 'x^' W + E	:(B)	;* accumulate the output
O	O ' + ' REM . OUTPUT			;* match ' + ' and OUTPUT the REMainder
END

Answer 8

JavaScript, 112 110 bytes

I found two alternatives with the same length. Call with currying syntax: f(A)(B)

A=>B=>(P=x=>x.split`+`.map(x=>x.split`x^`))(A).flatMap(a=>P(B).map(b=>a[0]*b[0]+'x^'+(a[1]- -b[1]))).join` + `

f=
A=>B=>(P=x=>x.split`+`.map(x=>x.split`x^`))(A).flatMap(a=>P(B).map(b=>a[0]*b[0]+'x^'+(a[1]- -b[1]))).join` + `

console.log( f('5x^4')('3x^23') )
console.log( f('6x^2 + 7x^1 + -2x^0')('1x^2 + -2x^3') )
console.log( f('3x^1 + 5x^2 + 2x^4 + 3x^0')('3x^0') )
console.log( f('4x^3 + -2x^14 + 54x^28 + -4x^5')('-0x^7') )
console.log( f('4x^3 + -2x^4 + 0x^255 + -4x^5')('-3x^4 + 2x^2') )

A=>B=>(P=x=>x.split`+`.map(x=>x.split`x^`))(A).flatMap(([c,e])=>P(B).map(([C,E])=>c*C+'x^'+(e- -E))).join` + `

f=
A=>B=>(P=x=>x.split`+`.map(x=>x.split`x^`))(A).flatMap(([c,e])=>P(B).map(([C,E])=>c*C+'x^'+(e- -E))).join` + `

console.log( f('5x^4')('3x^23') )
console.log( f('6x^2 + 7x^1 + -2x^0')('1x^2 + -2x^3') )
console.log( f('3x^1 + 5x^2 + 2x^4 + 3x^0')('3x^0') )
console.log( f('4x^3 + -2x^14 + 54x^28 + -4x^5')('-0x^7') )
console.log( f('4x^3 + -2x^4 + 0x^255 + -4x^5')('-3x^4 + 2x^2') )

-2 bytes (Luis): Remove spaces around split delimiter.

---

JavaScript, 112 bytes

Using String.prototype.matchAll.

A=>B=>(P=x=>[...x.matchAll(/(\S+)x.(\S+)/g)])(A).flatMap(a=>P(B).map(b=>a[1]*b[1]+'x^'+(a[2]- -b[2]))).join` + `

f=
A=>B=>(P=x=>[...x.matchAll(/(\S+)x.(\S+)/g)])(A).flatMap(a=>P(B).map(b=>a[1]*b[1]+'x^'+(a[2]- -b[2]))).join` + `

console.log( f('5x^4')('3x^23') )
console.log( f('6x^2 + 7x^1 + -2x^0')('1x^2 + -2x^3') )
console.log( f('3x^1 + 5x^2 + 2x^4 + 3x^0')('3x^0') )
console.log( f('4x^3 + -2x^14 + 54x^28 + -4x^5')('-0x^7') )
console.log( f('4x^3 + -2x^4 + 0x^255 + -4x^5')('-3x^4 + 2x^2') )

Answer 9

Python 2, 193 bytes

import re
f=re.finditer
lambda a,b:' + '.join(' + '.join(`int(m.group(1))*int(n.group(1))`+'x^'+`int(m.group(2))+int(n.group(2))`for n in f('(-?\d+)x\^(\d+)',b))for m in f('(-?\d+)x\^(\d+)',a))

Try it online!

Side note: First time doing a code golf challenge, so sorry if the attempt sucks haha

Answer 10

Retina, 110 bytes

\S\S+(?=.*\n(.+))
 $1#$&
|" + "L$v` (-?)(\d+)x.(\d+).*?#(-?)(\d+)x.(\d+)
$1$4$.($2*$5*)x^$.($3*_$6*
--|-(0)
$1

Try it online! Explanation:

\S\S+(?=.*\n(.+))
 $1#$&

Prefix each term in the first input with a #, a copy of the second input, and a space. This means that all of the terms in copies of the second input are preceded by a space and none of the terms from the first input are.

|" + "L$v` (-?)(\d+)x.(\d+).*?#(-?)(\d+)x.(\d+)
$1$4$.($2*$5*)x^$.($3*_$6*

Match all of the copies of terms in the second input and their corresponding term from the first input. Concatenate any - signs, multiply the coefficients, and add the indices. Finally join all of the resulting substitutions with the string  + .

--|-(0)
$1

Delete any pairs of -s and convert -0 to 0.

Answer 11

Jelly, 28 bytes

ṣ”+ṣ”xV$€)p/ZPSƭ€j⁾x^Ʋ€j“ + 

Try it online!

Full program. Takes the two polynomials as a list of two strings.

Explanation (expanded form)

ṣ”+ṣ”xV$€µ€p/ZPSƭ€j⁾x^Ʋ€j“ + ” Arguments: x
         µ                     Monadic chain.
          €                    Map the monadic link over the argument.
                               Note that this will "pop" the previous chain, so
                               it will really act as a link rather than a
                               sub-chain.
ṣ”+                             ṣ, right = '+'.
                                Split the left argument on each occurrence of
                                the right.
                                Note that strings in Jelly are lists of
                                single-character Python strings.
        €                       Map the monadic link over the argument.
       $                         Make a non-niladic monadic chain of at least
                                 two links.
   ṣ”x                            ṣ, right = 'x'.
                                  Split the left argument on each occurrence of
                                  the right.
      V                           Evaluate the argument as a niladic link.
            /                  Reduce the dyadic link over the argument.
           p                    Cartesian product of left and right arguments.
                       €       Map the monadic link over the argument.
                      Ʋ         Make a non-niladic monadic chain of at least
                                four links.
             Z                   Transpose the argument.
                 €               Map the monadic link over the argument.
                ƭ                 At the first call, call the first link. At the
                                  second call, call the second link. Rinse and
                                  repeat.
              P                    Product: ;1×/$
               S                   Sum: ;0+/$
                  j⁾x^           j, right = "x^".
                                 Put the right argument between the left one's
                                 elements and concatenate the result.
                        j“ + ” j, right = " + ".
                               Put the right argument between the left one's
                               elements and concatenate the result.

Aliasing

) is the same as µ€.
A trailing ” is implied and can be omitted.

Algorithm

Let's say we have this input:

["6x^2 + 7x^1 + -2x^0", "1x^2 + -2x^3"]

The first procedure is the Parsing, applied to each of the two polynomials. Let's handle the first one, "6x^2 + 7x^1 + -2x^0":

The first step is to split the string by '+', so as to separate the terms. This results in:

["6x^2 ", " 7x^1 ", " -2x^0"]

The next step is to split each string by 'x', to separate the coefficient from the exponent. The result is this:

[["6", "^2 "], [" 7", "^1 "], [" -2", "^0"]]

Currently, it looks like there's a lot of trash in these strings, but that trash is actually unimportant. These strings are all going to be evaluated as niladic Jelly links. Trivially, the spaces are unimportant, as they are not between the digits of the numbers. So we could as well evaluate the below and still get the same result:

[["6", "^2"], ["7", "^1"], ["-2", "^0"]]

The ^s look a bit more disturbing, but they actually don't do anything either! Well, ^ is the bitwise XOR atom, however niladic chains act like monadic links, except that the first link actually becomes the argument, instead of taking an argument, if it's niladic. If it's not, then the link will have an argument of 0. The exponents have the ^s as their first char, and ^ isn't niladic, so the argument is assumed to be 0. The rest of the string, i.e. the number, is the right argument of ^. So, for example, ^2 is \$0\text{ XOR }2=2\$. Obviously, \$0\text{ XOR }n=n\$. All the exponents are integer, so we are fine. Therefore, evaluating this instead of the above won't change the result:

[["6", "2"], ["7", "1"], ["-2", "0"]]

Here we go:

[[6, 2], [7, 1], [-2, 0]]

This step will also convert "-0" to 0.

Since we're parsing both inputs, the result after the Parsing is going to be this:

[[[6, 2], [7, 1], [-2, 0]], [[1, 2], [-2, 3]]]

The Parsing is now complete. The next procedure is the Multiplication.

We first take the Cartesian product of these two lists:

[[[6, 2], [1, 2]], [[6, 2], [-2, 3]], [[7, 1], [1, 2]], [[7, 1], [-2, 3]], [[-2, 0], [1, 2]], [[-2, 0], [-2, 3]]]

Many pairs are made, each with one element from the left list and one from the right, in order. This also happens to be the intended order of the output. This challenge really asks us to apply multiplicative distributivity, as we're asked not to further process the result after that.

The pairs in each pair represent terms we want to multiply, with the first element being the coefficient and the second being the exponent. To multiply the terms, we multiply the coefficients and add the exponents together (\$ax^cbx^d=abx^cx^d=ab(x^cx^d)=(ab)x^{c+d}\$). How do we do that? Let's handle the second pair, [[6, 2], [-2, 3]].

We first transpose the pair:

[[6, -2], [2, 3]]

We then take the product of the first pair, and the sum of the second:

[-12, 5]

The relevant part of the code, PSƭ€, doesn't actually reset its counter for each pair of terms, but, since they're pairs, it doesn't need to.

Handling all pairs of terms, we have:

[[6, 4], [-12, 5], [7, 3], [-14, 4], [-2, 2], [4, 3]]

Here, the Multiplication is done, as we don't have to combine like terms. The final procedure is the Prettyfying.

We first join each pair with "x^":

[[6, 'x', '^', 4], [-12, 'x', '^', 5], [7, 'x', '^', 3], [-14, 'x', '^', 4], [-2, 'x', '^', 2], [4, 'x', '^', 3]]

Then we join the list with " + ":

[6, 'x', '^', 4, ' ', '+', ' ', -12, 'x', '^', 5, ' ', '+', ' ', 7, 'x', '^', 3, ' ', '+', ' ', -14, 'x', '^', 4, ' ', '+', ' ', -2, 'x', '^', 2, ' ', '+', ' ', 4, 'x', '^', 3]

Notice how we've still got numbers in the list, so it's not really a string. However, Jelly has a process called "stringification", ran right at the end of execution of a program to print the result out. For a list of depth 1, it really just converts each element to its string representation and concatenates the strings together, so we get the desired output:

6x^4 + -12x^5 + 7x^3 + -14x^4 + -2x^2 + 4x^3

Answer 12

C# (Visual C# Interactive Compiler), 192 190 bytes

n=>m=>string.Join(g=" + ",from a in n.Split(g)from b in m.Split(g)select f(a.Split(p="x^")[0])*f(b.Split(p)[0])+p+(f(a.Split(p)[1])+f(b.Split(p)[1])));Func<string,int>f=int.Parse;string p,g;

Query syntax seems to be a byte shorter than method syntax.

Try it online!

Answer 13

Perl 6, 114 bytes

{my&g=*.match(/(\-?\d+)x\^(\d+)/,:g)».caps».Map;join " + ",map {"{[*] $_»{0}}x^{[+] $_»{1}}"},(g($^a)X g $^b)}

Try it online!

Answer 14

Python 2, 130 bytes

lambda a,b:' + '.join([`v*V`+'x^'+`k+K`for V,K in g(a)for v,k in g(b)])
g=lambda s:[map(int,t.split('x^'))for t in s.split(' + ')]

Try it online!