Home

Can Reach End

A tree with dead end written on it Photo by Mike Erskine

This post is part of the Algorithms Problem Solving series.

Problem description

In a particular board game, a player has to try to advance through a sequence of positions. Each position has a nonnegative integer associated with it, representing the maximum you can advance from that position in one move. You begin in the first position and win by getting to the last position.

For example, let A = (3,3,1,0,2,0,1) represent the board game, i.e., the lth entry in A is the maximum we can advance from L Then the game can be won by the following sequence of advances through A: take 1 step from A[0] to A[1], then 3 steps from A[1] to A[4], then 2 steps from A[4] to A[6], which is the last position. Note that A[0] = 3 >= 1, A[1] =3 >= 3, and A[4] = 2 >= 2, so all moves are valid. If A instead was (3,2,0,0,2,0,1), it would not be possible to advance past position 3, so the game cannot be won.

Write a program that takes an array of n integers, where A[i] denotes the maximum you can advance from the index i, and returns whether it is possible to advance to the last index starting from the beginning of the array.

Examples

Example 1:

Input: [3, 3, 7, 0, 2, 0, 1]
Output: True

Example 2:

Input: [2, 4, 1, 1, 0, 2, 3]
Output: True

Example 3:

Input: root = [3, 2, 0, 0, 2, 0, 1]
Output: False

Solutions

def can_reach_end(board_game):
    furthest_reach_so_far, last_index = 0, len(board_game) - 1
    current_index = 0

    while current_index <= furthest_reach_so_far and furthest_reach_so_far < last_index:
        furthest_reach_so_far = max(furthest_reach_so_far, board_game[current_index] + current_index)
        current_index += 1

    return furthest_reach_so_far >= last_index

Resources

Patreon Become a Patron Coffee icon Buy me a coffee