Symbolic Differentiation of Polynomials

Question

Symbolic Differentiation 1: Gone Coefishin'

Task

Write a program that takes in a polynomial in x from stdin (1 < deg(p) < 128) and differentiates it. The input polynomial will be a string of the following form:

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

where the coefficient of each term is an integer (-128 < a < 128). Each term is separated by one space, a +, and another space; linear and constant terms appear as above (i.e., no x^0 or x^1). Terms will appear in order of increasing degree, and those powers with zero coefficient are omitted. All terms with coefficient 1 or -1 display that coefficient explicitly.

Your output must have precisely the same form. Note that coefficients in the output might be as big as 127*127 == 16129.

Examples

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

Scoring

Your score is the length of your program in bytes, multiplied by three if you use a built-in or a library that does symbolic algebra.

• flawr: I can't believe that we haven't already had this challenge here!
• Martin Ender: @flawr We sort of did. (Although that one required other functions as well and didn't have as strict rules on the output format.)
• hYPotenuser: @flawr I thought the same thing... and yet I didn't find Martin's linked post searching. Ah well.

Answer 1

Retina, (削除) 53 (削除ここまで) (削除) 43 (削除ここまで) (削除) 42 (削除ここまで) (削除) 41 (削除ここまで) (削除) 40 (削除ここまで) 35 bytes

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

For counting purposes each line goes in a separate file, but you can run the above as a single file by invoking Retina with the -s flag.

This expects the numbers in the input string to be given in unary and will yield output in the same format. E.g.

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

instead of

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

Explanation

The code describes a single regex substitution, which is basically 4 substitutions compressed into one. Note that only one of the branches will fill group 2ドル so if any of the other three match, the match will simply be deleted from the string. So we can look at the four different cases separately:

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

If it's possible to reach a space from the beginning of the string without encountering an x that means the first term is the constant term and we delete it. Due to the greediness of +, this will also match the plus and the second space after the constant term. If there is no constant term, this part will simply never match.

x(?= )
<empty>

This matches an x which is followed by a space, i.e. the x of the linear term (if it exists), and removes it. We can be sure that there's a space after it, because the degree of the polynomial is always at least 2.

1(?=1*x.(1+))
1ドル

This performs the multiplication of the coefficient by the exponent. This matches a single 1 in the coefficient and replaces it by the entire corresponding exponent via the lookahead.

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

This reduces all remaining exponents by matching the trailing 1 (ensured by the lookahead). If it's possible to match ^11 (and a word boundary) we remove that instead, which takes care of displaying the linear term correctly.

For the compression, we notice that most of the conditions don't affect each other. (\^1)? won't match if the lookahead in the third case is true, so we can put those two together as

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

Now we already have the lookahead needed for the second case and the others can never be true when matching x, so we can simply generalise the 1 to a \w:

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

The first case doesn't really have anything in common with the others, so we keep it separate.

Answer 2

CJam, (削除) 43 (削除ここまで) 41 bytes

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

Thanks to @jimmy23013 for pointing out one bug and golfing off two bytes!

Try it online in the CJam interpreter.

How it works

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

Answer 3

Julia, 220 bytes

No regular expressions!

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

This creates a lambda function that accepts a string and returns a string. The innards mimic what happens when Julia code is evaluated: a string is parsed into symbols, expressions, and calls. I might actually try writing a full Julia symbolic differentiation function and submit it to be part of Julia.

Ungolfed + explanation:

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

Answer 4

Perl, (削除) 64 (削除ここまで) 63 bytes

62b code + 1 command line (-p)

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

Usage example:

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

Thanks Denis for -1b

Answer 5

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

Basically parse each term and print out the differentiated term in sequence. Fairly straightforward.

Answer 6

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||''):'')

ES5 Snippet:

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

Answer 7

Python 2, 166 bytes

Boy, this seems longer than it should be.

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)

The function d takes a non-constant term t and returns its derivative. The reason I def the function instead of using a lambda is so I can assign the exponent minus 1 to e, which then gets used another four times. The main annoying thing is having to cast back and forth between strings and ints, although Python 2's backtick operator helps with that.

We then split the input into terms and call d on each one that has "x" in it, thereby eliminating the constant term. The results are joined back together and printed.

Answer 8

CJam, (削除) 62 (削除ここまで) (削除) 57 (削除ここまで) (削除) 55 (削除ここまで) 49 bytes

Well, Dennis put this to shame before I even noticed that the site was back up. But here is my creation anyway:

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

Latest version saves a few bytes with shortcuts suggested by @Dennis (use variables, and split at space instead of +).

Try it online

• Dennis: Saving in a variable is shorter than popping in the else block. For example, _({'^a\}{;}? is 1 byte longer than :T({T'^a\}&.
• Dennis: If you split at spaces instead of plus signs, you don't need the ~ in the remaining else block and can eliminate that one as well.
• Reto Koradi: @Dennis That works, thanks. I originally wanted to eliminate the plus signs, but they drop out anyway when I test for the presence of x. I found some more improvements while I was at it. Mostly, because I have the values in variables now, I can recall them where I really need them, saving some stack manipulation. I also had a stray a that should have been deleted when I optimized the output generation earlier.

Answer 9

Pyth, 62 bytes

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

Pretty ugly solution, using some regex substitutions.

Answer 10

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

Indeed, the main annoyance is having to convert between strings and ints. Also, if a constant term was required, the code would only be 153 bytes.

• El'endia Starman: First answer, was shooting for beating DLosc, didn't quite get there.

Answer 11

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

Answer 12

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

Unfortunately, DLosc's trick to rename the split method and perform the differentiation in a specific function does not shorten my code...

Answer 13

Swift 6, (削除) 218 (削除ここまで) (削除) 214 (削除ここまで) 175 bytes

{""+(0ドル+"").split(separator:" + ").flatMap{let p=0ドル.split{0ドル>"]"},d=p.count>1 ?Int(p[1])!:1
return p[0]<0ドル ?"\(d*Int(p[0])!)\(d<2 ?"":d<3 ?"x":"x^\(d-1)") + ":""}.dropLast(3)}

Try it on SwiftFiddle!