Notes

Bash Fib Frog

fib_frog() {
    local -n _arr="$1"
    local _size=${#_arr[@]}
    local -a _fib=(0 1)
    local _i=1
    while (( _fib[_i] <= _size )); do
        ((_i++))
        _fib[_i]=$(( _fib[_i-1] + _fib[_i-2] ))
    done
    local -a _q_idx=(-1) _q_jmp=(0)
    local _head=0
    local -a _steps
    for ((_i = 0; _i < _size; _i++)); do _steps[_i]=0; done
    while (( _head < ${#_q_idx[@]} )); do
        local _cidx=${_q_idx[_head]} _cjmp=${_q_jmp[_head]}
        ((_head++))
        local _fidx
        for ((_fidx = ${#_fib[@]} - 1; _fidx >= 2; _fidx--)); do
            local _idx=$(( _cidx + _fib[_fidx] ))
            if (( _idx == _size )); then
                echo $(( _cjmp + 1 ))
                return
            fi
            if (( _idx > _size )) || (( ${_steps[_idx]:-0} )) || (( _arr[_idx] == 0 )); then
                continue
            fi
            if (( _arr[_idx] == 1 )); then
                _steps[_idx]=1
                _q_idx+=("$_idx")
                _q_jmp+=($(( _cjmp + 1 )))
            fi
        done
    done
    echo -1
}

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.

C++ Fib Frog

#include <queue>
#include <vector>

int fibFrog(const std::vector<int>& a)
{
    int size = static_cast<int>(a.size());

    std::vector<int> fib{0, 1};
    for (int i = 1; fib[i] <= size;) {
        ++i;
        fib.push_back(fib[i - 1] + fib[i - 2]);
    }

    struct Path {
        int idx;
        int jmp;
    };

    std::queue<Path> paths;
    paths.push({-1, 0});

    std::vector<bool> steps(size, false);

    while (!paths.empty()) {
        Path path = paths.front();
        paths.pop();

        for (int i = static_cast<int>(fib.size()) - 1; i >= 2; --i) {
            int idx = path.idx + fib[i];
            if (idx == size) {
                return path.jmp + 1;
            }
            if (idx > size || steps[idx] || a[idx] == 0) {
                continue;
            }
            if (a[idx] == 1) {
                steps[idx] = true;
                paths.push({idx, path.jmp + 1});
            }
        }
    }

    return -1;
}

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.

C# Fib Frog

static int FibFrog(int[] a)
{
    var size = a.Length;

    var fib = new List<int> { 0, 1 };
    for (int i = 1; fib[i] <= size;)
    {
        i++;
        fib.Add(fib[i - 1] + fib[i - 2]);
    }

    var queue = new Queue<(int Idx, int Jmp)>();
    queue.Enqueue((-1, 0));

    var visited = new bool[size];

    while (queue.Count > 0)
    {
        var (idx0, jmp) = queue.Dequeue();
        for (int i = fib.Count - 1; i >= 2; i--)
        {
            var idx = idx0 + fib[i];
            if (idx == size)
            {
                return jmp + 1;
            }
            if (idx > size || visited[idx] || a[idx] == 0)
            {
                continue;
            }
            if (a[idx] == 1)
            {
                visited[idx] = true;
                queue.Enqueue((idx, jmp + 1));
            }
        }
    }

    return -1;
}

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.

Elixir Fib Frog

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

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.

Erlang Fib Frog

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

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.

Go Fib Frog

func fibFrog(a []int) int {
	size := len(a)

	fib := []int{0, 1}
	for i := 1; fib[i] <= size; {
		i++
		fib = append(fib, fib[i-1]+fib[i-2])
	}

	type path struct {
		idx int
		jmp int
	}
	paths := []path{{idx: -1, jmp: 0}}
	steps := make([]bool, size)

	for len(paths) > 0 {
		cur := paths[0]
		paths = paths[1:]

		for i := len(fib) - 1; i >= 2; i-- {
			idx := cur.idx + fib[i]
			if idx == size {
				return cur.jmp + 1
			}
			if idx > size || steps[idx] || a[idx] == 0 {
				continue
			}
			if a[idx] == 1 {
				steps[idx] = true
				paths = append(paths, path{idx: idx, jmp: cur.jmp + 1})
			}
		}
	}

	return -1
}

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.

Haskell Fib Frog

import Data.Array (Array, listArray, (!))
import qualified Data.Sequence as Seq
import Data.Sequence (Seq, ViewL (..), viewl, (|>))
import qualified Data.Set as Set

fibFrog :: [Int] -> Int
fibFrog a = go (Seq.singleton (-1, 0)) (Set.singleton (-1))
  where
    n = length a
    leaves = listArray (0, n - 1) a :: Array Int Int

    -- distinct Fibonacci jump lengths, up to the first one exceeding n
    jumps = takeWhile (<= n) fibJumps
      where
        fibJumps = 1 : 2 : zipWith (+) fibJumps (tail fibJumps)

    go :: Seq (Int, Int) -> Set.Set Int -> Int
    go queue visited = case viewl queue of
      EmptyL -> -1
      (pos, steps) :< rest
        | any (\j -> pos + j == n) jumps -> steps + 1
        | otherwise ->
            let (queue', visited') = foldl (enqueue pos steps) (rest, visited) jumps
            in  go queue' visited'

    enqueue pos steps (q, visited) j
      | idx >= 0 && idx < n && leaves ! idx == 1 && not (Set.member idx visited) =
          (q |> (idx, steps + 1), Set.insert idx visited)
      | otherwise = (q, visited)
      where
        idx = pos + j

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.

Java Fib Frog

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution {
    public static int fibFrog(int[] a) {
        int size = a.length;

        List<Integer> fib = new ArrayList<>(List.of(0, 1));
        for (int i = 1; fib.get(i) <= size; ) {
            i++;
            fib.add(fib.get(i - 1) + fib.get(i - 2));
        }

        Deque<int[]> paths = new ArrayDeque<>();
        paths.add(new int[]{-1, 0}); // {idx, jmp}

        boolean[] steps = new boolean[size];

        while (!paths.isEmpty()) {
            int[] path = paths.poll();
            int curIdx = path[0];
            int jmp = path[1];

            for (int i = fib.size() - 1; i >= 2; i--) {
                int idx = curIdx + fib.get(i);
                if (idx == size) {
                    return jmp + 1;
                }
                if (idx > size || steps[idx] || a[idx] == 0) {
                    continue;
                }
                if (a[idx] == 1) {
                    steps[idx] = true;
                    paths.add(new int[]{idx, jmp + 1});
                }
            }
        }

        return -1;
    }
}

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.

Lisp Fib Frog

(defun fib-frog (a)
  (let* ((vec (coerce a 'vector))
         (size (length vec))
         (fib (make-array 2 :initial-contents '(0 1) :adjustable t :fill-pointer 2)))
    (let ((i 1))
      (loop while (<= (aref fib i) size)
            do (progn
                 (incf i)
                 (vector-push-extend (+ (aref fib (1- i)) (aref fib (- i 2))) fib))))
    (let ((paths (list (list :idx -1 :jmp 0)))
          (steps (make-array size :initial-element nil)))
      (loop while paths
            do (let ((path (pop paths)))
                 (loop for i from (1- (length fib)) downto 2
                       do (let ((idx (+ (getf path :idx) (aref fib i))))
                            (cond
                              ((= idx size) (return-from fib-frog (1+ (getf path :jmp))))
                              ((or (> idx size)
                                   (aref steps idx)
                                   (zerop (aref vec idx)))
                               nil)
                              ((= (aref vec idx) 1)
                               (setf (aref steps idx) t)
                               (setf paths (append paths (list (list :idx idx :jmp (1+ (getf path :jmp))))))))))))
      -1)))

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.

PHP Fib Frog

function fibFrog(array $a): int
{
    $size = count($a);

    $fib = [0, 1];
    for ($i = 1; $fib[$i] <= $size;) {
        $i++;
        $fib[$i] = $fib[$i - 1] + $fib[$i - 2];
    }

    $paths = [
        [
            'idx' => -1,
            'jmp' => 0
        ]
    ];

    $steps = array_fill(0, $size, false);

    while (count($paths) > 0) {
        $path = array_shift($paths);
        for ($i = count($fib) - 1; $i >= 2; $i--) {
            $idx = $path['idx'] + $fib[$i];
            if ($idx === $size) {
                return $path['jmp'] + 1;
            }
            if ($idx > $size
                || $steps[$idx]
                || $a[$idx] === 0
            ) {
                continue;
            }
            if ($a[$idx] === 1) {
                $steps[$idx] = true;
                $paths[]     = [
                    'idx' => $idx,
                    'jmp' => $path['jmp'] + 1
                ];
            }
        }
    }

    return -1;
}

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.