Buggy Robot

This problem puts a Robot on a 50x50 grid with a string of instructions, and asks how many modifications we have to make to the instructions to get from our start point to the goal. We present two ways to look at the same solution.

DP Formulation

It sounds like an edit distance problem....and it is! It just turns out instead of comparing one string to another, we're comparing one string to our position on the grid.

Normal edit distance says for a given pair of pointers into the strings

1. they match, simulate by incrementing both pointers (only allowable if the characters do actually match...)
2. They don't match
   1. "edit" one string, simulate by incrementing both pointers
   2. "add" to one string, simulated by incrementing the other strings pointer
   3. "remove" from one string, simulated by incrementing our own pointer

We DP over all possible pointer positions and get a solution

This problem is similar

1. The instruction is on the path, so increment the instruction pointer and move position on the grid
2. "remove" one from the string, simulated by incrementing our IP while not changing positions on the grid
3. "add" one to the string, for which we have 4 possibilities, and we change our position on the grid without updating our IP

dp[IP, pos]= min(dp(IP+1,pos+1), 1+dp(IP+1,pos), 1+dp(IP, move))

We'll notice the problem here. In the original string formulation of the problem, it's guaranteed that one of the pointers increments, meaning we are moving monotonically towards one corner of the DP table. In this case, the "move" step at the end has the potential to be cyclical. Since dynamic programming depends on a well-known ordering of sub-problems, we need to be slightly cleverer. The answer is the same as most other cases when we want to compute the shortest path to a given node when there might be cycles: dijkstra!

Dijkstra State Explosion Formulation

It's a classic distance minimization, where the distance is the current edit distance in the string, and the state space is our position on the grid and index into the instruction string. The edges of our graph are the same as described above, but with 0 distance for the first one, and 1 each for the second two. Simply run dijkstra from the start point until any time we reach the goal (regardless of position in the string.