How to find all possible words using adjacent letters in a matrix

Question

I have the following test matrix:

  ali
 gtm
 jea

I intend to create an algorithm that will help me find all possible words from a given minimum length to maximum length using only adjacent letters.

For instance:

Minimum: 3 letters

Maximum: 6 letters

Based on the test matrix, I should have the following results:

• ali
• alm
• Alg
• alto
• ati
• atm
• ATG
• ...
• atmea

and etc.

I created test code (C #) that has its own class that represents letters.

Each letter knows its neighbors and has a generation counter (to track them during the traversal).

Here is his code:

public class Letter { public int X { get; set; } public int Y { get; set; } public char Character { get; set; } public List<Letter> Neighbors { get; set; } public Letter PreviousLetter { get; set; } public int Generation { get; set; } public Letter(char character) { Neighbors = new List<Letter>(); Character = character; } public void SetGeneration(int generation) { foreach (var item in Neighbors) { item.Generation = generation; } } } 

I realized that if I want it to be dynamic, it should be based on recursion.

Unfortunately, the following code creates the first 4 words and then stops. It is not surprising that recursion stops at the indicated level of generations.

The main problem is that recursion returns only one level, but it is better to return to the starting point.

  private static void GenerateWords(Letter input, int maxLength, StringBuilder sb) { if (input.Generation >= maxLength) { if (sb.Length == maxLength) { allWords.Add(sb.ToString()); sb.Remove(sb.Length - 1, 1); } return; } sb.Append(input.Character); if (input.Neighbors.Count > 0) { foreach (var child in input.Neighbors) { if (input.PreviousLetter == child) continue; child.PreviousLetter = input; child.Generation = input.Generation + 1; GenerateWords(child, maxLength, sb); } } } 

So, I feel a little stuck, any idea how I should act?

Answer 1

From here, you can see this as a graph traversal problem. You start with each letter, each path of length min_size to max_size , with 3 and 6 as these values ​​in your example. I suggest a recursive procedure that builds words as paths through a grid. It will look something like this: replace the types and pseudo-code with your preferences.

 <array_of_string> build_word(size, current_node) { if (size == 1) return current_node.letter as an array_of_string; result = <empty array_of_string> for each next_node in current_node.neighbours { solution_list = build_word(size-1, next_node); for each word in solution_list { // add current_node.letter to front of that word. // add this new word to the result array } } return the result array_of_string } 

Will this lead you to a decision?

Answer 2

When solving such problems, I tend to use immutable classes, because everything is much easier to reason about. The next implementation uses ad hoc ImmutableStack , because it is quite simple to implement. In production code, I would probably want to look into System.Collections.Immutable for better performance ( visited would be ImmutableHashSet<> to indicate an obvious case).

So why do I need an immutable stack? To track the current character path and visit "locations" inside the matrix. Since the selected tool for the task is immutable, sending it in recursive calls is not a problem, we know that this cannot change, so I do not need to worry about my invariants at each level of recursion.

So, it allows you to implement an immutable stack.

We also implement the Coordinates helper class, which encapsulates our "locations" inside the matrix, gives us the semantics of equality of values ​​and a convenient way to get real neighbors of any given location. This will certainly come in handy.

 public class ImmutableStack<T>: IEnumerable<T> { private readonly T head; private readonly ImmutableStack<T> tail; public static readonly ImmutableStack<T> Empty = new ImmutableStack<T>(default(T), null); public int Count => this == Empty ? 0 : tail.Count + 1; private ImmutableStack(T head, ImmutableStack<T> tail) { this.head = head; this.tail = tail; } public T Peek() { if (this == Empty) throw new InvalidOperationException("Can not peek an empty stack."); return head; } public ImmutableStack<T> Pop() { if (this == Empty) throw new InvalidOperationException("Can not pop an empty stack."); return tail; } public ImmutableStack<T> Push(T value) => new ImmutableStack<T>(value, this); public IEnumerator<T> GetEnumerator() { var current = this; while (current != Empty) { yield return current.head; current = current.tail; } } IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); } struct Coordinates: IEquatable<Coordinates> { public int Row { get; } public int Column { get; } public Coordinates(int row, int column) { Row = row; Column = column; } public bool Equals(Coordinates other) => Column == other.Column && Row == other.Row; public override bool Equals(object obj) { if (obj is Coordinates) { return Equals((Coordinates)obj); } return false; } public override int GetHashCode() => unchecked(27947 ^ Row ^ Column); public IEnumerable<Coordinates> GetNeighbors(int rows, int columns) { var increasedRow = Row + 1; var decreasedRow = Row - 1; var increasedColumn = Column + 1; var decreasedColumn = Column - 1; var canIncreaseRow = increasedRow < rows; var canIncreaseColumn = increasedColumn < columns; var canDecreaseRow = decreasedRow > -1; var canDecreaseColumn = decreasedColumn > -1; if (canDecreaseRow) { if (canDecreaseColumn) { yield return new Coordinates(decreasedRow, decreasedColumn); } yield return new Coordinates(decreasedRow, Column); if (canIncreaseColumn) { yield return new Coordinates(decreasedRow, increasedColumn); } } if (canIncreaseRow) { if (canDecreaseColumn) { yield return new Coordinates(increasedRow, decreasedColumn); } yield return new Coordinates(increasedRow, Column); if (canIncreaseColumn) { yield return new Coordinates(increasedRow, increasedColumn); } } if (canDecreaseColumn) { yield return new Coordinates(Row, decreasedColumn); } if (canIncreaseColumn) { yield return new Coordinates(Row, increasedColumn); } } } 

Well, now we need a method that traverses the matrix, visiting each position after returning words that have a given minimum number of characters and do not exceed a specified maximum.

 public static IEnumerable<string> GetWords(char[,] matrix, Coordinates startingPoint, int minimumLength, int maximumLength) 

It looks right. Now that we are recursing, we need to track which characters we visited. It is easy to use our immutable stack, so our recursive method will look like this:

 static IEnumerable<string> getWords(char[,] matrix, ImmutableStack<char> path, ImmutableStack<Coordinates> visited, Coordinates coordinates, int minimumLength, int maximumLength) 

Now the rest is just laying and connecting the wires:

 public static IEnumerable<string> GetWords(char[,] matrix, Coordinates startingPoint, int minimumLength, int maximumLength) => getWords(matrix, ImmutableStack<char>.Empty, ImmutableStack<Coordinates>.Empty, startingPoint, minimumLength, maximumLength); static IEnumerable<string> getWords(char[,] matrix, ImmutableStack<char> path, ImmutableStack<Coordinates> visited, Coordinates coordinates, int minimumLength, int maximumLength) { var newPath = path.Push(matrix[coordinates.Row, coordinates.Column]); var newVisited = visited.Push(coordinates); if (newPath.Count > maximumLength) { yield break; } else if (newPath.Count >= minimumLength) { yield return new string(newPath.Reverse().ToArray()); } foreach (Coordinates neighbor in coordinates.GetNeighbors(matrix.GetLength(0), matrix.GetLength(1))) { if (!visited.Contains(neighbor)) { foreach (var word in getWords(matrix, newPath, newVisited, neighbor, minimumLength, maximumLength)) { yield return word; } } } } 

And you're done. Is this the most elegant or fastest algorithm? Probably not, but I think this is the most understandable and, therefore, supported. Hope this helps you.

UPDATE Based on the comments below, I ran several test cases, one of which:

 var matrix = new[,] { {'a', 'l'}, {'g', 't'} }; var words = GetWords(matrix, new Coordinates(0,0), 2, 4); Console.WriteLine(string.Join(Environment.NewLine, words.Select((w,i) => $"{i:00}: {w}"))); 

And the result is expected:

 00: ag 01: agl 02: aglt 03: agt 04: agtl 05: at 06: atl 07: atlg 08: atg 09: atgl 10: al 11: alg 12: algt 13: alt 14: altg