5
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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()))]))
\$\endgroup\$

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.