sebinsua · July 7, 2023 13:59
diff --git a/frog-jump.py b/frog-jump.py
 from typing import List, Tuple
 from collections import defaultdict, deque

 def next_moves(stones: List[int], stone: int, previous_jump: int) -> List[Tuple[int, int]]:
    return [
        (stone + next_jump, next_jump)
        for next_jump in [previous_jump-1, previous_jump, previous_jump+1]
        if next_jump > 0 and stone + next_jump in stones
    ]

 class SolutionBFSWithDP:
    def canCross(self, stones: List[int]) -> bool:
        if stones[1] != 1: 
            return False

        last_stone = stones[-1]

        seen = set()
        queue = deque([(0, 0)])
        while queue:
            stone, previous_jump = queue.popleft()
            for move in next_moves(stones, stone, previous_jump):
                # As soon as we encounter a move that lands on the last stone
                # we can return true as our frog has reached the other side
                # of the river.
                if move[0] == last_stone:
                    return True

                # We skip any move (stone, jump) that has already been seen.
                if move in seen:
                    continue

                # And only update our queue with new move (stone, jump) elements.
                queue.append(move)
                seen.add(move)
                    
        return False

 class Solution:
    def canCross(self, stones: List[int]) -> bool:
        # We can only jump 1 stone on our first move.
        if stones[1] != 1:
            return False

        dp = defaultdict(set)
        # The frog starts on the stone containing 0 (which happens to be the first stone).
        # They were placed there with no jump -- a jump of 0.
        dp[0].add(0)

        # We are going to build `dp` bottom-up by iterating through the stones
        # and then iterating through the previous jumps that would reach each stone.
        #
        # Basically, as the stones are ascending and the frog can only jump forwards
        # it's implied that if we reach a stone and there are no jumps that landed
        # on it we skip to the next stone and if none of the stones after this have
        # jumps that reached them then the frog has gotten trapped and we will return
        # false.
        #
        # But if a stone has been jumped to we will test to see where future jumps from
        # this stone land and update `dp[next_stone]` with these jumps so that a future
        # iteration of `for stone in stones` can consider them. As `next_moves` takes a
        # `previous_jump` value and produces moves that are `[jump-1, jump, jump+1]`
        # the frog might be jumping over stones in some cases.
        #
        # If at any point the last stone has a non-empty set of jumps that reach it
        # we immediately bail from the loop by returning `True` as this means the frog
        # was able to jump to the last stone.
        last_stone = stones[-1]

        for stone in stones:
            for previous_jump in dp[stone]:
                for (next_stone, next_jump) in next_moves(stones, stone, previous_jump):
                    dp[next_stone].add(next_jump)

                if len(dp[last_stone]) > 0:
                    return True

        return False
	from typing import List, Tuple
	from collections import defaultdict, deque

	def next_moves(stones: List[int], stone: int, previous_jump: int) -> List[Tuple[int, int]]:
	return [
	(stone + next_jump, next_jump)
	for next_jump in [previous_jump-1, previous_jump, previous_jump+1]
	if next_jump > 0 and stone + next_jump in stones
	]

	class SolutionBFSWithDP:
	def canCross(self, stones: List[int]) -> bool:
	if stones[1] != 1:
	return False

	last_stone = stones[-1]

	seen = set()
	queue = deque([(0, 0)])
	while queue:
	stone, previous_jump = queue.popleft()
	for move in next_moves(stones, stone, previous_jump):
	# As soon as we encounter a move that lands on the last stone
	# we can return true as our frog has reached the other side
	# of the river.
	if move[0] == last_stone:
	return True

	# We skip any move (stone, jump) that has already been seen.
	if move in seen:
	continue

	# And only update our queue with new move (stone, jump) elements.
	queue.append(move)
	seen.add(move)

	return False

	class Solution:
	def canCross(self, stones: List[int]) -> bool:
	# We can only jump 1 stone on our first move.
	if stones[1] != 1:
	return False

	dp = defaultdict(set)
	# The frog starts on the stone containing 0 (which happens to be the first stone).
	# They were placed there with no jump -- a jump of 0.
	dp[0].add(0)

	# We are going to build `dp` bottom-up by iterating through the stones
	# and then iterating through the previous jumps that would reach each stone.
	#
	# Basically, as the stones are ascending and the frog can only jump forwards
	# it's implied that if we reach a stone and there are no jumps that landed
	# on it we skip to the next stone and if none of the stones after this have
	# jumps that reached them then the frog has gotten trapped and we will return
	# false.
	#
	# But if a stone has been jumped to we will test to see where future jumps from
	# this stone land and update `dp[next_stone]` with these jumps so that a future
	# iteration of `for stone in stones` can consider them. As `next_moves` takes a
	# `previous_jump` value and produces moves that are `[jump-1, jump, jump+1]`
	# the frog might be jumping over stones in some cases.
	#
	# If at any point the last stone has a non-empty set of jumps that reach it
	# we immediately bail from the loop by returning `True` as this means the frog
	# was able to jump to the last stone.
	last_stone = stones[-1]

	for stone in stones:
	for previous_jump in dp[stone]:
	for (next_stone, next_jump) in next_moves(stones, stone, previous_jump):
	dp[next_stone].add(next_jump)

	if len(dp[last_stone]) > 0:
	return True

	return False