You have a maze represented as an $$M$$ by $$N$$ grid. Each cell is either:
- Occupied by a wall, or
- Occupied by a turret
Each turret is facing directly North, South, East, or West. One empty cell is the start cell, and a different empty cell is the goal cell.
You start at the "start cell". Every "turn" you can take a step either North, South, East, or West. You may not walk onto an occupied cell (by a wall or a turret). After taking a step, all of the turrets (simultaneously) rotate clockwise by 90 degrees. They then shoot a "ray" straight in their new direction. These rays cannot travel through walls or other turrets. If any of these rays hits you, you die.
Find the shortest path from "start cell" to "goal cell" without dieing.
- Graph Theory / Shortest path
- Dijkstra's Algorithm or BFS
- Modified Graph
- Time is important. Time repeats mod 4
With some experience, one should immediately recognize that this is a Graph Theory problem. Classically, whenever we are asked to find a "shortest path" from some state to some other state, this can likely be modelled as a graph, and we can use various algorithms to find the path (such as Dijkstra's Algorithm or Breadth-First-Search). In fact, without the lasers, this problem reduces to a well known variant of the Shortest Path problem on a grid, which can be solved by Breadth-First-Search.
This problem becomes difficult because of the lasers. While a path may be open from start cell to finish cell, the lasers make certain cells on this path impossible to walk on. Not only so, but these lasers are SPINNING! So a cell that may be available at once may become unusable depending on whether turrets have rotated to face this cell.
The classic Breadth-First-Search solution to this problem maintains a graph where each node is a cell $$(i,j)$$. The edges represent the possible steps that one can take while on that cell. But, as mentioned above, because of the spinning of the turrets, we cannot just use $$(i,j)$$ as our state. We need to keep track of time! We need to know how many steps have passed, because this will also tell us the direction of each of the turrets implicitly. How does this work? Well, for a given turret, suppose it was facing a certain direction at time 0 (in the input), and we know the current time, say $$t$$. Then we simply have to rotate the turret $$t$$ times from its initial orientation to know which direction it is facing now.
So time is sufficient information to know the orientation of each of the turrets. So we have a refined "graph" (this is a more abstract graph). Our nodes are tuples of the form: $$(i,j,t)$$ where $$i$$ is the current row, $$j$$ is the current column (so $$(i,j)$$ is the current cell); and $$t$$ is the total number of time-steps that have passed. The edges represent valid moves that can be taken. For example, to take a step to the right, we would move from node $$(i,j,t)$$ to node $$(i,j+1,t+1)$$ (since column $$j$$ increases by one, and time $$t$$ increases by 1). This would generalize to all four directions. Therefore, the node $$(i,j,t)$$ has edges to $$(i,j+1,t+1), (i,j-1,t+1), (i+1,j,t+1),$$ and $$(i-1,j,t+1)$$ (assuming these nodes exist).
With this "modified" graph, certain nodes should be "deleted". For example, if at time $$t+1$$, cell $$(i,j+1)$$ was is visible by a turret, then the node $$(i,j+1,t+1)$$ is invalid, and we cannot move there (i.e.: we can delete this node). Theoretically you can simply check all turrets against the cell at time $$t+1$$ to check if it's valid (ignoring efficiency for a second). Similarly, if cell $$(i,j+1)$$ is "occupied", then it is also invalid.
Once we have constructed this modified graph (in theory), the answer could be found by a breadth-first-search. Each path in this modified graph represents an actual path from start to finish in the original maze, accounting for the rotations of the turrets.
BUT! We are not done yet. I left out quite a few details. In particular, what about time, space and feasibility? How many nodes $$(i,j,t)$$ are there? Well $$0 \leq i \leq m$$ and $$0 \leq j \leq n$$ (so there are at most $$nm \leq 10,000$$ cells), but what about the third dimension: $$t$$? Time could theoretically be infinite! So are there infinitely many nodes?
We need one more observation to be able to shrink the set of nodes to a manageable (or even finite) level. There is a standard observation in graph theory that particularly pertains to shortest paths: In any shortest path, you will never visit the same node twice. This helps here because, if we think about the state of the entire maze, certain "nodes" $$(i,j,t)$$ are actually (in some senses)... the same! That is, if the maze happens to look identical at two times $$t_1$$ and $$t_2$$, then the nodes $$(i,j,t_1)$$ and $$(i,j,t_2)$$ are essentially equivalent: all of the turrets would be in the same positions, and we can make any of the same moves at $$t_2$$ as we could at $$t_1$$. So these two nodes could be described as "equivalent". So any shortest path that passes through $$(i,j,t_1)$$ would never pass through $$(i,j,t_2)$$ or vice versa.
Lastly, consider any time $$t$$ and time $$t+4$$. Four time steps later, the maze will look exactly the same. Why? Because all of the turrets will have rotated $$90 \times 4 = 360$$ degrees. So all turrets will still be facing the same way. So from the above characterization, nodes $$(i,j,t)$$ and $$(i,j,t+4)$$ are equivalent. In fact, $$(i,j,t)$$,$$(i,j,t+4)$$,$$(i,j,t+8)$$,..., are all equivalent! We can prove the following lemma: Nodes $$(i,j,t_1)$$ and $$(i,j,t_2)$$ are equivalent (i.e.: the maze looks exactly the same) if and only if $$t_1 \equiv t_2 \ (\mod 4)$$. So every node $$(i,j,t)$$ is "equivalent" to some other node with $$t$$ taken modulo 4. So we really only need to consider $$(i,j,0)$$, $$(i,j,1)$$, $$(i,j,2)$$, and $$(i,j,3)$$, for any pair $$(i,j)$$, since all the other times are equivalent to one of these! These define "equivalence classes" over the times. (And we can see, by inspection, that all the properties of our original graph still hold for this as well)
That's it! The total number of nodes in this graph is $$4 \times n \times m \leq 40,000$$. And each node has at most four neighbours. We can run the same BFS as described above, keeping track of which nodes we've visited (assuming we take $$t$$ mod 4 at all times), which cells are hit by lasers at certain times, and which cells are occupied. It takes a bit more work to implement it correctly, but that is the final solution! Accepted!
- If we know the time $$t$$ that has passed, we know the full state of the board. All the turrets move uniformly each time step. So we can easily compute the state of the maze if we know how many time steps have passed (and we obviously must know the original configuration of the board). This is important, because, simply by modifying our graph "state" to include time $$t$$, the problem becomes much easier.
- In the modified graph where nodes are $$(i,j,t)$$ tuples, running a breadth-first-search allows us to find a path from start to finish. This is assuming we avoid going through nodes $$(i,j,t)$$ that would be hit by turrets at that particular time. In any case, it is good to reduce this problem to a standard graph theory problem.
- Let $$(i,j,t_1)$$ and $$(i,j,t_2)$$ be two nodes where the player is on the same cell but at different times. Furthermore, suppose that $$t_1 \lt t_2$$ and that the entire board looks identical at times $$t_1$$ and $$t_2$$ (i.e.: all turrets face the same directions). If any shortest path from start to goal goes through $$(i,j,t_1)$$ then it will not go through $$(i,j,t_2)$$. You can prove this by contradiction or just see it intuitively. If we had a shortest path that goes through $$(i,j,t_1)$$ and $$(i,j,t_2)$$ then we consider the sequence of actions taken to get from $$(i,j,t_2)$$ to the finish. We could simply have taken these exact actions from $$(i,j,t_1)$$ to the finish since all of the same options must have been available at time $$t_1$$ (after-all, the board is identical). This would yield a shorter path from start to finish, and hence to a contradiction to the fact that this was a shortest path.
- We have an equivalence relation between nodes $$(i,j,t_1)$$ and $$(i,j,t_2)$$ that have identical looking boards. In fact, we can treat these as the same node. If there is a shortest path using one of these, then treating them as the same node will not change the shortest path in any way!
- The state of the board looks identical at time $$t$$ as it does at time $$t+4$$. As a consequence, it looks identical at times $$t+8, t+12, t+16, ..., t \pm 4k$$ for any integer $$k$$. The turrets rotate in 90 degree increments. So, every 4 steps, they will have rotated 360 degrees, which is the same as not rotating at all!
- Every node $$(i,j,t)$$ is therefore equivalent to the node $$(i,j,t%4)$$ where $$0 \leq (t%4) \lt 4$$ is the remainder of $$t$$ upon division by 4. This is a consequence of the above arguments.
- For any $$(i,j)$$ we can reduce our graph to only having $$(i,j,0)$$, $$(i,j,1)$$, $$(i,j,2)$$, $$(i,j,3)$$. This is implied by the previous observation. Now our graph is small enough.
- There exists a graph $$G$$ with $$v \leq 4\cdot n\cdot m$$ nodes and $$e \leq 4\cdot v$$ edges such that a path exists from start to finish in $$G$$ if and only if a path exists in the original maze from start to finish (without dying). This is precisely the graph of $$(i,j,t)$$ with $$0 \leq i \lt m$$ and $$0 \leq j \lt n$$ and $$0 \leq t \lt 4$$ that we have been describing. A breadth first search in this graph yields the final answer.
- An experienced programmer recognizes that "Mazes" and "paths" hints that the problem is a Graph Theory problem. It's also nice to recall classic problems that can be solved with Breadth-First-Search and some simple properties of Shortest Paths. With experience in these things, the key ideas needed to solve this problem can come almost instantly (i.e.: from "intuition"). A bit of knowledge with Number Theory or Congruences (modular arithmetic) might be handy here too!
- The spinning constraints are very complicated to deal with. Initially, it helps to "ignore" them as you try to think of ideas about the problem. For example, "How would this problem be solved without any turrets?" This is a good simplifying question because the answer is: "With Graph Theory, particularly Breadth-First-Search". And this is much easier to recognize because this simplified problem is a very common/classic Breadth-First-Search problem. So, if you don't have the "Experience" that we mention in the previous point, asking questions like this can help you to still come to the right "intuition". The next question you could ask is: "How could we solve this problem if there were turrets that did not rotate?" This is slightly harder, but it is still a nice intuition. This helps you to quickly figure out how to find "dead" cells and other techniques that might be useful later. By the time you come to the "full" problem, you will have much stronger ideas about the correct answer, and you will have solved some sub-problems that you would probably have had to solve anyway!
- Looking at some examples might help to understand this complex problem.
- We needed to notice that time was important. This was possible by considering what is the smallest amount of information we would need in order to be able to determine the state of the board. This is an example of "working backwards", where you ask reverse questions. The "forward" way of thinking would be more natural: "I know the state of the board. What do I do next?" Both ways of thinking reveal different properties of the problem. Altogether this would lead to the graph theory idea, and the fact that the state $$(i,j,t)$$ is necessary.
- The final observation was noticing that only $$t (\mod \ 4)$$ was necessary. But how do you come to that realization? That is hard (especially when you don't know what you're looking for). Writing out examples would help spark the insight. Also, recognizing that the graph is too big, and that it needs to be simplified, is a good "hint" that you need to reduce the state-space (i.e.: find a nice bound on $$t$$). This might also lead you to the right idea.
- Be careful and write down all of your observations. There are quite a few different constraints and ideas that need to be remembered.
- Shortest Path on modified graph. Often-times, adding constraints to graph problems simply requires modifying your graph. "Abstract" graphs are still graphs, but they require thinking out of the box. In this case, our graph wasn't the "maze" itself, but a combination of the "maze" and the current time. Overall, our nodes need to contain enough information to help us decide what steps are possible. In this case, "enough information" means: we need to know the time (modulo 4)
- Graph Theory / Breadth-First-Search / BFS on a Modified Graph
- Shortest Paths
- Grids and Mazes