HackerRank Solution: Python Iterables and iterators [Itertools]

Question: Python Iterables and Iterators (Itertools)

The itertools module standardizes a core set of fast, memory-efficient tools that are useful by themselves or in combination. Together, they form an iterator algebra making it possible to construct specialized tools succinctly and efficiently in pure Python.

To read more about the functions in this module, check out their documentation here.

You are given a list of N lowercase English letters. For a given integer K, you can select any K indices (assume 1-based indexing) with a uniform probability from the list.
Find the probability that at least one of the K indices selected will contain the letter: ‘a’.

Input Format:

The input consists of three lines. The first line contains the integer N, denoting the length of the list. The next line consists of N space-separated lowercase English letters, denoting the elements of the list.
The third and the last line of input contains the integer K, denoting the number of indices to be selected.

Output Format:

Output a single line consisting of the probability that at least one of the K indices selected contains the letter:’a’.Note: The answer must be correct up to 3 decimal places.

Constraints:

1 <= N <= 10
1 <= K < = N

All the letters in the list are lowercase English letters.

Sample Input:

4
a a c d
2

Sample Output:

0.8333

Explanation

All possible unordered tuples of length 2 comprising of indices from 1 to 4 are:(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)
Out of these 6 combinations, 5 of them contain either index 1 or index 2 which are the indices that contain the letter ‘a’.

Hence, the answer is 5/6.

Possible Solutions

Now we will discuss various methods to solve the iterable and iterator question from HackerRank. Here we will go through the following solutions

Simple solution
Using lambda function
Using list comprehension
Using for loop

Solution-1: Simple solution

Here is our first possible solution:

from itertools import combinations, groupby

# Read the input
count, letters, to_select = int(input()), input().split(), int(input())

# sort the letters so all a's are on left side
letters = sorted(letters)

# Find all possible combinations of to_select
combinations_of_letters = list(combinations(letters, to_select))

# find all which contain
contain = len([c for c in combinations_of_letters if 'a' in c])

# Print Results
print(contain / len(combinations_of_letters))

In the above script, the code then reads in 3 inputs: An integer count, a string of space-separated letters and an integer to_select. Then the list of letters is sorted in alphabetical order. All possible combinations of to_select letters from letters are found using the combinations function. The code then filters the combinations to find those that contain the letter 'a' using a list comprehension. The ratio of combinations containing 'a' to the total number of combinations is calculated and stored in the contain variable.

Solution-2: Using lambda function

Now, we will use the lamnda function to find the solution for the given problem:

from itertools import combinations, starmap
_ = int(input())

it = list(starmap(lambda *x: 'a' in x, combinations("".join(input().split()), int(input()))))

print(sum(it)/len(it))

Although the code looks messay and complex, but if we divide it into small parts, it is very simple: Here is how the code works:

It reads in an integer and discards it using the underscore variable _.
It reads in a string of space-separated letters and joins them into a single string.
It reads in another integer to_select and uses the combinations function to generate all possible combinations of to_select letters from the input string.
It uses the starmap function to apply a lambda function to each combination. The lambda function returns True if the combination contains the letter 'a' and False otherwise.
It converts the iterator returned by starmap into a list and stores it in the variable it.
It calculates the ratio of True values in it (i.e., the number of combinations containing 'a') to the total length of it and prints the result.

Solution-3: Using list comprehension

Now, we will solve the same problem in an alternative method using the list comprehensions:

from itertools import * 
n = int(input())
ls = input().split()
k = int(input())
com = list(combinations(ls, k))
tol = [i for i in com  if "a" in i ]
print(f'{(len(tol)/len(com)):.12f}')

The code first reads an integer n and discards it. Then reads a string of space-separated letters and splits it into a list of individual letters. Finally, it also reads another integer k, and uses the combinations function to generate all possible combinations of k letters from the input list of letters. It then filters the list of combinations to find those that contain the letter 'a' using a list comprehension.

Solution-4: Using for loop

Now let us use the for loop to solve the problem:

from itertools import combinations
l = int(input())
s = input().split()
c = int(input())

leng = len(list(combinations(s,c)))
data = 0
for i in combinations(s,c):
    if "a" in i:
        data+=1
print(float("{:.12f}".format(data/leng)))

The first part of the code is similar to the previous ones where it takes user input: Then it calculates the total number of combinations using the len function and stores it in the leng variable. It initializes a counter variable data to 0. Finally, the code iterates over the combinations, and for each combination that contains the letter 'a', it increments the data counter by 1.

Summary

In this short article, we learned four different methods to solve the iterator and iterable question from HackerRank and explained each solution in detail.