I am trying to find out a way to optimize my code which solves the following problem: There is a grid on which i have a target cell to reach. Along the road there are obstacles. I am given a set of instructions (F for forward, B for Back, L for turn left and R for turn right). I start at coordinate x = 0, y = 0 and my initial direction is to the right. I have to find that one instruction to change so that i can reach my target.
For example, let's say that my instructions are FFF and my target is located at (0, 2). If I change the first F into a L, then I can reach my target.
If we have N instructions and K obstacles, actually my code run in about O(N^2 * K). I am trying to find some optimization.
What I did so far is this: if I take the problem without the obstacles I could reach an O(N) time complexity by doing the following: Apply all the instructions as they are given. This brings me to some point on the grid which is my landing point. Then for each instruction, I test the 4 possibilities (actually 3 remaining) corresponding to F, B, L and R. F and B instructions induce a translation on my landing point. L and R instructions induce a rotation on that landing point. At each test I check if this makes me reach the goal's coordinate and if yes then i am done. So i just need to test the landing point and this gives me O(N) execution time
Now the problem is that if I take into consideration the obstacles, well I am stuck because I have no optimal way to check if an obstacle's coordinate intersects my path. This is because i have just computed the coordinates on my landing point and not the points on all the path. Of course I can compute each coordinate for each point for each coorect path but i end up in quadratic time.
My questions are the following:
I am looking for a hint so that i can try to solve it by myself.
You can reduce the number of paths to check with the following observations:
If a solution consists of replacing a "F" by a "B" or vice versa, then that means the original path's end point is two units away from the target point. Also, the replacement happens at a state where the direction is along the same axis (horizontal or vertical) as the axis on which both the endpoints lie. For example, if the path ends at (x, y) and the target is at (x + 2, y) then we can consider as solutions the paths where we replace a "F" in the right direction by a "B", or a "B" in the left direction by an "F". There might be several candidates in the path for such a replacement.
But here is the thing: if such a replacement at index i of the path leads to a valid solution, then all alternative replacements at greater indices will also be valid.
So we only need to try the rightmost candidate index (with a "B" or "F" in the expected direction)! If it gives a path that hits an obstacle, then all other alternatives will hit that obstacle too, so there is no need to try any alternative here.
If a solution consists of replacing a "R" by a "L" or vice versa, then this corresponds to a 180° turn from that point onwards. That means we must perform this mutation when the path is at a point that is halfway between the two endpoints (the current endpoint and the target). This is only possible if that middle point has integer coordinates (the difference between x coordinates should be even -- same for y). Like with the previous scenario, there might be several times that the path arrives at that point and makes a turn there ("L" or "R").
We only need to consider the last time when the path meets that half-way point and makes a turn! The reasoning is the same: if that last candidate makes the modified path hit an obstacle then this same obstacle will be hit if we had altered a "L" or "R" at a previous candidate index in the path!
If a solution consists of replacing a "R" or "L" by a "F" or "B" (or vice versa), then we change the number of moves on the path (either it increases or decreases by one), and the rest of the path is a quarter turn different from the original. By looking at the rectangle formed by the current end point and the target point, we know that the points of interest (to make the mutation) must be on (or next to) the two other corners of that rectangle: that is where the quarter rotation effect will take place. For it to be a solution, the rectangle should be one unit away from a square. The extra unit on either side of the rectangle represents the move that will be inserted ("F" or "B") or, if a "F" or "B" is removed (for "R" or "L") then this is explained by the missing unit in the shorter side of the rectangle.
So we need to find where the path meets those corner points (or the points one unit next to it), and see if we can apply that mutation there. Here there are different scenarios to consider: there are two corners to consider, and there is either the case where we insert a "F" or "B" (in place of "R" or "L", or where we remove it (to insert "R" or "L"). Thus we have 4 scenarios to look into. For each of these we only have to look at the last index in the path where the conditions are right for making the mutation.
These are all the cases to look into. They are limited to less than 10 cases, and for each we only need to identify the last index in the path that meets the conditions. And so we have less than 10 mutated paths to verify for obstacles, making this algorithm O(n).
I hope my messy explanation was clear enough to implement it.