Hackerrank Gem Stones I am working on some problems on Hackerrank.


  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 solved the problem but I don't feel that it is fast or pythonic. I was wondering if someone could help me increase the performance and perhaps reduce the amount of memory being used.

numRocks = int(raw_input())
rockList = []
for x in xrange(numRocks):
    rock = raw_input()
    # list of sets()
    rockList.append(set(rock))
gemElement = 0
for x in rockList[0]:
    rocks = len(rockList) - 1
    count = 0
    for y in rockList[1:]:
        if x in y:
            count += 1
            if count == rocks:
                gemElement += 1
print gemElement
Your solution looks pretty good. However, a few details can be changed to make your code more pythonic :

Unused variable

You can use _ to name a variable whose value is not used. In your case, it applies to the first loop variable x.

List comprehension

You can rewrite your initialisaion of rockList abusing list comprehension :

rockList = [set(raw_input())
    for _ in xrange(int(raw_input()))]


Simplifying the logic

At the moment, for each element in the first set, you look in how many other sets it appears to know if it is a gem. You can make things clearer by considering that by default it is a gem except if we don't find it in one of the other sets (and in that case, we can stop looping) :

for x in rockList[0]:
    is_gem = True
    for y in rockList[1:]:
        if x not in y:
            is_gem = False
            break
    if is_gem:
        gemElement += 1


Using Python good stuff

Using Python all builtin, we can write this all(x in y for y in rockList[1:]).

You can extract rockList[1:] to call it only once (note that the cute way to write this in Python 3 would be to use extended iterable unpacking). Your code becomes :

gemElement = 0
other_rocks = rockList[1:]
for x in rockList[0]:
    if all(x in y for y in other_rocks):
        gemElement += 1
print gemElement


Now, you can see that we can easily get the actual list of gems doing :

gems = (x for x in rockList[0]
    if all(x in y for y in other_rocks))


This is not an actual list but a generator expression, you'll need to call list(gems) if you want to see an actual list but we don't really care about the list, we just need the number of elements : len(list(gems)) or sum if you don't want to build an intermediate list in memory.

The code is now :

rockList = [set(raw_input())
    for _ in xrange(int(raw_input()))]
other_rocks = rockList[1:]
print sum(1 for x in rockList[0]
    if all(x in y for y in other_rocks))


One step back from the code

The problem we are trying to solve is linked to a common problem : computing the intersection of multiple sets. It is a generic enough problem so that we can google it and find this answer for instance.

Making the solution as concise as possible, one can write :

print len(set.intersection(*[
    set(raw_input())
    for _ in xrange(int(raw_input()))]))