# 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 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;
}


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];

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))
if (i - 1 >= 0 && !visited[i - 1] && edge(a, i, i - 1))
if (i + 2 < a.length && !visited[i + 2] && edge(a, i, i + 2))
if (i + 1 < a.length && !visited[i + 1] && edge(a, i, 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)$.

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));


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