The Minion Game

  • + 7 comments

    Python 3

    def minion_game(s):
        V = frozenset("AEIOU")
        n = len(s)
        ksc = sum(q for c, q in zip(s, range(n, 0, -1)) if c in V)
        ssc = n * (n + 1) // 2 - ksc
        if ksc > ssc:
            print("Kevin {:d}".format(ksc))
        elif ssc > ksc:
            print("Stuart {:d}".format(ssc))
        else:
            print("Draw")
    

    Several optimizations.

    1. Use frozenset for the vowels. This is the fastest to lookup in.
    2. Iterate through characters instead of indexing
    3. Iterate q reverse to avoid a subtraction in each sum
    4. Avoid repeated calls to len
    5. Only calculate Kevins score the hard way. Use the fact that the total number of substrings is n * (n + 1) / 2 and find Stuart's score by subtracting Kevin's from the total number of substrings.