Encrypt the Message
Autumn Tournament (2018)
Submission name: coding.cpp
Problem summary
Build a 5 × 5 substitution square from a keyword: keep each distinct letter in first-occurrence order, then append unused letters alphabetically. I and J share a cell represented by I. Remove spaces and punctuation from the message, replace J by I, and insert Q between every adjacent equal pair of letters (use Z between QQ). If the resulting length is odd, append Q, or Z if its last letter is Q. Encrypt consecutive pairs: letters in one row move right, letters in one column move down, both with wraparound; otherwise each keeps its row and takes the other letter’s column.
Input
A keyword line followed by one message line. All letters are uppercase Latin.
Output
The encrypted letter pairs, separated by single spaces.
Constraints
The keyword contains 6 to 30 letters; repeated letters count only once. The statement specifies no numerical message-length limit. The message can contain spaces and punctuation.
Worked example
Official statement sample.
Input
SQUANDER ALL IS KNOWN FLY AT ONCE
Output
SP SM FA TC MX SK PV NP TU DR
Solution analysis
- Normalize J to I before both deduplication and message processing. Append keyword letters not already used, then append the remaining alphabet except J. Store each letter’s row and column so encoding a pair takes constant time.
- Clean the message to letters. Scan the original cleaned sequence: before a letter equal to its predecessor, append a separator, Q normally or Z for repeated Q. This applies even when the repeated letters straddle a would-be pair boundary. Pad an odd final length using the same Q/Z rule.
- Take pairs from the prepared text. A same-row pair advances both columns modulo 5; a same-column pair advances both rows modulo 5. A rectangular pair swaps its columns. Always preserve pair order.
- With key SQUANDER, the grid begins S Q U A N / D E R B C. The message begins ALL, which becomes ALQL. A and L occupy opposite corners, so AL becomes SP; QL becomes SM. Continuing gives SP SM FA TC MX SK PV NP TU DR.
Why it works
The distinct-keyword-then-alphabet construction fills each of the 25 I/J-normalized letters exactly once. The preparation scan inserts precisely the required separators and padding. Position lookup identifies the exact rule for each pair, and modulo arithmetic implements wraparound. Concatenating those encodings in order gives the specified ciphertext.
Watch out. This task inserts separators between all adjacent equal original letters, not merely equal letters within an existing pair. Normalize J before checking repeats. Do not include punctuation in the encoded text. A repeated Q uses Z, and an unmatched final Q is padded with Z.
Commented C++17 solution
An independently written complete program with standard headers.
#include<array>
#include<iostream>
#include<string>
using namespace std;
int main(){
string keyword,message;
getline(cin,keyword);
getline(cin,message);
string square;
array<bool,26>used{};
auto addLetter=[&](char letter){
if(letter<'A'||letter>'Z'){
return;
}
if(letter=='J'){
letter='I';
}
if(!used[letter-'A']){
used[letter-'A']=true;
square+=letter;
}
};
for(char letter:keyword){
addLetter(letter);
}
for(char letter='A';letter<='Z';letter++){
addLetter(letter);
}
array<int,26>position{};
for(int i=0;i<25;i++){
position[square[i]-'A']=i;
}
string clean;
for(char letter:message){
if(letter>='A'&&letter<='Z'){
clean+=letter=='J'?'I':letter;
}
}
string prepared;
for(int i=0;i<static_cast<int>(clean.size());i++){
if(i>0&&clean[i]==clean[i-1]){
prepared+=clean[i]=='Q'?'Z':'Q';
}
prepared+=clean[i];
}
if(prepared.size()%2==1){
prepared+=prepared.back()=='Q'?'Z':'Q';
}
for(int i=0;i<static_cast<int>(prepared.size());i+=2){
int first=position[prepared[i]-'A'];
int second=position[prepared[i+1]-'A'];
int rowA=first/5;
int columnA=first%5;
int rowB=second/5;
int columnB=second%5;
if(rowA==rowB){
columnA=(columnA+1)%5;
columnB=(columnB+1)%5;
}
else if(columnA==columnB){
rowA=(rowA+1)%5;
rowB=(rowB+1)%5;
}
else{
// Opposite rectangle corners: keep rows and exchange columns.
int savedColumn=columnA;
columnA=columnB;
columnB=savedColumn;
}
if(i>0){
cout<<' ';
}
cout<<square[5*rowA+columnA]<<square[5*rowB+columnB];
}
cout<<'\n';
}