UVa 498: Polly the Polynomial

UVa 498: Polly the Polynomial

Written by on 22 May 2012

Topics: UVa Online Judge

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.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.