I wrote this article for TopCoder, but since they haven’t gotten back to me I’ll post it here instead.
The Java library is filled with an abundance of useful classes that can save you time and effort in contest environments. In this article I describe a handful of tools which I think are particularly useful.
If you’re a proficient Java programmer, chances are you’ll be familiar with some of the classes and methods described here. I’d suggest skimming through anyway to make sure you have a firm grasp on all of these techniques.
String Parsing
Although TopCoder problems usually supply input as ready-to-use variables, sometimes basic string parsing is necessary for extracting data. A few examples of problems for which this is necessary are MakingPotions and SmartWordToy.
The first method I will cover is the String.split(String regex) method. This method searches for delimiters which match the provided regular expression and returns an array of substrings. For example, to parse a string of space-separated integers, you could do the following:
String input = "12 34 56";
String[] pieces = input.split(" ");
In the above example, pieces will contain {"12", "34", "56"}.
When you need to extract integers from a string, String.split can be inconvenient in that it only produces arrays of strings. Another useful tool for string parsing is the java.util.Scanner class. Once you instantiate a Scanner, you can call methods like nextInt(), nextDouble() and nextLine(). By default it will ignore all whitespace (except that it uses it to delimit data), which is generally desirable. Here is an example demonstrating how a Scanner can be used:
java.util.Scanner sc = new java.util.Scanner("12 34 56");
int A = sc.nextInt(), B = sc.nextInt(), C = sc.nextInt();
// Now A will hold 12, B will hold 34, and C will hold 56
Scanners are especially useful in other contest environments where data must be read from standard input. To do this, you can construct a scanner using new Scanner(System.in).
String Formatting
Java supports printf-style formatting through the Formatter class, but it is easier to do formatting through other methods like String.format. These features allow programmers to combine various types of data into complex string representations with very little code. Here are some examples of string formatting:
String.format("%d", 42) // returns "42" (%d is for decimal)
String.format("%f", Math.PI) // returns "3.141593" (%f is for float)
String.format("%s", "hello") // returns "hello" (%s is for string)
String.format("%d, %f, %s", 42, Math.PI, "hello") // returns "42, 3.141593, hello"
String.format("%.2d", Math.PI) // returns "3.14" (.2 indicates 2 decimal places)
There are many uses for formatting. For a detailed guide, see the Formatter javadoc.
You should also be aware of the StringBuffer class, a mutable sequence of characters. Appending many items onto a plain String object is grossly inefficient as the immutable String is repeatedly reconstructed, but the StringBuffer offers constant amortized time for its append methods. StringBuffer also provides some extra goodies — for example, you can use it to reverse strings like this:
String reverse(String s) {
return new StringBuffer(s).reverse().toString();
}
If your program is single-threaded, you can cut some overhead by using StringBuilder instead.
Bases
A common task in contest-style programming is converting to and from binary and other bases; see HexatridecimalSum for an example. Thankfully, the Integer class contains two functions which make this unbelievably easy:
String Integer.toString(i, radix)
int Integer.parseInt(String s, int radix)
The term “radix” is esentially synonymous with “base.” The first method converts an integer to a specified base; the second method parses a numeric string encoded in some specified base and returns the result as an integer.
When combined with the String class, these functions can make otherwise tedious tasks very simple. For example, the SquareDigitNumbers problem can be solved with this one line of code:
public int getNumber(int n) {
return Integer.parseInt(Integer.toString(n, 4).replace("3", "9").replace("2", "4"));
}
Collections and Arrays
I won’t cover specific types of Collections — that’s a massive topic on which several books have been written. Rather, I want to bring attention to the java.util.Collections class, which provides a number of useful methods for working with collections:
The class java.util.Arrays provides similar functionality for sorting and searching arrays, though it lacks min and max functions. It also provides a couple other handy methods:
String Arrays.toString(Object[] a): converts an array to a string of the form [A, B, C, D]. This is particularly useful for debugging. If you have nested arrays, use Arrays.deepToString.boolean Arrays.equals(Object[] a1, Object[] a2): compares two arrays for equality by comparing each of their elements. Note that this is different from a1.equals(a2) — since arrays inherit their equals method from Object, the latter only checks whether a1 and a2 refer to the same array in memory (which is usually not what you want). To compare nested arrays for equality, use Arrays.deepEquals.
Note that although the Collections class doesn’t have these two methods, you can still apply them to collections by converting collections to arrays. Here is an example:
List<Integer> L = new LinkedList<Integer>();
for (int i = 0; i < 10; ++i)
L.add(i);
System.out.println(Arrays.toString(L.toArray(new Integer[0])));
Big Numbers
java.math.BigInteger is a handy class for dealing with arbitrarily large integers. The class has comprehensive support for common arithmetic operations, so rather than presenting a long list of functions you may find useful, I’ll give a simple example of how it can be used to implement the factorial function:
BigInteger factorial(BigInteger n) {
BigInteger result = new BigInteger("1");
for (BigInteger m = n; m.signum() == 1; m = m.subtract(BigInteger.ONE))
result = result.multiply(m);
return result;
}
If you’re dealing with large non-integral numbers, java.math.BigDecimal is a useful class for this.
Geometry
The java.awt.geom library contains a number of classes for representing points, lines, and various shapes. I generally prefer to store such objects using my own data structures, but even if you don’t want to use these classes for data representation, they provide a number of useful static methods for you to use. Note that all of the functions listed below take doubles as arguments
boolean Line2D.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4): tests whether two line segments intersect one another.double Line2D.ptLineDist(x1, y1, x2, y2, px, py): returns the shortest distance between a point and a line. Note that this treats the the given line as an infinitely long line, not a line segment; if you’re dealing with line segments, use Line2D.ptSegDist.int Line2D.relativeCCW(x1, y1, x2, y2, px, py): returns 1, 0, or -1 depending on whether path described by (x1, y1) -> (x2, y2) -> (px, py) is a counter-clockwise, straight, or clockwise turn. Note that the result is based on the java.awt coordinate system, wherein the y-axis points in the downward direction. If you’re working with standard Cartesian coordinates (y-axis points upward), just negate the result.double Point2D.distance(x1, y1, x2, y2): a convenience method for computing the distance between two points with minimal clutter.
Another useful function in the Java library is java.awt.Polygon.contains(x, y). Unfortunately this cannot be accessed in a static way — you must construct a Polygon first.
Conclusion
While Java can be slow compared to fully compiled languages, the expansive built-in library can be a great advantage to those who leverage its power effectively. I hope this tutorial taught you some new techniques that will be helpful in contest programming and elsewhere.
