A rover on a square grid starts at cell (0, 0). It receives a list of commands, each a tuple (direction, steps): "N" adds 1 to y, "S" subtracts 1 from y, "E" adds 1 to x and "W" subtracts 1 from x, once for every step. The rover occupies every cell it passes through, one step at a time, and the starting cell counts as visited.
Write first_revisit(commands) that returns the first cell the rover enters for the second time, as a tuple (x, y), or None if it never enters a cell twice.
Routes can be long: a list-based search that looks through every earlier cell at each step is too slow for the biggest tests.
Two helpers can build routes for Run: spiral_route(legs) gives a route that winds outwards and never crosses itself, and rover_route(n, seed) gives n random commands.
Examples
Input: commands = [("N", 2), ("E", 1), ("S", 1), ("W", 2)]
Output: (0, 1)
Explanation: the rover visits (0, 1), (0, 2), (1, 2), (1, 1) and then (0, 1) again.
Input: commands = [("E", 3)]
Output: None
Input: commands = [("N", 1), ("S", 1)]
Output: (0, 0)
Constraints
0 <= len(commands) <= 2000,1 <= steps <= 1000- the total number of steps is at most
2 * 10**5
Goals
- Represent a grid cell as an (x, y) tuple and store visited cells in a set
- See why a set makes the membership test fast enough for long routes