TITLE: Why Didn't I Know This Already? AUTHOR: Eugene Wallingford DATE: January 28, 2005 4:43 PM DESC: I learned two little bits of Java today. Not much, but it's fun to learn something new. ----- BODY: The little things I have left to learn... Twice today I encountered something about Java that I didn't know. First: a colleague had a piece of code with three variables typed as bytes:

piecesRemaining = piecesAtStart - piecesTaken; The compiler complained about a loss of precision. When he cast the righthand side of the expression to byte, everything worked fine:

piecesRemaining = (byte) (piecesAtStart - piecesTaken); So off I trudge to the Java Language Reference, where on Page 27 I find:

Java performs all integer arithmetic using int or long operations. A value that is of type byte, short, or char is widened to an int or a long before the arithmetic operation is performed.

So your RHS value are upcast to ints for the subtraction, resulting in a downcast on assignment. But why does Java work this way? Any ideas? Second: I'm teaching an undergraduate algorithms course this year for the first time in a long while, and I often find myself whipping up a quick program in Scheme or Java to demonstrate some algorithms we've designed in class. This afternoon I was implementing a brute-force algorithm for the old Gas Station Problem:

A cyclic road contains n gas stations placed at various points along the route. Each station has some number of gallons of gas available. Some stations have more gas than necessary to get to the next station, but other stations do not have enough gas to get to the next station. However, the total amount of gas at the n stations is exactly enough to carry a car around the route exactly once.
Your task: Find a station at which a driver can begin with an empty tank and drive all the way around the road without ever running out of gas.
The input to your algorithm is a list of n integers, one for each station. The ith integer indicates the number of miles a car can travel on the gas available at the ith station.
For simplicity, let's assume that stations are 10 miles apart. This means that the sum of the n integers will be exactly 10n.
The output of your algorithm should be the index of the station at which the driver should begin.

Our algorithm looked like this:

    for i ← 1 to n do
        tank ← 0
        for j ← i to ((i + n) mod n) do
            tank := tank + gas[j] - 10
            if tank < 0 then next i
        return i

How to do that next i thing? I don't know. So off again I go to the language reference to learn about labels and the continue statement. Now, to be honest, I knew about both of these, but I had never used them together or even thought to do so. But it works:

    outer:
    for ( int i = 0; i < gas.length; i++ )
    {
        tank = 0;
        for ( int j = i; j < i + gas.length; j++ )
        {
            tank = tank + gas[j % gas.length] - 10;
            if ( tank < 0 )
                continue outer;
        }
        return i;
     }

Some days I have major epiphanies, but more often I learn some little nugget that fills an unexpected hole in the web of my knowledge. The Java gurus among you are probably thinking, "He really didn't know that? Sheesh..." Neither one of these Java nuggets is earth-shaking, just the sort of details I only learn when I need to use them in program for the first time. I suppose I could study the Java Language Reference in my free time, but I don't have the sort of job for which that sounds attractive. (Is there such a job?) -----