Jump game in Java

Question

Looking for code review, suggestions for improvement, best practices etc.

The problem definiton is

Jump Game

Given an array start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array. Optimum result is when u reach the goal in minimum number of jumps.

For example

Given array A = {2,3,1,1,4}

possible ways to reach the end (index list)

i) 0,2,3,4 (jump 2 to index 2, then jump 1 to index 3 then 1 to index 4)

ii) 0,1,4 (jump 1 to index 1, then jump 3 to index 4)

Since second solution has only 2 jumps it is the optimum result.

Original post can be found at CarrerCup.

/**
 * http://www.careercup.com/question?id=10130965
 * 
 * Complexity: O(n2)
 */
public final class JumpGame {

    private JumpGame() {}

    public static Collection<Integer> checkAnswer (int[] a) {
        int[] jumpLength = new int[a.length];
        int[] prevIndex = new int[a.length];

        for (int i = 1; i < a.length; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                int diff  = i - j; // calculate differences in array indexes
                // if jump is possible && if this the shortest jump from the start 
                if ((a[j] >= diff) && (jumpLength[j] < min)) {
                        min = jumpLength[j] + 1;
                        jumpLength[i] = min;
                        prevIndex[i] = j;
                    }
                }
        }

        List<Integer> list = new ArrayList<Integer>();
        int ctr = a.length - 1;
        while (ctr > 0) {
            list.add(ctr);
            ctr = prevIndex[ctr];
        }
        list.add(0);

        Collections.reverse(list);
        return Collections.unmodifiableCollection(list);
    }



    public static void main(String[] args) {
        int[] a1 = {2,3,1,1,4};
        System.out.print("Expected: 0:1:4, Actual: ");
        for (Integer i : checkAnswer (a1)) {
            System.out.print(i + ":");
        }

        System.out.println();

        int[] a2 = {3, 1, 10, 1, 4};
        System.out.print("Expected: 0:3:4, Actual: ");
        for (Integer i : checkAnswer (a2)) {
            System.out.print(i + ":");
        }


    }
}

Answer 1

Coding style

Anytime when programming, but especially when you implement an algorithm, choose variable names that are a little more verbose. When you come back to your code after some time and you want to apply some changes to your implementation, you will at first only see a blend of some i and j which are meaningless names you probably have used in other algorithms, as well. Therefore, your first question will be: What did these variables mean again in this particular context? And other readers - like me - will ask themself the same question.

Rather use speaking names such as for example jumpBaseIndex for i. (You might want to find an even better name, this is just me brain storming. I am neither a fan of abbreviations, but this is something you could argue about. However, do not forget: Code is poetry.

Object-oriented design

At some point, you might want to extend your program (you never know) and then it is a good thing to apply object-orientation instead of offering a bunch of static methods. Do not worry about efficiency. The JVM will optimize the object-allocation away if your code becomes time-critical. Why not offer an API like that:

public final class JumpGame {

  private final int[] jump;

  public JumpGame(int[] jump) {
    this.jump = jump;
  }

  public List<Integer> checkAnswer(int[] a) {
    // implementation comes here
  }

This also allows you to add extensions such as for example an implementation that validates your input value.

Return type

You are creating a result with a List with a particular order but you are returning a Collection instead. A Collection does not have an explicit ordering since it could also be represented by a Set. Your result however requires such an ordering. Since you are as a matter of fact returning a List, this order is preserved but it is not communicated to your API's user.

Return value immutability

As long as you are not caching results, I do not see a point of returning an immutable List (see above) as a result. When you return the List you give up object ownership to the method's caller which will be the only code entity making use of this object. It should be up to this entity to decide on the result's immutability. In general, immutable collections are poorly implemented in Java since their immutability is not reflected by the collection's type. This might suprise the user of your object.

However, if you added caching to your solution (which you can since you chose an object-oriented aproach, see above), you should indeed wrap the list by calling Collections#unmodifiableList(List) in order to allow handing this object over to several callers. However, you must make this explicit in your method's javadoc.

Used List implementation

I would recommend you to use a LinkedList instead of an ArrayList to record the result. You only append to the end of that list but you never read a value from it while computing your result. At the same time, you do not know the size of the final result. If you want to further process the result and therefore require an ArrayList, you should at least give an estimate for the size of the array such as its upper bound of a.length. (Concerning a, rather find a better name, see above.)

Use shorter methods

Using shorter methods allows you to segment your code into logical units. This makes your code better readable. Your core method could look something like:

public static List<Integer> checkAnswer (int[] jump) {
  return asJumpTargetList(computePreviousIndex(jump));
}

private static int[] computePreviousIndex(int[] jump) {
  // first code segment comes here
}

private static List<Integer> asJumpTargetList(int[] previousIndex) {
  // second code segment comes here
}

As a good indicator, check if you use a lot of empty lines for grouping your code. If this is true, you should probably have used different methods instead and compose calls to these methods to get your result and it is time for some refactoring.

Algorithm efficiency

Your problem can be solved quite easily in linear time (O(n)). The idea behind this algorithm is the following:

From each index, you can reach allowedJumps[index] fields. It is best to jump as far as possible. However, if you cannot reach the finalIndex in a single jump, a short jump can be advantegous if it allows you to jump further in the next round than jumping to a higher index. This is true (if and only if)

allowedJumps[index_a] > allowedJumps[index_b] + (index_b - index_a)

where index_b > index_a. This can only be true if the optimal target index_c after jumping to index_a holds index_c > index_b for all possible values of index_b. Therefore, any possible jump target is considered at most once what yields a complexity of O(n). I'll spare you a mathematical proof which is however quite trivial and follows the same idea.

This is my suggestion for an efficient (O(n)) implementation where I added some console output instead of comments in order to allow you a better understanding of the computation.

import java.util.List;
import java.util.LinkedList;

public class JumpGame {

  public static void main(String[] args) { 
    JumpGame firstJumpGame = new JumpGame(new int[] {2, 3, 1, 1, 4});
    System.out.println(firstJumpGame.findShortestPath());

    System.out.println();

    JumpGame secondJumpGame = new JumpGame(new int[] {3, 1, 10, 1, 4});
    System.out.println(secondJumpGame.findShortestPath());

    System.out.println();

    // Check for special cases:

    JumpGame thirdJumpGame = new JumpGame(new int[] {1, 1});
    System.out.println(thirdJumpGame.findShortestPath());

    System.out.println();

    JumpGame forthJumpGame = new JumpGame(new int[] {1});
    System.out.println(forthJumpGame.findShortestPath());
  }

  private final int[] jump;

  public JumpGame(int[] jump) {
    this.jump = jump;        
  }

  public List<Integer> findShortestPath() {
    List<Integer> result = new LinkedList<Integer>();
    result.add(0);
    int current = 0, nextRelevantTarget = 1;
    System.out.println("I need to jump my way through indices 0 to " 
        + (jump.length - 1));
    while(current + jump[current] < jump.length - 1) {
      System.out.println("I am at " + current + " and could jump up to " 
          + (current + jump[current]));
      int currentMaximumReach = 0, currentBestTarget = 0;
      for(int jumpTarget = nextRelevantTarget; 
          jumpTarget <= current + jump[current]; jumpTarget++) {
        int targetMaximumReach = Math.min(jump.length - 1, jumpTarget + jump[jumpTarget]);
        currentMaximumReach = Math.max(currentMaximumReach, targetMaximumReach);
        System.out.println("When jumping to " + jumpTarget 
            + " I could jump up to " + targetMaximumReach);
        if(targetMaximumReach == currentMaximumReach) {
          currentBestTarget = jumpTarget;
          System.out.println(" -> This is my current best guess");
        }
      }
      nextRelevantTarget = current + jump[current] + 1;
      current = currentBestTarget;
      result.add(current);
      System.out.println(" => I am therefore jumping to " + current);
      System.out.println("    From there, I will at least jump to " 
          + nextRelevantTarget);
    }
    result.add(jump.length - 1);
    return result;        
  }
}

Note that I did not apply all suggested optimizations in order to keep the code concise.

Prefer unit tests over example code

Instead of demonstrating the capabilities of your code by a main method, rather add unit tests. Unit tests are more concice and allow you to express directly what you are expecting (also they can be run automatically. Here is an example using JUnit:

@Test
public void testAlgorithmCorrectness() {
  assertEquals(Arrays.asList(0, 1, 4), checkAnswer(new int[] {2, 3, 1, 1, 4}));
  assertEquals(Arrays.asList(0, 3, 4), checkAnswer(new int[] {3, 1, 10, 1, 4}));
}