7
\$\begingroup\$

This is the "Gemstones" problem on Hackerrank.

John has collected various rocks. Each rock has various minerals embeded in it. Each type of mineral is designated by a lowercase letter in the range a-z. There may be multiple occurrences of a mineral in a rock. A mineral is called a gemstone if it occurs at least once in each of the rocks in John's collection. Given a list of minerals embedded in each of John's rocks, display the number of types of gemstones he has in his collection. For example, the array of mineral composition strings [abc, abc, bc] The minerals b and c appear in each composite, so there are 2 gemstones.

This is my Python code:

def gemstones(arr):  
    for i in range(len(arr)):
        arr[i] = "".join(set(arr[i]))

    long = max(arr, key=len)
    arrlen = len(arr)
    flag,count = 0,0
    for i in long: 
        for j in range(arrlen):
            if i not in arr[j]: flag = 1
        if flag is 0: count += 1
        flag = 0
    return count

Are there ways to improve this code? I feel I'm not using the full functionality of Python.

A test case:

>>> arr = ['abcdde', 'baccd', 'eeabg']
>>> print(gemstones(arr))
2
\$\endgroup\$
9
\$\begingroup\$

You need to stop iterating over indexes and loop like a native. A first rewrite with that in mind would yield:

def gemstones(collection):
    collection = [''.join(set(rock)) for rock in collection]
    biggest_rock = max(collection, key=len)

    count = 0
    for mineral in biggest_rock:
        for rock in collection:
            if mineral not in rock:
                break
        else:
            count += 1
    return count

This version make use for the for...else construct. But the all() builtin would be more expressive:

def gemstones(collection):
    collection = [''.join(set(rock)) for rock in collection]
    biggest_rock = max(collection, key=len)

    count = 0
    for mineral in biggest_rock:
        if all(mineral in rock for rock in collection):
            count += 1

    return count

And counting a condition in a for-loop can be more efficient using sum():

def gemstones(collection):
    collection = [''.join(set(rock)) for rock in collection]
    biggest_rock = max(collection, key=len)

    return sum(
        all(mineral in rock for rock in collection)
        for mineral in biggest_rock
    )

Other than that, you won't have more gemstones than the amount of minerals in the smallest rock, so why doing extra work by using the biggest one to start with?


But you are going back and forth between strings and sets when the problem clearly calls for set intersection repeated on several elements of an array. Luckily, the set.intersection method accept a variable number of arguments. Just make sure to catch any error thrown in case the original collection is empty:

def gemstone(collection):
    rocks = map(set, collection)
    try:
        minerals = next(rocks)
    except StopIteration:
        return 0  # If the collection is empty, there is no gemstones
    return len(minerals.intersection(*rocks))
\$\endgroup\$
  • \$\begingroup\$ # If the collection is empty, there are no gemstones Python... always the naive implementation that gets ripped to shreds by native implementation... I'm not sure there anything that you can do in python that can't be turned into a list of native operations... Oh wait. Same goes for every language... Maybe python just has more than js. \$\endgroup\$ – FreezePhoenix Oct 1 '18 at 17:00
  • \$\begingroup\$ @FreezePhoenix I don't get what you're trying to convey. I could have used next(rocks, set()) to avoid the whole try and achieve the same result, is it somewhat related? \$\endgroup\$ – 409_Conflict Oct 1 '18 at 17:07
  • \$\begingroup\$ What I meant was that JS doesn't have as much built in as Python does. \$\endgroup\$ – FreezePhoenix Oct 1 '18 at 17:25
  • \$\begingroup\$ Why not just refactor except StopIteration: return 0 to minerals = next(rocks, 0)? next has its second argument the default value for a good reason. \$\endgroup\$ – Voile Oct 2 '18 at 4:17
  • 1
    \$\begingroup\$ @Voile For starter it should be next(rocks, set()) instead, and its perfectly valid, yes, see my previous comment. But then, it's more of a personal taste in this particular case, building an empty set each time and not using it most of the time feels odd to me, I’d rather spend a tiny extra time in exception handling the rare times collection is empty… Or even don't care at all, since OP code doesn't (max will TypeError if arr is empty). \$\endgroup\$ – 409_Conflict Oct 2 '18 at 8:08
2
\$\begingroup\$

You could do this in one line:

rocks = ['abcdde', 'baccd', 'eeabg']

len(set.intersection(*[set(r) for r in rocks]))

To get the actual set, leave off the len(...) bit, of course, or replace it with list(...) if you prefer the result as a list instead of a set.

\$\endgroup\$
1
\$\begingroup\$

An alternative way to solve this is to just write down the problem description in Python:

rocks = ['abcdde', 'baccd', 'eeabg']


def is_gemstone(mineral):
    return all(mineral in rock for rock in rocks)


minerals = {mineral for rock in rocks for mineral in rock}
gemstones = {mineral for mineral in minerals if is_gemstone(mineral)}

print(len(gemstones))
\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to Code Review. On this site we like answers that explain the process of improving the code more than the actual result. Currently you have an improved version of the code here but not so much explanation to it. \$\endgroup\$ – Simon Forsberg Oct 1 '18 at 21:06

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.