-4
\$\begingroup\$

John has discovered various rocks. Each rock is composed of various elements, and each element is represented by a lowercase Latin letter from 'a' to 'z'. An element can be present multiple times in a rock. An element is called a 'gem-element' if it occurs at least once in each of the rocks.

Given the list of rocks with their compositions, you have to print how many different kinds of gems-elements he has.

Input Format

The first line consists of N, the number of rocks. Each of the next N lines contain rocks’ composition. Each composition consists of small alphabets of English language.

Output Format

Print the number of different kinds of gem-elements he has.

Constraints

\$1 ≤ N ≤ 100\$

Each composition consists of only small Latin letters ('a'-'z'). 1 ≤ Length of each composition ≤ 100

Sample Input

3
abcdde
baccd
eeabg 

Sample Output

2 

Explanation

Only "a", "b" are the two kind of gem-elements, since these characters occur in each of the rocks’ composition.

I tried to solve this HackerRank problem in C#, however my code is not passed ALL tests. I've tested many times my code and it seems to me it should work. Please, guys, do you see any mistakes?

static void Main(string[] args)
{
    Console.WriteLine("Input quantity of rocks:");
    int quantityRocks;
    int.TryParse(Console.ReadLine().ToLower(), out quantityRocks);
    //  Getting inputted rocks
    if (quantityRocks > 0 && quantityRocks <= 100)
    {
        List<string> rocks = new List<string>();
        HashSet<char> uniqueLetters = new HashSet<char>();
        foreach (var word in rocks){
           foreach (var c in word)
                uniqueLetters.Add(c);
        }

        //  Putting rocks in a list of rocks
        for (int count = 0; count < quantityRocks; count++){
           Console.WriteLine("Input a rock:");
           string currentRock = Console.ReadLine();
           rocks.Add(currentRock);
           //  Getting unique letters
           foreach (var c in currentRock) {
               uniqueLetters.Add(c);
           }
        }
        //Logic to find out repeated rocks                
        int quantityOfRepeating = FindGemElements(uniqueLetters, rocks);                

        if (quantityOfRepeating != 0) {
            Console.WriteLine(quantityOfRepeating);
        }
        else {
            Console.WriteLine("There is no  repeated letters in all words");
        }
    }
}

and function which finds gem stones:

public static int FindGemElements(HashSet<char> uniqueLetters, List<string> rocks)
{
    int quantityRocks = rocks.Count;
    int quantityOfRepeating = 0;
    foreach (var letter in uniqueLetters)
    {
        quantityRocks = rocks.Count;
        foreach (var word in rocks)
        {
           if (word.IndexOf(letter) != -1)
           {
              //no actions as we find gem element
           }
           else
           {
              quantityRocks--;//decrement cause there is no gem element
           }
        }
        //if quantityRocks leaves the same, 
        //it means we've found gem element and increment it
            if (quantityRocks == rocks.Count)
            {
                quantityOfRepeating++;
            }
        }
        return quantityOfRepeating;
}

Any advice, remarks are welcome and will be highly appreciated.

Update:

The reason was that that I should remove everywhere Console.WriteLine(), except where result should be outputted(Console.WriteLine(quantityOfRepeating);).

\$\endgroup\$

closed as off-topic by t3chb0t, forsvarir, Vogel612, ferada, Marc-Andre Feb 26 '17 at 15:08

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – t3chb0t, forsvarir, Vogel612, ferada, Marc-Andre
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ my code has not passed ALL tests so it is broken and thus off-topic here. The only tests that may not pass are the time-out tests because this would be about performance optimization and not fixing bugs. \$\endgroup\$ – t3chb0t Feb 26 '17 at 8:33
  • 1
    \$\begingroup\$ How many tests are failing out of how many total? Do you know cause of the failures, for example, wrong answer or time limit exceeded? \$\endgroup\$ – Stop ongoing harm to Monica Feb 26 '17 at 11:19
  • \$\begingroup\$ @t3chb0t Are there performance tests at hackerrank.com? \$\endgroup\$ – StepUp Feb 26 '17 at 13:56
  • 2
    \$\begingroup\$ code works doesn't mean it compiles and runs, it means that it does what it is supposed to do and it doesn't because it doesn't pass hackerrank tests. \$\endgroup\$ – t3chb0t Feb 26 '17 at 19:29
  • 1
    \$\begingroup\$ @t3chb0t It looks like it works to me. It might just be failing out really badly on time test because it is horribly inefficient. Do you have evidence the code is not working? \$\endgroup\$ – paparazzo Feb 27 '17 at 0:27
1
\$\begingroup\$

This is the most useful hint in the problem:

Each composition consists of only small Latin letters ('a'-'z')

Since you are doing a challenge, if I did it for you, you will not learn much from it. But here is a BIG hint I will give you:

There are 26 characters (a-z). So make all of them gems. Now I will give you the first word: bob

Guess what? That first word I gave you, made all the letters, except for b and o, NOT gem. No more hints.

Now about your code:


You have this condition and if it is true, then all your code is inside it:

if (quantityRocks > 0 && quantityRocks <= 100)
{
    // code 
}

I would do this instead so the whole code block is not indented and it also shows there is nothing to do:

bool withinRange = quantityRocks > 0 && quantityRocks <= 100;
if (!withinRange)
{
    return; // or do whatever you want
}

// It is within range so the rest of your code can go here

In the following code you create a list and a hashset and then you traverse it: but what you are traversing through if you just created it?

List<string> rocks = new List<string>();
HashSet<char> uniqueLetters = new HashSet<char>();
foreach (var word in rocks)
{
    foreach (var c in word)
        uniqueLetters.Add(c);
}

In the following code you are traversing the words to search and see if they all have a letter. As soon as one does not have a letter, you know your answer that the letter is not a gem so why waste time and keep searching? Also you are not doing nothing in your if block so why do you have it?

foreach (var word in rocks)
{
    if (word.IndexOf(letter) != -1)
    {
        //no actions as we find gem element
    }
    else
    {
        quantityRocks--;//decrement cause there is no gem element
    }
}

Furthermore, try and write optimistic conditions if possible, your code will be easier to read. Like this:

foreach (var word in rocks)
{
    if (word.IndexOf(letter) == -1)
    {
        quantityRocks--;//decrement cause there is no gem element
    }
    // no else needed
}

MOST IMPORTANT POINT

What you are doing is a sequential search. I am sure this challenge is looking for an optimal search method. Therefore, you should try and use a better searching technique. See here for the different searching techniques.

Try creating a flowchart using good old fashioned approach with a pencil and paper. Think about your approach, see when you can stop searching, see what other ways you can optimize the search. Once you have a clear picture of what you want to do, put the flowchart in front of you and then convert the flow chart into code. If your code does not provide the correct result, do a walkthrough of your code to see where the issue could be. Then fix your flowchart, and change your code. Repeat until everything works.

When you are writing the code, try and concentrate on the algorithm of finding the gem letter given a set of words. Therefore, instead of using the console to enter the words, hardcode them into your code so you do not have to keep entering them. Your algorithm should not care about where the words are coming from.

var words = new List<string> { "One", "Two", "Other" /*, ... and so on */};

Create a list like above but make it a good set of words so you can test different scenarios. Then just keep testing that list.

Remember that writing code is the easiest part. The hard part is having a good solution (approach).

\$\endgroup\$
  • \$\begingroup\$ Thanks for so deep and wide answer!:) I will scrutinize your response. Thank a lot! \$\endgroup\$ – StepUp Feb 26 '17 at 12:32
  • \$\begingroup\$ You are welcome. I am glad I could help. Remember to pay very very close attention to the hint I gave you because that will make your algorithm incredibly faster. \$\endgroup\$ – CodingYoshi Feb 26 '17 at 15:49
0
\$\begingroup\$

Mixing building up uniqueLetters in with the input Main is not clean. Do that in your method that just does the calculation.

If a letter is not found on the first rock you are still searching all. Give up as soon as you don't find a letter.

    foreach (var word in rocks)
    {
       if (word.IndexOf(letter) != -1)
       {
          //no actions as we find gem element
       }
       else
       {
          quantityRocks--;//decrement cause there is no gem element 
          //you can break out here
       }
    }

You are getting everything and then eliminating. Your approach is very slow.

Start small and then eliminate - start with the first rock.

public static HashSet<char> GetGems(List<string> rocks)
{
    HashSet<char> gems = new HashSet<char>();
    List<char> gemsRemove = new List<char>();
    bool first = true;
    foreach(string rock in rocks.OrderBy(r => r.Length))
    {
        if(first)
        {
            first = false;
            foreach (char c in rock)
                gems.Add(c);
        }
        else
        {
            gemsRemove.Clear();
            foreach(char c in gems)      //working with the smallest possible set
                if (!rock.Contains(c))   //this is expensive but doing it as few a time as possible
                    gemsRemove.Add(c);
            foreach (char c in gemsRemove)
                gems.Remove(c);
            if (gems.Count == 0)
                return gems;
        }
    }
    Debug.WriteLine(string.Join(" ", gems));
    return gems;
}
\$\endgroup\$

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