5
\$\begingroup\$

I wanted to write something that would find all pyramid words within a supplied text file or list of strings. An example of a pyramid word is the word "deadheaded". It has one of the letter "h", two of "a", three of "e", and four of "d". This would form a pyramid if you were to stack the letters:

   h
  a a
 e e e
d d d d

I'm looking for input regarding various things, such as design (is this constructed well for a user and easy to understand?), extensibility, using the right data structures, dealing with input/output...

Would this be better designed with more OOP in it? For example, I could have a base class with sub classes finding words with different shapes than a pyramid. But I'm not sure how much it would help in this design, as it seems fairly script-like with all the string manipulation.

public class PyramidWordsFinder
{
    public PyramidWordsFinder()
    {
        this.pyramidWordList = new List<string>();
    }

    public IList<string> pyramidWordList { get; set; }

    public IReadOnlyList<string> LoadDictionaryFile(string filePath)
    {
        List<string> wordsDictionary = new List<string>();
        Encoding enc = Encoding.GetEncoding(1250);
        string[] lines = File.ReadAllLines(filePath, enc);
        wordsDictionary.AddRange(lines.Where(x => x.Length > 2));
        return wordsDictionary.AsReadOnly();
    }

    public void WriteWordListToFile(IEnumerable<string> words, string fullFileName)
    {
        if (String.IsNullOrWhiteSpace(fullFileName))
        {
            throw new ArgumentException("The file name is not correctly formed");
        }

        File.WriteAllLines(fullFileName, words);
    }

    public IList<string> FindPyramidWords(IReadOnlyList<string> wordList)
    {
        foreach (var word in wordList)
        {
            // Quick checks before seeing if pyramid word
            if (this.WordIsCorrectLength(word) && (word.ToLower().Distinct().Count() == this.GetMaximumLetterFrequency(word)))
                {
                if (this.DetermineIfWordIsPyramid(word))
                {
                    this.pyramidWordList.Add(word);
                }
            }
        }
        return this.pyramidWordList;
    }

    private int GetMaximumLetterFrequency(string word)
    {
        int total = 0;
        for (int i = 1; i <= word.Length; i++)
        {
            total += i;
            if (total == word.Length) return i;              
        }

        return 0;
    }

    private bool WordIsCorrectLength(string word)
    {
        var correctLengths = new List<int> {6, 10, 15, 21, 28, 36, 45, 55 };
        if (correctLengths.Any(item=> item == word.Length))
        {
            return true;
        }

        return false;
    }

    /// <summary>
    /// Determines if the given word is a pyramid word 
    /// </summary>
    /// <param name="word"></param>
    /// <returns></returns>
    public bool DetermineIfWordIsPyramid(string word)
    {
        var lowerCaseWord = word.ToLower();
        List<int> letterCounts = new List<int>();
        var distinctLetters = lowerCaseWord.ToLower().Distinct();

        // Adds up how many times each distinct letter is seen in the word
        foreach (var letter in distinctLetters)
        {
            var numLetters = lowerCaseWord.Count(x => x == letter);
            letterCounts.Add(numLetters);
        }

        // determines if the frequency the distinct letters descends consecutively
        var maximumLetterFrequency = this.GetMaximumLetterFrequency(lowerCaseWord);
        for (var i = maximumLetterFrequency; i >= 1; i--)
        {
            if (!letterCounts.Contains(i)) return false;
        }

        return true;
    }
}
\$\endgroup\$
  • \$\begingroup\$ You could combine correctLengths with WordIsCorrectLength in a dictionary \$\endgroup\$ – paparazzo Dec 14 '16 at 7:59
  • 1
    \$\begingroup\$ Why do you exclude 3 letter words? "too" seems like a perfectly good pyramid word to me. \$\endgroup\$ – RobH Dec 14 '16 at 16:19
  • \$\begingroup\$ @RobH Originally it was part of the code, but I questioned the use of it - I believe a user wouldn't want all that clutter, because the idea of this is generally to find unique and longer words (this was also my experience when loading a dictionary). I did overload some functions to specify minimum length but ended up removing it as I wanted to simplify my code \$\endgroup\$ – headacheDilemma Dec 14 '16 at 23:40
6
\$\begingroup\$

SRP

You should start by splitting this class into smaller pieces to satisfy the Single Responsibility Priciple. One class should do only one thing and yours is doing at least two:

  • it reads and writes files
  • it finds the pyramid words

This means you should:

  • Create one module for reading and writing words into a file
  • Let the second module only find pyramid words

The first module could be the DictionaryFile

class DictionaryFile 
{
    public IReadOnlyList<string> LoadDictionary(string filePath)
    {
        // ...
    }

    public void SaveDictionary(IEnumerable<string> words, string fileName)
    {
        // ...
    }
}

Keep the names clear but not too long if this is not necessary.


The second module is the PyramidWordFinder:

class PyramidWordFinder
{
    private readonly HashSet<int> _lengths = new HashSet<int>();

    public PyramidWordFinder(int maxLength)
    {
        var length = 3;
        var i = 1;
        while (length <= maxLength)
        {    
            _lengths.Add(length);
            length = ++i + length + 1;
        }
    }

    public bool IsPyramidWord(string value)
    {
        if (!_lengths.Contains(value.Length)) { return false; }

        var groups = value
            .GroupBy(x => x.ToString(), StringComparer.OrdinalIgnoreCase)
            .Select(x => x.Count())
            .OrderBy(x => x);
        return groups.SequenceEqual(Enumerable.Range(1, groups.Length));
    }       
}

HashSet

Instead of having a list with predefined lengths, you can calculate them based on the max length and save them in a HashSet<int> for faster lookup which is O(1) in comparison to the list where it's O(n).

LINQ

To determine whether a word is a pyramid you can use LINQ where you first group each letter and sort it in the ascending order. Then you check if the count is increasing by one:

var groups = value
    .GroupBy(x => x.ToString(), StringComparer.OrdinalIgnoreCase)
    .Select(x => x.Count())
    .OrderBy(x => x);        
return groups.SequenceEqual(Enumerable.Range(1, groups.Length));

StringComparer

With the StringComparer.OrdinalIgnoreCase you don't need to call ToLower or ToUpper.

IEnumerable

public IList<string> FindPyramidWords(IReadOnlyList<string> wordList)

Don't return a complete list of words if this isn't necessary. Use an iterator instead - by using LINQ or the yield return. What if you wanted just the first three words? You would need to calculate them all anyway. With deferred execution you can stop whereever you want to.

Example

You can now easily find all pyramid words with linq:

var pwf = new PyramidWordFinder(maxLength: 55); // or use constant
var words = new string[] { /* words */ }; // from the file
var pyramidWords = words.Where(pwf.IsPyramidWord).ToList();

I'm aware of the fact that the LINQ solution might not be the fastest one but it's definitely the esiest one. If you don't notice any performance hit then why make it so complex? Premature optimization is the root of all evil.

The point is that you should separate each feature so that you can work on it and test it without affecting the others. If you can focus on one thing at a time you can better optimize it.

\$\endgroup\$
  • \$\begingroup\$ I gave you a +1 but I think your constructor is wrong. For example, new PyramidWordFinder(16) adds 21 to the list of lenghts. Just FYI, triangular numbers are defined by xn = n*(n+1) / 2 which may make calculating them easier for you. \$\endgroup\$ – RobH Dec 15 '16 at 10:13
  • \$\begingroup\$ @RobH you're right. I now see where the bug is - it first adds the length to the HashSet and then checks it - this is of course to late. The formula looks nice. I had a gut feeling that there might be something like this but I'm not a good matematician ;-) \$\endgroup\$ – t3chb0t Dec 15 '16 at 10:29
  • \$\begingroup\$ I've fixed the loop. \$\endgroup\$ – t3chb0t Dec 15 '16 at 10:33
1
\$\begingroup\$

This is just a lot of overhead

public IReadOnlyList<string> LoadDictionaryFile(string filePath)
{
    List<string> wordsDictionary = new List<string>();
    Encoding enc = Encoding.GetEncoding(1250);
    string[] lines = File.ReadAllLines(filePath, enc);
    wordsDictionary.AddRange(lines.Where(x => x.Length > 2));
    return wordsDictionary.AsReadOnly();
}
  • Read each line into an array
  • Then filter into wordsDictionary based on a size but that size is smaller than the minimum
  • Then return the List
  • Then process the List

Why not just process the word ASAP for IsPyramidWord?
This is looking at processing efficiency more than form.

public IEnumerable<string> LoadPyramidWordFromFile(string filePath)
{   // to more generalize pass a method to perform the validation
    if (!File.Exists(filePath))
        throw new ArgumentException("The file name is not correctly formed");
    string word;
    Encoding enc = Encoding.GetEncoding(1250);
    using (StreamReader sr = new StreamReader(filePath, enc))
    {
        while (sr.Peek() >= 0)
        {
            word = sr.ReadLine().Trim();
            if(DetermineIfWordIsPyramid(word))
                yield return word;
        }
    }
}
private Dictionary<int, int> correctLengths = new Dictionary<int, int> 
        { { 6, 3 }, { 10, 4 }, { 15, 5 }, { 21, 6 }, { 28, 7 }, { 36, 8 }, { 45, 9 }, { 55, 10 } };
private bool DetermineIfWordIsPyramid(string word)
{
    if (string.IsNullOrEmpty(word))
        return false;

    if (correctLengths.Keys.Contains(word.Length))
    {
        var lowerCaseWord = word.ToLower();
        var maxLetterFrequency = correctLengths[lowerCaseWord.Length];                 
        var distinctLetters = lowerCaseWord.Distinct();
        if (distinctLetters.Count() != maxLetterFrequency) // cheap check
            return false;  
        HashSet<int> letterCounts = new HashSet<int>();  // lookup on HashSet is a little faster
        // Adds up how many times each distinct letter is seen in the word
        foreach (var letter in distinctLetters)
        {
            var numLetters = lowerCaseWord.Count(x => x == letter);
            letterCounts.Add(numLetters);
        }
        for (var i = maxLetterFrequency; i >= 1; i--)
        {
            if (!letterCounts.Contains(i)) return false;
        }
        return true;
    }
    else
        return false;          
}
private bool DetermineIfWordIsPyramidB(string word)
{   // I think this will be a little more efficient 
    // some people may not find it as readable 
    // using Dictionary eliminates several string operations
    if (string.IsNullOrEmpty(word))
        return false;

    if (correctLengths.Keys.Contains(word.Length))
    {
        var maxLetterFrequency = correctLengths[word.Length];
        Dictionary<char, int> charCount = new Dictionary<char, int>();
        foreach(char c in word.ToLower())
        {
            if (charCount.ContainsKey(c))
            {
                charCount[c]++;
                if (charCount[c] > maxLetterFrequency) // cheap early check
                    return false;
            }
            else
            {
                charCount.Add(c, 1);
                if (charCount.Count() > maxLetterFrequency) // cheap early check
                    return false;
            }
        }  
        if (charCount.Count() != maxLetterFrequency) // cheap check
                    return false;          
        for (var i = maxLetterFrequency; i >= 1; i--)
        {
            if (!charCount.Values.Contains(i))
                return false;
        }
        return true;
    }
    else
        return false;
}
\$\endgroup\$
  • \$\begingroup\$ DetermineIfWordIsPyramidB - this is an interesting naming convention ;-) \$\endgroup\$ – t3chb0t Dec 15 '16 at 13:01

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.