Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Recently a question was asked that solved a hackerrank problem: Counting gems amongst the rocks

The description of the challenge is:

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 was in the process of writing an answer when the question was closed because the code in the question was failing to produce the right results.

My recommended solution to the problem is likely quite fast, but it is also relatively complicated. I am sure it can be improved, and simplified.

I have included a simple main method that shows how it can be used, and produces the sample output.

public class GemCounter {

    private static final int LETTERCOUNT = 26; 

    // Start with 1 bit set for each element/letter.
    private int gemsSoFar = (1 << LETTERCOUNT) - 1; 

    public GemCounter() {
        // default constructor. Does nothing.
    }

    public void processRock(final String rock) {
        int gotElement = 0; // no bits are set.
        for (int i = 0; i < rock.length(); i++) {
            int element = rock.charAt(i) - 'a';
            if (element >= 0 && element < LETTERCOUNT) {
                // bitwise OR the bit that represents the element
                gotElement |= 1 << element;
            }
        }
        // only bits that were found in this rock
        // and also that have been seen before
        // will remain set.
        gemsSoFar = gemsSoFar & gotElement;
    }

    public int getGemCount() {
        // count the number of bits that are still set.
        return Integer.bitCount(gemsSoFar);
    }

    public static void main(String[] args) {
        String[] rocks = {"abcdde", "baccd", "eeabg"};

        GemCounter gemcount = new GemCounter();
        for (String rock : rocks) {
            gemcount.processRock(rock);
            System.out.printf("Processed %s, got %d gems still%n", rock, gemcount.getGemCount());
        }

        System.out.printf("%d rocks have %d gems%n", rocks.length, gemcount.getGemCount());

    }

}
share|improve this question

3 Answers 3

up vote 11 down vote accepted

Not much to say.

Logical operators used a bit inconsistently:

    gotElement |= 1 << element;
    gemsSoFar = gemsSoFar & gotElement;

better use &= in the second line, or spell out the first.

gotElement is somewhat unclear. rockElements, maybe?

In real life I'd also oppose extensive comments.

share|improve this answer

You have added

public GemCounter() {
    // default constructor. Does nothing.
}

which is not needed for the program to work because,

The compiler automatically provides a no-argument, default constructor for any class without constructors. This default constructor will call the no-argument constructor of the superclass. In this situation, the compiler will complain if the superclass doesn't have a no-argument constructor so you must verify that it does. If your class has no explicit superclass, then it has an implicit superclass of Object, which does have a no-argument constructor [1].

therefore this also violates YAGNI

"You aren't gonna need it" (acronym: YAGNI) is a principle of extreme programming (XP) that states a programmer should not add functionality until deemed necessary. XP co-founder Ron Jeffries has written: "Always implement things when you actually need them, never when you just foresee that you need them [2].


References

[1]“Providing Constructors for Your Classes.” [Online]. Available: http://docs.oracle.com/javase/tutorial/java/javaOO/constructors.html. [Accessed: 27-Aug-2014].
[2]“You aren’t gonna need it,” Wikipedia, the free encyclopedia. 24-Aug-2014.

share|improve this answer

It's not a bad solution. It's not immediately obvious what processRock() function does, so I would just make some minor adjustments in the way the problem is decomposed and in naming, for clarity.

private static final String ALL_ELEMENTS = "abcdefghijklmnopqrstuvwxyz";
private int commonElements = bitsOfRock(ALL_ELEMENTS);

private static int bitsOfRock(String rock) {
    int bits = 0;
    for (int i = 0; i < rock.length(); i++) {
        int element = rock.charAt(i) - 'a';
        if (element >= 0 && element < ALL_ELEMENTS.length()) {
            // bitwise OR the bit that represents the element
            bits |= 1 << element;
        }
    }
    return bits;
}

public void requireElementsOfRock(String rock) {
    commonElements &= bitsOfRock(rock);
}

public int getElementCount() {
    return Integer.bitCount(commonElements);
}

For even better clarity, at the cost of a bit of performance, you could also use a java.util.BitSet.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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