4
\$\begingroup\$

This is a continuation of my LINQ stories from Pangrams-Hackerrank. Similarly, this challenge has been asked before in python Pangrams python Implementation but I have tried to accomplish this challenge using LINQ.

Here is a summary of the question

Roy wanted to increase his typing speed for programming contests. So, his friend advised him to type the sentence "The quick brown fox jumps over the lazy dog" repeatedly, because it is a pangram. (Pangrams are sentences constructed by using every letter of the alphabet at least once.)

After typing the sentence several times, Roy became bored with it. So he started to look for other pangrams.

Given a sentence , tell Roy if it is a pangram or not.

Input Format

Input consists of a string .

Constraints

Length of can be at most 103(1≤|s|≤103) and it may contain spaces, lower case and upper case letters. Lower-case and upper-case instances of a letter are considered the same.

Output Format

Output a line containing pangram if is a pangram, otherwise output not pangram.

Sample Input

Input #1

We promptly judged antique ivory buckles for the next prize    

Input #2

We promptly judged antique ivory buckles for the prize 

Sample Output

Output #1

pangram

Output #2

not pangram

Explanation

In the first test case, the answer is pangram because the sentence contains all the letters of the English alphabet.

Here is my implementation

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.IO;
class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */

            string pangramInput = Console.ReadLine();
            var alphabet = Enumerable.Range(97, 26).Select((x) => (char)x);
            var pangramCheck = pangramInput.Replace(" ", "").ToLower().OrderBy((letter) => letter).Distinct().SequenceEqual(alphabet);
            string answer = pangramCheck ? "pangram" : "not pangram";
            Console.WriteLine(answer);
    }
}

Thoughts

I know this is a simple exercise and can be achieved without LINQ but the main idea is to know how to use LINQ functions.

  • Is the use of LINQ right? are there other simpler alternatives?
\$\endgroup\$
4
\$\begingroup\$

First a review...

Long extension chains

With lengthy linq chains it's a good idea to break them into multiple lines. Especially here on CR so that we don't have to scroll horizontally.

String interpolation

string answer = pangramCheck ? "pangram" : "not pangram";

We could optimize it as:

var answer = $"{(pangramCheck ? string.Empty : "not ")}pangram";

or you can make it even prettier by encapsulating this logic in an extension:

public static string Negate(this string value, bool negate)
{
    return $"{(negate ? string.Empty : "not ")}{value}";
}

so you then have:

Console.WriteLine("pangram".Negate(isPangram));

Consistency

string text
string answer

Don't you like var for strings because you already use for the other two variables? ;-)

Magic numbers

Enumerable.Range(97, 26)

This would be easier to understand if you used constants:

const string alphabetLength = z - a + 1;
Enumerable.Range('a', alphabetLength)

Not LINQ

.Replace(" ", "").ToLower()

This two kill the linq idea of your question. Consider this instead:

text
    .Select(char.ToLower)
    .Where(char.IsLetter)

Alternative solution

Then an alternative version...

If using a HashSet<char> is still linq-ish enougth then I replaced the Distinct with the Aggregate that uses one and makes it na O(n) solution for the English aphabet:

const int alphabetLength = 'z' - 'a' + 1;
var isPangram =
    text
    .Select(char.ToLower)
    .Where(char.IsLetter)
    .Aggregate(new HashSet<char>(), (acc, next) => { acc.Add(next); return acc; })
    .Count == alphabetLength;

UPDATE

Well, I forgot that we don't have to scan the entire string. As soon as we have the required chars we can stop. So this improved version should be faster for long texts:

const int alphabetLength = 'z' - 'a' + 1;
var chars = new HashSet<char>();

var testedChars = text
    .Select(char.ToLower)
    .Where(char.IsLetter)
    .TakeWhile(x => { chars.Add(x); return chars.Count != alphabetLength; })
    .Count();

var isPangram = chars.Count == alphabetLength;
\$\endgroup\$
  • \$\begingroup\$ i think the string interpolation suggestion is Fancy Code Syndrome, the original is clear and efficient. I like the rest \$\endgroup\$ – pm100 Nov 1 '16 at 16:32
  • \$\begingroup\$ This solution implies that a string which contains a non-Roman letter and all 26 Roman letters is not a pangram. Or one which contains 26 non-Roman letters is a pangram. \$\endgroup\$ – Eric Lippert Nov 1 '16 at 18:48
  • \$\begingroup\$ @EricLippert well, I guess we all know that there probably won't be any non-roman letter because Roy learns the English alphabet and has an English keyboard, when we apply the YAGNI priciple, we don't have to care about the rest of the world and what alphabets they use, do we? ;-) \$\endgroup\$ – t3chb0t Nov 1 '16 at 19:08
1
\$\begingroup\$

I've been inspired by Tolani and Heman. I used char[]. Bellow is my code snippet.

    char[] pangramInput = "We promptly judged antique ivory buckles for the next prize"
                          .ToLowerInvariant().ToCharArray();
    var alphabet = Enumerable.Range(97, 26).Select((x) => (char)x);
    var pangramCheck = alphabet.All(v => pangramInput.Contains(v));

Elapsed time measured with 32kB 'Lorem ipsum' text:

  • Tolani 12 ms
  • Heman 11 ms
  • t3chb0t 7 ms (TakeWhile version ~8 ms)
  • Tomas 2 ms
\$\endgroup\$
  • \$\begingroup\$ It should be faster now. I forgot we don't have to scan the entire string. \$\endgroup\$ – t3chb0t Nov 3 '16 at 9:59
  • \$\begingroup\$ Oh no, this is even slower now ;-] Could you post the test code? I'd like to run it too. \$\endgroup\$ – t3chb0t Nov 3 '16 at 13:12
  • \$\begingroup\$ @t3chb0t, I've sent you test code on gmail. \$\endgroup\$ – Tomáš Paul Nov 5 '16 at 22:41
0
\$\begingroup\$

Just playing Devil's advocate because I didn't like the O(n lg n) time for this...

string pangramInput = Console.ReadLine().ToLower();
var alphabet = Enumerable.Range(97, 26).Select((x) => (char)x);
var pc = pangramInput.Select((c, i) => new{val = c, idx = i})
                     .GroupBy(x => x.val, x=>x.idx)
                     .ToDictionary(k => k.Key, v => v);
var pangramCheck = alphabet.All(v => pc.ContainsKey(v));
string answer = pangramCheck ? "pangram" : "not pangram";
Console.WriteLine(answer);

From a performance standpoint, this might be much better. Not only is it O(n), but I think this uses laziness a little more and allows for non-alphabets.

Looking at just the Linq, I suppose both of these work as well. Yours might be a little more readable.

\$\endgroup\$
  • \$\begingroup\$ Your method won't work for the given string. It's case sensitive. You need to specify a custom comparer for the dictionary. I wonder also why do you need the index? This doesn't look like O(n). First GroupBy is already (n) then ToDictionary which is +26 in the worst case scenario, then All which is another +26. \$\endgroup\$ – t3chb0t Nov 1 '16 at 6:42
  • \$\begingroup\$ That is O(n) since the number of distinct characters is at most n, so even if it is actually 2n + 26 at very worst, it's O(n). \$\endgroup\$ – Heman Gandhi Nov 1 '16 at 15:23

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.