Solution to Ladder by codility | Code Says

Solution to Ladder by codility | Code Says
Question: https://codility.com/demo/take-sample-test/ladder

You have to climb up a ladder. The ladder has exactly N rungs, numbered from 1 to N. With each step, you can ascend by one or two rungs. More precisely:

• with your first step you can stand on rung 1 or 2,
• if you are on rung K, you can move to rungs K + 1 or K + 2,
• finally you have to stand on rung N.

Your task is to count the number of different ways of climbing to the top of the ladder.

For example, given N = 4, you have five different ways of climbing, ascending by:

• 1, 1, 1 and 1 rung,
• 1, 1 and 2 rungs,
• 1, 2 and 1 rung,
• 2, 1 and 1 rungs, and
• 2 and 2 rungs.

Given N = 5, you have eight different ways of climbing, ascending by:

• 1, 1, 1, 1 and 1 rung,
• 1, 1, 1 and 2 rungs,
• 1, 1, 2 and 1 rung,
• 1, 2, 1 and 1 rung,
• 1, 2 and 2 rungs,
• 2, 1, 1 and 1 rungs,
• 2, 1 and 2 rungs, and
• 2, 2 and 1 rung.

The number of different ways can be very large, so it is sufficient to return the result modulo 2P, for a given integer P.

Assume that the following declarations are given:

struct Results {
  int * C;
  int L;
};

Write a function:

struct Results solution(int A[], int B[], int L);

that, given two non-empty zero-indexed arrays A and B of L integers, returns an array consisting of L integers specifying the consecutive answers; position I should contain the number of different ways of climbing the ladder with A[I] rungs modulo 2B[I].

For example, given L = 5 and:

    A[0] = 4   B[0] = 3
    A[1] = 4   B[1] = 2
    A[2] = 5   B[2] = 4
    A[3] = 5   B[3] = 3
    A[4] = 1   B[4] = 1

the function should return the sequence [5, 1, 8, 0, 1], as explained above.

http://alexandrastech.blogspot.com/2014/10/solution-to-codility-lesson-11-ladder.html

The key here is to notice that the number of ways of ascending for N=4 is Fibonacci(N+1).

I created a cache of the first x fibonacci numbers modulo 2^y where x is the max value in array a and y is the max value in array b. 

Then, for every earlier fibonacci number f (f <= x) you can look up in the cache and take cache[f] and modulo it again by whatever value is in b. 

So for example, if we consider the first few fibonacci numbers and cache them modulo 2^3:

Fib(index) =                                            1, 1, 2, 3, 5, 8, 13, 21

index =                                                   0, 1, 2, 3, 4, 5,  6,  7 

cache value = Fib(index) % 8 =             1, 1, 2, 3, 5, 0,  5,  5

Note that in this example, array b will contain values in the range (1, 3).

So we iterate over array a, look up the corresponding value in the cache and take it modulo corresponding value in b. 

def solution(A, B):

    limit    = max(A)                 # The possible largest N rungs

    result   = [0] * len(A)           # The result for each query

    modLimit = (1 << max(B)) - 1      # To avoid big interger in fibs

    # Compute the Fibonacci numbers for later use

    fib    = [0] * (limit+2)

    fib[1] = 1

    for i in xrange(2, limit + 2):

        fib[i] = (fib[i - 1] + fib[i - 2]) & modLimit ////

    for i in xrange(len(A)):

        # To climb to A[i] rungs, you could either

        # come from A[i]-1 with an one-step jump

        # OR come from A[i]-2 with a two-step jump

        # So from A[i] rungs, the number of different ways of climbing

        # to the top of the ladder is the Fibonacci number at position

        # A[i] + 1

        result[i] = fib[A[i]+1] & ((1<<B[i])-1)

    return result

https://github.com/jlhuang/codility-lessons/blob/master/lesson%2011%20:%20Fibonacci%20numbers/Ladder/Solution.java

http://www.martinkysel.com/codility-ladder-solution/
We first compute the Fibonacci sequence for the first L+2 numbers. The first two numbers are used only as fillers, so we have to index the sequence as A[idx]+1 instead of A[idx]-1. The second step is to replace the modulo operation by removing all but the n lowest bits. A discussion can be found on Stack Overflow.

def solution(A, B):

    L = max(A)

    fib = [0] * (L+2)

    fib[1] = 1

    for i in xrange(2, L + 2):

        fib[i] = fib[i - 1] + fib[i - 2]

    return_arr = [0] * len(A)

    for idx in xrange(len(A)):

        return_arr[idx] = fib[A[idx]+1] & ((1 << B[idx]) - 1)

    return return_arr

Bad solution:

def solution(A, B):

    limit = len(A)

    result = [0] * len(A)

    fib = [0] * (limit+2)

    fib[1] = 1

    for i in xrange(2, limit + 2):

        fib[i] = fib[i - 1] + fib[i - 2]

    for i in xrange(limit):

        result[i] = fib[A[i]+1] % (1<<B[i])

    return result

http://codility-lessons.blogspot.com/2015/03/lesson-11-ladder-ladder.html
Read full article from Solution to Ladder by codility | Code Says