1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
import java.math.BigInteger;
import java.util.*;
import java.util.regex.*;
import java.util.stream.*;
// TODO: Replace examples and use TDD development by writing your own tests
public class SolutionTest {
@Test
public void sampleTests() {
assertEquals(new BigInteger("12"), Equation.differentiate("12x+2", 3));
assertEquals(new BigInteger("5"), Equation.differentiate("x^2-x", 3));
assertEquals(new BigInteger("-20"), Equation.differentiate("-5x^2+10x+4", 3));
}
@Test
public void moreTests() {
assertEquals(new BigInteger("9"), Equation.differentiate("x^2+3x+3",3) );
assertEquals(new BigInteger("1062300"), Equation.differentiate("1000x^2+300x+200",531) );
assertEquals(new BigInteger("87017"), Equation.differentiate("21x^2+35x+3",2071) );
assertEquals(new BigInteger("38509884"), Equation.differentiate("66x^3+3x^2+3",441) );
assertEquals(new BigInteger("5962009860"), Equation.differentiate("21x^4+3x^3",414) );
assertEquals(new BigInteger("-2480823269890144044"), Equation.differentiate("-21x^5+3x^3",12398) );
assertEquals(new BigInteger("-2469135813"), Equation.differentiate("-x^2+3x-3",1234567908) );
assertEquals(new BigInteger("-6045"), Equation.differentiate("-7x^5+22x^4-55x^3-94x^2+87x-56",-3) );
assertEquals(new BigInteger("-3300404885229567012"), Equation.differentiate("-123x^5+3x",8559) );
assertEquals(new BigInteger("119769696967118"), Equation.differentiate("x^2",59884848483559L) );
}
private static class RefSolver {
final static private Pattern PATTERN = Pattern.compile("\\+?(?<coef>-?\\d*)(?<var>x?\\^?)(?<exp>\\d*)");
final static private BigInteger ZERO = BigInteger.ZERO;
private static BigInteger differentiate(String s, long x) {
BigInteger bigX = new BigInteger(""+x);
Map<Integer,BigInteger> derivate = new HashMap<>();
Matcher m = PATTERN.matcher(s);
while (m.find()) {
BigInteger coef = new BigInteger( "-".equals(m.group("coef")) ? "-1"
: m.group("coef").isEmpty() ? "1": m.group("coef") ),
exp = new BigInteger(!m.group("exp").isEmpty() ? m.group("exp")
: m.group("var").isEmpty() ? "0" : "1");
int exp_1 = exp.intValue()-1;
if (exp_1!=-1 && !exp.equals(ZERO) && !coef.equals(ZERO)) {
derivate.put(exp_1, derivate.getOrDefault(exp_1, ZERO)
.add(exp.multiply(coef)) );
}
}
return derivate.entrySet()
.stream()
.map( me -> me.getValue().multiply( bigX.pow(me.getKey()) ) )
.reduce(BigInteger.ZERO, (a,b) -> a.add(b));
}
}
private static final Random rnd = new Random();
private static int rand(int x) { return rnd.nextInt(x+1); }
private static int rand(int a, int b) { return a + rnd.nextInt(b-a+1); }
@Test
public void randomTests() {
for (int i=0 ; i<100 ; i++) {
long x = rand(1,10000);
String s = "";
while (s.isEmpty()) {
List<String> eq = IntStream.range(0,rand(2,7))
.mapToObj(SolutionTest::getRndTerm)
.collect(Collectors.toList());
Collections.reverse(eq);
s = String.join("+",eq).replaceAll("^\\+|\\+(?=[+-]|$)|\\b1(?=x)", "");
}
BigInteger exp = RefSolver.differentiate(s,x);
//System.out.println(s + " => "+exp);
assertEquals(exp, Equation.differentiate(s,x));
}
}
private static String getRndTerm(int exp) {
int coef = rand(9)==0 ? 0 : rand(-100,100);
if (coef==0) return "";
if (exp==0) return coef+"";
if (exp==1) return coef+"x";
return String.format("%dx^%d", coef, exp);
}
}
|