jump.py

# https://edabit.com/challenge/Fz92j7nQEkoRXhRE7

from typing import Union, List

def _jumping_frog(n: int, stones: List[int], path: List[int]=None, visited: List[int]=None, paths: List[List[int]]=None) -> None:
  current_position = path[-1]

  # reched final state
  if current_position == n:
    paths.append(path)
    return

  jumps = stones[current_position]

  # reached invalid state
  if jumps == 0:
    return

  # mark current position as visited
  visited.append(current_position)

  for next_position in \
    filter(
      lambda p: p not in visited,
      [min(n, current_position + jumps), max(0, current_position - jumps)]):
    _jumping_frog(
      n, stones,
      path=[*path, next_position],
      visited=visited,
      paths=paths)

def jumping_frog(n: int, stones: List[int]) -> Union[int, str]:
  paths = []
  _jumping_frog(n, stones, path=[0], visited=[], paths=paths)
  return min(len(p) for p in paths) if paths else 'no chance :-('

class Test:
  @staticmethod
  def assert_equals(i: int, o: int, s: str=None) -> None:
    assert i == o, f'failed {s if s else ""}'.rstrip()

Test.assert_equals(jumping_frog(5, [1, 1, 1, 1, 1]), 6, "simple stone-by-stone")
Test.assert_equals(jumping_frog(5, [1, 3, 1, 1, 1]), 4, "leapfrog 1")
Test.assert_equals(jumping_frog(5, [1, 5, 1, 1, 1]), 3, "leapfrog 2")
Test.assert_equals(jumping_frog(8, [2, 8, 1, 1, 1, 1, 1, 1]), 4, "leapfrog 3")
Test.assert_equals(jumping_frog(5, [1, 1, 0, 1, 1]), "no chance :-(")
Test.assert_equals(jumping_frog(5, [1, 2, 0, 1, 1]), 5)
Test.assert_equals(jumping_frog(50, [3, 0, 2, 2, 1, 1, 4, 2, 4, 1, 2, 3, 3, 0, 1, 3, 1, 2, 1, 2, 0, 0, 2, 3, 2, 0, 4, 3, 3, 0, 3, 0, 0, 1, 4, 0, 4, 2, 1, 3, 2, 0, 2, 0, 0, 3, 1, 0, 4, 1]), "no chance :-(")
Test.assert_equals(jumping_frog(50, [4, 1, 2, 0, 4, 2, 3, 4, 4, 4, 4, 2, 1, 4, 0, 0, 2, 1, 4, 1, 2, 4, 1, 4, 2, 3, 0, 4, 0, 4, 3, 4, 3, 0, 2, 3, 4, 3, 4, 0, 1, 2, 2, 2, 1, 2, 1, 2, 3, 4]), 19)