Diferenciación simbólica de polinomios

20

Diferenciación simbólica 1: Gone Coefishin '

Tarea

Escriba un programa que tome un polinomio en x de stdin (1 <deg (p) <128) y lo diferencie. El polinomio de entrada será una cadena de la siguiente forma:

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

donde el coeficiente de cada término es un número entero (-128 <a <128). Cada término está separado por un espacio, a + y otro espacio; los términos lineales y constantes aparecen como arriba (es decir, no x^0o x^1). Los términos aparecerán en orden creciente y se omiten las potencias con coeficiente cero . Todos los términos con coeficiente 1 o -1 muestran ese coeficiente explícitamente.

Su salida debe tener exactamente la misma forma. Tenga en cuenta que los coeficientes en la salida pueden ser tan grandes como 127 * 127 == 16129.

Ejemplos

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

Puntuación

Su puntaje es la longitud de su programa en bytes, multiplicado por tres si usa una biblioteca incorporada o una que hace álgebra simbólica.

hYPotenuser
fuente
¡No puedo creer que no hayamos tenido este desafío aquí!
flawr
55
@flawr Lo hicimos. (Aunque esa también requería otras funciones y no tenía reglas estrictas sobre el formato de salida).
Martin Ender
@flawr Pensé lo mismo ... y sin embargo no encontré la búsqueda de publicaciones vinculadas de Martin. Ah bueno.
hYPotenuser

Respuestas:

15

Retina , 53 43 42 41 40 35 bytes

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

Para contar, cada línea va en un archivo separado, pero puede ejecutar lo anterior como un solo archivo invocando Retina con la -sbandera.

Esto espera que los números en la cadena de entrada se den en unario y producirán resultados en el mismo formato. P.ej

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

en lugar de

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

Explicación

El código describe una única sustitución de expresiones regulares, que es básicamente 4 sustituciones comprimidas en una. Tenga en cuenta que solo una de las ramas llenará el grupo, $2por lo que si cualquiera de las otras tres coincide, la coincidencia simplemente se eliminará de la cadena. Entonces podemos ver los cuatro casos diferentes por separado:

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

Si es posible llegar a un espacio desde el comienzo de la cadena sin encontrar uno, xeso significa que el primer término es el término constante y lo eliminamos. Debido a la codicia de +, esto también coincidirá con el más y el segundo espacio después del término constante. Si no hay un término constante, esta parte simplemente nunca coincidirá.

x(?= )
<empty>

Esto coincide con un xseguido de un espacio, es decir, el xdel término lineal (si existe), y lo elimina. Podemos estar seguros de que hay un espacio después, porque el grado del polinomio siempre es al menos 2.

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

Esto realiza la multiplicación del coeficiente por el exponente. Esto coincide con un solo 1en el coeficiente y lo reemplaza por todo el exponente correspondiente a través de la búsqueda anticipada.

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

Esto reduce todos los exponentes restantes al hacer coincidir el final 1(asegurado por la búsqueda anticipada). Si es posible hacer coincidir ^11(y un límite de palabra), lo eliminamos, lo que se encarga de mostrar el término lineal correctamente.

Para la compresión, notamos que la mayoría de las condiciones no se afectan entre sí. (\^1)?no coincidirá si la anticipación en el tercer caso es verdadera, por lo que podemos juntar esos dos como

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

Ahora ya tenemos el lookahead necesario para el segundo caso y los otros nunca pueden ser verdaderos cuando coinciden x, por lo que simplemente podemos generalizar 1a \w:

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

El primer caso realmente no tiene nada en común con los demás, por lo que lo mantenemos separado.

Martin Ender
fuente
9

CJam, 43 41 bytes

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

¡Gracias a @ jimmy23013 por señalar un error y jugar dos bytes!

Pruébelo en línea en el intérprete de CJam .

Cómo 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
fuente
5

Perl, 64 63 bytes

Código 62b + 1 línea de comando (-p)

No es sorprendente por el momento, pero continuaré tratando de acortarlo.

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

Ejemplo 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'

Gracias Denis por -1b

Jarmex
fuente
5

Julia, 220 bytes

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

Esto crea una función lambda que acepta una cadena y devuelve una cadena. Las entrañas imitan lo que sucede cuando se evalúa el código de Julia: una cadena se analiza en símbolos, expresiones y llamadas. De hecho, podría intentar escribir una función de diferenciación simbólica completa de Julia y enviarla para que sea parte de Julia.

Ungolfed + explicación:

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.
fuente
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;}

Básicamente analiza cada término e imprime el término diferenciado en secuencia. Bastante sencillo.

Cole Cameron
fuente
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 de 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
fuente
2

Python 2, 166 bytes

Chico, esto parece más largo de lo que debería 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)

La función dtoma un término no constante ty devuelve su derivada. La razón por la que defla función en lugar de usar una lambda es para poder asignar el exponente menos 1 a e, que luego se usa otras cuatro veces. Lo principal y molesto es tener que lanzar de un lado a otro entre cadenas e ints, aunque el operador de backtick de Python 2 ayuda con eso.

Luego dividimos la entrada en términos y recurrimos da cada uno que contiene "x", eliminando así el término constante. Los resultados se vuelven a unir e imprimir.

DLosc
fuente
2

CJam, 62 57 55 49 bytes

Bueno, Dennis lo avergonzó antes de que me diera cuenta de que el sitio estaba funcionando nuevamente. Pero aquí está mi creación de todos modos:

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

La última versión guarda algunos bytes con accesos directos sugeridos por @Dennis (use variables y divídalas en el espacio en lugar de +).

Pruébalo en línea

Reto Koradi
fuente
1
Guardar en una variable es más corto que aparecer en el bloque else. Por ejemplo, _({'^a\}{;}?es 1 byte más largo que :T({T'^a\}&.
Dennis
1
Si se divide en espacios en lugar de signos más, no necesita el ~bloque restante y puede eliminar ese también.
Dennis
@ Dennis Eso funciona, gracias. Originalmente quería eliminar los signos más, pero de todos modos desaparecen cuando pruebo la presencia de x. Encontré algunas mejoras más mientras estaba en ello. Principalmente, debido a que ahora tengo los valores en variables, puedo recordarlos donde realmente los necesito, ahorrando algo de manipulación de la pila. También tuve un parásito aque debería haberse eliminado cuando optimicé la generación de salida antes.
Reto Koradi
1

Pyth, 62 bytes

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

Solución bastante fea, usando algunas sustituciones de expresiones regulares.

orlp
fuente
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 hecho, la molestia principal es tener que convertir entre cadenas e ints. Además, si se requería un término constante, el código solo tendría 153 bytes.

El'endia Starman
fuente
La primera respuesta, fue disparar por vencer a DLosc, no llegó allí.
El'endia Starman
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
fuente
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]])

Desafortunadamente, el truco de DLosc para cambiar el nombre del método de división y realizar la diferenciación en una función específica no acorta mi código ...

pjmv
fuente