Hackerrank Submission Optimisation for Melodious Password

Given question from Hackerrank:

• a password consists of exactly n lowercase English letters.

• the password is melodious, meaning that consonants can only be next to

vowels and vowels can only be next to consonants. Example: bawahaha

• the password cannot contain the letter y (because it's both a

consonant and vowel).

• the first letter of the password can be either

a vowel or consonant.

Given the length, n, of the password,

print all of the possible passwords that meet the conditions above.

Input Format

The line of input contains the integer (the length of the password).

Constraints

Output Format

Print each of the possible passwords, one per line. The order of the passwords does not matter.

My Code in Python:

import sys
import itertools

n = int(raw_input().strip())

consonants = ['b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 'z']
vowels = ['a', 'e', 'i', 'o', 'u']

test4 = ['b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 'z', 'a', 'e', 'i', 'o', 'u']
answer = set(itertools.product(test4, repeat=n))

for letters in answer:
    for j in xrange(len(letters)):
        flag = 1
        if j != len(letters) - 1:
            if letters[j] in vowels and letters[j+1] in vowels:
                flag = 0
                break
            if letters[j] in consonants and letters[j+1] in consonants:
                flag = 0
                break

    if flag:
        for j in letters:
            sys.stdout.write(j)
        print ""

Can this code be optimized in any way?

Keeping the way that you're doing this at the moment, you can:

• Change consonants to a string. This allows for easier readability, and may give better performance than a list.

• Name constants in UPPER_SNAKE_CASE.

• Using itertools.pairwise, you can remove all bar one if. This is as you can categorise each letter, l in consonants. And then compare if they are the same.

• You should use a function, as it can be faster

• You should use a if __name__ == '__main__' guard.

• You should use print ''.join(letters), rather than for j in letters: sys.stdout.write(j).

• You can yield from the function instead, so that if it's not fast enough, you can group prints. Or use it in other ways.

This can lead to:

import itertools

CONSONANTS = 'bcdfghjklmnpqrstvwxz'
VOWELS = 'aeiou'

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = itertools.tee(iterable)
    next(b, None)
    return izip(a, b)

def generate_answers(n):
    consonants = CONSONANTS
    for answer in itertools.product(consonants + VOWELS, repeat=n):
        letter_categories = (l in consonants for l in answer)
        if all(a != b for a, b in pairwise(letter_categories)):
            yield ''.join(answer)

if __name__ == '__main__':
    for answer in generate_answers(int(raw_input().strip())):
        print(answer)

However, this is based around an inefficient usage of itertools.product.
You instead want to pass it the arguments so that it'll create them efficiently.
This is easy to do when n is even:

def generate_answers(n):
    return chain(product(CONSONANTS, VOWELS, repeat=n//2),
                 product(VOWELS, CONSONANTS, repeat=n//2))

To, do this efficiently when n is odd, is also quite easy.
You want to do roughly the same thing, but if the first item of the products is not the same as the first character of the first argument, then stop looping.
And so you can use:

import itertools

CONSONANTS = 'bcdfghjklmnpqrstvwxz'
VOWELS = 'aeiou'

def product(a, b, repeat):
    if repeat % 2 == 0:
        for ret in itertools.product(a, b, repeat=repeat//2):
            yield ret
    else:
        for ret in itertools.product(b, a, repeat=repeat//2+1):
            if ret[0] != b[0]:
                break
            yield ret[1:]

def generate_answers(n):
    return itertools.chain(product(CONSONANTS, VOWELS, repeat=n),
                           product(VOWELS, CONSONANTS, repeat=n))

if __name__ == '__main__':
    for answer in generate_answers(int(raw_input().strip())):
        print(''.join(answer))

StackExchange Code Review Q#157792, answer score: 5