25
\$\begingroup\$

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.

Alex A.
24.8k5 gold badges39 silver badges120 bronze badges
asked Aug 1, 2015 at 14:02
\$\endgroup\$
3
  • \$\begingroup\$ I can't believe that we haven't already had this challenge here! \$\endgroup\$ Commented Aug 1, 2015 at 14:19
  • 5
    \$\begingroup\$ @flawr We sort of did. (Although that one required other functions as well and didn't have as strict rules on the output format.) \$\endgroup\$ Commented Aug 1, 2015 at 14:21
  • \$\begingroup\$ @flawr I thought the same thing... and yet I didn't find Martin's linked post searching. Ah well. \$\endgroup\$ Commented Aug 1, 2015 at 15:51

13 Answers 13

15
\$\begingroup\$

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.

answered Aug 1, 2015 at 15:57
\$\endgroup\$
9
\$\begingroup\$

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 " + ".
answered Aug 1, 2015 at 16:11
\$\endgroup\$
0
6
\$\begingroup\$

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
answered Aug 1, 2015 at 19:40
\$\endgroup\$
0
5
\$\begingroup\$

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

answered Aug 1, 2015 at 17:39
\$\endgroup\$
0
4
\$\begingroup\$

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.

answered Aug 1, 2015 at 19:08
\$\endgroup\$
2
\$\begingroup\$

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>

answered Aug 1, 2015 at 18:56
\$\endgroup\$
2
\$\begingroup\$

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.

answered Aug 2, 2015 at 7:52
\$\endgroup\$
2
\$\begingroup\$

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

answered Aug 1, 2015 at 16:54
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Saving in a variable is shorter than popping in the else block. For example, _({'^a\}{;}? is 1 byte longer than :T({T'^a\}&. \$\endgroup\$ Commented Aug 2, 2015 at 5:49
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 2, 2015 at 16:24
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Aug 2, 2015 at 17:32
1
\$\begingroup\$

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.

answered Aug 1, 2015 at 14:43
\$\endgroup\$
1
\$\begingroup\$

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.

answered Aug 3, 2015 at 5:14
\$\endgroup\$
1
  • \$\begingroup\$ First answer, was shooting for beating DLosc, didn't quite get there. \$\endgroup\$ Commented Aug 3, 2015 at 5:14
0
\$\begingroup\$

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')
answered May 21, 2017 at 12:39
\$\endgroup\$
0
\$\begingroup\$

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

Taylor Raine
8,9732 gold badges29 silver badges53 bronze badges
answered May 21, 2017 at 16:06
\$\endgroup\$
0
\$\begingroup\$

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!

answered Mar 27, 2024 at 14:45
\$\endgroup\$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.