Polinomialception

22

Biorąc pod uwagę dwa wielomiany f,go dowolnym stopniu względem liczb całkowitych, twój program / funkcja powinna ocenić pierwszy wielomian w drugim wielomianu. f(g(x))(aka skład (fog)(x) dwóch wielomianów)

Detale

Wbudowane są dozwolone. Możesz założyć dowolne rozsądne formatowanie jako wejście / wyjście, ale format wejścia i wyjścia powinien być zgodny. Np. Formatowanie jako ciąg

x^2+3x+5

lub jako lista współczynników:

[1,3,5] or alternatively [5,3,1]

Ponadto można założyć, że wielomiany wejściowe są w pełni rozwinięte, a oczekuje się, że wyjściowe zostaną w pełni rozwinięte.

Przykłady

A(x) = x^2 + 3x + 5, B(y) = y+1
A(B(y)) = (y+1)^2 + 3(y+1) + 5 = y^2 + 5y + 9

A(x) = x^6 + x^2 + 1, B(y) = y^2 - y
A(B(y))= y^12 - 6y^11 + 15y^10 - 20y^9 + 15y^8 - 6y^7 + y^6 + y^4 - 2 y^3 + y^2 + 1

A(x) = 24x^3 - 144x^2 + 288x - 192, B(y) = y + 2
A(B(y)) = 24y^3

A(x) = 3x^4 - 36x^3 + 138x^2 - 180x + 27, B(y) = 2y + 3
A(B(y)) = 48y^4 - 96y^2
wada
źródło
co z wbudowanymi?
Maltysen
1
@Maltysen „Szczegóły: Wbudowane są dozwolone. (...)” : D
flawr 23.04.16
2
Myślę, że „każdy rozsądny format” może być nieco rozciągliwy. Jeśli dozwolona jest funkcja, która ocenia wielomian, funkcja kompozycji (.)jest odpowiedzią w języku Haskell. Prawdopodobnie masz na myśli pewną reprezentację listy współczynników.
xnor 24.04.16
1
Tytuł! Właśnie to dostałem :-D
Luis Mendo
2
@LuisMendo Szybki myśliciel = P
wada

Odpowiedzi:

10

Haskell, 86 72 bajtów

u!c=foldr1((.u).zipWith(+).(++[0,0..])).map c
o g=(0:)!((<$>g).(*))!pure

Definiuje funkcję o, która o g foblicza kompozycję f ∘ g. Wielomiany są reprezentowane przez niepustą listę współczynników rozpoczynającą się od stałego terminu.

Próbny

*Main> o [1,1] [5,3,1]
[9,5,1]
*Main> o [0,-1,1] [1,0,1,0,0,0,1]
[1,0,1,-2,1,0,1,-6,15,-20,15,-6,1]
*Main> o [2,1] [-192,288,-144,24]
[0,0,0,24]
*Main> o [3,2] [27,-180,138,-36,3]
[0,0,-96,0,48]

Jak to działa

Brak wbudowanych bibliotek lub bibliotek związanych z wielomianem. Obserwuj podobne nawroty

f (x) = a + f₁ (x) x ⇒ f (x) g (x) = ag (x) + f₁ (x) g (x) x,
f (x) = a + f₁ (x) x ⇒ f (g (x)) = a + f₁ (g (x)) g (x),

odpowiednio do mnożenia i składu wielomianu. Oboje przyjmują formę

f (x) = a + f₁ (x) x ⇒ W (f) (x) = C (a) (x) + U (W (f₁)) (x).

Operator !rozwiązuje powtarzalność tego formularza dla W przy U i C, używając zipWith(+).(++[0,0..])do dodawania wielomianowego (zakładając, że drugi argument jest dłuższy - dla naszych celów zawsze będzie). Następnie,

(0:)mnoży argument wielomianowy przez x (przez przygotowanie współczynnika zerowego);
(<$>g).(*)mnoży argument skalarny przez wielomian g;
(0:)!((<$>g).(*))mnoży argument wielomianu przez wielomian g;
purepodnosi argument skalarny do stałego wielomianu (lista singletonów);
(0:)!((<$>g).(*))!puretworzy argument wielomianowy z wielomianem g.

Anders Kaseorg
źródło
9

Mathematica, 17 bajtów

Expand[#/.x->#2]&

Przykładowe użycie:

In[17]:= Expand[#/.x->#2]& [27 - 180x + 138x^2 - 36x^3 + 3x^4, 3 + 2x]

              2       4
Out[17]= -96 x  + 48 x
feersum
źródło
7

TI-Basic 68k, 12 bajtów

a|x=b→f(a,b)

Użycie jest proste, np. W pierwszym przykładzie:

f(x^2+3x+5,y+1)

Który zwraca

y^2+5y+9
wada
źródło
Wydaje mi się, że oszustwo wymaga, aby dane wejściowe były w różnych zmiennych. Czy to ma znaczenie dla tej odpowiedzi?
feersum
Nie krępuj się, wyraźnie zezwoliłem na dowolny rozsądny dogodny format wejściowy.
flawr
Jeśli chodzi o edycję komentarza: tak, to ma znaczenie.
flawr 23.04.16
Nie znam zbyt dobrze zasad na tej stronie. Czy poprawne jest bycie 1 bajtem w TI-BASIC?
asmeurer
@asmeurer Rzeczywiście: TI-Basic jest oceniany przez kodowanie zastosowane w odpowiednich kalkulatorach. Jeśli jesteś zainteresowany szczegółami, możesz przeczytać to tutaj na meta . Tabela tokenów można znaleźć tutaj na ti-basic-dev .
flawr
6

Python 2, 138 156 162 bajtów

Dane wejściowe powinny być najpierw listami liczb całkowitych o najmniejszych mocach.

def c(a,b):
 g=lambda p,q:q>[]and q[0]+p*g(p,q[1:]);B=99**len(`a+b`);s=g(g(B,b),a);o=[]
 while s:o+=(s+B/2)%B-B/2,;s=(s-o[-1])/B
 return o

Nie golfowany:

def c(a,b):
 B=sum(map(abs,a+b))**len(a+b)**2
 w=sum(B**i*x for i,x in enumerate(b))
 s=sum(w**i*x for i,x in enumerate(a))
 o=[]
 while s:o+=min(s%B,s%B-B,key=abs),; s=(s-o[-1])/B
 return o

W tym obliczeniu współczynniki wielomianowe są postrzegane jako cyfry (które mogą być ujemne) liczby w bardzo dużej bazie. Po wielomianach w tym formacie mnożenie lub dodawanie jest operacją na liczbach całkowitych. Tak długo, jak podstawa jest wystarczająco duża, nie będzie żadnych elementów przenoszących się na sąsiednie cyfry.

-18 od ulepszenia związanego Bzgodnie z sugestią @xnor.

feersum
źródło
Niezła metoda. Dla B, to 10**len(`a+b`)wystarczy?
xnor
@ xnor Może ... trudno mi to powiedzieć.
feersum
+1 To naprawdę kreatywne rozwiązanie i fajne wykorzystanie bigintów !!!
flawr 24.04.16
@xnor Teraz udało mi się przekonać, że długość tego współczynnika jest liniowa na długości wejściowej :)
feersum 24.04.2016
5

Python + SymPy, 59 35 bajtów

from sympy import*
var('x')
compose

Dzięki @asmeurer za grę w golfa przy 24 bajtach!

Testowe uruchomienie

>>> from sympy import*
>>> var('x')
x
>>> f = compose
>>> f(x**2 + 3*x + 5, x + 1)
x**2 + 5*x + 9
Dennis
źródło
1
SymPy ma compose()funkcję.
asmeurer 24.04.16
1
Gdzie jest odpowiedź Nie definiuje już żadnych funkcji ani nic nie robi ...
feersum
1
@feersum Nigdy tak nie było. Właśnie edytowałeś ten meta post.
Mego
3
@feersum Edytowałeś zaakceptowany meta post, aby zmodyfikować zasady dotyczące własnego programu. To nie jest ok
Mego
3
@feersum Choć być może myślałeś, że twoje sformułowania były niejednoznaczne, najwyraźniej nie było to dla reszty społeczności. Zaakceptowaliśmy konsensus, który from module import*;functionbył ważnym wnioskiem. Niezależnie od tego jest to nowsza polityka, która umożliwia importowanie i funkcje pomocnicze z nienazwanymi lambdas.
Mego
3

Szałwia, 24 bajty

lambda A,B:A(B).expand()

Począwszy od Sage 6.9 (wersja działająca na http://sagecell.sagemath.org ), wywołania funkcji bez wyraźnego przypisania argumentów ( f(2) rather than f(x=2)) powodują, że denerwujący i nieprzydatny komunikat jest drukowany na STDERR. Ponieważ STDERR może być domyślnie ignorowany w kodzie golfa, jest to nadal ważne.

Jest to bardzo podobne do odpowiedzi Dennisa na SymPy, ponieważ Sage jest a) zbudowany na Pythonie, i b) używa Maximy , systemu algebry komputerowej bardzo podobnej do SymPy na wiele sposobów. Jednak Sage jest znacznie potężniejszy niż Python z SymPy, a zatem jest wystarczająco innym językiem, że zasługuje na swoją własną odpowiedź.

Sprawdź wszystkie przypadki testowe online

Mego
źródło
2

PARI / GP , 19 bajtów

(a,b)->subst(a,x,b)

co pozwala ci to zrobić

%(x^2+1,x^2+x-1)

dostać

% 2 = x ^ 4 + 2 * x ^ 3 - x ^ 2 - 2 * x + 2

Charles
źródło
1

MATLAB z Symbolicznym zestawem narzędzi, 28 bajtów

@(f,g)collect(subs(f,'x',g))

To anonimowa funkcja. Aby go wywołać, przypisz go do zmiennej lub użyj ans. Dane wejściowe są łańcuchami o formacie (spacje są opcjonalne)

x^2 + 3*x + 5

Przykładowy przebieg:

>> @(f,g)collect(subs(f,'x',g))
ans = 
    @(f,g)collect(subs(f,'x',g))
>> ans('3*x^4 - 36*x^3 + 138*x^2 - 180*x + 27','2*x + 3')
ans =
48*x^4 - 96*x^2
Luis Mendo
źródło
1

Python 2, 239 232 223 bajty

r=range
e=reduce
a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
m=lambda p,q:[sum((p+k*[0])[i]*(q+k*[0])[k-i]for i in r(k+1))for k in r(len(p+q)-1)]
o=lambda f,g:e(a,[e(m,[[c]]+[g]*k)for k,c in enumerate(f)])

„Właściwa” implementacja, która nie nadużywa baz. Najpierw najmniej znaczący współczynnik.

ajest dodatkiem wielomianowym, mjest mnożeniem wielomianowym i ojest kompozycją.

orlp
źródło
Czy to m([c],e(m,[[1]]+[g]*k))nie to samo co e(m,[[c]]+[g]*k)?
Neil,
@Neil Dobry telefon, można zgnieść dwa w jednym!
lub
a=lambda*l:map(lambda x,y:(x or 0)+(y or 0),*l)
Anders Kaseorg 24.04.16
@AndersKaseorg Racja, dodałem go, dzięki :)
24.04.16
Może być możliwe uproszczenie dodawania wielomianu, ponieważ myślę, że jedna lista będzie zawsze dłuższa od drugiej, więc nie potrzebujesz jej ( or 0)w tej wersji.
Neil,
1

JavaScript (ES6), 150 103 bajtów

(f,g)=>f.map(n=>r=p.map((m,i)=>(g.map((n,j)=>p[j+=i]=m*n+(p[j]||0)),m*n+(r[i]||0)),p=[]),r=[],p=[1])&&r

Akceptuje i zwraca wielomiany jako tablicę a = [a 0 , a 1 , a 2 , ...], która reprezentuje 0 + a 1 * x + a 2 * x 2 ...

Edycja: Zaoszczędziłem 47 bajtów, zmieniając wielomian rekurencyjny na iteracyjny, co pozwoliło mi na scalenie dwóch mapwywołań.

Objaśnienie: r jest wynikiem, który zaczyna się od zera, reprezentowanym przez pustą tablicę, a p oznacza g h , która zaczyna się od jednego. p mnoży się kolejno przez każdą f h , a wynik kumuluje się w r . p jest także mnożone przez g jednocześnie.

(f,g)=>f.map(n=>            Loop through each term of f (n = f[h])
 r=p.map((m,i)=>(           Loop through each term of p (m = p[i])
  g.map((n,j)=>             Loop though each term of g (n = g[j])
   p[j+=i]=m*n+(p[j]||0)),  Accumulate p*g in p
  m*n+(r[i]||0)),           Meanwhile add p[i]*f[h] to r[i]
  p=[]),                    Reset p to 0 each loop to calculate p*g
 r=[],                      Initialise r to 0
 p=[1]                      Initialise p to 1
)&&r                        Return the result
Neil
źródło
1

Pyth, 51 34 bajtów

AQsM.t*LVG.usM.t.e+*]0k*LbHN0tG]1Z

Zestaw testowy .

Leaky Nun
źródło
2
kiedy python outgolfs pyth
downrep_nation 24.04.16
@ downrep_nation już nie :)
Leaky Nun
1

Rubinowy 2.4 + wielomian , 41 + 12 = 53 bajty

Używa flagi -rpolynomial. Dane wejściowe to dwa Polynomialobiekty.

Jeśli ktoś obezwładni mnie w waniliowym Ruby (bez wielomianowej biblioteki zewnętrznej), będę pod wielkim wrażeniem.

->a,b{i=-1;a.coefs.map{|c|c*b**i+=1}.sum}
Wartość tuszu
źródło