Moving chips between cells

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 b1 && d1 && b rightMax)return 1+leftMax;
   return 2+rightMax;
}

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 toVisit = new LinkedList();
    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)\$.

StackExchange Code Review Q#82801, answer score: 2