CODEWITHSUNDEEP
c#algorithmlinqfind
Nizhgo
Nizhgo

Reputation: 13

Find in the List of words with letters in certain positions

I'm doing a crossword puzzle maker. The user selects cells for words, and the program compiles a crossword puzzle from the dictionary (all words which can be used in the crossword) - List<string>.

I need to find a word (words) in a dictionary which matches given mask (pattern).

For example, I need to find all words which match

#a###g

pattern, i.e. all words of length 6 in the dictionary with "a" at index 1 and "g" at index 5

The number of letters and their position are unknown in advance

How do I realize this?

Upvotes: 0

Views: 450

Answers (2)

Caius Jard
Caius Jard

Reputation: 74605

I need to find a word in a list with "a" at index 1 and "g" at index 5, like the following

wordList.Where(word => word.Length == 6 && word[1] == 'a' && word[5] == 'g')

The length check first will be critical to preventing a crash, unless your words are arranged into different lists by length..

If you mean that you literally will pass "#a###g" as the parameter that conveys the search term:

var term = "#a###g";
var search = term.Select((c,i) => (Chr:c,Idx:i)).Where(t => t.Chr != '#').ToArray();
var words = wordList.Where(word => word.Length == term.Length && search.All(t => word[t.Idx] == t.Chr));

How it works:

  • Take "#a###g" and project it to a sequence of the index of the char and the char itself, so ('#', 0),('a', 1),('#', 2),('#', 3),('#', 4),('g', 5)
  • Discard the '#', leaving only ('a', 1),('g', 5)
  • This means "'a' at position 1 and 'g' at 5"
  • Search the wordlist demanding that the word length is same as "#a###g", and also that All the search terms match when we "get the char out of the word at Idx and check it matches the Chr in the search term

Upvotes: 0

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186678

You can convert word description (mask)

 #a###g

into corresponding regular expression pattern:

 ^\p{L}a\p{L}{3}g$

Pattern explained:

 ^        - anchor, word beginning
 \p{L}    - arbitrary letter
 a        - letter 'a'
 \p{L}{3} - exactly 3 arbitrary letters
 g        - letter 'g'
 $        - anchor, word ending

and then get all words from dictionary which match this pattern:

Code:

using System.Linq;
using System.Text.RegularExpressions;

...

private static string[] Variants(string mask, IEnumerable<string> availableWords) {
  Regex regex = new Regex("^" + Regex.Replace(mask, "#*", m => @$"\p{{L}}{{{m.Length}}}") + "$");

  return availableWords
    .Where(word => regex.IsMatch(availableWords))
    .OrderBy(word => word)
    .ToArray();
}

Demo:

string[] allWords = new [] {
  "quick",
  "brown",
  "fox",
  "jump",
  "rating",
  "coding"
  "lazy",
  "paring",
  "fang",
  "dog", 
};

string[] variants = Variants("#a###g", allWords);

Console.Write(string.Join(Environment.NewLine, variants));

Outcome:

paring
rating

Upvotes: 1

Related Questions