Massive Algorithms: Codility - Lesson 11: FibFrog

Codility - Lesson 11: FibFrog

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

The Fibonacci sequence is defined using the following recursive formula:

    F(0) = 0
    F(1) = 1
    F(M) = F(M - 1) + F(M - 2) if M >= 2

A small frog wants to get to the other side of a river. The frog is initially located at one bank of the river (position −1) and wants to get to the other bank (position N). The frog can jump over any distance F(K), where F(K) is the K-th Fibonacci number. Luckily, there are many leaves on the river, and the frog can jump between the leaves, but only in the direction of the bank at position N.

The leaves on the river are represented in a zero-indexed array A consisting of N integers. Consecutive elements of array A represent consecutive positions from 0 to N − 1 on the river. Array A contains only 0s and/or 1s:

0 represents a position without a leaf;

1 represents a position containing a leaf.

The goal is to count the minimum number of jumps in which the frog can get to the other side of the river (from position −1 to position N). The frog can jump between positions −1 and N (the banks of the river) and every position containing a leaf.

For example, consider array A such that:

    A[0] = 0
    A[1] = 0
    A[2] = 0
    A[3] = 1
    A[4] = 1
    A[5] = 0
    A[6] = 1
    A[7] = 0
    A[8] = 0
    A[9] = 0
    A[10] = 0

The frog can make three jumps of length F(5) = 5, F(3) = 2 and F(5) = 5.

Write a function:

int solution(int A[], int N);

that, given a zero-indexed array A consisting of N integers, returns the minimum number of jumps by which the frog can get to the other side of the river. If the frog cannot reach the other side of the river, the function should return −1.

For example, given:

    A[0] = 0
    A[1] = 0
    A[2] = 0
    A[3] = 1
    A[4] = 1
    A[5] = 0
    A[6] = 1
    A[7] = 0
    A[8] = 0
    A[9] = 0
    A[10] = 0

the function should return 3, as explained above.

BFS:
http://codesays.com/2014/solution-to-fib-frog-by-codility/
To solve this question, we are using the Breadth First Search with pruning. For a game with N intermediate nodes, the count of Fibonacci numbers, to say CF, is proportional to log(N) [Wikipedia]. And with our pruning, for each node, there are CF attempts to jump. So the total number of overall attempts is proportional to N*CF = N*log(N). That is, the worst-case time complexity is O(N*log(N)).
利用BFS。仅记录当前位置和下一跳位置，当下一跳位置为终点时算法结束，返回跳数。对下一跳位置用贪心算法，先尝试可能到达的最远的下一跳位置（与当前位置距离为Fibonacci值，该位置有荷叶），若以该位置为下一跳最终不可达到终点，则尝试可能到达的第二远的下一跳位置，算法如此进行，若不论以何位置为下一跳均不能到达终点，则返回-1.
http://www.cnblogs.com/parapax/p/3651384.html
http://blog.csdn.net/liushuying668/article/details/39524055
就是个BFS，因为是求最小的步数，所以状态只要记录当前的位置以及走过的步数就好，状态转移的数组是fib数列（最大的fib数不应当大于河岸的长度，也就是A的size），每次找下一个状态的时候用贪心看最远能跳到哪里。

vector<int> dynamicFibs(int n) {
    vector<int> fibs;
    fibs.push_back(0);
    fibs.push_back(1);
    for(int i=2;i<=n+2;i++) {
        int tmp = fibs[i-1]+fibs[i-2];
        if(tmp>n+2) {
            break;
        }
        fibs.push_back(tmp);
    }
    return fibs;
}
typedef struct state {
    int pos;
    int step;
}state;
int solution(vector<int> &A) {
    // write your code in C++98
    const int size = A.size();
    if(size==0) {
        return 1;
    }
    vector<int> fibs = dynamicFibs(size);
    int maxAction = fibs.size();
    bool visited[size];
    fill(visited,visited+size,false);
    queue<state> q;
    state start = {-1,0};
    q.push(start);
    while(!q.empty()) {
        state s = q.front();
        q.pop();
        for(int i = maxAction;i>=1;i--) {
            int nextPos = s.pos+fibs[i];
            if(nextPos==size) {
                return s.step+1;
            }
            if(nextPos>size||A[nextPos]==0||visited[nextPos]==true) {
                continue;
            }
            state next;
            next.pos = nextPos;
            next.step = s.step+1;
            q.push(next);
            visited[nextPos] = true;
        }
    }
    return -1;   
}

http://www.martinkysel.com/codility-fibfrog-solution/

def solution(A):

    # you can always step on the other shore, this simplifies the algorithm

    A.append(1)

    fib_set = get_fib_seq_up_to_n(len(A))

    # this array will hold the optimal jump count that reaches this index

    reachable = [-1] * (len(A))

    # get the leafs that can be reached from the starting shore

    for jump in fib_set:

        if A[jump-1] == 1:

            reachable[jump-1] = 1

    # iterate all the positions until you reach the other shore

    for idx in xrange(len(A)):

        # ignore non-leafs and already found paths

        if A[idx] == 0 or reachable[idx] > 0:

            continue

        # get the optimal jump count to reach this leaf

        min_idx = -1

        min_value = 100000

        for jump in fib_set:

            previous_idx = idx - jump

            if previous_idx < 0:

                break

            if reachable[previous_idx] > 0 and min_value > reachable[previous_idx]:

                min_value = reachable[previous_idx]

                min_idx = previous_idx

        if min_idx != -1:

            reachable[idx] = min_value +1

    return reachable[len(A)-1]

https://github.com/acprimer/Codility/blob/master/src/Lesson11/FibFrog.java
public int solution(int[] A) {
int[] fib = new int[MAX_STEP];
fib[0] = fib[1] = 1;
for (int i = 2; i < MAX_STEP; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
int n = A.length;
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = -1;
if (i < n && A[i] == 0) continue;
if (Arrays.binarySearch(fib, i + 1) >= 0) {
dp[i] = 1;
continue;
}
for (int j = 1; j < MAX_STEP; j++) {
if (i - fib[j] < 0) break;
if (dp[i - fib[j]] == -1) continue;
if (dp[i] == -1) dp[i] = dp[i - fib[j]] + 1;
else dp[i] = Math.min(dp[i], dp[i - fib[j]] + 1);
}
}
return dp[n];
}
http://codility-lessons.blogspot.com/2015/03/lesson-11-fibfrog-fib-frog.html
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.
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;
}
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.
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;
}
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.
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;
}

Codility - Lesson 11: FibFrog

Labels

Popular Posts