In Problem 498 at UVa Online Judge, Polly the Polynomial, we are asked to evaluate a polynomial. The problem is easier that usual, but its designed to help engineers remember the basic algebra skills, which they supposedly forget as they progress further in their studies.

## Interpretation

Each test case consists of a number of pairs of lines. The first line in each pair is a representation of a polynomial. The coefficients of the polynomial are given in decreasing order of the degree of , and are separated by a space. For example, the line “*5 2 8 -3*” represents the polynomial:

The second line in each pair is a list of s that we’re supposed to evaluate the polynomial at. Each and each coefficient of the polynomial is an integer, and the result will therefore also be an integer.

The problem itself isn’t that hard, and the solution doesn’t have to be more than a couple of *for*-loops. But today we’re going to think about *code reuse*. Let’s say that sometime in the future you get a problem that also deals with polynomials. In the worst-case scenario, you’d have to code everything from the start, and the resulting code might look exactly like that code from the polynomial problem you did a week ago. So today, we’re going to think about the future and try to make code that we can use later, maybe store it in a code library of ours. That way we can improve it and add code to it over time, and that day when you next need to work with polynomials, you already have the code ready.

## Implementation

In order to make our code reusable, we’re going to create a *Polynomial* class. Then we can add properties and methods to that class in the future. But the basics first. What do we need to represent a polynomial? From a mathematicians perspective, we only need the infinite list of coefficients, but from a programmers perspective, we need to know the coefficients, but also the *degree* of the polynomial, or the highest power of that is used. Then we can store the coefficients in an array of size . The basic structure of our polynomial class looks like the following:

// the Polynomial class public class Polynomial { // the coefficients of the polynomial, // where the i-th element is the coefficient of x^i private int[] coefficients; // the degree of the polynomial private int degree; // the constructor for a polynomial of degree 'deg' public Polynomial(int deg) { degree = deg; coefficients = new int[deg + 1]; } // return the degree of the polynomial public int getDegree() { return degree; } // get the coefficient for x^i public int get(int i) { return coefficients[i]; } // set the coefficient for x^i public void set(int i, int value) { coefficients[i] = value; } }

In this problem, we’re supposed to evaluate the polynomial at a given . Let’s implement the straightforward *evaluate* function (which of course is a member function of our *Polynomial* class).

// evaluate the polynomial at 'x' public int evaluate(int x) { // keep a running sum int result = 0; // loop through each coefficient of the polynomial for (int i = 0; i <= getDegree(); i++) { // add (coefficient at x^i) * x^i to the running sum result += get(i) * (int)Math.pow(x, i); } // return the running sum return result; }

This code is alright, but we can still improve it by using Horner’s method. Let’s take a look at the polynomial we had before:

If we factor one from each term in the polynomial which has at least one we get:

Then we can keep on doing that in the inner-most polynomial and get:

In our new *evaluate* method, we’re going to do exactly the reverse of what we just did. We have a running sum, initially zero, and then loop from the coefficient at the highest degree down to the coefficient at the lowest degree. For each coefficient, we multiply the running sum by and then add the current coefficient to the running sum.

// evaluate the polynomial at 'x' public int evaluate(int x) { // keep a running sum int result = 0; // loop through each coefficient of the polynomial, // starting at the one at the highest degree and going down for (int i = getDegree(); i >= 0; i--) { // multiply by x and then add the current coefficient result = result * x + get(i); } // return the running sum return result; }

Horner’s method can often come in handy when evaluating polynomials, for example when you’re doing base conversion. But enough of that. We have enough in our *Polynomial* class for this problem, so now it’s on to reading the input.

Reading the input in this problem is a bit trickier than usual. We have to read all integers on a line, but we’re not told how many integers are on the line. An easy way to do it would be to read the line as a string and then maybe split it up by the space character and convert each part to an integer. Well, it turns out that this problem has a huge amount of input, so we have to read the input very efficiently. Since I’m no Java expert, I ended up doing the parsing manually. I read the line into a string, and then looped through each character in the string and parsed each integer manually. Other methods I tried gave me a *Time Limit Exceeded* verdict at the online judge.

This is what the *readLineToIntegers* method looks like. Notice the use of Horner’s scheme when I parse the integer (decimal (base-10) integers can be thought of as polynomials with ).

// read a line from the input, and convert it to a list of integers public List<Integer> readLineToIntegers(Scanner in) { // the result list List<Integer> res = new ArrayList<Integer>(); // the line as a string String line = in.nextLine(); // current integer being read int x = 0; // the sign of the integer being read, // 1 if it's positive, // -1 if it's negative, // -2 if i'm not currently reading an integer int sign = -2; // loop through each character of the line for (int i = 0; i < line.length(); i++) { // if the current character is a newline if (line.charAt(i) == '\n') { // then we've finished reading the line break; } // if the current character is a minus else if (line.charAt(i) == '-') { // then the current integer is negative sign = -1; } // if the current character is a space else if (line.charAt(i) == ' ') { // if we're not currently reading an integer, // then just go onto the next character if (sign == -2) continue; // add the current integer to the list res.add(sign * x); // reset the current integer x = 0; sign = -2; } // if the current character is a digit else { // if we weren't reading an integer, // then change the sign to positive if (sign == -2) sign = 1; // convert the character digit to an integer int digit = (int)(line.charAt(i) - '0'); // append the current digit to to integer. // notice the use of Horner's scheme x = x * 10 + digit; } } // if there's still an integer being read if (sign != -2) { // add it to the list res.add(sign * x); } // return the list return res; }

Yes, I know. The code is a bit long… But since we’re focusing on code reuse, this method is actually a great piece of code to have in our code library (along with the *Polynomial* class and all our other handy code).

Now we can finally implement the *main* method (in this case a non-static *run* method because we’re using a non-static class). It’s pretty simple, now that we’ve implemented all the main functionality elsewhere.

public void run(Scanner in, PrintWriter out) { // while there are still input cases left while (in.hasNextInt()) { // read the coefficients with our handy readLineToIntegers method List<Integer> coefficients = readLineToIntegers(in); // create a Polynomial of degree coefficients.size() - 1 Polynomial p = new Polynomial(coefficients.size() - 1); // loop through the coefficients for (int i = 0; i < coefficients.size(); i++) { // and change the appropriate coefficient of the polynomial p.set(coefficients.size() - i - 1, coefficients.get(i)); } // read the list of x's List<Integer> xs = readLineToIntegers(in); // loop through the x's for (int i = 0; i < xs.size(); i++) { // print a space between to consecutive outputs if (i != 0) out.print(" "); // print the result of the polynomial evaluated at the current x out.print(p.evaluate(xs.get(i))); } // print an endline after each test case out.println(); } } public static void main(String[] args) throws Exception { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out, true); new Main().run(in, out); }

## Conclusion

We’ve finally got a working solution. We put a little extra work into this problem, but that extra work might save us some work the next time we need to work with polynomials (or read integers from a line). We also did some manual input parsing, but that can be a handy skill to have.

The blog image is of some green worm, similar to what I thought of when I read the problem title “Polly the Polynomial”. It was captured by Sigursteinn Sigurdsson who released it under the creative commons license.

You can take a look at the complete source code here.

So what do you think? Did/would you solve it differently? Leave a comment and let us know.

Written by Bjarki Ágúst on 22 May 2012

Topics: UVa Online Judge