Java Lessons from uHunt Chapter 1

This post is part of a series on Java syntax and libraries for solving the problems in each chapter of uHunt, a tool for competitive programming practice. You can find the rest of the posts in the series by visiting my uHunt Java post category.

A few months ago, I wrote two posts related to uHunt Chapter 1. The first post covers general lessons learned from completing the 39 starred problems in that chapter. The second one is a summary of the corresponding chapter of Competitive Programming 3, the companion textbook. Although I have covered Java language features in those and other posts, I thought it would be useful to provide an overall summary of the parts of Java that I found useful when solving the problems in that chapter.

Why Java?

UVa Online Judge accepts a limited set of languages: C/C++, Pascal, and Java. C and Pascal have become specialized languages. If you want to use one of those, you should have a good reason for it. That leaves C++ and Java. If you use C++, you’ll spend less time fighting the time limit. If you use Java, you’ll spend less time fighting syntax and shooting your leg off. I don’t have anything against C++, but I don’t use low-level languages much, and I’d rather spend my limited learning time on math and problem-solving techniques than on syntax. So I’m using Java. There are many other reasons to choose one language or the other, and much of what I write about on this site is language-agnostic. But this week’s post is focused on the specific language features offered by Java.

Language Basics

When you’re solving ad-hoc problems like those in uHunt Chapter 1, you don’t need to know a lot of programming language features, or even a lot about algorithms. Although the problems have varying difficulty levels, and some can take a long time to figure out, it doesn’t take long to learn the language skills required to solve them. This is one of the misconceptions about competitive programming: people assume that all competitive programming is about obscure algorithms and sophisticated techniques. That’s not accurate at the beginning. You can spend a long time increasing programming fluency and getting better at general problem-solving.

Since this is Chapter 1, I’m going to start with the basics of what a programmer would need to get up to speed with Java and programming puzzles. I’m assuming some non-Java language experience, so I won’t be covering basic syntax like if and case. I’ll go roughly in the order that you would encounter these concepts if you worked through the uHunt Chapter 1 starred problems, which is also roughly the order of the tests in my Reference.java reference class. You can use the code in that class to get more detail and complete functions for each section. With that in mind, here is a set of Java features that is useful for solving the Chapter 1 starred problems.

import

At the top of a .java file, you’ll usually see one or more lines like this:

import java.util.*;

The purpose of the Java import statement is to save you some keystrokes and make your code more readable. Rather than using an import statement, you could instead refer to classes by their fully-qualified names. For example, ArrayList is a commonly-used Java collection class that I’ll discuss below. If you import java.util.* then you can construct it like this:

ArrayList<String> list = new ArrayList<>();

(Note the Java 7 diamond operator, <>, which also saves keystrokes).

Without the import statement, that line would result in a cannot find symbol error from the compiler. To resolve the error, you would have to construct the ArrayList like this:

java.util.ArrayList<String> list = new java.util.ArrayList<>();

Since you’ll be using a lot of features from java.util, you might as well import it at the top of your solution template.

In addition to the regular import statement, there’s a special type of import statement called a static import. The canonical example of this type of import is:

import static java.lang.Math.*;

The purpose of the static import is to provide access to static final fields and static methods from a class. In this example, you’ll be able to call sqrt instead of Math.sqrt and use PI instead of Math.PI. As with a regular import, the goal is to reduce typing and keep your code looking clean.

There are three other packages besides the ones mentioned so far that I have found useful to import for the Chapter 1 starred problems. The first one is java.lang.*, which is imported automatically by the compiler. That’s why you can reference String in a Java source file with no import statements. The second one is java.io.*, which contains input and output facilities. And the last one is java.text.DecimalFormat, which is one way to format decimal output — e.g., for problem 579.

public class Main

A Java source file can contain at most one public class, and the name of that class must match the name of the source file. Don’t try to fight it. That’s just the way Java works. So for UVa solutions, you will be editing your code in a file called Main.java, since UVa only accepts classes called Main. Since all of your solution files will be called Main.java, this can become confusing if you save them on your local disk. To keep things organized, I keep each Main.java on my local machine in a directory whose name matches the UVa problem number.

public static void main(String args[])

For console applications, such as those that you’ll use for UVa solutions, you’ll need a method with the exact signature shown above. Even if you’re not using the args array of command-line arguments, public static void main() won’t cut it. If your main method doesn’t match exactly, the Java Runtime Environment will helpfully repeat this requirement for you when you run your program.

Input and Output

The one thing that almost all competitive programming problems have in common is that they read input from stdin and write output to stdout. While this may seem like a simple process, there are some complications to consider. The challenge is that programming problems are designed to measure a solution’s performance, and sometimes this includes input and output performance. The basic I/O operations used by a Java console application aren’t fast enough. I covered the details of this problem and how to resolve it in Why is Java I/O Slow?, but here’s a quick review.

I/O is a slow process compared to other work that a program does, so you want to limit how often you read input or write output. Java provides a built-in way to limit the number of I/O calls you make. To take advantage of it, you use the BufferedReader and BufferedWriter classes. These classes receive input and output calls, but they don’t call the corresponding operating system functions every time. Instead, they buffer input and output in memory. Since calling the OS functions is what takes time, this results in an overall performance gain.

BufferedReader and BufferedWriter can be initialized as follows (once you import java.io.*):

BufferedReader stdin =
    new BufferedReader(new InputStreamReader(System.in));
BufferedWriter stdout =
    new BufferedWriter(new OutputStreamWriter(System.out));

You can then call stdin.readLine to read input, and stdout.write to write output.

Even these buffered I/O routines are slow compared to in-memory Java operations. So you can make your I/O even faster by limiting how often you call stdout.write. An effective way to do this is to append to a StringBuilder when you would normally write to stdout, and then periodically write and clear the StringBuilder. For code that implements this approach and the rest of the buffered reading/writing process, see my UVa solution template, which I use whenever I start a new solution.

String.split

UVa OJ problem input often contains space-delimited strings or numbers that need to be processed individually. There are a few ways to do this, but a good approach is to start with the following:

String[] tokens = line.trim().split("\\s+");

If line is a string containing a line of input, this statement returns an array of strings so that you can process each token separately. The call to trim and the \\s+ regex ensures that you don’t have any problems with extra whitespace.

For the special case where you need to split on the pipe character (e.g., UVa 403), the regex to use is "\\|".

Note: In some UVa OJ puzzle solutions that you may find online, the authors use the StringTokenizer class to split a string into tokens. However, Java documentation specifies that using this class “is discouraged in new code.”

For-Each loop

You can use a standard for loop to iterate through an array or collection, but often it’s cleaner and more convenient to do this:

for (String s : tokens) { // do something with s }

This construct is called a foreach loop in general, but in Java the term enhanced for-loop is also used. This syntax is nice and clean, but if you need more control over the index — for example, you need to print it, or process every second element of a collection — it’s probably better to use a standard for loop instead.

Integer.parseInt and Double.parseDouble

Puzzle input data is often numeric, so if you read it as a String, you have to convert it before using it. For integer data, you can do this using Integer.parseInt(str). Other data types have similar parsing functions.

I encountered one problem in Chapter 1 where the UVa OJ input contained unexpected non-numeric characters mixed in with numbers. In those situations, you can catch NumberFormatException to ignore strings that have non-numeric characters.

String.charAt

Java annoyance #1: You can’t get a character from a string using str[i]. The compiler will helpfully tell you: “array required, but String found.” You have to use str.charAt(i). This is probably why for-each syntax doesn’t work with strings (“for-each not applicable to expression type”). How annoying. There are ways to convert between strings and arrays of characters, but it’s generally not worth it just for better syntax.

A similar annoyance: when you want an element of an ArrayList, you have to use al.get(0) rather than al[0].

String.length(), StringBuilder.length(), Array.length, ArrayList.size()

Java annoyance #2: Remembering whether to use length(), length, or size() when you need to know how many items are currently in the object you’re evaluating. Here are the rules:

• For String and StringBuilder, use length().
• For primitive arrays like char[] and int[], use length (without the parens).
• For other collections (e.g., ArrayList), use size() (with the parens).

This is one of those things you should write on a note and stick to your monitor.

ArrayList<Character>

Speaking of ArrayList, here’s Java annoyance #3: Generics don’t support primitive types. So if you declare an ArrayList<char>, the compiler will tell you: “unexpected type.” You have to use ArrayList<Character>. The same is true of int/Integer, boolean/Boolean, and so on.

toUpperCase, toLowerCase

Puzzles can be picky about the character case they want to see in output. Also, when comparing strings and characters, it’s good practice to make sure the item you’re comparing is in the case you expect. Java provides methods to convert to uppercase and lowercase. For a character, you have to use a static method:

char cUp = Character.toUpperCase(c)

With a String, you can just call the method directly:

String strUp = str.toUpperCase()

sqrt, ceil, floor, pow

Programming puzzles often involve math, so it’s helpful to have standard mathematical functions available. If you use the import static statement suggested at the beginning of this post, then you can just call those functions by name.

Java math functions generally work like their paper and pencil math counterparts. One quirk has to do with return types: floor and ceil, which map a floating point number to an integer, store that integer in a double return value. The reason for that counter-intuitive behavior may have to do with the range of values that can be stored in int or long variables compared to double. Or maybe not. In any case, you’ll often want to convert the result to an integer data type, which you can do by casting the result:

int f = (int)floor(5.5);

Arrays.sort, Collections.sort

Although you may want to learn how to implement Quicksort so you can impress your friends at parties, most of the time you’ll be using sorting mechanisms that are built into the language. Java makes it fairly easy to sort arrays and collections. If you have an array a, calling Arrays.sort(a) will sort the array in-place. You can do the same thing with a collection c (e.g., an ArrayList) by calling Collections.sort(c). You can sort your own custom objects as well, but you won’t need to do that until Chapter 2.

String.substring

Sometimes you have to manipulate parts of an input string, and you can do that using String.substring. The main issue with substring is remembering how its parameters are interpreted. Here’s how it works: The first parameter specifies the starting index of the substring. If a second parameter is supplied, it specifies the index after the ending index. Both indexes are 0-based, as is standard for string operations in Java. For example, str.substring(2, 10) returns the substring made up of the third to the tenth characters of str. Alternatively, you can think of it as the substring made up of the characters of str between index two and index nine, inclusive, or between index two inclusive and index ten exclusive. Got it? This may be another one for the sticky note on your monitor.

String.format and DecimalFormat

To print an integer with leading spaces or leading zeros, you can use String.format. There are a lot of format string options, but here are a few common examples that are applicable to programming puzzle output:

• String.format("%03d", 5) returns 005. The 3 indicates the width of the field. If the number you pass to format has fewer than three digits, then leading zeros are added.
• String.format("%3s", 5) is the corresponding syntax when you want leading spaces instead of leading zeros.
• String.format("%.3f", 5.5) rounds a floating point number to three places after the decimal point, adding trailing zeros if necessary. Note that your JVM locale will affect what character is used for the decimal separator.
• new java.text.DecimalFormat("#0.000").format(5.5) is an alternate way to obtain the same formatting as the previous example.

String.contains

To determine if string #1 contains string #2 (i.e., string #2 is a substring of string #1), you can use String.contains:

str1.contains(str2) returns true if str2 is a substring of str1.

Converting between characters and integers

Java characters are very similar to 16-bit unsigned integers. The Java documentation on data types even describes them in terms of integers from 0 to 65535. UVa problems don’t deal with Unicode, which makes things even simpler. Like ints, chars can be used as operands in arithmetic operations. For example, 'a' + 'a' returns 194. That’s not very useful, but what about 'm' - 'a'? That returns 12, which tells you that m is the 12th letter of the zero-based alphabet (where a == 0).

If you’re working on a problem that requires you to operate on individual characters, you can make use of this property of Java char to get a lot of information without using anything more complicated than arithmetic and casts. Here are a few more examples:

• (int)c returns the ASCII value of c
• (char)n returns the character associated with the ASCII value n
• (char)(n + 'a') returns the nth letter in a zero-based alphabet. For example, if n == 12 then it returns ‘m‘ . This allows you to convert back and forth between characters and their positions in the alphabet.

Attack of the clone()

Consider an integer array nums that contains some integers, maybe the return value of a function:

int[] nums = giveMeIntegers();

You may want a copy of this array that you can modify without affecting the original. This is useful in puzzles (e.g., UVa 1061) that you solve in a series of iterations, where the results of iteration n can be used to calculate iteration n+1, but where the original results of each iteration need to be used in the output.

To make a copy of nums, you might assume that you can do this:

int[] nums2 = nums;

You now have another integer array, nums2. But it actually isn’t a separate array. It’s just a reference to the original nums array. If you set nums2[0] = 1, the first element of nums will also get set to one. This won’t work if you need to refer to the original value of nums[0] when you’re building your problem output.

To solve this problem, Java offers a clone method. int[] nums2 = nums.clone() gives you a separate copy of nums, which you can modify without affecting the original. Of course, this copy isn’t free. It takes time to make the copy, and memory to store it. So you don’t want to use this feature except when you really do need to refer back to the original values in nums.

Java collections have an analogous clone method, but you won’t need that until Chapter 2.

Array literal syntax

Sometimes you know what the elements of your array should be at compile time. Java allows you to declare, create, and initialize an array in one statement, using the following syntax:

char[] directions = new char[] { 'N', 'S', 'E', 'W' };

List.contains

You can find out if a Java list (e.g., an ArrayList) contains a particular value using List.contains. For example:

ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
boolean c = list.contains(20);  // true

Keep in mind that List.contains runs in linear — $O(n)$ — time, so it’s not efficient to use on long lists or lists that you have to check a large number of times. In that case, a HashMap may be appropriate if the data you’re storing doesn’t have any duplicates. More on that in a future chapter review.

List.toArray

Java provides a method to convert a list to an array:

Integer[] arr = list.toArray(new Integer[list.size()]);

Notice that when you’re using a typed list, you have to pass in an array of the same type and the correct size. And due to Java annoyance #3, you can’t use primitive type, even though you’re getting an array back.

So why would you want to convert a list to an array? Normally you wouldn’t. But arrays do have a bit of a performance edge over lists, so if you’re going to do a lot of work on a fixed-size collection, it might make sense to first convert it to an array.

GregorianCalendar

If you’re solving a puzzle that involves calendar calculations, you definitely want to use a calendar class rather than figuring out the calculations from scratch (unless you’re doing that for the purpose of learning about calendars). While there are better date/time libraries if you’re writing an actual product in Java, the GregorianCalendar class is sufficient for programming puzzles. Here are some tips on how to use it.

Get an instance to work with:

Calendar cal = GregorianCalendar.getInstance();

Set the date/time to July 30, 2015 at midnight. Notice that the month parameter is zero-based, so you have to pass in 6 rather than 7 for July. The day and year, however, accept values that match what you see on a regular calendar:

cal.set(2015, 6, 30, 0, 0, 0);

Move forward one day in the calendar to July 31:

cal.add(Calendar.DATE, 1);

Retrieve the new month. You can verify that the month is still 6 (July), since July has 31 days:

int newMonth = cal.get(Calendar.MONTH);

Don’t forget to add one to the month if you need to display it as a number, since human-readable numeric date formats for the Gregorian calendar assign 1 to January rather than 0.

Default values for variables

To wrap up this Java overview for Chapter 1, here’s another difference between primitive types and reference types in Java. Consider a scenario where you’re using an array of integers to make a frequency count, like how many times each letter of the alphabet occurs in a word. Assuming that your word contains only lowercase letters, you can count each letter as follows:

String str = "hedgehog";
int[] primitiveLetterCounts = new int[26];
for (char c : str.toCharArray()) primitiveLetterCounts[c - 'a']++;

However, the similar code below will not work. You’ll get a NullPointerException when you run it:

Integer[] referenceLetterCounts = new Integer[26];
for (char c : str.toCharArray()) referenceLetterCounts[c - 'a']++;

The reason for this difference is that when Java initializes variables, it uses an appropriate representation of zero. For primitive numeric data types, the default value that Java uses is in fact zero. But for reference types, it is null. So the elements in the array of Integer, are not automatically initialized to 0. If you need to use the Integer reference type, you have to do the initialization manually.

Learning a Language by Solving Programming Puzzles

That concludes this tour of the features I found useful while solving the first 39 starred uHunt problems in Java. Prior to starting Project 462, I had used Java on occasion, but not extensively. If you made a similar list, it would doubtless be different than mine because you have different experience, and you would not approach the problems in the same way I did. However, one thing that I can guess about your list is that it would omit most of the features that Java offers. That is central to the nature of studying programming puzzles: You learn a subset of the language, but you keep returning to that subset, becoming more and more fluent with it as you continue practicing. Eventually the pace of language learning tapers off as you consolidate your knowledge of the core feature set that you need. But there are always more problem-solving techniques and algorithm details to learn.

(Image credit: my reference class in Eclipse)