'''
This approach consists in getting the number of possible paths for each
position where we stop in a grid. We know that once we reach the bottom
or the right of the grid, there is only one path possible from there,
so we take advantage of this fact and calculate the total number of
possible paths starting from the bottom right corner. A 2x2 grid would
have 9 indices starting at 0:
012
345
678

We start at index 8 and will calculate the number of possible paths for
all previous positions. From index 8, we calculate that index 4 must
have 2 possible paths to reach index 8 (4>7>8 and 4>5>8). We then find
that index 3 has 3 possible paths since from there we can go right to
index 4 (2 paths) or down to index 6 (1 path). We continue by checking
index 1, which would be the sum of the number of paths at index 4 and
index 2, which is 3 possible paths from there. Now, we are left at the
beginning and the total number of possible paths is index 3 + index 1
(3 + 3 = 6).

The values used would then be tweaked a little depending on the size
of the grid, but the algorithm remains the same. Here is how it works
concretely:

- Get the number of positions in the grid. 2x2 means 9 positions by
counting all intersections. With a 2x2 starting at index 0, we have the
following positions:
012
345
678

- Generate a list corresponding to the length of previously found number
  of positions and give a value of 1 to each position. For a 2x2, it is
  [1,1,1,1,1,1,1,1,1]
- Determine the multiple to be used to check if an index falls in the
  first column (grid_size + 1). The indices in the first column are 0, 3
  and 6, so multiple = 3.
- Start from the bottom right corner of the grid (index 8). Get the
  index of that position starting at zero (length of positions - 1).
- Start a while loop:
    - Check if current position is equal to grid size, meaning we got to
      the last position to evaluate. Return the value of the first index if
      this is the case.
    - Check if current position is a multiple of 3 in that example.
      If so, we skip and go back one index. For instance, if index was 6
      (multiple of 3), go back to index 5.
    - Determine the index of position to the left of current position
      and the index of position above current position. Sum the two together
      and give that value to the index that corresponds to one step left
      and one step up in the grid. Starting at 8, we sum index 7 and index
      5 (result = 2) and set that value for index 4, which is the number of
      possible paths from that index number.
    - Decrement current position by one and repeat the process until we
      break out of the loop.
'''

GRID_SIZE = 100


def num_paths(grid_size):
    '''Return the number of possible paths in a grid of size `grid_size`
    when going only right and down as an integer.'''
    num_points = (grid_size + 1) ** 2
    path_list = [1] * num_points
    multiple = grid_size + 1  # Indices of first column match this multiple

    # Last index in list
    starting_point = len(path_list) - 1

    while True:
        if starting_point == grid_size:
            return path_list[0]
        if starting_point % multiple == 0:
            starting_point -= 1
        else:
            previous = starting_point - 1
            previous2 = starting_point - multiple
            left_up_index = previous2 - 1
            left_up_value = sum([path_list[previous], path_list[previous2]])
            path_list[left_up_index] = left_up_value
            starting_point -= 1


if __name__ == '__main__':
    print(num_paths(GRID_SIZE))