-module(fib_frog).
-export([fib_frog/1]).

fib_frog(A) ->
    Size = length(A),
    Arr = array:from_list(A),
    Fibs = gen_fibs(Size),
    bfs([-1], sets:from_list([-1]), Fibs, Size, Arr, 0).

gen_fibs(Size) ->
    gen_fibs(0, 1, Size, []).

gen_fibs(_A, B, Size, Acc) when B > Size ->
    lists:reverse(Acc);
gen_fibs(A, B, Size, Acc) ->
    gen_fibs(B, A + B, Size, [B | Acc]).

bfs(Frontier, Visited, Fibs, Size, Arr, Level) ->
    Hit = lists:any(fun(Idx) ->
        lists:any(fun(F) -> Idx + F =:= Size end, Fibs)
    end, Frontier),
    case Hit of
        true -> Level + 1;
        false ->
            NextCandidates = lists:usort([Idx + F || Idx <- Frontier, F <- Fibs,
                                            Idx + F >= 0, Idx + F < Size,
                                            array:get(Idx + F, Arr) =:= 1,
                                            not sets:is_element(Idx + F, Visited)]),
            case NextCandidates of
                [] -> -1;
                _ ->
                    Visited1 = sets:union(Visited, sets:from_list(NextCandidates)),
                    bfs(NextCandidates, Visited1, Fibs, Size, Arr, Level + 1)
            end
    end.