How I REACTO to Algos: Caesar Decipher

How I react to algos

It is finally time to decipher the Caesar Cipher.
First, here's a quick reminder of what the Caesar Cipher is, from 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.

In the last article we explored the Caesar Cipher and created a function to encrypt messages suing a secret key. In this article we will decipher an encoded message. After this we will be able to encrypt and decrypt using the Caesar Cipher, opening up some more avenues of exploration. Before we go any further, I'd like to point out my previous articles in this REACTO series:

• Caesar Cipher
• Tournament Winner
• Pig Latin
• First Double

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

Okay, you know what to do now.

The Prompt

Create a function that will receive a string secret and a key number as input and return a decoded version of the secret. A secret is decoded by replacing each letter in the secret with the letter that is a specified number (the key argument) of letters ahead of it in the alphabet. When shifting, if the selection goes beyond the last letter of the alphabet you should continue counting from the first letter of the alphabet. Decoded messages should be returned in all upper case.

R: Restate the prompt

I worded the prompt similarly to the previous prompt for Caesar Cipher because the goal is nearly identical. The solution should be very similar so let's just jump right into it. First, I am restating this prompt, again reflecting the restatement of the last prompt. Except this time we know that the function may receive a string containing non-letter characters which must remain unaltered, and the input string may be in either lower or upper case.

/* 
R: Restate

Create a function that takes two args: a string and a number.
Return an decoded version of the string in all upper case.
In order to decode the string, each letter needs to be unshifted by the number argument.
While unshifting, if we need to go right of the last letter in the alphabet we should wrap to the first letter of the alphabet.
Non-letter characters should not be altered.
*/

E: Examples

To test this function we are going to use the secrets generated in the previous article, Caesar Cipher. Those secrets will now be our test inputs and the decoded messages will be the expected outputs.

sample input

// example 1

> message = "QEB NRFZH YOLTK CLU GRJMBA LSBO QEB IXWV ALD";
> key = 3;

> caesarCipher(message, key);

THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG


// example 2

> message2 = "OHCL FVB LCLY OLHYK VM AOL IFGHUAPUL NLULYHSZ WYVISLT?";
> key2 = 19;

> caesarCipher(message2, key2);

Have you ever heard of The Byzantine Generals problem?


// example 3

> message3 = "YMJD XFB FGTZY 5 BTQAJX HNWHQNSL YMJ KNJQI!";
> key3 = 99;

> caesarCipher(message3, key3);

They saw about 5 wolves circling the field!

A: Approach

Time to plan an approach to solving the prompt. This is going to very similar to our approach to the caesarCipher problem, except we traverse the alphabet in the opposite direction using the key.

When we previously encoded the message THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG with a key 3 we got the secret string QEB NRFZH YOLTK CLU GRJMBA LSBO QEB IXWV ALD. Thus, we should now be able to decode the secret QEB NRFZH YOLTK CLU GRJMBA LSBO QEB IXWV ALD with the same key of 9 and get back the string message THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG. This is our goal.

First, we can lay out the first steps:

/*
A: Approach

- create function caesarDecipher(secret, key)
*/

We know that we should return a string in all upper case, and that the input string may be in any case. I would want to convert the input string to upper case before iterating over it. We are also going to use a string constant to hold all of the letter of the alphabet in order. This string should already be in all upper case to make comparisons simpler. Before iterating over the secret string we should set up an accumulator to build up the decoded message.

When iterating over the string the algorithm needs to visit each character of the secret in order, starting from the 0 index. We can use a for loop limited to the length of the string, just as we did for the cipher function. In each loop, we should declare a constant for that current character of the string secret and check if it is a letter. If it is not a letter it will be added to the decoded message string, and if it is a letter it will need to be decoded first and then added to the message string.

If the current character is a letter get the index of it in the constant string alphabet. This letter will then be replaced with another letter of the alphabet that is key letters ahead of it. We will also wrap from letter Z to letter A when the key requires we go beyond the index of 25, the last index of the alphabet. Wrapping can be acheived by getting the remainder of the sum of the current index divided by 26. 26 because that is the number of letters in the alphabet, and will eb the length of the alphabet string.

To clarify the point on wrapping; the position of the letter X is 23 and, for example, the key is 5 then the position of the decoded would be 28. There is no index past 25, though. That's why we need to wrap, and we can do that by adding the index of the current character to the key number. That sum may be divided by 26, the total length of the alphabet, to give us a remainder. Whatever that remainder number is will be the location of the decoded letter:

• letter X is at index 23
• index 23 + key 5 = 28
• and the remainder of 28 / 26 = 2
• the letter at index 2 is C

Once the replacement letter, or the decoded letter, is found it will be added to the decoded message string. After every character of the input string has been visited the decoded message string can be returned. The end!

Now it can be added to a comment and then we can add that comment into our fucntion!

/*
A: Approach

- create function caesarDecipher(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:
--- add the key value to the current character's index to get the index of the substitute character (decoded character)
--- IF the index for the substitute character is greater than 26:
---- the value for the substitute's index should be updated to be the remainder of this index and 26
--- get the substitute character at this new index from the alphabet constant and add it to the decoded message
-- ELSE if character is not a letter, add it to the decoded message without change
- return the decoded message
*/

C: Code

I'm going to drop the approach comments into the function and use that as my guide.

// - create function caesarDecipher(message, key)
function caesarDecipher(secret, shift) {
  // - create constant for alphabet characters, all caps
  let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

  // - create variable for the return string value (encoded message)
  let message = "";

  // - convert input string to upper case
  secret = secret.toUpperCase();

  // - iterate over input string
  for (let i = 0; i < secret.length; i++) {
    // -- create constant for the current character
    let char = secret[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) {
      // --- add the key value to the current character's index to get the index of the substitute character (decoded character)
      let newPos = pos + shift;

      // --- IF the index for the substitute character is greater than 26:
      if (newPos >= 26) {
        // ---- the value for the substitute's index should be updated to be the remainder of this index and 26
        newPos = newPos % 26;
      }

      // --- get the substitute character at this new index from the alphabet constant and add it to the decoded message
      let newChar = alphabet[newPos];
      message += newChar;

      // -- ELSE if character is not a letter, add it to the decoded message without change
    } else {
      message += char;
    }
  }
  // - return the decoded message
  return message;
}

Let's note the use of indexOf() which returns -1 if the character is not found in the target string. Also, we are checking if the index is over 26, but we don't need to do that. Even if the number is below 25 and we use the modulo operator to get the remainder with 26 it will simply return the same index. For example, if the new index position is 5, the result fo 5 % 26 will be 5. Therefore, the conditional checking if the new index is over 26 is unnecessary. I will include that change below. Here's the code without the comments:

function caesarDecipher(secret, shift) {
  let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  let message = "";
  secret = secret.toUpperCase();
  for (let i = 0; i < secret.length; i++) {
    let char = secret[i];
    let pos = alphabet.indexOf(char);
    if (pos > -1) {
      let newPos = (pos + shift) % 26;
      let newChar = alphabet[newPos];
      message += newChar;
    } else {
      message += char;
    }
  }
  return message;
}

T: Test

Now for the tests!

Here is a Codepen with the function in the JS tab on the left and the results on the right. Feel free to play around with the code and explore.

O: Optimize

Nothing more to add here that wasn't covered in caesarCipher algo. Since we need to visit each character in the input string the time complexity will remain O(n) and so will the space.

And that is the last step! If you have any questions or suggestions, please leave a comment below!

What's Next?

Well, now that we can encode and a decode a message we should build an app that can do this for others!! Well, luckily I have already put together this app last summer when I first came across the Caesar Cipher. Back then I went about it the opposite of how we did in this series, so I will be updating the functions there to reflect these updates. By the time you visit this link, it should already be updated. And yes, I did spell cipher with a y a bunch of times. I think I'll stick with cipher though!

am-hernandez.github.io/caesarCipher

Visit the CaesarCipher app here to share secret messages with friends!

Look out for a follow-up where I will walk you through creating this app from these last two algos

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 if you'd like to see more content like this as I post about my explorations into the world of web development. I'll see you around!