Diferensiasi Simbolik Polinomial

20

Diferensiasi Simbolik 1: Gone Coefishin '

Tugas

Tulis sebuah program yang mengambil polinomial dalam x dari stdin (1 <deg (p) <128) dan bedakan. Input polinomial akan berupa string dengan bentuk berikut:

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

di mana koefisien setiap istilah adalah bilangan bulat (-128 <a <128). Setiap istilah dipisahkan oleh satu spasi, +, dan ruang lain; istilah linear dan konstan muncul seperti di atas (yaitu, tidak ada x^0atau x^1). Persyaratan akan muncul dalam urutan peningkatan derajat, dan kekuatan-kekuatan dengan koefisien nol dihilangkan. Semua istilah dengan koefisien 1 atau -1 menampilkan koefisien itu secara eksplisit.

Output Anda harus memiliki bentuk yang persis sama. Perhatikan bahwa koefisien dalam output mungkin sebesar 127 * 127 == 16129.

Contohnya

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

Mencetak gol

Skor Anda adalah panjang program Anda dalam byte, dikalikan tiga jika Anda menggunakan built-in atau perpustakaan yang melakukan aljabar simbolis.

hYPotenuser
sumber
Saya tidak percaya bahwa kita belum memiliki tantangan ini di sini!
flawr
5
@ flawr Kami semacam melakukannya. (Meskipun yang satu membutuhkan fungsi lain juga dan tidak memiliki aturan ketat pada format output.)
Martin Ender
@ flawr Saya memikirkan hal yang sama ... namun saya tidak menemukan pencarian yang terhubung dengan Martin. Baiklah
hYPotenuser

Jawaban:

15

Retina , 53 43 42 41 40 35 byte

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

Untuk menghitung tujuan setiap baris masuk dalam file terpisah, tetapi Anda dapat menjalankan di atas sebagai file tunggal dengan memanggil Retina dengan -sbendera.

Ini mengharapkan angka-angka dalam string input untuk diberikan secara unary dan akan menghasilkan output dalam format yang sama. Misalnya

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

dari pada

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

Penjelasan

Kode ini menjelaskan satu penggantian satu regex, yang pada dasarnya 4 substitusi dikompresi menjadi satu. Perhatikan bahwa hanya satu cabang yang akan mengisi grup $2sehingga jika salah satu dari tiga kecocokan lainnya, kecocokan hanya akan dihapus dari string. Jadi kita dapat melihat empat kasus berbeda secara terpisah:

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

Jika mungkin untuk mencapai ruang dari awal string tanpa menemukan xyang berarti istilah pertama adalah istilah konstan dan kami menghapusnya. Karena keserakahan +, ini juga akan cocok dengan plus dan spasi kedua setelah suku konstan. Jika tidak ada istilah yang konstan, bagian ini tidak akan pernah cocok.

x(?= )
<empty>

Ini cocok dengan xyang diikuti oleh spasi, yaitu xistilah linear (jika ada), dan menghapusnya. Kita dapat yakin bahwa ada spasi setelahnya, karena tingkat polinomial selalu minimal 2.

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

Ini melakukan penggandaan koefisien oleh eksponen. Ini cocok dengan satu 1dalam koefisien dan menggantinya dengan seluruh eksponen yang sesuai melalui lookahead.

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

Ini mengurangi semua eksponen yang tersisa dengan mencocokkan trailing 1(dipastikan oleh lookahead). Jika mungkin untuk mencocokkan ^11(dan batas kata) kami menghapusnya sebagai gantinya, yang mengurus menampilkan istilah linear dengan benar.

Untuk kompresi, kami perhatikan bahwa sebagian besar kondisi tidak saling memengaruhi. (\^1)?tidak akan cocok jika lookahead dalam kasus ketiga benar, jadi kita bisa menggabungkan keduanya

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

Sekarang kita sudah memiliki lookahead yang dibutuhkan untuk kasus kedua dan yang lain tidak pernah benar ketika mencocokkan x, jadi kita bisa menggeneralisasi 1ke \w:

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

Kasus pertama tidak benar-benar memiliki kesamaan dengan yang lain, jadi kami menyimpannya secara terpisah.

Martin Ender
sumber
9

CJam, 43 41 byte

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

Terima kasih kepada @ jimmy23013 karena menunjukkan satu bug dan bermain golf dengan dua byte!

Cobalah online di juru bahasa CJam .

Bagaimana itu bekerja

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
sumber
5

Perl, 64 63 byte

Kode 62b + 1 baris perintah (-p)

Tidak luar biasa saat ini, tetapi saya akan terus mencoba mempersingkatnya.

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

Contoh penggunaan:

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

Terima kasih Denis untuk -1b

Jarmex
sumber
5

Julia, 220 byte

Tidak ada ekspresi reguler!

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," + "))

Ini menciptakan fungsi lambda yang menerima string dan mengembalikan string. Jeroan meniru apa yang terjadi ketika kode Julia dievaluasi: string diurai menjadi simbol, ekspresi, dan panggilan. Saya mungkin benar-benar mencoba menulis fungsi diferensiasi simbolis Julia penuh dan mengirimkannya untuk menjadi bagian dari Julia.

Penjelasan + tidak dikumpulkan:

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.
sumber
3

C, 204 162 byte

#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;}

Pada dasarnya parsing setiap istilah dan cetak istilah yang dibedakan secara berurutan. Cukup mudah.

Cole Cameron
sumber
2

JavaScript ES6, 108 byte

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

Cuplikan 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
sumber
2

Python 2, 166 byte

Wah, sepertinya ini lebih lama dari seharusnya.

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)

Fungsi ini dmengambil istilah yang tidak konstan tdan mengembalikan turunannya. Alasan saya deffungsinya daripada menggunakan lambda adalah agar saya dapat menetapkan eksponen minus 1 kee , yang kemudian digunakan empat kali lagi. Hal menjengkelkan utama adalah harus bolak-balik antara string dan int, meskipun operator backtick Python 2 membantu dengan itu.

Kami kemudian membagi input menjadi istilah dan memanggil dmasing-masing yang ada "x"di dalamnya, sehingga menghilangkan istilah konstan. Hasilnya disatukan kembali dan dicetak.

DLosc
sumber
2

CJam, 62 57 55 49 byte

Nah, Dennis mempermalukan ini bahkan sebelum saya perhatikan bahwa situs itu kembali. Tapi ini ciptaan saya:

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

Versi terbaru menyimpan beberapa byte dengan cara pintas yang disarankan oleh @Dennis (gunakan variabel, dan pisahkan di ruang alih-alih +).

Cobalah online

Reto Koradi
sumber
1
Menyimpan dalam variabel lebih pendek daripada muncul di blok lain. Misalnya, _({'^a\}{;}?lebih panjang 1 byte dari :T({T'^a\}&.
Dennis
1
Jika Anda membagi pada spasi alih-alih tanda plus, Anda tidak perlu ~di blok yang lain dan dapat menghilangkan yang juga.
Dennis
@ Dennis Itu berhasil, terima kasih. Saya awalnya ingin menghilangkan tanda-tanda plus, tetapi mereka tetap putus ketika saya menguji keberadaan x. Saya menemukan beberapa peningkatan saat saya melakukannya. Sebagian besar, karena saya memiliki nilai-nilai dalam variabel sekarang, saya dapat mengingatnya di mana saya benar-benar membutuhkannya, menyimpan beberapa manipulasi tumpukan. Saya juga memiliki nyasar ayang seharusnya dihapus ketika saya mengoptimalkan generasi keluaran sebelumnya.
Reto Koradi
1

Pyth, 62 byte

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

Solusi yang cukup jelek, menggunakan beberapa penggantian regex.

orlp
sumber
1

Python 3, 176 byte

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

Memang, gangguan utama adalah harus mengkonversi antara string dan int. Juga, jika syarat konstan diperlukan, kode hanya 153 byte.

El'endia Starman
sumber
Jawaban pertama, adalah menembak karena mengalahkan DLosc, tidak cukup sampai di sana.
El'endia Starman
0

Python 2, 229 byte

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
sumber
0

Python 2, 174 byte

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

Sayangnya, trik DLosc untuk mengubah nama metode split dan melakukan diferensiasi dalam fungsi tertentu tidak mempersingkat kode saya ...

pjmv
sumber