Ball Position in a Tilting Maze After Timed Tilt Events

A game board holds a rectangular maze and a single ball. At any moment the board is in one of five states: "up", "down", "left", "right" or "flat". While the board is tilted, that is, in any state other than "flat", the ball rolls one cell per second in the tilt direction, as long as the cell next to it in that direction is not a wall.

You are given the maze, the ball's starting cell, a list of events that each tilt the board to a new state at a given time, and an end time. Return the cell the ball occupies at the end time.

Function Signature

def ball_position(maze: list[str], start: list[int], events: list[tuple[int, str]], end_time: int) -> list[int]:

maze[i][j] is '#' for a wall and '.' for an open cell. start is [row, col]. Each event is (time, state).

Rules

• Row 0 is the top row and column 0 is the leftmost column. From (row, col), "up" leads to (row - 1, col), "down" to (row + 1, col), "left" to (row, col - 1) and "right" to (row, col + 1).
• The board is "flat" from time 0 until the first event. An event (t, state) puts the board into state at time t, and the board stays in that state until the next event.
• Time advances in whole seconds. For each second s = 0, 1, ..., end_time - 1, the board's state during that second is the state set by the last event with time <= s, or "flat" if there is none. If that state is not "flat" and the neighboring cell in that direction is inside the maze and open, the ball moves into it at the end of the second. Otherwise the ball does not move.
• Cells outside the maze behave like walls, so the ball never leaves the maze.
• Events with time >= end_time have no effect.
• Return the ball's cell [row, col] at time end_time. If end_time is 0, this is start.

Constraints

• 1 <= len(maze) <= 100 and 1 <= len(maze[0]) <= 100; all rows have the same length, and every character is '#' or '.'.
• start is an open cell.
• 0 <= len(events) <= 10^4
• 0 <= time <= 10^9 for every event, and event times are strictly increasing.
• Every state is one of "up", "down", "left", "right" and "flat".
• 0 <= end_time <= 10^9

Examples

Example 1

Input: maze = ["#######", "#.....#", "#.###.#", "#.....#", "#######"], start = [1, 1],
 events = [(0, "right"), (2, "flat"), (5, "down"), (8, "right")], end_time = 12
Output: [1, 5]

During seconds 0 and 1 the ball rolls right to (1, 3). During seconds 2 to 4 the board is flat. During seconds 5 to 7 the board tilts down, but (2, 3) is a wall, so the ball stays. From second 8 it rolls right to (1, 4) and then (1, 5); (1, 6) is a wall, so it stays at (1, 5) through second 11.

Example 2

Input: maze = ["#######", "#.....#", "#.###.#", "#.....#", "#######"], start = [1, 5],
 events = [(1, "down"), (3, "left"), (100, "up")], end_time = 103
Output: [1, 1]

Second 0 is flat. During seconds 1 and 2 the ball rolls down to (3, 5). During seconds 3 to 6 it rolls left to (3, 1), and (3, 0) is a wall, so it rests there through second 99. During seconds 100 and 101 it rolls up through (2, 1) to (1, 1), and during second 102 the wall at (0, 1) blocks it.

Example 3

Input: maze = ["..", ".."], start = [0, 0],
 events = [(0, "left"), (1, "down"), (2, "right"), (4, "up")], end_time = 4
Output: [1, 1]

During second 0 the ball would leave the maze, so it stays. Second 1 moves it down to (1, 0) and second 2 moves it right to (1, 1). During second 3 the edge of the maze blocks it. The event at time 4 is not before end_time, so it has no effect.