cencry - encryption

problem

Marko is going to write a secret letter to a friend. He thought it is better to encrypt letter so that no other person can read it. After long thought he came up with an encryption scheme which was lame but he thought it will work anyways.

To encrypt a text he first wrote two infinite strings of characters first string consists only of vowels and second string consists of consonants only.

aeiouaeiouaeiouaeiouaeiou……………….. bcdfghjklmnpqrstvwxyzbcdfghjklmnpqrstvwxyz…

Following is the scheme for encryption :

let c be any character to be encrypted. let k be the count of number of times c character occurred in text to be encrypted until now. first find which of two infinite string contains that character. then look for kth occurrence of that character in that string. replace character c by corresponding character in second string. For example, encrypted text of “baax” will be “abho”.

Input: First line of input will contains t, number of test cases. Then t test case follows each test case in a line. Each test case will be a string of small Latin alphabets. Length of string will be less than 5*10^4

Output: For each test case print encrypted text.

Sample :

Input:

2
baax
aaa

Output:

abho
bhn

Source

solution

What’s nice about this problem is that it pretty much gives you the solution (i.e. how to go about getting the answer). The challenge lies in being able to implement that solution efficiently. The glaring issue being: maintaining a long sequence of vowels and a long sequence of consonants isn’t really sustainable as the length of our input string gets large.

But of course, the kicker is that we don’t actually have to maintain such long sequences. Modular arithmetic saves us by allowing us to figure out teh character at an arbitrarily large index without having to generate the sequence.

Giving us:

from sys import stdin
from collections import defaultdict

VOWELS = "aeiou"
CONS = "bcdfghjklmnpqrstvwxyz"
VOWELS2IDX = {vowel:idx for idx, vowel in enumerate(VOWELS)}
CONS2IDX = {cons:idx for idx, cons in enumerate(CONS)}

def readint():
    return int(stdin.readline())

def readtext():
    return stdin.readline().strip()

def encrypt(text: str):
    freq = defaultdict(int)
    encrypted = ""
    for c in text:
        k = freq[c]
        if c in VOWELS2IDX:
            idx = 5*k + VOWELS2IDX[c] # there are 5 vowels
            encrypted += CONS[idx % 21]
        else:
            idx = 21*k + CONS2IDX[c] # there are 21 consonants
            encrypted += VOWELS[idx % 5]
        freq[c] += 1
    return encrypted

if __name__ == "__main__":
    t = readint()
    for _ in range(t):
        text = readtext()
        print(encrypt(text))

Using dictionaries just allows us to find the index of characters efficiently.