"The Minion Game" challenge

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


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("D

StackExchange Code Review Q#106238, answer score: 13