Diferenciação simbólica de polinômios

20

Diferenciação simbólica 1: ido coefishin '

Tarefa

Escreva um programa que capte um polinômio em x de stdin (1 <deg (p) <128) e o diferencie. O polinômio de entrada será uma sequência do seguinte formato:

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

onde o coeficiente de cada termo é um número inteiro (-128 <a <128). Cada termo é separado por um espaço, um + e outro espaço; termos lineares e constantes aparecem como acima (ou seja, não x^0ou x^1). Os termos aparecerão em ordem crescente e os poderes com coeficiente zero são omitidos. Todos os termos com coeficiente 1 ou -1 exibem esse coeficiente explicitamente.

Sua saída deve ter exatamente a mesma forma. Observe que os coeficientes na saída podem ser tão grandes quanto 127 * 127 == 16129.

Exemplos

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

Pontuação

Sua pontuação é o comprimento do seu programa em bytes, multiplicado por três, se você usar uma biblioteca interna ou uma que faça álgebra simbólica.

hYPotenuser
fonte
Não acredito que ainda não tivemos esse desafio aqui!
flawr
5
@ flawr Nós meio que fizemos. (Apesar de que um exigido outras funções e não têm como regras estritas sobre o formato de saída.)
Martin Ender
@ flawr Eu pensei a mesma coisa ... e ainda não encontrei a pesquisa vinculada de Martin. Ah bem.
HYPotenuser

Respostas:

15

Retina , 53 43 42 41 40 35 bytes

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

Para fins de contagem, cada linha entra em um arquivo separado, mas você pode executar o procedimento acima como um único arquivo, chamando Retina com o -ssinalizador.

Isso espera que os números na sequência de entrada sejam fornecidos em unário e produzirão a saída no mesmo formato. Por exemplo

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

ao invés de

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

Explicação

O código descreve uma única substituição de regex, que é basicamente 4 substituições compactadas em uma. Observe que apenas uma das ramificações preencherá o grupo. $2Se alguma das outras três corresponder, a correspondência será simplesmente excluída da sequência. Então, podemos analisar os quatro casos diferentes separadamente:

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

Se é possível alcançar um espaço desde o início da string sem encontrar um, xisso significa que o primeiro termo é o termo constante e nós o excluímos. Devido à ganância +, isso também corresponderá ao mais e ao segundo espaço após o termo constante. Se não houver um termo constante, essa parte simplesmente nunca corresponderá.

x(?= )
<empty>

Isso corresponde a um xque é seguido por um espaço, ou seja, xo termo linear (se existir), e o remove. Podemos ter certeza de que há um espaço depois dele, porque o grau do polinômio é sempre pelo menos 2.

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

Isso realiza a multiplicação do coeficiente pelo expoente. Isso corresponde a um único 1no coeficiente e o substitui por todo o expoente correspondente por meio do visor.

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

Isso reduz todos os expoentes restantes, correspondendo à direita 1(garantida pela cabeça de impressão). Se for possível corresponder ^11(e um limite de palavras), removeremos isso, o que cuidará da exibição correta do termo linear.

Para a compactação, percebemos que a maioria das condições não se afetam. (\^1)?não corresponderá se o lookahead no terceiro caso for verdadeiro, para que possamos colocar esses dois juntos como

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

Agora já temos a aparência necessária para o segundo caso e os outros nunca podem ser verdadeiros quando combinados x, para que possamos simplesmente generalizar o 1para \w:

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

O primeiro caso realmente não tem nada em comum com os outros, então mantemos em separado.

Martin Ender
fonte
9

CJam, 43 41 bytes

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

Obrigado a @ jimmy23013 por apontar um bug e jogar fora dois bytes!

Experimente online no intérprete CJam .

Como funciona

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

Perl, 64 63 bytes

Código 62b + 1 linha de comando (-p)

Não é incrível no momento, mas vou continuar tentando encurtá-lo.

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

Exemplo de uso:

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

Obrigado Denis por -1b

Jarmex
fonte
5

Julia, 220 bytes

Sem expressões regulares!

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

Isso cria uma função lambda que aceita uma string e retorna uma string. As entranhas imitam o que acontece quando o código Julia é avaliado: uma string é analisada em símbolos, expressões e chamadas. Na verdade, posso tentar escrever uma função de diferenciação simbólica completa de Julia e enviá-la para fazer parte de Julia.

Ungolfed + explicação:

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

C, 204 162 bytes

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

Analise basicamente cada termo e imprima o termo diferenciado em sequência. Bastante direto.

Cole Cameron
fonte
2

JavaScript ES6, 108 bytes

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

Fragmento 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
fonte
2

Python 2, 166 bytes

Rapaz, isso parece mais longo do que deveria ser.

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)

A função dpega um termo não constante te retorna sua derivada. A razão defpela qual a função, em vez de usar um lambda, é para que eu possa atribuir o expoente menos 1 a e, que é usado mais quatro vezes. A principal coisa chata é ter que passar de um lado para o outro entre strings e ints, embora o operador de backtick do Python 2 o ajude.

Em seguida, dividimos a entrada em termos e apelamos da cada uma "x"delas, eliminando assim o termo constante. Os resultados são reunidos novamente e impressos.

DLosc
fonte
2

CJam, 62 57 55 49 bytes

Bem, o Dennis envergonhou isso antes que eu percebesse que o site estava de volta. Mas aqui está minha criação de qualquer maneira:

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

A versão mais recente salva alguns bytes com os atalhos sugeridos por @Dennis (use variáveis ​​e divida no espaço em vez de +).

Experimente online

Reto Koradi
fonte
1
Salvar em uma variável é mais curto do que aparecer no bloco else. Por exemplo, _({'^a\}{;}?é 1 byte mais longo que :T({T'^a\}&.
Dennis
1
Se você dividir em espaços em vez de sinais de adição, não precisará do ~bloco restante e poderá eliminá-lo também.
Dennis
@ Dennis Isso funciona, obrigado. Originalmente, eu queria eliminar os sinais de mais, mas eles desaparecem de qualquer maneira quando eu testo a presença de x. Eu encontrei mais algumas melhorias enquanto estava nisso. Principalmente, como agora tenho os valores nas variáveis, posso lembrá-los onde realmente preciso deles, economizando alguma manipulação de pilha. Eu também tive um desvio aque deveria ter sido excluído quando otimizei a geração de saída anteriormente.
Reto Koradi
1

Pitão, 62 bytes

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

Solução bastante feia, usando algumas substituições de regex.

orlp
fonte
1

Python 3, 176 bytes

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

De fato, o principal incômodo é ter que converter entre strings e ints. Além disso, se um termo constante fosse necessário, o código seria apenas 153 bytes.

El'endia Starman
fonte
A primeira resposta, foi atirar por derrotar o DLosc, não chegou lá.
El'endia Starman 03/08/2015
0

Python 2, 229 bytes

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

Python 2, 174 bytes

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

Infelizmente, o truque do DLosc para renomear o método split e executar a diferenciação em uma função específica não reduz o meu código ...

pjmv
fonte