I'm trying to solve the FibFrog Codility problem and I came up with the following approach:

1. If len(A) is 0 we know we can reach the other side in one jump.
2. If len(A) 1 is a fibonacci number, we can also reach it in one jump.
3. Else, we loop through A, and for the positions we can reach, we check if we can either reach them directly from -1 using a fibonacci number (idx 1 in fibonaccis) or if we can reach them by first jumping to another position (reachables) and then jumping to the current position. In either case, we also check if we can go from the current position to the end of the river - if we can, then we can return because we found the minimum number of steps required.
4. Finally, if unreachable is True once this loop completes, this means we can't reach any position using a Fibonacci number, so we return -1.

I'm getting 83% correctness and 0% performance with this approach.

I understand the solution is O(n^2), assuming the array consists of only 1, the nested loop for v in reachables: would run n times - however I'm not sure how else I can compute this, since for each of the positions I need to check whether we can reach it from the start of the array, or from any previous positions using a fibonacci number.

    def solution(A):
        if len(A) == 0: return 1 
        fibonaccis = fibonacci(len(A)   3)
        if len(A)   1 in fibonaccis: return 1
        leaves = [0] * len(A)
        unreachable = True
        reachables = []
        for idx, val in enumerate(A): 
            if val == 1: 
                if idx   1 in fibonaccis: 
                    unreachable = False
                    leaves[idx] = 1
                    if len(A) - idx in fibonaccis: 
                        return 2
                    reachables.append(idx)
                elif len(reachables) > 0: 
                    for v in reachables: 
                        if idx - v in fibonaccis: 
                            leaves[idx] = leaves[v]   1
                            if len(A) - idx in fibonaccis: 
                                return leaves[v]   2
                            reachables.append(idx)
                            break
        if unreachable: return -1 
        if len(A) - reachables[-1] in fibonaccis: 
            return leaves[reachables[-1]]   1
    
    def fibonacci(N): 
        arr = [0] * N
        arr[1] = 1
        for i in range(2, N): 
            arr[i] = arr[i-1]   arr[i-2]
        return arr

CodePudding user response：

Some suggestions for improving performance of your algorithm -

• If len(A) = 100000, you are calculating 100003 fibonacci numbers, while we only need fibonacci numbers which are less than 100k, which would be <30 of them.
• Your solution is O(n^4), since each X in reachables or Y in fibonaccis operation is O(N) where N is len(A). (and length of fibonaccis being N because of above issue)
• Since you are doing a lot of item in list operations on fibonaccis and reachables, consider making it a set or a dictionary for faster(O(1) instead of O(n)) lookup.
• Even with the above changes, the algorithm would be O(N^2) because of nested looping across A and reachables, so you need to come up with a better approach.

With your existing implementation, you need to traverse through all the paths and then in the end you will get the smallest number of jumps.

Instead of this approach, if you start at 0, and then keep a count of the number of jumps you have taken so far, and maintain how far(and to which numbers) you can reach after each jump then you can easily find the minimum jumps required to reach the end. (this will also save on redundant work you would have to do in case you have all 1s in A.

e.g. for

A = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
fibonacci = set(1, 2, 3, 5)

At first jump, we can reach following 1-based indexes -

reachable = [1, 2, 3, 5]
jumps = 1

After second jump

reachables = [2, 3, 4, 5, 6, 7, 8]
jumps = 2

After third jump

reachables = [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
jumps = 3

so you have reached the end(10) after 3 jumps.

Please check out @nialloc's answer here - https://stackoverflow.com/a/64558623/8677071 which seems to be doing something similar.