Ceasar Redux

From IEEEXtreme 17.0 (2023), view on CSAcademy

Problem Statement

Caesar Redux

Time limit:

2500 ms (Python 3)
1000ms (C)
1280ms (JavaScript)

Memory limit: 256 MB

The Caesar cipher is a simple encryption technique that was used by Julius Caesar to send secret messages to his allies. It works by shifting the letters in the plaintext message by a certain number of positions. Decryption is performed by shifting in the opposite direction by the same number of positions.

A program that implements this technique is needed to encrypt a plaintext message or decrypt a ciphertext messages. Spaces are not affected by encryption or decryption.

You need to determine whether the value that is provided is plaintext or ciphertext. If the value provided is plaintext, you should output the encrypted message given the shift value above. If the provided value is ciphertext, you should output the decrypted message.

Standard Input

Input begins with an integer n on a line by itself that indicates how many messages are in the input.

The next 2n lines contain a line with the shift amount followed by a line with either a plaintext or a ciphertext message.

Standard Output

For each message in the input, output the plaintext if the message is ciphertext, or the ciphertext if the message is plaintext.

Constraints and notes

1≤ n ≤ 25
The shift value will be between 1 and 25, inclusive.
Each message will consist of lowercase letters and spaces, and contain between 3 and 300 characters.
If the message provided contains the word “the”, then it is plaintext. Otherwise, it is ciphertext.

Example

Input

2
19
we accept the ieeextreme challenge
19
qbspbz jhlzhy olsk aol vmmpjl vm wvuapmle theptbz wypvy av iljvtpun kpjahavy

Output

dl hjjlwa aol pllleayltl johsslunl
julius caesar held the office of pontifex maximus prior to becoming dictator

Solution

The problem involves implementing the Caesar cipher encryption technique to either encrypt or decrypt a given message based on specific conditions. We’ll start by brainstorming how to approach the problem, what data structures we will use, and follow it with the code solution and its explanation.

Problem Overview

The problem revolves around the classic Caesar cipher, which shifts the letters in a message by a given number of positions (shift). The input can either be plaintext (unencrypted message) or ciphertext (encrypted message). Our job is to determine the type of message and either encrypt it or decrypt it accordingly.

Key Details:

If the input message contains the word "the", it’s considered plaintext, and we should encrypt it.
Otherwise, it’s ciphertext, and we should decrypt it.
Spaces are not affected by encryption or decryption.
Each message will consist of lowercase letters and spaces.

Constraints:

1≤ n ≤ 25, where n is the number of messages.
The shift value will be between 1 and 25, inclusive.
Each message will contain between 3 and 300 characters.

Approach

Step 1: Plan

Input Parsing: First, we need to handle multiple messages. The input starts with an integer (n), which indicates the number of message-shift pairs. We will then process 2 lines for each message: the shift value and the message itself.
Determine if the Message is Plaintext or Ciphertext: A message is considered plaintext if it contains the word “the”. If not, it’s ciphertext. Based on this determination, we will either encrypt or decrypt the message.
Encryption and Decryption: The Caesar cipher works by shifting letters:
- Encryption: Shift the characters forward by a certain number of positions.
- Decryption: Shift the characters backward by the same number of positions.

Step 2: Data Structures

Strings: We will manipulate the input message string character by character. We need to check if each character is a letter and adjust its position in the alphabet based on the shift.
Looping Constructs: We’ll use loops to process the input and go through each character in the string.

Step 3: Encryption and Decryption Logic

For encryption, we will:

Shift each letter backward by the given shift value to simulate encryption.
Handle wrapping around the alphabet using modular arithmetic.

For decryption, we:

Shift each letter forward by the same shift value to reverse the encryption process.

def parser():
    """This function is provided. It is used to read the input"""
    while 1:
        # end = []
        data = list(input().split('\n'))
        for number in data:
            if len(number) > 0:
                yield(number)

input_parser = parser()

# get_word, get_number functions will be provided to help get the input data

def get_word():
global input_parser
return next(input_parser)

def get_number():
data = get_word()
try:
return int(data)
except ValueError:
return float(data)

def testShift(value):
try:
return int(value)
except ValueError:
return 101

testCases = get_number()

sententeces = []
shift_list = []
flags = []

for i in range(testCases):
shift_list.append(get_number())
sententeces.append(get_word())

for sentence in sententeces:
s = sentence.split(' ')
if 'the' in s:
flags.append(True)
else:
flags.append(False)

for k in range(len(sententeces)):
sentence = sententeces[k]
shift = int(shift_list[k])
Letter = ''
if flags[k]:

        for character in range(len(sentence)):
            char = sentence[character]

            char = ord(char)

            if char > 96 and char < 123:
                char2 = char - shift
                if char2 < 97:
                    char2 = char2 + 26
                char = chr(char2)
                Letter = Letter + char
            else:
                char = chr(char)
                Letter = Letter + char

    else:
        for character in range(len(sentence)p):
            char = sentence[character]

            char = ord(char)

            if char > 96 and char < 123:
                char2 = char + shift
                if char2 > 122:
                    char2 = char2%122+96
                char = chr(char2)
                Letter = Letter + char
            else:
                char = chr(char)
                Letter = Letter + char
    print(Letter)

#include <iostream>
#include <vector>
#include <sstream>
#include <string>

using namespace std;

vector<string> input_parser() {
  vector<string> result;
  string line;
  while (getline(cin, line)) {
      if (!line.empty()) {
          result.push_back(line);
      }
  }
  return result;
}

string get_word(vector<string>& input_data, int& current_index) {
  return input_data[current_index++];
}

int get_number(vector<string>& input_data, int& current_index) {
  string data = get_word(input_data, current_index);
  try {
      return stoi(data);
  } catch (invalid_argument&) {
      return static_cast<int>(stof(data)); // Use float conversion if it's not an int
  }
}

int testShift(int value) {
  try {
      return value;
  } catch (...) {
      return 101;
  }
}

int main() {
  vector<string> data = input_parser(); // read input from the user
  int current_index = 0;

  int testCases = get_number(data, current_index);

  vector<string> sentences;
  vector<int> shift_list;
  vector<bool> flags;

  for (int i = 0; i < testCases; i++) {
      shift_list.push_back(get_number(data, current_index));
      sentences.push_back(get_word(data, current_index));
  }

  for (const string& sentence : sentences) {
      istringstream iss(sentence);
      string word;
      bool found = false;
      while (iss >> word) {
          if (word == "the") {
              found = true;
              break;
          }
      }
      flags.push_back(found);
  }

  for (size_t k = 0; k < sentences.size(); k++) {
      string sentence = sentences[k];
      int shift = shift_list[k];
      string result = "";
      bool hasThe = flags[k];

      if (hasThe) {
          for (char ch : sentence) {
              if (ch >= 'a' && ch <= 'z') {
                  int char_shifted = ch - shift;
                  if (char_shifted < 'a') {
                      char_shifted += 26;
                  }
                  result += static_cast<char>(char_shifted);
              } else {
                  result += ch;
              }
          }
      } else {
          for (char ch : sentence) {
              if (ch >= 'a' && ch <= 'z') {
                  int char_shifted = ch + shift;
                  if (char_shifted > 'z') {
                      char_shifted = char_shifted % 'z' + 'a' - 1;
                  }
                  result += static_cast<char>(char_shifted);
              } else {
                  result += ch;
              }
          }
      }
      cout << result << endl;
  }

  return 0;
}

Explanation

Function caesar_cipher_encrypt(ciphertext, shift):
- This function takes the input ciphertext and shifts each character backward by the specified shift value to produce the encrypted message.
- We loop through each character in the input text, checking if it’s a letter, and adjust its position in the alphabet using modular arithmetic to handle wrapping around from 'z' to 'a'.
- Non-letter characters, such as spaces, remain unchanged.
Function caesar_cipher_decrypt(plaintext, shift):
- This function reverses the Caesar cipher by shifting the characters forward by the shift value, effectively decrypting the message.
- Like the encryption function, it processes each letter individually and leaves spaces unchanged.
Main Program:
- First, we read the number of message-shift pairs.
- For each pair, we read the shift value and message, and determine whether the message is plaintext or ciphertext by checking for the presence of the word “the”.
- Based on this check, we either encrypt or decrypt the message and print the result.

Input/Output Match check:

Input:

2
19
we accept the ieeextreme challenge
19
qbspbz jhlzhy olsk aol vmmpjl vm wvuapmle theptbz wypvy av iljvtpun kpjahavy

Output:

dl hjjlwa aol pllleayltl johsslunl
julius caesar held the office of pontifex maximus prior to becoming dictator

Explanation:

The first message contains the word "the", so it’s considered plaintext, and we encrypt it using a backward shift of 19.
The second message does not contain the word "the", so it’s considered ciphertext, and we decrypt it using the same shift of 19 to recover the original plaintext.

This solution efficiently handles both encryption and decryption with a time complexity of (O(m)), where (m) is the number of characters in the message. Given the constraints, this solution will run within the allowed time limits.