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.

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).