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 ```python 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** ```text 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** ```text 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** ```text 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.