How to Differentiate a Polynomial in Java

The challenge

Create a function that differentiates a polynomial for a given value of x.

Your function will receive 2 arguments: a polynomial as a string, and a point to evaluate the equation as an integer.

Assumptions:

  • There will be a coefficient near each x, unless the coefficient equals 1 or -1.
  • There will be an exponent near each x, unless the exponent equals 0 or 1.
  • All exponents will be greater or equal to zero

Examples:

Equation.differenatiate("12x+2", 3) ==> 12 Equation.differenatiate("x^2+3x+2", 3) ==> 9
Code language: Java (java)

The solution in Java code

Option 1:

import java.math.BigInteger; import java.util.regex.Pattern; import java.util.regex.Matcher; public class Equation { private static final Pattern TERM = Pattern.compile("(.*?)x(\\^\\d+)?"); public static BigInteger differentiate(String equation, long x) { BigInteger xb = BigInteger.valueOf(x); BigInteger result = BigInteger.ZERO; Matcher m = TERM.matcher(equation); while (m.find()) { long k = 1; String ks = m.group(1); if (!ks.isEmpty() && !ks.equals("+")) k = ks.equals("-") ? -1 : Long.parseLong(ks); int p = 1; String ps = m.group(2); if (ps != null) p = Integer.parseInt(ps.substring(1)); result = result.add(BigInteger.valueOf(k).multiply(BigInteger.valueOf(p)).multiply(xb.pow(p - 1))); } return result; } }
Code language: Java (java)

Option 2:

import java.math.BigInteger; import java.util.ArrayList; public class Equation { public static BigInteger differentiate(String equation, long x) { if(equation.equals("")) { return new BigInteger("0"); } ArrayList<String> list = new ArrayList<>(); char[] charEquation = equation.toCharArray(); String temp = "" + charEquation[0]; for (int i = 1; i < charEquation.length; i++) { if (charEquation[i] == '-' || charEquation[i] == '+') { list.add(temp); temp = "" + charEquation[i]; } else temp += charEquation[i]; } list.add(temp); BigInteger sum = new BigInteger("0"); for (String el : list) { if(el.contains("^")) { sum = sum.add(pow(el, x)); } else if (el.contains("x")){ sum = sum.add(noPow(el)); } } BigInteger bi = new BigInteger(String.valueOf(sum)); return bi; } public static BigInteger noPow (String equation) { if (equation.toCharArray()[0] == '-' || equation.toCharArray()[0] == '+') { String coef = ""; for (int i = 1; i < equation.toCharArray().length; i++) { if(equation.toCharArray()[i] == 'x') { break; } else { coef += equation.toCharArray()[i]; } } if (coef.equals("")) coef = "1"; if (equation.toCharArray()[0] == '-') { return new BigInteger(coef).multiply(new BigInteger("-1")) ; } return new BigInteger(coef) ; } else { String coef = ""; for (int i = 0; i < equation.toCharArray().length; i++) { if(equation.toCharArray()[i] == 'x') { break; } else { coef += equation.toCharArray()[i]; } } if(coef.equals("")) coef = "1"; return new BigInteger(coef); } } public static BigInteger pow(String equation, long x) { if(equation.toCharArray()[0] == '-' || equation.toCharArray()[0] == '+') { String coef = ""; int counter = 0; for (int i = 1; i < equation.toCharArray().length; i++) { if(equation.toCharArray()[i] == 'x') { counter = i; break; } else { coef += equation.toCharArray()[i]; } } if(coef.equals("")) coef = "1"; String powCoef = ""; for (int i = counter + 2; i < equation.toCharArray().length; i++) { powCoef += equation.toCharArray()[i]; } BigInteger biCoef = new BigInteger(coef); BigInteger biPowCoef = new BigInteger(powCoef); biCoef = biCoef.multiply(biPowCoef); biPowCoef = biPowCoef.add(new BigInteger("-1")); BigInteger result = biCoef.multiply(new BigInteger(String.valueOf(x)).pow(Integer.valueOf(biPowCoef.toString()))); if(equation.toCharArray()[0] == '-') { return result.multiply(new BigInteger("-1")); } return result; } else { String coef = ""; int counter = 0; for (int i = 0; i < equation.toCharArray().length; i++) { if(equation.toCharArray()[i] == 'x') { counter = i; break; } else { coef += equation.toCharArray()[i]; } } if(coef.equals("")) coef = "1"; String powCoef = ""; for (int i = counter + 2; i < equation.toCharArray().length; i++) { powCoef += equation.toCharArray()[i]; } BigInteger biCoef = new BigInteger(coef); BigInteger biPowCoef = new BigInteger(powCoef); biCoef = biCoef.multiply(biPowCoef); biPowCoef = biPowCoef.add(new BigInteger("-1")); BigInteger result = biCoef.multiply(new BigInteger(String.valueOf(x)).pow(Integer.valueOf(biPowCoef.toString()))); return result; } } }
Code language: Java (java)

Option 3:

import java.util.*; import java.math.BigInteger; public class Equation { public static BigInteger differentiate(String equation, long x) { BigInteger res = BigInteger.ZERO, X = BigInteger.valueOf(x); equation += "+"; Map <Integer, Integer> copt = new HashMap <> (); char[] token = equation.toCharArray(); int coeff = 1, power = 1, leng = token.length; boolean isPow = false; for (int i = 0; i < leng; i++) { if (token[i] == '+' || token[i] == '-') { if (isPow) copt.put(power, coeff); isPow = false; power = 1; coeff = token[i] == '+' ? 1 : -1; } if (token[i] == 'x') isPow = true; if (Character.isDigit(token[i])) { StringBuilder sb = new StringBuilder(); sb.append(token[i]); while (i < leng - 1 && Character.isDigit(token[i+1])) sb.append(token[++i]); int value = Integer.parseInt(sb.toString()); if (isPow) power *= value; else coeff *= value; } } for (int p : copt.keySet()) { BigInteger mul = BigInteger.valueOf(p * copt.get(p)); res = res.add(X.pow(p - 1).multiply(mul)); } return res; } }
Code language: Java (java)

Test cases to validate our solution

import org.junit.Test; import static org.junit.Assert.assertEquals; import org.junit.runners.JUnit4; import java.math.BigInteger; 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)); } }
Code language: Java (java)

Additional test cases

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); } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments