Find a path: Depth first search

Got stuck on a question about computing possible moves across a one dimensional array.

Given

A game representing an array of integers. Here is an example game board, which is kept short for simplicity

index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
value | 3 | 2 | 0 | 1 | 3 | 1 | 2 | 0 | 0 |

The point of the game is to reach the final index in the array; this is the winning condition. If you reach a zero that is not the final position, you have lost. Not all game boards are winnable.
The game starts at index 0. You can move to a new index within the range of the current index, plus the current value.  For example, from index 0 in the example, you may move forward 0, 1, 2, or 3 spaces

Implement a function that will determine if a given game board has a winnable path

General idea is start at the beginning and compute the maximum amount of distance you can move and then move there. If it works then continue if not go back one step and decrement distance by 1 and try again. Repeat till you have reached the end or get stuck.

Initial pass tried to do a while loop to track the changes, but this approach was hard to keep track of and I didn't finish in time.

Thought about it a bit more and it's a search a depth first search to be specific. Therefore if I need to keep the possible next steps as a stack of choices and pop them off as needed.

Check for the end conditions

• Am I at the end node
• Am I at a dead node value of index is 0
• Is the stack empty

Now the solution is this. Keep track of the nodes visited as a set and also the dead nodes as another set. Subtract the sets for the path

from collections import deque
from icecream import ic

def find_winning_path(moves: list[int]) -> set:
    current_stack = deque([0])
    visited_nodes = set()
    dead_nodes = set()
    while current_stack:
        index = current_stack.pop()
        if index in visited_nodes:
            continue
        visited_nodes.add(index)
        if index == len(moves) - 1:
            return visited_nodes - dead_nodes
        if moves[index] == 0:
            dead_nodes.add(index)
            continue
        for move in range(1, moves[index] + 1):
            next_index = index + move
            if next_index < len(moves):
                current_stack.append(next_index)
    return visited_nodes - dead_nodes


if __name__ == "__main__":
    moves = [3, 2, 0, 1, 3, 1, 2, 0, 0]
    winning_node = len(moves) - 1
    if winning_node in ic(find_winning_path(moves)):
        ic('Has a winning path')
    else:
        ic('No winning path')