FibFrog.py

# Returns an array of fibonnaci numbers up to max_num
def fibonacci(max_num):
    fib_arr = [1,2]
    
    n_fib = 0
    while n_fib < max_num:
        n_fib = fib_arr[-2] + fib_arr[-1]
        fib_arr.append(n_fib)
    
    return fib_arr

def solution(A):
    
    fib_nums = fibonacci(len(A) + 1)
    
    #return dyn(A,fib_nums)
    return bfs_search(A,fib_nums)
 
# Dynamic programming  
#inspired by http://www.martinkysel.com/codility-fibfrog-solution/
def dyn(A,fib_nums):
    
    A.insert(0,1)
    A.append(1)
    
    reach = [-1] * len(A)
    reach[0] = 0
    
    for i in xrange(len(A)): 
        if A[i] == 0 or reach[i] == -1:
            continue
        
        for jump_len in fib_nums:
            jump_idx = i + jump_len
            
            if jump_idx >= len(reach):
                break
            
            if reach[jump_idx] < reach[i] + 1 and reach[jump_idx] != -1:
                continue
            
            reach[jump_idx] = reach[i] + 1
            
    return reach[-1]
    
from collections import deque
# Breadth First Search
#inspired by http://codesays.com/2014/solution-to-fib-frog-by-codility/
def bfs_search(A,fib_nums):
    
    lenA = len(A)
    queue = deque()
    queue.appendleft((-1,0))
    visited_set = [False] * lenA
    
    while queue:
        
        state = queue.popleft()
        c_pos = state[0]
        c_moves = state[1]
        
        for jump_len in fib_nums:
            
            next_pos = c_pos + jump_len
            
            if next_pos == lenA:
                return c_moves + 1
            
            elif next_pos > lenA \
            or A[next_pos] == 0 \
            or visited_set[next_pos]:
                continue
            
            queue.append((next_pos,c_moves+1))
            visited_set[next_pos] = True
            
    return -1
    
    
# Depth First Search
# Won't work properly without Astar
#inspired by http://codesays.com/2014/solution-to-fib-frog-by-codility/
def dfs_search(A,fib_nums):
    
    lenA = len(A)
    queue = [[-1,0]]
    
    while queue:
        
        state = queue.pop()
        c_pos = state[0]
        c_moves = state[1]
        
        for jump_len in fib_nums:
            if c_pos + jump_len == lenA:
                return c_moves + 1
            
            elif c_pos + jump_len > lenA \
            or A[c_pos + jump_len] == 0:
                continue
            
            queue.append([c_pos+jump_len,c_moves+1])
            
    return -1