Optimizing a recursive path finding algorithm

Question

On input i get width and height of matrix, string of text and another string of finalText I want to reach. The characters of the first string are assigned to matrix. My goal is to find shortest way to create finalText from characters in matrix, starting at position (0,0), and return number of steps.

So I create a dictionary of all coordinates and characters from finalText.

Dictionary<Tuple<int, int>, char> coords = new Dictionary<Tuple<int, int>, char>();
for (int i = 0; i < height; i++)
{
 for (int j = 0; j < width; j++){
 if (finalText.Contains(matrix[j, i]))
 coords.Add(new Tuple<int, int>(j, i), matrix[j, i]);
 }
}

And then use it in my function. I basically calculate steps in all possible paths and then return the shortest one.

static int ShortestPath(char[,] matrix, string str, int x, int y, int steps, Dictionary<Tuple<int,int>,char> coords)
 {
 if (str.Length == 0)
 {
 return steps;
 }
 else
 {
 List<int> l = new List<int>();
 foreach (var item in coords)
 {
 if (item.Value == str[0])
 l.Add(ShortestPath(matrix, str.Substring(1), item.Key.Item1, item.Key.Item2,
 steps + (Math.Abs(x - item.Key.Item1) + Math.Abs(y - item.Key.Item2)), coords));
 }
 
 int min = l[0];
 for (int i = 1; i < l.Count; i++)
 {
 if (l[i] < min)
 min = l[i];
 }
 return min;
 }
 }

The algorithm is working, but for bigger matrices it's too slow and I have no idea how to optimize it or do it otherwise.

• coderodde: Can you provide the entire project? Something like a GitHub repository or similar.
• greybeard: In the code presented, I can't discern width and height of matrix, string of text and another string of finalText from the introduction.
• RobH: Can you try to expand the problem statement a bit more? I'm struggling to understand what you're trying to do. I think you'll want to use Dijkstra's algorithm for the best performance
• Enrique Castaneda: I think you would have a lot more useful answers if you take the time to explain what you want to achieve. I don´t know if I understand correctly, but you have a matrix with a bunch of letters and you want to know how many operations does it takes to end with a desired string. However it is not clear whether you should always start at the same point (0,0), or a diagonal step costs the same as a vertical or horizontal one. As a minor review, consider renaming your vars to reflect what they do. I also think your problem is in the recursive step
• Levyi: @EnriqueCastaneda Oh, i forgot, i can move only vertically or horizontally. Also, starting at (0,0) means that #steps to achieve first character in string is calculated by |0-x| + |0-y|. (as i pass zeros to the function)

Answer 1

I am not a C# programmer, so I don't quite understand your algorithm. However, there is couple of things I could tell you:

Advice 1: Unnecessary else

You have:

{
 if (str.Length == 0)
 {
 return steps;
 }
 else
 {
 List<int> l = new List<int>();
 ...
 }
}

You could write simply:

{
 if (str.Length == 0)
 {
 return steps;
 }
 List<int> l = new List<int>();
 ...
}

Advice 2: Use min or similar

Instead of

int min = l[0];
for (int i = 1; i < l.Count; i++)
{
 if (l[i] < min)
 min = l[i];
}

you could write

int min = l[0];
for (int i = 1; i < l.Count; i++) 
{
 min = Math.Min(min, l[i]);
}

(See this.)

Hope that helps.

Answer 2

I miss comments.

I don't see matrix used in ShortestPath().

Just returning the minimum, don't build the List<int> l in the first place.

---

Having a look at shortest path algorithms in general and Dijkstra's in particular is solid advice.

Things I might consider:

• create Counters for both finalText and the entire matrix (say, available)
• If there is any character occurring in finalText but missing from available (assuming characters/cells/elements may be used more than once - occurring more frequently otherwise), there's no solution
• the problem splits into problems that can be handled independently at any string consisting of characters occurring just once: solitaires
• remove all prefixes and suffixes of solitaires
• using sum norm / taxicab distance, for any start and target, intermediate points increase distance only when introducing the need to "turn back" (lying outside the rectangle defined by start and target in case of just one intermediate).

• coderodde: Nice point about no list.
• greybeard: It may be a good idea generally to process characters required by finalText by increasing frequency in the matrix.