How I react to algos
Today we are going to go over the Caesar Cipher. Or cypher... Or cipher? 🤔
What is the Caesar Cipher anyway? Well, I'll let Wikipedia do some explaining on that matter:
In cryptography, a Caesar cipher ... is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence.
Our goal will be to encode a message using this cipher! Before we go any further on this algo, I'd like to point out my previous articles in this series:
Now, a quick recap on how we will get to our solution using REACTO.
This is REACTO
REACTO is an acronym that represents the method we will use in solving this problem. As a reminder, these are the steps:
- R: Restate
- E: Example
- A: Approach
- C: Code
- T: Test
- O: Optimize
🏁 Let's get started!
The Prompt
Create a function that will receive a string message and a key number as input and return an encoded version of the message. A message is encoded by replacing each letter in the message with the letter that is a specified number (the key argument) of letters before it in the alphabet. When shifting, if the selection goes beyond the first letter of the alphabet you should continue counting from the last letter of the alphabet. Encoded messages should be returned in all upper case.
R: Restate the prompt
Here's where we can make note of the prompt and restate it in our own own words. I actually worded the prompt above so I will just word it differently below in the way I normally would.
/*
R: Restate
Create a function that takes two args: a string and a number.
Return an encoded version of the string in all upper case.
In order to encode the string, each letter needs to be shifted by the number argument.
While shifting, if we need to go left of the first letter in the alphabet we should wrap to the last letter of the alphabet.
*/
Clarifying questions:
Q: Might the function receive non-letter characters?
A: Yes, the function may receive non-letter characters. Only letters will be shifted, keep other character in places.Q: Will the input string always be all caps?
A: The input string may be in lower or upper case or a mix of both.
Okay, so that's cleared up and will be added to the restatement of the prompt in our notes:
/*
R: Restate
Create a function that takes two args: a string and a number.
Return an encoded version of the string in all upper case.
In order to encode the string, each letter needs to be shifted by the number argument.
While shifting, if we need to go left of the first letter in the alphabet we should wrap to the last letter of the alphabet.
Non-letter characters should not be altered.
*/
E: Examples
In this section we will need to create some examples of the expected return values. Examples should be provided and we can always add more for clarification. We'll pull the first example from that same Wikipedia article on Caesar Cipher.
// example 1
> message = "THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG";
> key = 3;
> caesarCipher(message, key);
QEB NRFZH YOLTK CLU GRJMBA LSBO QEB IXWV ALD
// example 2
> message2 = "Have you ever heard of The Byzantine Generals problem?";
> key2 = 19;
> caesarCipher(message2, key2);
OHCL FVB LCLY OLHYK VM AOL IFGHUAPUL NLULYHSZ WYVISLT?
// example 3
> message3 = "They saw about 5 wolves circling the field!";
> key3 = 99;
> caesarCipher(message3, key3);
YMJD XFB FGTZY 5 BTQAJX HNWHQNSL YMJ KNJQI!
We could come up with many examples, but this should be good for now. We can see that the spacing and punctuation are preserved.
A: Approach
Before coding it will be best to think through an approach to finding a resolution. First step is definitely going to be creating the function that takes two arguments. What else?
I will write out the approach in a comment below the restatement of the prompt. You might find that you write your approach and then edit it a few times before moving on to the next step of coding your solution.
In the function we will want to create a string that holds every letter of the alphabet in order and in all caps.
/*
A: Approach
- create function caesarCipher(message, key)
- create constant for alphabet characters, all caps
*/
Making the alphabet upper case will make it easier to match the letters in the message. Even if the letters in the message were lower case, we will end up converting these letters to upper case before iterating over the message string. We should also set up an accumulator to form the encoded message as we iterate over the input string.
/*
A: Approach
- create function caesarCipher(message, key)
- create constant for alphabet characters, all caps
- create variable for the return string value (encoded message)
- convert input string to upper case
*/
This brings us the what I was alluding to earlier, we need to iterate over the input string. With each iteration we should get the current character of the input string and check if it is a letter by comparing it to the alphabet constant. If the character is in the character constant then it is a letter. If the character is not a letter we should just add it to the encoded message and move on to the next character in the input string. If the character is a letter we will need to do more work.
/*
A: Approach
- create function caesarCipher(message, key)
- create constant for alphabet characters, all caps
- create variable for the return string value (encoded message)
- convert input string to upper case
- iterate over input string
-- create constant for the current character
-- check if current character is a letter
--- if character is not a letter, add it to the encoded message without change
--- else if char is a letter ....?
*/
What should you do if a character is a letter? You should get the index of that letter in the alphabet and then combine it with the input key number. Ok, so we get the index of the current letter, but how do we use the key value that was the second argument to the function?
The key is the shift number, and the prompt states we move down the alphabet key number of times. If we have the key 3 and the current character is D, then the encoded letter should be A. The character D is the fourth letter of the alphabet and so is at its index 3. With a key of 3, we can see that 3 - 3 = 0, and that the letter at index 0 is A. So D would be A if the key is 3.
Below, you can see that if you rotate the cipher string left by 3 you will end up with the plain alphabet. That's like calling .shift() three times on cipher if it was an array, and adding the shifted letters to the end of the same array as they come off the front.
┌────────┬─────────────────────────────────────────────────────┐
│ plain │ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z │
├────────┼─────────────────────────────────────────────────────┤
│ cipher │ X Y Z A B C D E F G H I J K L M N O P Q R S T U V W │
└────────┴─────────────────────────────────────────────────────┘
The cipher is created by unshifting the plain alphabet and the alphabet is recreated by shifting the cipher text.
Let's get back to the code! We know we need to subtract the key from the current index of the current character but what if we generate a negative number for the new index? In order to handle these cases we need to consider the amount of letters in the alphabet. There are 26 letters in the alphabet, so the indices range from 0-25. If we go below 0 we will need to make sure we can wrap back around the other end of the alphabet. If our starting position is the 0 index and the key is 3, our new position will be at -3. Since the new position is below 0 we know that we must count back from the last index, 25, three times. If we do that it will make the new position 22, or letter W, which is one less index than we intend. That's because there are 26 letters but 25 indices, since we start counting indices at 0. So we should add a 1 to the new position if it is below zero, then get the remainder from dividing this new position by 26. The remainder number will be negative so we can add that to the number of the last index, 25, to get to the updated new position of 23, or the letter X.
/*
A: Approach
- create function caesarCipher(message, key)
- create constant for alphabet characters, all caps
- create variable for the return string value (encoded message)
- convert input string to upper case
- iterate over input string
-- create constant for the current character
-- check if current character is a letter and get the index of that letter in the alphabet
--- if character is not a letter, add it to the encoded message without change
--- else if character is a letter, subtract the key value from its alphabet index to get the index of the substitute character (encoded character)
---- if the new index is less than 0, the value should instead be the value of the remainder from new index +1 divided by 26 plus 25
*/
The last step in our approach would leave us with a negative number if the new index was below 0 and performed a modulo operation for the remainder. So if we add that negative remainder to 25 (number of indices in alphabet), we will get the appropriate letter by counting backward from the last index. This way, no matter how large the key is we will still get to our letter. In programming we won't actually have a letter wheel to rotate so we need to consider the 0th index and wrapping!
Once we have this new index position we can grab the corresponding letter from the alphabet and add it to the encoded message we will be returning at the end of the function. Then we may return the encoded message and be done!
This is the updated approach:
/*
A: Approach
- create function caesarCipher(message, key)
- create constant for alphabet characters, all caps
- create variable for the return string value (encoded message)
- convert input string to upper case
- iterate over input string
-- create constant for the current character
-- check if current character is a letter and get the index of that letter in the alphabet
-- IF character is a letter:
--- subtract the key value from current character's index to get the index of the substitute character (encoded character)
--- IF the index for the substitute character is less than 0:
---- the value for the substitute's index should instead be 25 plus the remainder of this index+1 and 26
--- get the substitute character at this new index from the alphabet constant and add it to the encoded message
-- ELSE if character is not a letter, add it to the encoded message without change
- return the encoded message
*/
C: Code
Time to code! 🧑💻
This has been a very long article yet our approach seems so simple! Let's put the plan to action by pasting the approach comments into the function to serve as a guide.
if you would like to take some time to figure this out do not scroll any further! Otherwise, keep scrolling when you are ready and prepare for spoilers!
// - create function caesarCipher(message, key)
function caesarCipher(message, key) {
// - create constant for alphabet characters, all caps
const alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
// - create variable for the return string value (encoded message)
let secret = "";
// - convert input string to upper case
message = message.toUpperCase();
// - iterate over input string
for (let i = 0; i < message.length; i++) {
// -- create constant for the current character
let char = message[i];
// -- check if current character is a letter and get the index of that letter in the alphabet
let pos = alphabet.indexOf(char);
// -- IF character is a letter:
if (pos > -1) {
// --- subtract the key value from current character's index to get the index of the substitute character (encoded character)
let newPos = pos - key;
// --- IF the index for the substitute character is less than 0:
if (newPos < 0) {
// ---- the value for the substitute's index should instead be 25 plus the remainder of this index+1 and 26
newPos = 25 + (newPos + 1) % 26;
}
// --- get the substitute character at this new index from the alphabet constant and add it to the encoded message
let newChar = alphabet[newPos];
secret += newChar;
// -- ELSE if character is not a letter, add it to the encoded message without change
} else {
secret += char;
}
}
// - return the encoded message
return secret;
}
And here is the function with no comments:
function caesarCipher(message, key) {
const alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
let secret = "";
message = message.toUpperCase();
for (let i = 0; i < message.length; i++) {
let char = message[i];
let pos = alphabet.indexOf(char);
if (pos > -1) {
let newPos = pos - key;
if (newPos < 0) {
newPos = 25 + (newPos + 1) % 26;
}
let newChar = alphabet[newPos];
secret += newChar;
} else {
secret += char;
}
}
return secret;
}
Let me take a moment to point out the use of the method indexOf(). It returns the value of the index where the character provided in the argument is found in the target string or array. If the character is not in the string the method will return -1. So if the the method returns a number greater than -1 we can assume it is a letter.
T: Test
The exciting part is translating the approach into code. The fun part is testing the code! Let's take a look at the codepen provided below where I laid out some tests.
🎉! We passed our own tests again! Nice! We should now give some thought to optimizing this function.
O: Optimize
Going over the alphabet is always going to be constant no matter the size of the input string, so not worth optimizing that. We do, though, create a new string the same size as the input string but in upper case when we use message = message.toUpperCase(). I can imagine for a very large input string this would be a problem. Maybe we should only check if the upper case version matches without turning the entire string to upper case? I did time the differences for this kind of change and it seemed to go even slower. I will have to look into that some more and talk about it in the follow up to this article or else update this section. We do loop over the entire input string and that will always happen because we need to visit every character in the message. With that, we know the time complexity is going to remain O(n). The space complexity will be the same. So, at the moment there is no optimization obvious to me right now, except making the alphabet constant an object. If you have any input on this please comment below!
What's Next?
Next, we are going to decipher a coded message!
Thank You
Once again, I would like to thank you for taking time out of your day to read this post. Follow me here on dev.to if you'd like to see more content like this. I'll see you around!
Top comments (0)