Symboliczne różnicowanie wielomianów

20

Różnicowanie symboliczne 1: Przeminęło Coefishin '

Zadanie

Napisz program, który pobiera wielomian w x od stdin (1 <deg (p) <128) i różnicuje go. Wielomian wejściowy będzie ciągiem następującej postaci:

"a + bx + cx^2 + dx^3 +" ...

gdzie współczynnik każdego składnika jest liczbą całkowitą (-128 <a <128). Każdy termin jest oddzielony jedną spacją, znakiem + i inną spacją; warunki liniowe i stałe pojawiają się jak wyżej (tj. brak x^0lub x^1). Warunki pojawią się w kolejności rosnącego stopnia, a moce o zerowym współczynniku zostaną pominięte. Wszystkie terminy ze współczynnikiem 1 lub -1 wyświetlają ten współczynnik jawnie.

Twój wynik musi mieć dokładnie taką samą formę. Zauważ, że współczynniki na wyjściu mogą być tak duże, jak 127 * 127 == 16129.

Przykłady

"3 + 1x + 2x^2" ==> "1 + 4x"
"1 + 2x + -3x^2 + 17x^17 + -1x^107" ==> "2 + -6x + 289x^16 + -107x^106"
"17x + 1x^2" ==> "17 + 2x"

Punktacja

Twój wynik to długość twojego programu w bajtach, pomnożona przez trzy, jeśli używasz wbudowanej lub biblioteki, która wykonuje algebrę symboliczną.

hYPotenuser
źródło
Nie mogę uwierzyć, że nie mieliśmy tutaj tego wyzwania!
flawr
5
@flawr My tak zrobiliśmy. (Chociaż ta również wymagała innych funkcji i nie miała tak surowych reguł dotyczących formatu wyjściowego.)
Martin Ender
@flawr Myślałem o tym samym ... a mimo to nie znalazłem powiązanego wyszukiwania Martina. Ach tak.
hYPotenuser

Odpowiedzi:

15

Retina , 53 43 42 41 40 35 bajtów

^[^x]+ |(\^1)?\w(?=1*x.(1+)| |$)
$2

Dla celów zliczania każda linia przechodzi w osobny plik, ale możesz uruchomić powyższy jako pojedynczy plik, wywołując Retina z -sflagą.

Oczekuje to, że liczby w ciągu wejściowym zostaną podane pojedynczo i da wynik w tym samym formacie. Na przykład

1 + 11x + -111x^11 + 11x^111 + -1x^11111
-->
11 + -111111x + 111111x^11 + -11111x^1111

zamiast

1 + 2x + -3x^2 + 2x^3 + -1x^5
-->
2 + -6x + 6x^2 + -5x^4

Wyjaśnienie

Kod opisuje pojedyncze podstawienie wyrażenia regularnego, które zasadniczo składa się z 4 podstawień skompresowanych w jedno. Zauważ, że tylko jedna z gałęzi zapełni grupę, $2więc jeśli którykolwiek z pozostałych trzech pasujących elementów, dopasowanie zostanie po prostu usunięte z łańcucha. Możemy więc spojrzeć osobno na cztery różne przypadki:

^[^x]+<space>
<empty>

Jeśli możliwe jest dotarcie do spacji od początku łańcucha bez napotkania znaku x, oznacza to, że pierwszy termin jest terminem stałym i usuwamy go. Ze względu na chciwość +, będzie to również pasować do plus i drugiej spacji po stałym terminie. Jeśli nie ma stałego terminu, ta część po prostu nigdy nie będzie pasować.

x(?= )
<empty>

Dopasowuje to, po xktórym następuje spacja, tj. xTerminu liniowego (jeśli istnieje), i usuwa go. Możemy być pewni, że jest po nim spacja, ponieważ stopień wielomianu wynosi zawsze co najmniej 2.

1(?=1*x.(1+))
$1

Wykonuje to pomnożenie współczynnika przez wykładnik. Odpowiada to pojedynczej 1wartości współczynnika i zastępuje ją przez cały odpowiedni wykładnik za pośrednictwem lookahead.

(\^1)?1(?= |$)
<empty>

Zmniejsza to wszystkie pozostałe wykładniki, dopasowując końcowe 1(zapewnione przez lookahead). Jeśli możliwe jest dopasowanie ^11(i granicy słów), usuwamy to, co dba o prawidłowe wyświetlanie terminu liniowego.

W przypadku kompresji zauważamy, że większość warunków nie ma na siebie wpływu. (\^1)?nie będzie pasować, jeśli spojrzenie w trzecim przypadku jest prawdziwe, więc możemy połączyć te dwa razem jako

(\^1)?1(?=1*x.(1+)| |$)
$2

Teraz mamy już uprzedzona potrzebne do drugiej sprawy i inni nigdy nie może być prawdą podczas dopasowywania x, dzięki czemu możemy łatwo uogólnić 1Do \w:

(\^1)?\w(?=1*x.(1+)| |$)
$2

Pierwszy przypadek tak naprawdę nie ma nic wspólnego z innymi, dlatego trzymamy go oddzielnie.

Martin Ender
źródło
9

CJam, 43 41 bajtów

Qleu'^/';*'+/{~:E[*'x['^E(]]E<}/]1>" + "*

Dzięki @ jimmy23013 za wskazanie jednego błędu i odgranie dwóch bajtów!

Wypróbuj online w interpretatorze CJam .

Jak to działa

Q           e# Leave an empty array on the bottom of the stack.
l           e# Read a line from STDIN.
eu'^/';*    e# Convert to uppercase and replace carets with semicolons.
'+/         e# Split at plus signs.

{           e# For each resulting chunk:
  ~         e#   Evaluate it. "X" pushes 1 and ";" discards.
            e#   For example, "3X" pushes (3 1) and "3X;2" (3 2).
   :E       e#   Save the rightmost integer (usually the exponent) in E.
   [        e#
     *      e#   Multiply both integers.
            e#   For a constant term c, this repeats the empty string (Q) c times.
     'x     e#   Push the character 'x'.
     ['^E(] e#   Push ['^' E-1].
   ]        e#
   E<       e#  Keep at most E elements of this array.
            e#  If E == 1, 'x' and ['^' E-1] are discarded.
            e#  If E == 2, ['^' E-1] is discarded.
            e#  If E >= 3, nothing is discarded.
}/          e#

]           e# Wrap the entire stack in an array.
1>          e# Discard its first element.
            e# If the first term was constant, this discards [""]. ["" 'x']
            e# or ["" 'x' ['^' E-1]], depending on the constant.
            e# In all other cases, it discards the untouched empty array (Q).
" + "*      e# Join all kept array elements, separating by " + ".
Dennis
źródło
5

Perl, 64 63 bajtów

Kod 62b + 1 linia poleceń (-p)

W tej chwili nie jest to niesamowite, ale nadal będę starał się to skracać.

s/(\d+)x.(\d+)/$1*$2."x^".($2-1)/eg;s/\^1\b|^\d+ . |x(?!\^)//g

Przykład użycia:

echo "1 + 2x + 3x^2" | perl -pe 's/(\d+)x.(\d+)/$1*$2."x^".($2-1)/eg;s/\^1\b|^\d+ . |x(?!\^)//g'

Dzięki Denis za -1b

Jarmex
źródło
5

Julia, 220 bajtów

Bez wyrażeń regularnych!

y->(A=Any[];for i=parse(y).args[2:end] T=typeof(i);T<:Int&&continue;T==Symbol?push!(A,1):(a=i.args;c=a[2];typeof(a[3])!=Expr?push!(A,c):(x=a[3].args[3];push!(A,string(c*x,"x",x>2?string("^",ex-1):""))))end;join(A," + "))

Tworzy to funkcję lambda, która przyjmuje ciąg i zwraca ciąg. Wewnętrzne naśladują to, co dzieje się, gdy analizowany jest kod Julii: ciąg jest przetwarzany na symbole, wyrażenia i wywołania. Mogę spróbować napisać pełną funkcję różnicowania symbolicznego Julii i zgłosić ją jako część Julii.

Niegolfowane + wyjaśnienie:

function polyderiv{T<:AbstractString}(y::T)

    # Start by parsing the string into an expression
    p = parse(y)

    # Define an output vector to hold each differentiated term
    A = Any[]

    # Loop through the elements of p, skipping the operand
    for i in p.args[2:end]

        T = typeof(i)

        # Each element will be an integer, symbol, or expression.
        # Integers are constants and thus integrate to 0. Symbols
        # represent x alone, i.e. "x" with no coefficient or
        # exponent, so they integrate to 1. The difficulty here
        # stems from parsing out the expressions.

        # Omit zero derivatives
        T <: Int && continue

        if T == Symbol
            # This term will integrate to 1
            push!(A, 1)
        else
            # Get the vector of parsed out expression components.
            # The first will be a symbol indicating the operand,
            # e.g. :+, :*, or :^. The second element is the
            # coefficient.
            a = i.args

            # Coefficient
            c = a[2]

            # If the third element is an expression, we have an
            # exponent, otherwise we simply have cx, where c is
            # the coefficient.
            if typeof(a[3]) != Expr
                push!(A, c)
            else
                # Exponent
                x = a[3].args[3]

                # String representation of the differentiated term
                s = string(c*x, "x", x > 2 ? string("^", x-1) : "")

                push!(A, s)
            end
        end
    end

    # Return the elements of A joined into a string
    join(A, " + ")
end
Alex A.
źródło
3

C, 204 162 bajty

#define g getchar()^10
h,e;main(c){for(;!h&&scanf("%dx%n^%d",&c,&h,&e);h=g?g?e?printf(" + "):0,0:1:1)e=e?e:h?1:0,e?printf(e>2?"%dx^%d":e>1?"%dx":"%d",c*e,e-1):0;}

Zasadniczo przeanalizuj każdy termin i wydrukuj zróżnicowany termin po kolei. Dość bezpośredni.

Cole Cameron
źródło
2

JavaScript ES6, 108 bajtów

f=s=>s.replace(/([-\d]+)(x)?\^?(\d+)?( \+ )?/g,(m,c,x,e,p)=>x?(c*e||c)+(--e?x+(e>1?'^'+e:''):'')+(p||''):'')

Fragment kodu ES5:

// ES5 version, the only difference is no use of arrow functions.
function f(s) {
  return s.replace(/([-\d]+)(x)?\^?(\d+)?( \+ )?/g, function(m,c,x,e,p) {
    return x ? (c*e||c) + (--e?x+(e>1?'^'+e:''):'') + (p||'') : '';
  });
}

[
  '3 + 1x + 2x^2',
  '1 + 2x + -3x^2 + 17x^17 + -1x^107',
  '17x + 1x^2'
].forEach(function(preset) {
  var presetOption = new Option(preset, preset);
  presetSelect.appendChild(presetOption);
});

function loadPreset() {
  var value = presetSelect.value;
  polynomialInput.value = value;
  polynomialInput.disabled = !!value;
  showDifferential();
}

function showDifferential() {
  var value = polynomialInput.value;
  output.innerHTML = value ? f(value) : '';
}
code {
  display: block;
  margin: 1em 0;
}
<label for="presetSelect">Preset:</label>
<select id="presetSelect" onChange="loadPreset()">
  <option value="">None</option>
</select>
<input type="text" id="polynomialInput"/>
<button id="go" onclick="showDifferential()">Differentiate!</button>
<hr />
<code id="output">
</code>

George Reith
źródło
2

Python 2, 166 bajtów

Chłopcze, wydaje się to dłuższe niż powinno.

S=str.split
def d(t):e="^"in t and int(S(t,"^")[1])-1;return`int(S(t,"x")[0])*(e+1)`+"x"[:e]+"^%d"%e*(e>1)
print" + ".join(d(t)for t in S(raw_input()," + ")if"x"in t)

Funkcja dprzyjmuje nietrwały składnik ti zwraca jego pochodną. Powodem, dla którego ja defzamiast funkcji lambda jest to, że mogę przypisać wykładnik minus 1 doe , który następnie jest używany cztery razy. Główną irytującą rzeczą jest konieczność rzucania tam i z powrotem między ciągami znaków i ints, chociaż pomaga w tym operator wsteczny Python 2.

Następnie dzielimy dane wejściowe na terminy i wzywamy dkażdego z nich "x", co eliminuje stały składnik. Wyniki są ponownie łączone i drukowane.

DLosc
źródło
2

CJam, 62 57 55 49 bajtów

Dennis wstydził się tego, zanim jeszcze zauważyłem, że strona została ponownie uruchomiona. Ale oto moje dzieło:

lS/{'x/:T,({T~1>:T{~T~*'xT~(:T({'^T}&}&" + "}&}/;

Najnowsza wersja zapisuje kilka bajtów ze skrótami sugerowanymi przez @Dennis (używaj zmiennych i rozdzielaj spacje zamiast +).

Wypróbuj online

Reto Koradi
źródło
1
Zapisanie zmiennej jest krótsze niż pojawienie się w bloku else. Na przykład _({'^a\}{;}?jest o 1 bajt dłuższy niż :T({T'^a\}&.
Dennis
1
Jeśli podzielisz się spacjami zamiast znaków plus, nie potrzebujesz ~bloku w pozostałym bloku i możesz go również wyeliminować.
Dennis
@Dennis To działa, dzięki. Początkowo chciałem wyeliminować znaki plus, ale i tak wypadają, gdy testuję na obecność x. Znalazłem kilka ulepszeń, gdy byłem przy tym. Głównie, ponieważ mam teraz wartości w zmiennych, mogę je przywołać tam, gdzie naprawdę ich potrzebuję, oszczędzając trochę manipulacji stosami. Miałem też błąd, aktóry powinien był zostać usunięty, gdy wcześniej zoptymalizowałem generowanie danych wyjściowych.
Reto Koradi,
1

Pyth, 62 bajty

jJ" + "m::j"x^",*Fdted"x.1$"\x"x.0"kftTmvMcd"x^"c:z"x ""x^1 "J

Całkiem brzydkie rozwiązanie, wykorzystujące pewne podstawienia wyrażeń regularnych.

orlp
źródło
1

Python 3, 176 bajtów

s=input().split(' + ')
y='x'in s[0]
L=map(lambda x:map(int,x.split('x^')),s[2-y:])
print(' + '.join([s[1-y][:-1]]+['x^'.join(map(str,[a*b,b-1])).rstrip('^1')for a,b in L]))

Rzeczywiście, główną irytacją jest konieczność konwersji między ciągami znaków i ints. Ponadto, jeśli wymagany byłby stały termin, kod miałby tylko 153 bajty.

El'endia Starman
źródło
Pierwsza odpowiedź, kręcenie za pokonanie DLosc, nie całkiem tam dotarła.
El'endia Starman
0

Python 2, 229 bajtów

import os
print' + '.join([i,i[:-2]][i[-2:]=='^1'].replace('x^0','')for i in[`a*b`+'x^'+`b-1`for a,b in[map(int,a.split('x^'))for a in[[[i+'x^0',i+'^1'][i[-1]=='x'],i]['^'in i]for i in os.read(0,9**9).split(' + ')]]]if i[0]!='0')
nog642
źródło
0

Python 2, 174 bajty

print' + '.join(['%d%s%s'%(b[0]*b[1],'x'*(b[1]>1),'^%d'%(b[1]-1)*(b[1]>2))for b in[map(int,a.split('x^')if 'x^'in a else[a[:-1],1])for a in input().split(' + ')if 'x'in a]])

Niestety sztuczka DLosc polegająca na zmianie nazwy metody podziału i wykonaniu różnicowania w określonej funkcji nie skraca mojego kodu ...

pjmv
źródło