defmodule FibFrog do
  def fib_frog(a) do
    size = length(a)
    jumps = size |> build_fib([1, 0]) |> Enum.reverse()
    a_map = a |> Enum.with_index() |> Map.new(fn {v, i} -> {i, v} end)

    bfs([{-1, 0}], MapSet.new(), jumps, a_map, size)
  end

  defp build_fib(size, [last | _] = acc) when last > size do
    acc |> Enum.reverse() |> Enum.drop(2)
  end

  defp build_fib(size, [a, b | _] = acc), do: build_fib(size, [a + b | acc])

  defp bfs([], _visited, _jumps, _a_map, _size), do: -1

  defp bfs([{idx, jmp} | rest], visited, jumps, a_map, size) do
    case try_jumps(jumps, idx, jmp, size, a_map, visited) do
      {:found, result} -> result
      {:continue, new_paths, visited} -> bfs(rest ++ new_paths, visited, jumps, a_map, size)
    end
  end

  defp try_jumps(jumps, idx, jmp, size, a_map, visited) do
    Enum.reduce_while(jumps, {:continue, [], visited}, fn f, {:continue, paths, visited} ->
      next_idx = idx + f

      cond do
        next_idx == size ->
          {:halt, {:found, jmp + 1}}

        next_idx > size or MapSet.member?(visited, next_idx) or Map.get(a_map, next_idx) == 0 ->
          {:cont, {:continue, paths, visited}}

        true ->
          {:cont, {:continue, paths ++ [{next_idx, jmp + 1}], MapSet.put(visited, next_idx)}}
      end
    end)
  end
end