Moving chips between cells

Question

Challenge:

You are given a line of N cells with positive integers written in them. Initially a chip is placed on the leftmost cell. Each time it can be moved in any direction (to the left or to the right) on a neighboring cell or across the neighboring cell on the next one. The move is valid if the two numbers - the one the chip is standing on and the one the chip is going to be moved onto - have a common divisor greater than one. How far to the right is it possible to move a chip?

I have a working (I think) method of passing this challenge by recursively checking this method until it finds the optimum solution. I know this is probably the slowest way to do this (\$O(n!)\$?), and it seems that this isn't good enough, because the website I'm submitting my answer to says that I've exceeded my time limit.

Is there any way I can speed up this code?

int chipMoving(int[] a) {

   if(a.length == 1)return 0; //base case
   int b = a[0], c = a[1],d = b;
   while (c!=0){
     int f = c;
     c = b%c;
     b = f;
   }//b is now gcd of a[0] and a[1]

   if(a.length == 2)return b<=1?0:1; //if there are only two terms, return whether we can use the next number one or not 
   int e = a[2];
   while (e!=0){
     int f = e;
     e = d%e;
     d = f;
   }//e is now the gcd of a[0] and a[2]

   int leftMax = chipMoving(Arrays.copyOfRange(a,1,a.length));
   int rightMax = chipMoving(Arrays.copyOfRange(a,2,a.length));

   //if only one is available, use that one
   if(b>1 && d<=1)return 1+leftMax;
   if(d>1 && b<=1)return 2+rightMax;

   //check which is better and return that
   if(leftMax > rightMax)return 1+leftMax;
   return 2+rightMax;
}

Answer 1

I am not convinced that your code works correctly. For example if I run it with the {5,3,15,1,1,3,1} input it will result in 6 what is definietly wrong. (Nothing can have a common divisor with 1 greater than 1).

My other concern is that you only move the chip forward, although it might be necesarry to move it backwards. For example:

{5, 3, 15, 9, 1, 3, 1}

You can get to the 3 on index 5, but only if you step back from the 15 to the 3. Here is the route:

0 -> 2 -> 1 -> 3 -> 5

Your approach is to simulate the optimal route of the chip and the return the result. A cleaner approach would be to calculate all visitable positions and then return the rightmost.

This problem can be naturally interpreted as a graph traversal. The nodes are the cells, and an edge is defined between two nodes if the difference of their indices are at most 2, and they have a common divisor greater then 1.

For this you need a function that finds the greates common divisor. For example:

int gcd(long a, long b) {

    if (b==0)
        return a;
    else
        return gcd(b, a % b);
}

One that tells you if an edge exists between two nodes:

boolean edge(int[] a, int i, int j){
    return gcd(a[i], a[j]) > 1;
}

You need to mark all visited cell using a breath first traversal:

private static boolean[] getVisited(int[] a) {
    boolean[] visited = new boolean[a.length];

    Queue<Integer> toVisit = new LinkedList<Integer>();
    toVisit.add(0);

    while (!toVisit.isEmpty()) {
        int i = toVisit.remove();
        if (visited[i])
            continue;
        visited[i] = true;
        if (i - 2 >= 0 && !visited[i - 2] && edge(a, i, i - 2))
            toVisit.add(i - 2);
        if (i - 1 >= 0 && !visited[i - 1] && edge(a, i, i - 1))
            toVisit.add(i - 1);
        if (i + 2 < a.length && !visited[i + 2] && edge(a, i, i + 2))
            toVisit.add(i + 2);
        if (i + 1 < a.length && !visited[i + 1] && edge(a, i, i + 1))
            toVisit.add(i + 1);
    }
    return visited;
}

And then find the rightmost visited cell:

int chipMoving(int[] a) {
    boolean[] visited = getVisited(a);

    for (int i = visited.length - 1; i >= 0; --i)
        if (visited[i])
            return i;

    return 0;
}

The runtime characteristics of finding the visited cells is \$O(N)\$, searching for the rightmost visited is also \$O(N)\$. That makes together \$O(N)\$.

Answer 2

To help ensure correctness, it is a good idea to always use braces around your one-line if and loop statements:

if(a.length == 1) { return 0; }

at a minimum, some people would say you should split it into multiple lines:

if(a.length == 1) {
    return 0;
}

---

You should be consistent with your space around operators; with spaces is easier to read:

while (e!=0){
  int f = e;
  e = d%e;
  d = f;
}

This should be (I used a 4-space indent, 2 spaces is fine, but I prefer 4):

while (e != 0){
    int f = e;
    e = d % e;
    d = f;
}

It is a good idea to use space around arguments too:

chipMoving(Arrays.copyOfRange(a, 1, a.length));

instead of:

chipMoving(Arrays.copyOfRange(a,1,a.length));

---

Gábor Angyal's answer covers the other aspects of the code very well.