Lesson 11: FibFrog (Fib Frog)

Lesson 11: FibFrog
https://codility.com/programmers/lessons/11

This is classified as an ambitious problem. So let's solve this step-by-step.

First of all, we know that the 25th and 26th fibonacci numbers are 75,025 and 121,393 respectively.
Since N is between 1 ... 100,000 in this problem computing 25 fibonacci numbers is enough.

Then we try jumping recursively we reach the other bank (at the position N), and pick up the smallest number of jumps made to reach at the position N among all the successful cases.

The code below implements this strategy. However, as shown,  the strategy doesn't give a good score.
As the timeout occurs, we don't even know if the implementation performs correctly or not even in the correctness section.

 #include <alloca.h>
void check(int* A, int pos, int* fibN, int fibN_length, int cnt, int* min, int N)
{
    //we perform one more jump in this check
    cnt++;
        
    //try the largest jump as possible.
    int fibIdx = fibN_length - 1;
    int fib;

    //check if the frog can arrive the other bank by the next jump.
    while(fibIdx > 1){
        fib = fibN[fibIdx];
        
        //the forg reached to the other bank. this route is over.
        if (pos + fib == N){
            //update the min 
            *min = cnt < *min ? cnt : *min;
            break;
        }
        else if (pos + fib < N){
            break;
        }
        fibIdx--;
    }
    
    //now we seek for the smaller jumps can be used to investigate other routes.
    while(fibIdx > 1){
        fib = fibN[fibIdx];
        //try recursion, if there is any leaf there.
        if (A[pos + fib] == 1){
           check(A, pos + fib, fibN, fibN_length, cnt, min, N);
        }
        fibIdx--;
    }
    
    return;    
}

int solution(int A[], int N) 
{
    //for N = 0, 1, 2, the distance to jump from `-1' (the origin)
    //can be 1, 2, 3. then we know these a fibonacci number.
    if (N <= 2){
        return 1;
    }
    //we now N <= 100,000. Since fib(25) == 75025, fib(26) = 121393,
    //we only have to generate 25 fibonacci numbers.
    int fibN_length = 26;
    int* fibN = (int*)alloca(fibN_length * sizeof(int));
    
    fibN[0] = 0;
    fibN[1] = 1;
    
    int i = 2;
    while (i < fibN_length){
        fibN[i] = fibN[i - 1] + fibN[i - 2];
        //if one jump is enough, we can simply return here.
        if (fibN[i] == N + 1){
            return 1;
        }
        i++;
    }
    
    int min = 0x7FFFFFFF;
    check(A, -1, fibN, fibN_length, 0, &min, N);
    
    return min == 0x7FFFFFFF ? -1 : min;
}


So, now it is clear that we need to improve the performance. The problem is that we check all the possible cases. The below code checks if the current number of jumps exceeds the minimum number of jumps that let the frog reaches at the position N (the other bank) performed so far, and stop jumping recursively, since it is clear that performing one more jump doesn't contribute to get an answer.

The below code implements this strategy and give the 100% correctness score, but the performance score is still 83%. The whole tat score is 91%, and due to one timeout error.

 #include <alloca.h>
void check(int* A, int pos, int* fibN, int fibN_length, int cnt, int* min, int N)
{
    //we perform one more jump in this check
    cnt++;
    
    //we will have one more jump later in this code.
    //so if cnt is already min, we don't have any smaller number 
    //of jumps in this route.
    if (cnt >= *min){
        return;
    }
    
    //try the largest jump as possible.
    int fibIdx = fibN_length - 1;
    int fib;

    //check if the frog can arrive the other bank by the next jump.
    while(fibIdx > 1){
        fib = fibN[fibIdx];
        
        //the forg reached to the other bank. this route is over.
        if (pos + fib == N){
            //update the min. As we checked cnt < *min already,
            //cnt is always smaller than *min here. 
            *min = cnt;
            break;
        }
        else if (pos + fib < N){
            break;
        }
        fibIdx--;
    }
    
    //now we seek for the smaller jumps can be used to investigate other routes.
    while(fibIdx > 1){
        fib = fibN[fibIdx];
        //try recursion, if there is any leaf there.
        if (A[pos + fib] == 1){
           check(A, pos + fib, fibN, fibN_length, cnt, min, N);
        }
        fibIdx--;
    }
    
    return;    
}

int solution(int A[], int N) 
{
    //for N = 0, 1, 2, the distance to jump from `-1' (the origin)
    //can be 1, 2, 3. then we know these a fibonacci number.
    if (N <= 2){
        return 1;
    }
    //we now N <= 100,000. Since fib(25) == 75025, fib(26) = 121393,
    //we only have to generate 25 fibonacci numbers.
    int fibN_length = 26;
    int* fibN = (int*)alloca(fibN_length * sizeof(int));
    
    fibN[0] = 0;
    fibN[1] = 1;
    
    int i = 2;
    while (i < fibN_length){
        fibN[i] = fibN[i - 1] + fibN[i - 2];
        //if one jump is enough, we can simply return here.
        if (fibN[i] == N + 1){
            return 1;
        }
        i++;
    }
    
    int min = 0x7FFFFFFF;
    check(A, -1, fibN, fibN_length, 0, &min, N);
    
    return min == 0x7FFFFFFF ? -1 : min;
}


So, we still need to improve the performance. 

We take totally a different strategy this time.

Let's say there is a position that can reach the other bank by the next jump and there are two different routes to reach the position, and each requires 2 and 3 jumps respectively. So the number of jumps  required to the other bank that passes this route will be 3 or 4 as one more jump is performed. Yet, what we need to answer is the minimum number of jumps, we can neglect 4. 

So we only have to memorize the minimum number of jumps to reach the position N (the other bank).

We prepare the array 'reached' to memorize the minimum number of jumps to reach each position, and all the next jumps made from the position are treated as 'reached[i] + 1'th jumps, as we only have to consider the minimum number of jumps.

First, we check all the position that can be reached by the first jump (the position with a leaf that can be reached by fibonacci number). We memorize that we can reach there by 1 jump. 

Then we scan the array `reached' from head to tail and pick up the reachable positions by the first jump. When we found a reachable position, then we perform the second jump from there, and memorize the positions that can be reached by 2 jumps, we repeat this for all the cells, memorizing only the minimum number of jumps that can reach each position.

The below code implements this strategy and gives the 100% score.

#include <alloca.h>
#include <memory.h>

int solution(int A[], int N) 
{
    //for N = 0, 1, 2, the distance to jump from `-1' (the origin)
    //can be 1, 2, 3. then we know these a fibonacci number.
    if (N <= 2){
        return 1;
    }
    
    //each reached[i] cell remembers the minimum jumps made to reach there so far.
    int reached_size = sizeof(int) * N;
    int* reached = (int*)alloca(reached_size);
    memset(reached, 0x00, reached_size);
    
    //these two cells can be reached when there are leaves there.
    //since 0 and 1 can be reached by the first jump, we only care if 
    //there is a leaf or not.
    reached[0] = A[0]; 
    reached[1] = A[1];
    
    //we now N <= 100,000. Since fib(25) == 75025, fib(26) = 121393,
    //we only have to generate 25 fibonacci numbers.
    int fibN_length = 26;
    int* fibN = (int*)alloca(fibN_length * sizeof(int));
    
    fibN[0] = 0;
    fibN[1] = 1;
    
    int i = 2;
    while (i < fibN_length){
        fibN[i] = fibN[i - 1] + fibN[i - 2];
        //if one jump is enough, we can simply return here.
        if (fibN[i] - 1 == N){
            return 1;
        }
        //we also mark the position that can be reached by the first jump.
        if (fibN[i] - 1 < N && A[fibN[i] - 1] == 1){
            reached[fibN[i] - 1] = 1; 
        }
        i++;
    }
    
    //let's check each cell
    int min = 0x7FFFFFFF;
    for (i = 0; i < N; i++){
        //if the cell is not reachable, we can neglect it.
        if (reached[i] == 0){   
            continue;
        }
        int min_jumps_to_here = reached[i];
        int j;
        
        for (j = 2; j < fibN_length; j++){
            int next_pos = i + fibN[j];            
            
            //if we can reach the other bank (the position N),
            // update min if necessary.
            if (next_pos == N){
                min = min_jumps_to_here + 1 < min ? min_jumps_to_here + 1 : min;
                break;
            }
            
            //if the next jump is too large, or there is no leaf there,
            //we can neglect this jump.
            if (next_pos > N || A[next_pos] == 0){
                continue;
            }
                        
            //if we have never reached to the next position before, or we can reach 
            //the next position with less jumps, update the min number of jumps
            // at the position.
            if (reached[next_pos] == 0 || 
                reached[next_pos] > min_jumps_to_here + 1){
                reached[next_pos] = min_jumps_to_here + 1;
            }
        }
    }
    
    return min == 0x7FFFFFFF ? -1 : min;
}