27
\$\begingroup\$

Description

Software like Swype and SwiftKey lets smartphone users enter text by dragging their finger over the on-screen keyboard, rather than tapping on each letter.

Example image of Swype

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

Notes/Hints

Assumptions about the input strings:

  • QWERTY keyboard
  • Lowercase a-z only, no whitespace or punctuation
  • The first and last characters of the input string will always match the first and last characters of the desired output word
  • Don't assume users take the most efficient path between letters
  • Every letter of the output word will appear in the input string

Problem 284

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;

namespace swipe
{
    class Program
    {
        static string path = "C:\\Users\\px06\\Documents\\Visual Studio 2015\\Projects\\swipe\\swipe\\words.txt";
        static void Main(string[] args)
        {
            string[] input = { "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews" };

            string[] words = File.ReadAllLines(path);

            var watch = System.Diagnostics.Stopwatch.StartNew();

            foreach (string inp in input)
            {
                var acceptable = reduce(words, inp);
                foreach (int i in acceptable)
                {
                    if (check(words[i], inp))
                    {
                        Debug.WriteLine(words[i]);
                    }
                }
            }
            watch.Stop();
            Console.WriteLine("Run time(ms): " + watch.ElapsedMilliseconds);
            Console.ReadLine();
        }

        static List<int> reduce(string[] list, string input)
        {
            List<int> acceptableList = new List<int>();
            int count = 0;
            foreach(string word in list)
            {
                if (word.Length >= 5 && input[0] == word[0] && input[input.Length - 1] == word[word.Length - 1])
                {
                    acceptableList.Add(count);
                }
                count++;
            }
            return acceptableList;
        }

        static bool check(string word, string input)
        {
            int charcheck = 0;

            foreach (char c in word)
            {
                charcheck = input.IndexOf(c, charcheck);
                if (charcheck == -1)
                {
                    return false;
                }
            }
            return true;
        }
    }
}

qwertyuytresdftyuioknn -> queen, question -> runtime: 2ms

gijakjthoijerjidsdfnokg
gaeing
garring
gathering
gating
geeing
gieing
going
goring
Run time(ms): 2

Trying a very complex string to see if I could find the word:

chlordiazepoxides

Input:

cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews

Output:

caches
cades
cafes
caffs
cages
caids
cairds
capes
caphs
capos
capotes
capouches
capuches
cards
cares
caress
carices
caries
carious
caroches
carps
carpus
carries
carroches
carrots
carrs
carryouts
cartes
cartouches
carts
carves
casefies
caseous
cases
casettes
cashes
cashews
cassettes
cassis
castes
castoffs
castors
casts
casus
catches
cates
catguts
catties
caucus
caves
cavies
cedes
cepes
cercis
cercus
ceres
ceriphs
cerites
ceros
cerous
certes
certifies
cetes
chads
chafes
chaffs
chairs
chaos
chapes
chaps
chards
chares
charges
chariots
charpoys
charros
charrs
chars
charts
chasers
chases
chassepots
chasses
chasseurs
chassis
chats
chaws
chayotes
chays
cheeps
cheerios
cheeros
cheers
chefs
cheroots
cherries
cherts
chess
cheths
chevies
chevres
chews
chias
chiaus
chichis
chics
chiders
chides
chiefs
chiggers
chigoes
chippies
chips
chiros
chirps
chirres
chirrs
chirrups
chits
chitters
chitties
chives
chivies
chivvies
chlorates
chlordiazepoxides
chlorides
chlorids
chlorites
chlorous
choices
choirs
choosers
chooses
chops
choragus
chordates
chords
choregus
chores
chorioids
chorizos
choroids
chorus
choruses
chorusses
choses
chotts
choughs
chousers
chouses
choushes
chows
christies
chrysophytes
chuddahs
chuddars
chudders
chufas
chuffs
chuggers
chugs
churches
churrs
chutes
chutists
ciders
cigars
circuits
circus
cires
cirrous
cirrus
cissies
cissoids
cists
cistus
citators
citers
cites
cities
citifies
citrates
citreous
citrous
citrus
citruses
civies
civvies
clachs
clades
clads
clags
claps
claries
clarifies
claroes
claros
clashes
clasps
class
classers
classes
classics
classifies
classis
clastics
clasts
claughts
claves
clavus
claws
clays
clefs
clefts
clepes
clergies
clerics
clerids
clerihews
clevis
clews
cliches
cliffs
clifts
clips
clitics
cloches
clods
cloggers
clogs
cloistress
cloots
clops
closeouts
closers
closes
closets
closures
clothes
cloths
clots
clotures
clouds
cloughs
clours
clouters
clouts
cloves
cloys
clozes
clues
clutches
clutters
coaches
coacts
coapts
coasts
coatees
coatis
coats
coaxes
coccids
coccus
codas
codders
codecs
coderives
coders
codes
codfishes
codgers
codices
codifies
codirects
codrives
coeds
coerces
coffeepots
coffees
coffers
coffrets
coffs
cogitates
cogitos
coiffes
coiffeurs
coiffures
coifs
coirs
coitus
coituses
cooches
cooees
cooers
cooeys
coofs
coops
coopts
cooters
cooties
coots
copes
copies
copihues
coppices
cordages
corders
cordgrass
cordgrasses
cordierites
cordites
cords
corduroys
corers
cores
corgis
corps
corpus
corrades
corrects
corridas
corridors
corries
corrodes
corrupts
corsacs
corsages
corsairs
corses
corsets
corteges
cortexes
cortices
corvees
corves
coryphees
cosecs
coses
cosets
coseys
coshes
cosies
cossets
costs
coteries
cotes
cotrustees
cottages
cottars
cottas
cotters
cottiers
cotypes
couches
cougars
coughs
coupes
coups
courages
courgettes
couriers
coursers
courses
courteous
courters
courtiers
courts
courtsides
courtyards
couters
couths
coutures
coves
coxes
coydogs
coyotes
coypous
coypus
cozes
cozeys
cozies
cozzes
crafts
crags
crapes
crappies
craps
crases
crashes
crasis
crass
cratches
crates
craves
craws
crazes
crazies
creches
creeds
creepies
creeps
crepes
cress
cretics
crews
criers
cries
cripes
crises
crisis
crisps
critics
critters
critturs
crocs
crocus
crofts
croppies
crops
crores
cross
crouches
crows
cruces
crudes
crudites
cruds
cruets
cruisers
cruises
cruors
crusades
cruses
crusets
crushes
crusts
crutches
cruxes
crypts
cuddies
cuffs
cuifs
cuirass
cuirasses
cuishes
cuisses
cupids
curacies
curaghs
curares
curaris
curassows
curates
curatives
curators
curches
curds
curers
cures
curets
curettes
curfews
curfs
curies
curios
curious
curites
currachs
curraghs
currieries
curriers
curries
currs
cursers
curses
cursives
cursors
curtseys
curtsies
curves
cuscus
cusecs
cuspides
cuspids
cuspis
cusps
cussers
cusses
cussos
custodes
custos
cutches
cutes
cuteys
cutgrass
cutgrasses
cuties
cutis
cutises
cutoffs
cutouts
cuttages
cutters
cutties
cutups
cyders
cypres
cypress
cystoids
cysts
Run time(ms): 5

I just wanted to see what I can improve on my code. I'm very new to C# so I'd like some suggestions on what I can do to either improve efficiency or improve it in general. For the most part it looks like it works well, but could I improve this any further? Is there anything else I could add to make it even faster?

Would anyone know the efficiency of this program? I have a feeling it's \$O(\log n)\$ but obviously that shouldn't be the case by looking at the structure.

I tried feeding in 1,000,000 randomly generated characters and here is the output:

zaikai
zamindari
zastrugi
zecchini
zingani
zingari
zombi
zucchini
Run time(ms): 2

I know that the runtime is significantly decreased by cutting down the dictionary by the first index of the word word[0] == dict[word[0]] and then the last element word[last] == dict[word[last]], so what factors here would determine speed? The only ones I can think of are: size of dictionary and location of the first char (i.e. starting with a z). Even the input size doesn't determine the runtime, so the complexity isn't increasing even though I am trying to find a match in check().

That being said, Visual Studio is using up to 27 MB of RAM while computing the 1M long string... but who really cares about space-complexity?

\$\endgroup\$
  • 5
    \$\begingroup\$ It's a very good question that includes both the working code and examples - just the way it should be ;-) \$\endgroup\$ – t3chb0t Sep 29 '16 at 8:34
  • 1
    \$\begingroup\$ I guess you could simplify the code by using a regular expression which has all the middle characters as optional ones cg?h?h?j?k?k?l?l?o?o?i?u?y?t?...?s and match that pattern with the word list. I doubt that this has any better performance than what you are doing now, so I just leave it as a comment here. \$\endgroup\$ – I'll add comments tomorrow Sep 29 '16 at 11:26
  • 3
    \$\begingroup\$ @I'lladdcommentstomorrow I mainly avoided regex because I don't really understand how to use more complex aspects of it like groups and conditions. But I also avoided it because I feel that it over-complicates code and doesn't really provide much of a benefit over using normal classes and interfaces that are provided in languages. I think the regex method may be a lot slower simply due to the iterations, unless I can combine it withthe last step of just searching the words. I'll try giving it a go and see what the speeds look like! ~ I'll add comments tomorrow \$\endgroup\$ – px06 Sep 29 '16 at 11:37
  • \$\begingroup\$ @I'lladdcommentstomorrow That will turn ugly very fast. \$\endgroup\$ – Mast Sep 29 '16 at 11:39
  • \$\begingroup\$ @px06 your feelings are correct. You stated that you are new to C#, my comment was more FYI: there's regex and it could solve the problem but you probably don't even want to try it if you are looking for performance. \$\endgroup\$ – I'll add comments tomorrow Sep 29 '16 at 11:47
11
\$\begingroup\$

I'll review your code as written first then move onto the other questions.

It's the convention in C# to name all methods in PascalCase reduce should be Reduce.

You're already using System.Diagnostics so you don't need to qualify the Stopwatch.StartNew() call.

input is a collection so should be pluralised (like you've done for words). It should be inputs.

foreach (string inp in input). Don't abbreviate your variable names, it just makes code harder to read with no benefit (in C# at least).

foreach(var input in inputs)
{

I've also used var here to demonstrate its usage. It can be used when the type of the assignment is obvious or when the exact type isn't important. I tend to use it everywhere if I'm honest.

This code is confusing:

var acceptable = reduce(words, inp);
foreach (int i in acceptable)
{

Without reading the implementation of reduce I have no idea what this code is about. Consider with more descriptive names:

foreach(var wordIndex in GetCandidateWordIndicies(words, input))
{

Now we're communicating what our code is doing without having to look at the implementation. Long and descriptive names are always preferable to short and ambiguous ones.

This would be better served by a for loop:

int count = 0;
foreach(string word in list)
{
    // stuff
    count++;
}

Like this:

for (var i = 0; i < list.Count; i++)
{
    var word = list[i];
    if (word.Length >= 5 && input[0] == word[0] && input[input.Length - 1] == word[word.Length - 1])
    {
        acceptableList.Add(i);
    }
}

I'd also refactor the if to use First() and Last() (which are optimised implementations when the collection implements ICollection`):

if (word.Length >= 5 
    && input.First() == word.First() 
    && input.Last() == word.Last())

That's a bit easier to skim.

In your check method charcheck should have been called currentPosition. I was initially confused by what you were doing and actually thought there may have been a bug with the ordering of the input letters.


Complexity

Your solution clearly depends on both size of the input dictionary (n) and the length of the input (m).

You loop over all words in the dictionary so your solution can't be any better than O(n).

Also you call input.IndexOf(c, charcheck);. I'm not 100% sure what the complexity of string.IndexOf is in C# but it's going to be related to the length of the string in some way - the naive implementation would be O(n*m) (m == 1 as you're searching 1 char at a time) worst case. Update: speculation confirmed by https://stackoverflow.com/a/2584204/1402923

That means your algorithm is definitely tied to both the size of the dictionary and the length of the input.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the response! I see that C# conventions are quite different to Java which is what I'm used to, I will more read into them to make my code adapt a consistent format with the .NET standard. Regarding GetCandidateWordIndicies that you pointed out. If I am doing something like foreach(var x in Get(something)), will the Get() method be called for every iteration or is it a one-time thing? Also, is there any benfit of using forover foreach like you've explained? I first thought that the complexity would be O(n*m), but was a little bit thrown off by other factors. \$\endgroup\$ – px06 Sep 29 '16 at 13:16
  • \$\begingroup\$ @px06 - I haven't given it a huge amount of thought but I'd agree that the worst case would be O(n*m). To answer your question about the foreach, the method will only be called once. If you need the index I think it's much better to use a for rather than foreach and track the index as well but it's personal preference afaik. \$\endgroup\$ – RobH Sep 29 '16 at 13:18
7
\$\begingroup\$

Just a little tip, no full review.

You can escape the tedious escaping of the escape character in a string literal by putting an @ in front of it:

string path = "C:\\Users\\px06\\...";

becomes

string path = @"C:\Users\px06\...";

The rest of both lines were omitted for brevity.

\$\endgroup\$
  • 8
    \$\begingroup\$ Just FYI this is called a Verbatim string literal. See string documentation on msdn \$\endgroup\$ – RobH Sep 29 '16 at 11:31
  • \$\begingroup\$ Do you not also need to close a verbatim string literal? \$\endgroup\$ – MTCoster Sep 29 '16 at 15:21
  • \$\begingroup\$ @MTCoster I never heard about our seen anything like that. How would that look like? Do you mean there should also be an @ after the closing " ? \$\endgroup\$ – I'll add comments tomorrow Sep 29 '16 at 16:17
  • \$\begingroup\$ @I'lladdcommentstomorrow My mistake, I assumed that that was the entire line missing a close ", not just the first part \$\endgroup\$ – MTCoster Sep 29 '16 at 16:19
  • 1
    \$\begingroup\$ @MTCoster answer clarified. \$\endgroup\$ – I'll add comments tomorrow Sep 29 '16 at 16:24
5
\$\begingroup\$
  1. Always specify access modifiers,

  2. Follow the .Net naming guidelines, methods and namespaces are PascalCase

  3. RobH beat me to the rest of the usual cosmetic stuff.

When it comes to performance there may be a lot to gain from constructing a map from [FirstCharacter, LastCharacter] -> CandidateWord. Constructing such a mapping is not free but if you parse multiple inputs it will be worth it.

You can construct the map using Linq:

var words = File.ReadAllLines(path);
var wordLookup = words.Where(word => word.Length >= 5)
                      .GroupBy(word => word[0])
                      .ToDictionary(group => group.Key, group => group.ToLookup(w => w[w.Length - 1]));

Dictionary and Lookup are hash-based maps that provide constant time lookup (terms and conditions may apply).

And then you can find candidates by using a helper:

private static IEnumerable<string> GetCandidateWords(string input, Dictionary<char, ILookup<char, string>> candidateLookup)
{
    var firstChar = input[0];
    var lastChar = input[input.Length - 1];
    var maxLength = input.Length;
    return candidateLookup[firstChar][lastChar].Where(w => w.Length <= maxLength);
}

And then you filter out the valid words:

public static IEnumerable<string> GetValidWords(this string input, Dictionary<char, ILookup<char, string>> candidateLookup)
{
    var candidateWords = GetCandidateWords(input, candidateLookup);
    return candidateWords.Where(candidate => ValidateCandidateWord(input, candidate));
}

And your check now renamed to be more explicit about it's function:

private static bool ValidateCandidateWord(string input, string word)
{
    int searchFrom = 0;
    foreach(var c in word)
    {
        var currentIndex = input.IndexOf(c, searchFrom);
        if(currentIndex == -1)
        {
            return false;
        }
        searchFrom = currentIndex + 1;
    }

    return true;
}

I changed it to search from the next character on, this means queen is no longer a valid option from qwertyuytresdftyuioknn as there is only a single e after the first u. I can't tell which way is correct from the spec so this is based on opinion.

If you put all the methods in a static class you end up with an extension method on string:

public static class StringSwipeExtentions
{
    private static IEnumerable<string> GetCandidateWords(string input, Dictionary<char, ILookup<char, string>> candidateLookup)
    {
        var firstChar = input[0];
        var lastChar = input[input.Length - 1];
        var maxLength = input.Length;
        return candidateLookup[firstChar][lastChar].Where(w => w.Length <= maxLength);
    }

    public static IEnumerable<string> GetValidWords(this string input, Dictionary<char, ILookup<char, string>> candidateLookup)
    {
        var candidateWords = GetCandidateWords(input, candidateLookup);
        return candidateWords.Where(candidate => ValidateCandidateWord(input, candidate));
    }

    private static bool ValidateCandidateWord(string input, string word)
    {
        int searchFrom = 0;
        foreach(var c in word)
        {
            var currentIndex = input.IndexOf(c, searchFrom);
            if(currentIndex == -1)
            {
                return false;
            }
            searchFrom = currentIndex + 1;
        }

        return true;
    }
}

And you using it:

public static void Main()
{
    var inputs = new[]
    { 
        "qwertyuytresdftyuioknn",
        "gijakjthoijerjidsdfnokg",
        "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews"
    };

    var words = File.ReadAllLines(path);
    var wordLookup = words.Where(word => word.Length >= 5)
                          .GroupBy(word => word[0])
                          .ToDictionary(group => group.Key, group => group.ToLookup(w => w[w.Length - 1]));

    foreach(var input in inputs)
    {
        var stopwatch = System.Diagnostics.Stopwatch.StartNew();
        var validWords = input.GetValidWords(wordLookup);
        stopwatch.Stop();
        Console.WriteLine("{0} done in {1}ms, valid words:", input, stopwatch.ElapsedMilliseconds);
        foreach(var validWord in validWords)
        {
            Console.WriteLine(validWord);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Still reading through your answer, but it's worth mentioning that in the input string qwertyuytresdftyuioknn, queen is acceptable because on a practical Swype keyboard, you would hover your finger over the letter you want, and keep it there if you wish to repeat the character, i.e. allow doubles. loop, hoop, queen etc. Why are we making use of Dictionary exactly? I'm a little bit confused on the usage of your GetCandidateWords() method, mind explaining it a little bit? \$\endgroup\$ – px06 Sep 29 '16 at 13:58
  • \$\begingroup\$ That's nearly what I'd do except I'd use a Dictionary<string, IEnumerable<string> where the key is first and last char concatenated to make it a bit simpler. \$\endgroup\$ – RobH Sep 29 '16 at 14:05
  • \$\begingroup\$ you can use w.First() & w.Last() instead of w[0] or w[w.Length - 1] and the 5 if it would be a const int minWordLength then it would be a perfect answer - anyway +1 for the dictionary+lookup approach ;-) \$\endgroup\$ – t3chb0t Sep 29 '16 at 14:05
  • 1
    \$\begingroup\$ @RobH with the composite key you'd have to use TryGetValue as it's not guaranteed that every combo will have a value. Lookup returns an empty sequence for a missing key. Maybe there's a language where not every character is used at the start of a word and then it should be TryGetValue anyway. \$\endgroup\$ – Johnbot Sep 29 '16 at 14:12
  • \$\begingroup\$ I added a note about why I chose a map based approach. Dictionary has constant time lookup which can potentially save you a factor n if you reuse it for multiple inputs. \$\endgroup\$ – Johnbot Sep 29 '16 at 14:19
2
\$\begingroup\$

Since your programm should only find words with 5 or more characters, you could filter out words that have less characters. This will reduce the amount of loaded words.

For this purporse you can use File.ReadLines with a Linq-statement.

int minimumWordLength = 5;

HashSet<string> words = new HashSet<string>();
foreach (string line in File.ReadLines(path).Where(p=>p.Length >= minimumWordLength))
{
    words.Add(line);
}

Using ReadLines and Linq the amount of words can be reduced even more, since you are only interested in words that

The first and last characters of the input string will always match the first and last characters of the desired output word

string input = "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews";
int minimumWordLength = 5;
string firstChar = input[0].ToString();
string lastChar = input[input.Lenght-1].ToString();

foreach (string line in File.ReadLines(path)
                            .Where(p=>p.Length >= minimumWordLength)
                            .Where(p=>p.StartsWith(firstChar) && p.EndsWith(lastChar)))
{
    words.Add(line);
}

This changes would make your reduce method obsolete and you can directly check the words with your method check.

\$\endgroup\$
1
\$\begingroup\$

You algorithm is - in my opinion - good, but you could check the candidates in one operation in a Filter function as shown below.

I have modified your solution with some comments below:

  // Changed to static because it implements an extension to IEnumerable<string>
  static class Program
  {
    // use @ to get rid of the \\ as another commentor explained
    static string path = @"C:\Users\px06\Documents\Visual Studio 2015\Projects\swipe\swipe\words.txt";

    static void Main(string[] args)
    {
      string[] input = { "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews" };

      string[] words = File.ReadAllLines(path);

      var watch = System.Diagnostics.Stopwatch.StartNew();

      foreach (string inp in input)
      {
        foreach (var validWord in words.Filter(inp))
        {
          Console.WriteLine(validWord);
        }
      }

      watch.Stop();
      Console.WriteLine("Run time(ms): " + watch.ElapsedMilliseconds);
      Console.ReadLine();
    }

    // This is combining reduce() and check() in one iteration
    static IEnumerable<string> Filter(this IEnumerable<string> words, string input)
    {
      foreach (string word in words)
      {
        // calling check() at the same time
        if (word.Length >= 5 && input[0] == word[0] && input[input.Length - 1] == word[word.Length - 1] && check(word, input))
        {
          yield return word;
        }
      }
    }

    static bool check(string word, string input)
    {
      int charcheck = 0;

      foreach (char c in word)
      {
        charcheck = input.IndexOf(c, charcheck);
        if (charcheck == -1)
        {
          return false;
        }
      }
      return true;
    }
  }

You could even skip the Filter function and gain the same with a Where() like:

  // Changed to static because it implements an extension to IEnumerable<string>
  static class Program
  {
    // use @ to get rid of the \\ as another commentor explained
    static string path = @"C:\Users\px06\Documents\Visual Studio 2015\Projects\swipe\swipe\words.txt";

    static void Main(string[] args)
    {
      string[] input = { "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews" };

      string[] words = File.ReadAllLines(path);

      var watch = System.Diagnostics.Stopwatch.StartNew();

      foreach (string inp in input)
      {
        foreach (var validWord in words.Where(word => word.Length >= 5 && inp[0] == word[0] && inp[inp.Length - 1] == word[word.Length - 1] && check(word, inp)))
        {
          Console.WriteLine(validWord);
        }
      }

      watch.Stop();
      Console.WriteLine("Run time(ms): " + watch.ElapsedMilliseconds);
      Console.ReadLine();
    }

    static bool check(string word, string input)
    {
      int charcheck = 0;

      foreach (char c in word)
      {
        charcheck = input.IndexOf(c, charcheck);
        if (charcheck == -1)
        {
          return false;
        }
      }
      return true;
    }
  }

If you store the words in a dictionary you can gain a couple of ms in performance and your n in O(n*m) would be reduced a bit. Dictionary is close to O(1):

  // Changed to static because it implements an extension to IEnumerable<string>
  static class Program
  {
    // use @ to get rid of the \\ as another commentor explained
    static string path = @"C:\\Users\\px06\\Documents\\Visual Studio 2015\\Projects\\swipe\\swipe\\words.txt";

    static void Main(string[] args)
    {
      string[] input = { "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews", "ardidtrwekfsisuklms" };
      var words = File.ReadAllLines(path).GroupBy(str => str[0]).ToDictionary(gr => gr.Key);

      var watch = System.Diagnostics.Stopwatch.StartNew();

      foreach (string inp in input)
      {
        foreach (var validWord in words[inp[0]].Where(word => word.Length >= 5 && inp[0] == word[0] && inp[inp.Length - 1] == word[word.Length - 1] && check(word, inp)))
        {
          Console.WriteLine(validWord);
        }

        Console.WriteLine();
      }

      watch.Stop();
      Console.WriteLine("Run time(ms): " + watch.ElapsedMilliseconds);
      Console.ReadLine();
    }

    static bool check(string word, string input)
    {
      int charcheck = 0;

      foreach (char c in word)
      {
        charcheck = input.IndexOf(c, charcheck);
        if (charcheck == -1)
        {
          return false;
        }
      }
      return true;
    }
  }
\$\endgroup\$
  • \$\begingroup\$ I see what you're saying here and as I'm new to the C#.NET language and framework as a whole I don't exactly know how yeild works but I'm guessing it's just the state-machine concept that can store a pointer to the last location being looked at. However, it seems like we would need to itereate through the IEnumerable every single time for the loop? Am I right in saying that this is creating a predicate and then stepping through it further? It almost seems like this is running in some quadratic fashion. \$\endgroup\$ – px06 Sep 29 '16 at 11:17
  • \$\begingroup\$ I ran the program with the input given in the question and the runtime increases significantly to about 250+ ms, which seems a little bit counterintuitive when trying to achieve efficiency in not only calculating but matching and finding the words. \$\endgroup\$ – px06 Sep 29 '16 at 11:18
  • 2
    \$\begingroup\$ Can you not access norvig.com/ngrams/enable1.txt ? That is the dictionary file I'm using, and what is required to be used for the challenge itself. \$\endgroup\$ – px06 Sep 29 '16 at 11:40
  • 1
    \$\begingroup\$ I've uploaded it to gist so you can retrieve it from here: gist.githubusercontent.com/redrails/… \$\endgroup\$ – px06 Sep 29 '16 at 12:12
  • 1
    \$\begingroup\$ Thanks. When I run your code in release mode on my computer it's duration ranges from 234 to 301. The same for my two versions. So how did come with 5ms as show above? Possible answer you are printing with Debug.WriteLine() instead of Console.WriteLine() which is deactivated in release mode? \$\endgroup\$ – Henrik Hansen Sep 29 '16 at 12:29
0
\$\begingroup\$

I started to refactor the original code, but using a class just made sense. A class for MajicWord makes it easier to expand. Getting the middle characters would be more difficult. Using GetHashCode() for the Dictionary Key makes sense.

This is about 40x as fast as your solution (runs in 5 ms)
Uses a Dictionary with a Key of first and last letter
So lookup to the candidates (matching first and last) is \$O(1)\$
On the candidates it iterates on middle (pretty minor)
Depends on a class called MajicWord for the heavy lifting

{
    static void Main(string[] args)
    {
        string wordToMatch = "cghhjkkllooiuytrrdfdftgyuiuytrfdsaazzseertyuioppoiuhgfcxxcfvghujiiuytrfddeews";
        Stopwatch sw = new Stopwatch();
        sw.Start();
        List<string> wordMatches = WordMatches(wordToMatch); /*quen*/
        sw.Stop();
        //foreach (string s in wordMatches)
        //    Console.WriteLine(s);
        Console.WriteLine(string.Join(", ", wordMatches));
        Console.WriteLine("milliseconds first pass is high as has to build dictionary");
        Console.WriteLine("milliseconds  me " + sw.ElapsedMilliseconds.ToString() + Environment.NewLine);
        Console.ReadLine();
    }
    private static Dictionary<Int32, List<MajicWord>> wordSet;
    public static List<string> WordMatches(string input)
    {
        if (wordSet == null)
        {
            wordSet = new Dictionary<Int32, List<MajicWord>>();
            try
            {   // Open the text file using a stream reader.
                string line;
                using (StreamReader sr = new StreamReader(@"words.txt"))
                {
                    while ((line = sr.ReadLine()) != null)
                    {
                        if (line.Length < 5)
                            continue;
                        //Debug.WriteLine(line);
                        MajicWord mw = new MajicWord(line);
                        if (!wordSet.ContainsKey(mw.GetHashCode()))
                            wordSet.Add(mw.GetHashCode(), new List<MajicWord>());
                        wordSet[mw.GetHashCode()].Add(mw);
                    }
                }
            }
            catch (Exception e)
            {
                Console.WriteLine("The file could not be read:");
                Console.WriteLine(e.Message);
            }
            //foreach (List<MajicWord> lmw in wordSet.Values)
            //    Debug.WriteLine(lmw.Count.ToString());
            Debug.WriteLine("end ctro");
        }
        Stopwatch sw = new Stopwatch();
        sw.Start();
        List<string> wordMatches = new List<string>();
        MajicWord wtm = new MajicWord(input);
        List<MajicWord> candidates = wordSet[wtm.GetHashCode()];
        IEnumerable<MajicWord> matches = candidates.Where(x => x.IsMatchOrder(wtm));
        foreach (MajicWord mw in matches.OrderBy(x => x.Word))
            wordMatches.Add(mw.Word);
        sw.Stop();
        Console.WriteLine("milliseconds WordMatches " + sw.ElapsedMilliseconds.ToString() + Environment.NewLine);
        return wordMatches;
    }
}

public class MajicWord
{
    public override bool Equals(Object obj)
    {
        if (!(obj is MajicWord)) return false;

        MajicWord mw = (MajicWord)obj;
        return (string.Compare(mw.Word, this.Word, true) == 0);
    }
    public override int GetHashCode()
    {
        return (int)CharFirst * 17 ^ (int)CharLast;
        //((int)CharFirst - 97)*26 + (int)CharLast - 97; this hashes better for a-z
    }
    public bool IsMatch(MajicWord mwm)
    {
        if (mwm.GetHashCode() != this.GetHashCode())
            return false;
        return (this.MiddleHash).IsSubsetOf(mwm.MiddleHash);
    }
    public bool IsMatchOrder(MajicWord mwm)
    {
        //if (!IsMatch(mwm))  // this slowed it down
        //    return false;

        if (mwm.GetHashCode() != this.GetHashCode())
            return false;

        if (this.Word.Length > mwm.Word.Length)
            return false;

        int charcheck = 0;
        foreach (char c in this.WordMiddle)
        {
            charcheck = mwm.WordMiddle.IndexOf(c, charcheck);
            if (charcheck == -1)
            {
                return false;
            }
        }
        return true;
    }
    public string Word { get; private set; }
    private string wordMiddle = null;
    public string WordMiddle
    {
        get
        {
            if(wordMiddle == null)
            {
                StringBuilder sb = new StringBuilder();
                for (int i = 1; i < Word.Length - 1; i++)
                    sb.Append(Word[i]);
                wordMiddle = sb.ToString();
            }
            return wordMiddle;
        }
    }
    public char CharFirst { get; private set; }
    public char CharLast { get; private set; }
    HashSet<char> middleHash = null;
    public HashSet<char> MiddleHash
    {   
        get
        {
            if(middleHash == null)
            {
                middleHash = new HashSet<char>();
                for (int i = 1; i < Word.Length - 1; i++)
                    middleHash.Add(Word[i]);
            }
            return middleHash;
        }
    }
    public MajicWord(string word)
    {
        if (word.Length < 2)
            throw new IndexOutOfRangeException();
        Word = word.ToLower();
        CharFirst = Word[0];
        CharLast = Word[Word.Length-1];
    }
}
\$\endgroup\$
  • \$\begingroup\$ @janos I did explain I felt a class for MajicWord makes it easier to expand. Getting the middle characters would be more difficult. Using GetHashCode() for the Dictionary Key makes sense. I started to refactor OP code but using a class just made sense. If you want to delete I am OK. It is smoking fast. \$\endgroup\$ – paparazzo Oct 9 '16 at 20:49
  • 2
    \$\begingroup\$ I cleaned it up a little, adding more explanation from your comment, and removing stuff that's not really useful for anyone. Feel free to further improve it. I also invite you to re-read our article on how-to-answer. \$\endgroup\$ – janos Oct 9 '16 at 21:11

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.