FibFrog from Codility

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 an 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.

There are some stuffs that we should pay attention to:

• the frog can get to the other side of the river (from position −1 to position N), therefore the real length of the way is N + 1.
• The frog can jump over any distance F(K), where F(K) is the K-th Fibonacci number means to reach position ith, the frog could go from positions (i — F(K)) where i — F(K) ≥ 0 and there is a leave at the position i — F(K).
• there are many leaves on the river, and the frog can jump between the leaves, thus there are some immediate positions are not permitted.
• The goal is to count the minimum number of jumps, so OPT(n) = min(1 + OPT(n — F[K]))

import sys


def generate_fib_steps(n):
    a, b = 1, 1
    yield 1
    while a + b <= n:
        yield a + b
        a, b = b, a + b


def solution(A):
    n = len(A) + 1

    ret = [sys.maxsize] * (n + 1)
    ret[0] = 0

    for i in range(1, n + 1):
        if (i < n and A[i - 1] == 1) or (i == n):
            ret[i] = min([ret[i - x] + 1 for x in generate_fib_steps(i)])

    return ret[-1] if ret[-1] < sys.maxsize else -1