3
\$\begingroup\$

I thought this question was particularly interesting DailyProgrammer 284: Wandering Fingers so thought I'd have a pop at it myself. See the other question for the nitty gritty but the brief problem statement is:

You'll be given a string of characters representing the letters the user has dragged their finger over.

For example, if the user wants "rest", the string of input characters might be "resdft" or "resert".

Input

Given the following input strings, find all possible output words 5 characters or longer.

  1. qwertyuytresdftyuioknn
  2. gijakjthoijerjidsdfnokg

Output

Your program should find all possible words (5+ characters) that can be derived from the strings supplied.

Use http://norvig.com/ngrams/enable1.txt as your search dictionary.

The order of the output words doesn't matter.

  1. queen question
  2. gaeing garring gathering gating geeing gieing going goring

I've made the assumption that this is the English alphabet (i.e. [a-z]) which is pretty normal for a qwerty keyboard.

I created a simple lookup class:

public class AutocompleteCache
{
    private readonly IList<string>[] cache = new IList<string>[26*26]; 

    public AutocompleteCache(IEnumerable<string> wordList)
    {
        if (wordList == null)
        {
            throw new ArgumentNullException(nameof(wordList));
        }
        foreach (var word in wordList.Where(w => w.Length >= 5))
        {
            var index = CalculateIndex(word);
            var cachedWords = cache[index];
            if (cachedWords == null)
            {
                cache[index] = new List<string>();
            }
            cache[index].Add(word);
        }
    }

    private static int CalculateIndex(string word)
    {
        Debug.Assert(!string.IsNullOrEmpty(word));
        return (word[0] - 97)*26 + (word[word.Length - 1] - 97);
    }

    public IEnumerable<string> SuggestWords(string input)
    {
        if (string.IsNullOrEmpty(input))
        {
            return Enumerable.Empty<string>();
        }
        var candidates = (cache[CalculateIndex(input)] ?? Enumerable.Empty<string>());
        return candidates.Where(candidate => CheckWordIsValidForInput(candidate, input));
    }

    private bool CheckWordIsValidForInput(string word, string input)
    {
        int currentPosition = 0;
        foreach (var c in word)
        {
            currentPosition = input.IndexOf(c, currentPosition);
            if (currentPosition == -1)
            {
                return false;
            }
        }
        return true;
    }
}

The responsibility of this class is to take a dictionary of words and sort it into an array of lists of words. The index of the array is determined by a simple calculation of the first and last letters of the word (CalculateIndex). Which gives us an O(1) lookup for the list of candidate words. This is the same complexity as using a dictionary would have but has smaller constant terms than using the dictionary. The overall algorithm is O(n*m) with O(n) startup cost where n is the number of words and m is the length of the input string. The memory requirement is O(k^2) where k is the alphabet length (hard coded to 26 here).

I benchmarked this against the OP's solution and Jonbot's dictionary and found that for input 1 over 10000 iterations it's approximately twice as fast as Jobbot's and about 200 times faster than OPs solution. For words with a larger list of candidates, i.e. more common first and last letters, it ends up being only very slightly faster ~5% that the dictionary approach but still an order of magnitude faster than the OP.

Usage of the code:

 var words = File.ReadAllLines(@"C:\some\path\to\dictionary.txt");
 var autoCompleteCache = new AutocompleteCache(words);
 var results = autoCompleteCache.SuggestWords("quen"); 
 Console.WriteLine(string.Join(", ", results)); // queen

Looking for any and all comments.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Clearly it has some problems \$\endgroup\$
    – paparazzo
    Oct 7 '16 at 23:55
  • 1
    \$\begingroup\$ @Paparazzi what a completely pointless comment. If the problems are so clear to you, please would you spell them out to me? The only major issue I can see is that it is very coupled to the alphabet which I've already made note of. \$\endgroup\$
    – RobH
    Oct 8 '16 at 10:41
  • \$\begingroup\$ Just wanted to reuse clearly as you used it in a comment to me. I felt the need for the word was pointless also. \$\endgroup\$
    – paparazzo
    Oct 8 '16 at 11:27
  • 1
    \$\begingroup\$ How come that's O(1) when you have loops + Where? \$\endgroup\$
    – Denis
    Oct 8 '16 at 11:57
  • \$\begingroup\$ @denis - I didn't say the algorithm was O(1) I said: Which gives us an O(1) lookup for the list of candidate words. I'll edit the question to make that clearer. \$\endgroup\$
    – RobH
    Oct 9 '16 at 19:20
1
\$\begingroup\$

To me it looks fine. Just some minor adjustments:

I think it would look even nicer if you defined constants for the magic numbers.

 const int AlphabetLength = 26;
 const int MinWordLength = 5;

In place of 97 I'd put simply an 'a'.


Instead of

currentPosition == -1

I suggest

currentPosition < 0

The -1 looks like a magic number. I sometimes use a constant for it that I name IndexOutOfRange.


You use var everywhere but here :-)

int currentPosition = 0;

It might also be a good idea to move the code from the constructor into a new method like AddWords or AddWord so you can extend the dictionary later if necessary. Usually those dictionaries can learn new words.

\$\endgroup\$
1
  • \$\begingroup\$ All very helpful comments thanks! I'm not sure how that int snuck in there ;) \$\endgroup\$
    – RobH
    Oct 10 '16 at 7:34
0
\$\begingroup\$

Below please find some comments and suggestions inline:

  public class AutocompleteCache
  {
    private readonly string[][] cache; // Why not a jagged array as it is a one time creation?
    private readonly int alphabetSize;

    // sizeOfAlphabet makes it usefull for other languages than english
    public AutocompleteCache(IEnumerable<string> wordList, int sizeOfAlphabet = 26)
    {
      if (wordList == null)
      {
        throw new ArgumentNullException(nameof(wordList));
      }

      alphabetSize = sizeOfAlphabet;

      //cache = new List<string>[alphabetSize * alphabetSize];
      cache = new string[alphabetSize * alphabetSize][];

      //foreach (var word in wordList.Where(w => w.Length >= 5))
      //{
      //  var index = CalculateKey(word);
      //  var cachedWords = cache[index];
      //  if (cachedWords == null)
      //  {
      //    cache[index] = new List<string>();
      //  }
      //  cache[index].Add(word);
      //}

      // You could use linq here:
      var groups = wordList.GroupBy(w => CalculateKey(w));
      foreach (var group in groups)
      {
        cache[group.Key] = group.ToArray();
      }
    }

    // Just for test
    public void PrintCache()
    {
      var min = cache.Where(arr => arr != null).Min(arr => arr.Length);
      var max = cache.Where(arr => arr != null).Max(arr => arr.Length);
      var avg = cache.Where(arr => arr != null).Average(arr => arr.Length);

      Console.WriteLine($"Min: {min} -> Max: {max} -> Average: {avg}");
    }

    // Why static if private?
    private /* static */ int CalculateKey(string word)
    {
      return (word[0] - 97) * alphabetSize + (word[word.Length - 1] - 97);
    }

    public IEnumerable<string> SuggestWords(string input)
    {
      if (string.IsNullOrEmpty(input))
        return Enumerable.Empty<string>();

      var key = CalculateKey(input);

      // You should check for valid key...
      if (key < 0 || key >= cache.Length)
        return Enumerable.Empty<string>();

      // ... because an invalid key will cause an exception here
      //var candidates = (cache[CalculateKey(input)] ?? Enumerable.Empty<string>());
      //return candidates.Where(candidate => IsCandidateValid(candidate, input));

      // You know the key is in range here.
      return cache[key]?.Where(candidate => IsCandidateValid(candidate, input)) ?? Enumerable.Empty<string>();
    }

    private bool IsCandidateValid(string candidate, string input)
    {
      int currentPosition = 0;
      foreach (var c in candidate)
      {
        currentPosition = input.IndexOf(c, currentPosition);
        if (currentPosition == -1)
        {
          return false;
        }
      }
      return true;
    }
  }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.