Hackerrank Submission Optimisation for Melodious Password

Question

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?

Answer 1

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))

Answer 2

Algorithm

The exercise asks for all possible words where consonants and vowels are alternating. The current algorithm achieves this by generating all possible words, and then filtering that result to remove words that violate the constraint of alternating consonants and vowels. This doesn't sound very efficient, so let's analyze the problem space a bit.

How many possible solutions are there, for the maximum required length \$n = 6\$?

$$ 2 * 20 * 5 * 20 * 5 * 20 * 5 = 2000000 $$

In contrast, how many possible words are there before the filtering is applied?

$$ 25*25*25*25*25*25 = 244140625 $$

An algorithm that would generate directly the required words would be more than 100 times faster than the current approach.

What is test4?

It looks like the concatenation of consonants and vowels. You could have written as such, and with a meaningful name:

letters = consonants + vowels

What is flag?

flag only has values 0 and 1. So why not make it a boolean?

Alternative implementation

It's possible to create all the valid words using a recursive function. Consider this signature:

def passwords(word, l1, l2):

Where the parameters are:

• word: a password that is being built
• l1: a set of letters
• l2: the other set of letters. That is, when l1 is vowels, then l2 is consonants, and when l1 is consonants, then l2 is vowels

When the length of word is equal to n, it is ready to print (or to yield).

Otherwise, for each letter in l1, recursively call passwords(word + letter, l2, l1). Notice that word will grow, and l1 and l2 are swapped. This is how consonants and vowels will be naturally alternating.

To get all possible valid passwords, start the recursion twice, once with passwords('', vowels, consonants), and a second time with passwords('', consonants, vowels).