CF 102697114 - Viginere Cipher

CF 102697114 - Viginere Cipher

Rating: -
Tags: -
Solve time: 49s
Verified: yes

Solution

Problem Understanding

We are given a plaintext sentence on the first input line and a keyword on the second line. The task is to encrypt the sentence with the classical Vigenère cipher.

Each letter of the keyword represents a shift in the alphabet, where a means shift by 0, b means shift by 1, and so on up to z, which means shift by 25. The keyword is repeated as many times as necessary, but spaces in the plaintext are not encrypted and do not consume a character from the keyword. The encrypted sentence must keep its original spaces and preserve the case of each plaintext letter.

For example, with plaintext Here is an example test case and key fish, the first four letters use shifts f, i, s, h. The next plaintext letter after a space continues with the next key character rather than restarting the key.

The published problem has a 1 second time limit and a 256 MB memory limit. The statement does not expose a restrictive maximum plaintext length, so the natural target is a single linear pass over the input. An algorithm with work proportional to the number of characters is sufficient, while constructing large auxiliary structures or repeatedly searching through the alphabet is unnecessary.

The first edge case is a plaintext containing spaces. For input

a a
b

the correct output is

b b

The first a uses key b, and the second a also uses key b because the space is skipped rather than consuming a key character. An implementation that advances the key index for every character would incorrectly use a different key position for the second a.

The second edge case is a key that is shorter than the plaintext. For input

abcde
bc

the key sequence is bcbc b, so the output is

bddff

A careless implementation that uses each key character only once would run out of key characters instead of wrapping back to the beginning.

The third edge case is mixed case. For input

Az
b

the output is

Ba

The shift is computed using the same alphabet positions, but the result must be written using the original letter's case. Treating everything as lowercase would produce the wrong capitalization.

Approaches

A direct implementation can simulate the Vigenère tableau. For every plaintext letter, convert it to a number from 0 to 25, convert the corresponding key character to another number, add the two values modulo 26, and convert the result back to a letter. If this is implemented by searching through all 26 possible output characters for every plaintext character, the work is 26n character comparisons for a plaintext of length n. This is still linear because the alphabet has fixed size 26, and for the actual problem it is not genuinely too slow. However, it performs unnecessary work and makes the implementation more complicated than the mathematical operation requires.

The key observation is that the Vigenère tableau is just modular addition. If p is the plaintext letter's alphabet position and k is the key letter's position, the encrypted position is

(p + k) mod 26.

There is no need to construct the tableau or search it. We can calculate the answer directly.

The key index advances only when an alphabetic plaintext character is processed. When a space is encountered, we copy it directly and leave the key index unchanged. After using the last key character, the index wraps around with modulo len(key).

The brute-force approach works because it eventually performs the same alphabet shift, but fails to exploit the fact that every lookup in the Vigenère table has a simple arithmetic formula. The observation that encryption is modular addition reduces the work to one constant amount of computation per input character.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(26n) = O(n)	O(26)	Accepted, but unnecessary work
Optimal	O(n)	O(n) for the output	Accepted

Algorithm Walkthrough

1. Read the plaintext and the key, removing only the newline characters. We must not use a transformation that removes internal spaces because those spaces have to appear unchanged in the output.
2. Set a key pointer to 0. This pointer represents the key character that will encrypt the next plaintext letter.
3. Process the plaintext from left to right. For every space, append the space to the result and do not change the key pointer. The cipher skips spaces, so the next actual letter must continue using the same key position.
4. For every alphabetic character, obtain its alphabet position with ord(character.lower()) - ord('a'). Obtain the corresponding key shift with ord(key[key_index].lower()) - ord('a').
5. Add the plaintext position and key shift modulo 26. The modulo is what makes z wrap around to a.
6. Convert the resulting position back to a character. If the original plaintext character was uppercase, convert the result to uppercase as well. Append the encrypted character to the result.
7. Advance the key pointer and wrap it with modulo len(key). This repeats the keyword indefinitely without ever explicitly constructing a repeated string.
8. Print the completed result. Since the result is accumulated in a list and joined once, the program avoids repeatedly rebuilding an immutable Python string.

Why it works

At every alphabetic position, the algorithm uses exactly the key character that occupies that position in the repeated keyword, because the key pointer advances once per encrypted letter and never advances over spaces. The encrypted alphabet position is computed as (plaintext_position + key_position) % 26, which is exactly the Vigenère encryption rule. Since the result is converted back to the original case and all non-encrypted characters are copied unchanged, every output character is correct.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    plaintext = input().rstrip('\n')
    key = input().rstrip('\n')

    result = []
    key_pos = 0
    key_len = len(key)

    for ch in plaintext:
        if ch == ' ':
            result.append(ch)
            continue

        base = ord('A') if ch.isupper() else ord('a')

        p = ord(ch) - base
        k = ord(key[key_pos].lower()) - ord('a')

        encrypted = (p + k) % 26
        out = chr(base + encrypted)

        result.append(out)
        key_pos = (key_pos + 1) % key_len

    sys.stdout.write(''.join(result) + '\n')

if __name__ == "__main__":
    solve()

The first two lines read the plaintext and key while preserving spaces. rstrip('\n') removes the input newline without stripping meaningful spaces from the sentence.

key_pos counts encrypted letters rather than raw character positions. That distinction is the main implementation detail of the problem. If the plaintext contains a space, the loop continues without modifying key_pos.

The base variable lets the same arithmetic handle uppercase and lowercase letters. For A, the alphabet position is 0, while for a it is also 0. The encrypted position is calculated independently of case, and base is then used to restore the original case.

The modulo operation handles wraparound. For example, z has position 25, and adding a shift of 2 gives (25 + 2) % 26 = 1, which corresponds to b.

The key pointer is advanced only after encrypting a letter. Writing (key_pos + 1) % key_len makes the key repeat automatically. There is no off-by-one issue because the current key character is read before the pointer is incremented.

The result is stored in a list because repeated concatenation such as result += out can cause unnecessary string copying. Joining once at the end gives a clean linear-time construction.

Worked Examples

For the first example, the plaintext is Here is an example test case and the key is fish. The key advances only over letters.

Plaintext	Key	Plain position	Key position	Encrypted
H	f	7	5	M
e	i	4	8	m
r	s	17	18	j
e	h	4	7	l
space	unchanged			space
i	f	8	5	n
s	i	18	8	a
space	unchanged			space
a	s	0	18	s
n	h	13	7	u

Continuing the same process for the entire sentence produces

Mmjl na su jfstutw ajal jfaw

The trace demonstrates that spaces do not consume key characters. After encrypting Here, the next letter i uses f again rather than i.

For a second example, consider

abcde
bc

The key has length two, so it repeats as b c b c b.

Plaintext	Key	Plain position	Key position	Encrypted
a	b	0	1	b
b	c	1	2	d
c	b	2	1	d
d	c	3	2	f
e	b	4	1	f

The resulting ciphertext is bddff. This trace exercises key wrapping and shows why the key index must be taken modulo the key length.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every plaintext character is processed exactly once, with constant-time arithmetic for each character.
Space	O(n)	The result contains one output character for each input character.

The algorithm performs one pass over the plaintext and uses only constant extra state besides the output. Since there are no nested loops depending on the input size and no repeated construction of the keyword, it scales linearly with the message length and comfortably fits the stated 1 second and 256 MB limits.

Test Cases

import sys
import io

def solve():
    input = sys.stdin.readline

    plaintext = input().rstrip('\n')
    key = input().rstrip('\n')

    result = []
    key_pos = 0
    key_len = len(key)

    for ch in plaintext:
        if ch == ' ':
            result.append(ch)
            continue

        base = ord('A') if ch.isupper() else ord('a')
        p = ord(ch) - base
        k = ord(key[key_pos].lower()) - ord('a')

        encrypted = (p + k) % 26
        result.append(chr(base + encrypted))

        key_pos = (key_pos + 1) % key_len

    sys.stdout.write(''.join(result) + '\n')

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    try:
        solve()
        return sys.stdout.getvalue()
    finally:
        sys.stdin = old_stdin
        sys.stdout = old_stdout

# Provided sample
assert run("Here is an example test case\nfish\n") == \
       "Mmjl na su jfstutw ajal jfaw\n", "sample 1"

# Minimum-size input
assert run("a\nb\n") == "b\n", "minimum-size case"

# Key longer than the plaintext
assert run("abc\nxyz\n") == "xzz\n", "key longer than plaintext"

# Spaces must not advance the key
assert run("a a\nb\n") == "b b\n", "spaces must not consume key characters"

# Uppercase/lowercase preservation and alphabet wraparound
assert run("Az\nb\n") == "Ba\n", "case and wraparound"

# Repeated key and exact key-boundary transition
assert run("abcde\nbc\n") == "bddff\n", "key repetition"

The first test reproduces the provided sample. The next tests target the smallest possible plaintext, a keyword longer than the plaintext, spaces in the middle of the message, case preservation with alphabet wraparound, and the exact point where a short key starts repeating.

Test input	Expected output	What it validates
a / b	b	Minimum-size plaintext and key indexing
abc / xyz	xzz	Key longer than the plaintext
a a / b	b b	Spaces do not advance the key
Az / b	Ba	Uppercase preservation and wraparound
abcde / bc	bddff	Repeating-key boundary and modulo indexing

Edge Cases

For spaces, consider the exact input

a a
b

The first a has position 0 and the key character b has shift 1, producing b. The space is copied unchanged and the key pointer remains at the end of the first key character. The second a therefore also uses b and becomes b. The final output is b b.

For key repetition, consider

abcde
bc

The key positions are b, c, b, c, b. The corresponding shifts are 1, 2, 1, 2, 1, giving b, d, d, f, f. The output is bddff. The modulo operation on the key pointer is what produces the third b after the first two key characters have been consumed.

For mixed case and alphabet wraparound, consider

Az
b

A has alphabet position 0, and adding the shift for b, which is 1, produces B. For z, the position is 25, so adding 1 gives 26, and 26 % 26 is 0, producing a. The original cases are preserved, so the final output is Ba.

For a keyword longer than the message, consider

abc
xyz

The three plaintext letters use only x, y, and z. Their shifts are 23, 24, and 25, so the encrypted positions are 23, 25, and 25, giving xzz. The unused part of the keyword never needs to be processed.

For a plaintext consisting entirely of spaces, such as

     
abc

every character is copied directly and the key pointer never moves. The output remains the same sequence of spaces. The algorithm does not attempt to index the key for a character that should not be encrypted, which avoids both incorrect key alignment and unnecessary work.