Ваша задача состоит в том, чтобы взять два целочисленных полиномиальных выражения с одной переменной и умножить их на их упрощенное перво-членное разложение слева направо (AKA FOIL в случае биномов). Не объединяйте одинаковые термины и не переупорядочивайте результат. Чтобы быть более явным в отношении расширения, умножьте первый член в первом выражении на каждый член во втором по порядку и продолжайте в первом выражении, пока все члены не будут умножены на все остальные члены. Выражения будут даны в упрощенном варианте LaTeX.

Каждое выражение будет представлять собой последовательность терминов, разделенных +(с ровно одним пробелом на каждой стороне). Каждый термин будет соответствовать следующему регулярному выражению: (нотация PCRE)

-?\d+x\^\d+

В простом английском языке термин является необязательным первым, -за которым следуют одна или несколько цифр, за которыми xследует целая неотрицательная сила (с ^)

Пример полного выражения:

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

При подключении к LaTeX вы получаете $6x^3 + 1337x^2 + -4x^1 + 2x^0$

Вывод также должен соответствовать этому формату.

Так как в этом формате скобки не окружают показатели степени, LaTeX будет отображать многозначные показатели неправильно. (например, 4x^3 + -2x^14 + 54x^28 + -4x^5отображается как $4x^3 + -2x^14 + 54x^28 + -4x^5$ ). Вам не нужно учитывать это, ивы не должны включать скобкив свои выходные данные.

Примеры тестовых случаев

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

Правила и предположения

• Вы можете предположить, что все входные данные соответствуют именно этому формату. Поведение для любого другого формата не определено для целей этой задачи.
  • Следует отметить, что любой метод взятия двух полиномов действителен при условии, что оба считываются как строки, соответствующие вышеуказанному формату.
• Порядок многочленов имеет значение из-за ожидаемого порядка расширения продукта.
• Вы должны поддерживать входные коэффициенты между $-128$ и $127$ и входные показатели до $255$ .
  • Поэтому должны поддерживаться выходные коэффициенты между $-16,256$ и $16,384$ и показателями до $510$ .
• Можно предположить, что каждый входной многочлен содержит не более 16 членов
  • Поэтому вы должны (как минимум) поддерживать до 256 терминов в выводе
• Термины с нулевыми коэффициентами должны быть оставлены как есть, с показателями, правильно объединенными
• Отрицательный ноль допускается на входе, но семантически неотличим от положительного нуля. Всегда выводите положительный ноль. Не опускайте нулевые условия.

Счастливого гольфа! Удачи!

R , 159 153 148 байт

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)

Попробуйте онлайн!

Я действительно хотел использовать outer, так что почти наверняка есть более эффективный подход.

Хаскелл , 131 122 байта

(%)=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)

Попробуйте онлайн!

f анализирует полином из строки, ! умножает два из них и форматирует результат.

H.PWiz сохранил 9 байтов. Благодарность!

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

Рубин , 102 100 98 байт

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

Попробуйте онлайн!

Как?

Первый шаг: получить все числа из обоих полиномов: scanвозвращает числа в виде массива пар строк. Затем сделайте декартово произведение из 2 списков. Теперь у нас есть все числа, где они нам нужны, но все-таки в неправильном порядке.

Пример: если мы умножим 3x^4на -5x^2, мы получим числа как [["3","4"],["-5","2"]], первая идея состояла в том, чтобы сжать и сгладить этот список, а затем поместить числа в выражение, которое будет оценено как [3*-5, 4+2]. На самом деле нам не нужно переупорядочивать числа, мы могли бы сделать это внутри выражения, используя временную переменную: выражение становится [3*(z=4,-5),z+2].

После оценки этих выражений мы получаем коэффициент и показатель степени, нам нужно соединить их, используя "x^", а затем объединить все те, которые используют "+".

Haskell, 124 121 байт

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)

Примечание: TIO не хватает Data.Lists, поэтому я импортирую Data.Lists.Splitи Data.List: Попробуйте онлайн!

Изменить: -3 байта благодаря @Lynn.

Pyth - 39 байт

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

Попробуйте онлайн .

JavaScript (Вавилонский узел) , 118 байт

Принимает вход как (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` + `

Попробуйте онлайн!

Python 2 , 193 байта

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

Попробуйте онлайн!

Примечание: в первый раз выполнил кодовый гольф, так что извините, если попытка отстой хаха

Сетчатка , 110 байт

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

Попробуйте онлайн! Объяснение:

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

Перед каждым термином в первом входе добавьте префикс #, копию второго ввода и пробел. Это означает, что всем терминам в копиях второго ввода предшествует пробел, и ни один из терминов из первого ввода не является.

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

Сопоставьте все копии терминов во втором входе и соответствующие им термины из первого ввода. Объедините любые -знаки, умножьте коэффициенты и добавьте индексы. Наконец, объедините все полученные замены со строкой  + .

--|-(0)
$1

Удалите любые пары -s и конвертируйте -0в0 .

СНОБОЛ4 (CSNOBOL4) , 192 176 байт

	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

Попробуйте онлайн!

	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

Perl 6 , 114 байт

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

Попробуйте онлайн!

Python 2 , 130 байт

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(' + ')]

Попробуйте онлайн!

C # (интерактивный компилятор Visual C #) , 192 190 байт

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;

Синтаксис запроса кажется на байт короче, чем синтаксис метода.

Попробуйте онлайн!

Желе , 28 байт

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

Попробуйте онлайн!

Полная программа. Принимает два полинома в виде списка из двух строк.

Пояснение (развернутая форма)

ṣ”+ṣ”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

)так же, как µ€.
Трейлинг ”подразумевается и может быть опущен.

Алгоритм

Допустим, у нас есть этот вход:

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

Первой процедурой является синтаксический анализ, применяемый к каждому из двух полиномов. Давайте разберемся с первым,"6x^2 + 7x^1 + -2x^0" :

Первый шаг - разделить строку '+', чтобы разделить термины. Это приводит к:

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

Следующим шагом является разделение каждой строки на 'x', чтобы отделить коэффициент от показателя степени. Результат таков:

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

В настоящее время похоже, что в этих строках много мусора, но этот мусор на самом деле не важен. Все эти строки будут оцениваться как ниладические ссылки Jelly. Тривиально, пробелы не важны, так как они не находятся между цифрами чисел. Таким образом, мы могли бы также оценить ниже и получить тот же результат:

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

Они ^выглядят немного более тревожно, но на самом деле они тоже ничего не делают! Что ж, ^это побитовый атом XOR, однако ниладические цепочки действуют как монадические ссылки, за исключением того, что первая ссылка фактически становится аргументом, вместо того, чтобы принимать аргумент, если он неладический. Если это не так, то ссылка будет иметь аргумент 0. Экспоненты имеют ^символ s в качестве первого символа и ^не нильадные, поэтому предполагается, что аргумент будет 0. Остальная часть строки, то есть число, является правильным аргументом ^. Так, например, ^2есть$0\text{ XOR }2=2$, Очевидно, что$0\text{ XOR }n=n$, Все показатели целые, поэтому у нас все хорошо. Следовательно, оценка этого вместо вышеизложенного не изменит результат:

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

Вот так:

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

Этот шаг также будет преобразован "-0"в 0.

Поскольку мы анализируем оба входа, результат после синтаксического анализа будет следующим:

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

Разбор теперь завершен. Следующая процедура - Умножение.

Сначала мы возьмем декартово произведение этих двух списков:

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

Составлено много пар, каждая с одним элементом из левого списка и одной справа по порядку. Это также, случается, предполагаемый порядок вывода. Эта задача действительно требует от нас применения мультипликативной дистрибутивности, поскольку нас просят не обрабатывать результат после этого.

Пары в каждой паре представляют термины, которые мы хотим умножить, причем первый элемент является коэффициентом, а второй - показателем степени. Чтобы умножить слагаемые, мы умножим коэффициенты и сложим экспоненты вместе ($ax^cbx^d=abx^cx^d=ab(x^cx^d)=(ab)x^{c+d}$). Как мы это делаем? Давайте разберемся со второй парой,[[6, 2], [-2, 3]] .

Сначала мы транспонируем пару:

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

Затем мы берем произведение первой пары и сумму второй:

[-12, 5]

Соответствующая часть кода, PSƭ€ самом деле не сбрасывает свой счетчик для каждой пары терминов, но, поскольку они являются парами, в этом нет необходимости.

Обрабатывая все пары терминов, мы имеем:

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

Здесь умножение сделано, так как нам не нужно объединять одинаковые термины. Последняя процедура - Prettyfying.

Сначала мы присоединяемся к каждой паре с "x^":

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

Затем мы присоединяемся к списку " + ":

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

Обратите внимание, что у нас все еще есть числа в списке, так что на самом деле это не строка. Тем не менее, в Jelly есть процесс, называемый «stringification», запускаемый прямо в конце выполнения программы для вывода результата. Для списка глубины 1 он просто конвертирует каждый элемент в его строковое представление и объединяет строки вместе, поэтому мы получаем желаемый результат:

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

JavaScript, 112 110 байт

Я нашел две альтернативы одинаковой длины. Вызов с карринг синтаксисом: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 байта ( Луис ): убрать пробелы вокруг splitразделителя.

JavaScript, 112 байт

Используя 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') )