"The Minion Game" challenge

Question

This is an implementation of the minion game, which takes in string input and declares a winner between two pre-determined players.

The logic is player 1 gets all sequenced words not starting with a vowel and player 2 gets all sequenced words starting with vowel in the input string.

Objective: performance optimisation. The code passed all the test cases, but I am very unsure where to tune the performance.

For a 1000 letter word, here are the time stats:

• real 0m10.142s
• user 0m6.386s
• sys 0m0.743s

---

import string
import sys
import itertools

def minion(str):
    person_a_name = 'Stuart'
    person_b_name = 'Kevin'
    letter_list = [a for a in str]
    l = len(letter_list)
    vowel = ['A','E','I','O','U']
    consonants = ['Q','W','R','T','Y','P','S','D','F','G','H','J','K','L','Z','X','C','V','B','N','M']
    all_word = []
    person_a_words = []
    person_b_words = []
    all_word = [letter_list[start:end+1] for start in xrange(l) for end in xrange(start, l)]
    for array in all_word:
        if array[0] in vowel:
            person_b_words.append(array)
    for array in all_word:
        if array[0] in consonants:
            person_a_words.append(array)
    if len(person_a_words) == len(person_b_words):
        print 'Draw'
    if len(person_a_words) > len(person_b_words):
        print person_a_name, len(person_a_words)
    if len(person_b_words) > len(person_a_words):
        print person_b_name, len(person_b_words)

def main():
    str = raw_input()
    minion(str.upper())

if __name__ == '__main__':
    main()

Sample input / output:

banana
Stuart 12

guavaisanotherfruit     
Kevin 98

Answer 1

The big performance hit probably comes in this block of code, where you don a bunch of array manipulations and looping:

all_word = [letter_list[start:end+1] for start in xrange(l)
                                     for end in xrange(start, l)]
for array in all_word:
    if array[0] in vowel:
        person_b_words.append(array)
for array in all_word:
    if array[0] in consonants:
        person_a_words.append(array)
if len(person_a_words) == len(person_b_words):
    print 'Draw'
if len(person_a_words) > len(person_b_words):
    print person_a_name, len(person_a_words)
if len(person_b_words) > len(person_a_words):
    print person_b_name, len(person_b_words)

Appending to an array is a (relatively) expensive operation, as is looping over a list. I can see a number of optimisations here. [Edit: I wrote these in the order I thought of them; the big performance gain comes on the last item. I'm leaving the remaining items because they're still instructive, even if not directly applicable here.]

• Only loop over all_word once. You can check for starting with a consonant and vowel in the same iteration of the loop:

  for array in all_word:
      if array[0] in vowel:
          person_b_words.append(array)
      elif array[0] in consonants:
          person_a_words.append(array)
  

  We've just cut out an iteration over all_word. If all_word is large, that will be a significant saving.

• Don't store the words in a list, just the count. All you care about is the relative number of words in each list; the words themselves don't matter. It's much easier to increment an integer than mutate a list, so consider the following:

  person_a_words = 0
  person_b_words = 0
  for array in all_word:
      if array[0] in vowel:
          person_b_words += 1
      elif array[0] in consonants:
          person_a_words += 1
  

  and then you can compare the two integers at the end. That's bound to be a performance saving.

• Don't construct all_word as a list; use a generator. If you replace the square brackets with parens:

  all_word = (letter_list[start:end+1] for start in xrange(l)
                                       for end in xrange(start, l))
  

  then this becomes a generator comprehension instead of a list comprehension. This means it only creates the elements as they're needed by the for loop; it doesn't create them all in memory before continuing.

  Using generators instead of lists is a really good way to reduce occupancy and speed up programs.

• Do you even need to use all_word? For each value of start, the first letter of the resulting words will be the same, and this gives you (l - start) different words. You don't actually need to create the words; you just care about their initial letter, and how many distinct words they create.

  You could just add the number of distinct words to each person's score directly:

  person_a_words = 0
  person_b_words = 0
  for idx, letter in enumerate(letter_list):
      if letter in vowel:
          person_b_words += len(letter_list) - idx
      else:
          person_a_words += len(letter_list) - idx
  

  That is substantially faster: I just ran this with a 1.5m character string, and it finished in ~1.5s.

Other non-performance related comments:

• Don't use str as a variable name; overriding builtins is bad practice.
• You've imported the string, sys and itertools modules, but you never use any of them. Why?
• PEP 8 requires a space after commas in a list; you should add this in vowel and consonants.

• You can get the individual letters of a string by calling list() on it. These calls are equivalent:

  letter_list = [a for a in my_string]
  letter_list = list(my_string)
  

  although in this case, you don't need to coerce to a list first – you can iterate over the characters of a string directly.

• There's no need to assign the length of letter_list to a variable, especially not one with as undescriptive a name as l. It just makes your code harder to read.
• The name of your function isn't particularly helpful. Ideally it should give me some idea of what the function does. There should also be a docstring to explain the result.
• I would rename the person_a* and person_b* variables to be consonant* and vowel*, respectively – that will make the code easier to read. A and B don't really mean anything (and as evidence, I got them the wrong way round when I first wrote that sentence).

• Your function is doing some work (finding out whether there are more vowel sub-words or consonant subwords) and printing to screen (the result). It would be better to separate this into two functions: one that does the work, the other does the result.

  That makes it easier to reuse the work of vowels vs. consonants.

• To aid readability, I'd keep the same order of variables when you do the comparison at the end. i.e.

  if vowel_count > consonant_count:
      print("Vowels victorious!")
  elif vowel_count < consonant_count:
      print("Consonants champion!")
  else:
      print("Draw!")
  

Answer 2

There are two points I would like to emphasize as really performance penalties in your code:

• Memory usage when generating all the possible word combinations, which is exponential when increasing word length
• Unneccessary complexity to calculate points

Before diving into these points, I would like to say that both alexwlchan and SuperBiasedMan has given good pointers related to other code smells and stuff you need to look into as well.

Exponential memory usage

There is only line which really stands out and will require a load of memory when the length of the text increases:

all_word = [letter_list[start:end+1] 
               for start in xrange(length) 
                  for end in xrange(start, length)]

Lets do some numbers, in a text of length = 4, like in abcd, you'll get the following word combinations:

• 4 words starting with first letter: abcd, abc, ab, a
• 3 words starting with second letter: bcd, bc, b
• 2 words starting with third letter: cd, c
• 1 word starting with fourth letter: d

In other words the total points available in your game for a text with length, \$N\$, is the sum of \$N + N-1 + N-2 + ... + 2 + 1\$. Luckily there exist an easy formula to calculate this number: \$(N+1)*N/2\$. This is listed at points in the table below.

But that was only the points (or number of words), when looking at memory usage we need at least to look at how long each of the words are. Continueing with our example with \$N=4\$, we have 4 words of length 1, 3 words of length 2, and so on. In general \$N \cdot 1 + (N-1)\cdot 2 + ... + 2\cdot (N-2) + 1\cdot N\$. I haven't found the general formula¹ for this, but made a simple Python function to calculate it:

# Shift the range index by +1 so that we get the proper 1 to N sequence
sum( (n+1-k)*k for k in xrange(1, n+1) )

In the table below I've listed the length of text with corresponding number of points/words, and how many characters are needed to store these words. As can be seen these number increase quite fast. The last line is memory usage in megabytes when using memory_profiler on the original code.

text length :   4   10     50     100       500       1000         5000 
points/words:  10   55   1275    5050    125250     500500      1250250
characters:    20  220  22100  171700  20958500  167167000  20845835000
usage in MiB:       ~0   0.24    1.52    185.68    1251.93     too much

Unneccessary complexity

When reviewing your original problem statement, you need to calculate points of words starting with either a vowel or a consonant. You don't need to actually now the words.

Combining this with knowledge from previous section that at a given position, \$k\$, in the text you can generate \$N-k\$ words, the total complexity reduces quite nicely to a method like the following:

def count_minion_words(text):
    text_length = len(text)
    word_count_vowels = 0
    word_count_consonants = 0

    for (index, character) in enumerate(text):
        if character in ['A', 'E', 'I', 'O', 'U']:
            word_count_vowels += text_length - index
        else:
            word_count_consonants += text_length - index
    return (word_count_vowels, word_count_consonants)

This doesn't require any memory besides the original text, loops through the entire text in one go, and calculates the points for word counts starting with either a vowel or consonant. Feel free to test this one with text length of 1000 or more. Tested it with a text of length 1.5m, and it completed within 0.35 seconds.

---

1 Added: Thanks to my question at Mathematica SE I now know that the formula is:

$$ \frac{n(n+1)(n+2)}{6} $$

Answer 3

I have multiple performance ideas, some smaller than others but consistent good performance choices are a good mindset to be in.

Minor notes, you can get a list of characters from a string just using list(). So instead of your list comprehension, use letter_list = list(str). Note that I agree you should use a different name than str, but for now I'm focusing on performance.

Also when you call len(letter_list) it's slower than getting the length of a string, so call len(str) instead. Generally, strings are faster than lists. If you don't need more complex list capabilities, stick with strings. So instead of making vowel and consonant lists, make them strings.

But even more efficient than lists, are integers. And you create lists of each person's words as if those matter. But all you need is a count of these values. Replacing every append with += 1 would be much faster. This is the main source of slowness I believe.

for array in all_word:
    if array[0] in vowel:
        person_b_words += 1
    else:
        person_a_words += 1

We also only need to loop once if you use an else. It might be faster to use sum here, but that does get more complicated and might not actually prove helpful. If you're interested to know more I could explain later.

Now of course you no longer need multiple len calls, you can just compare the variables directly as they're both integers. You should also use elif and else statements since you know only one of the conditions is possible.

if person_a_words == person_b_words:
    print 'Draw'
elif person_a_words > person_b_words:
    print person_a_name, person_a_words
else:
    print person_b_name, person_b_words

I think another thing you could is find a more intelligent way to iterate over all the sequeunces. You make a huge list of strings, but you only need the first letter of each. It'd be easier if you used a loop that got each first letter the appropriate amount of times rather than your huge list based on the indices range.

Answer 4

Using Python2 this worked.

def minion_game(s):
    Stuart, Kevin = 0,0
    length = len(s)
    for idx,sub in enumerate(s):
        if sub in 'AEIOU': Kevin += length - idx
        else: Stuart += length - idx
    print(['Draw','Kevin {}'.format(Kevin),'Stuart {}'.format(Stuart)][0 if Kevin == Stuart else 1 if Kevin>Stuart else 2])


if __name__ == '__main__':
    s = raw_input()
    minion_game(s)