cs50 Pset2: Caesar’s cipher solution explained
Oh Jeebus, so last week I completed the Mario task which wasn’t actually too hard.
Then I moved on because the Credit task was a little bitch. One of my old school friends Nick has been trying to help me on Linked in (whilst he’s travelling/working remotely LOL) he told me to break the problem down and solve EACH section separately first. I was completely stuck so I decided to leave the “MORE” comfortable tasks and focus on completing the “LESS” comfortable ones first.
So this “LESS” comfortable one also F’d me up. I was on this one for about 2 weeks. I started avoiding it and put it off for a while because I found it too difficult. I finally managed to finish it after crying myself to sleep every night from the feelings of inadequacy (kidding). I ended up researching a shit ton online for the ‘key’ section because I was so stuck.
I will explain in this walkthrough my solutions of how I completed this problem set step by step.
The Caesar Cipher
For pset2 the task was to create a Caesar cipher which would be a Key to ‘encrypting’ a word. It is known as the “shift cipher” as the letters of one alphabet are shifted a number of steps against another alphabet to create a secret message. It was created by Julius Caesar so that he could communicate secretly with his army.
First of all the cs50 provided a walkthrough teaches you how to use a function properly and put in this new ‘argument’ thing I have never seen before…
int main(int argc, string argv)
I was like wtf is this shit? I spent about a week confused despite reading up and watching the lectures multiple times. NOW I finally get it. So the first argument/parameters entered is defining how many strings are in the array of argv. The amount should be an integer NOT a character so you put the int in front to define the type. argv will be the program name that you type into the terminal which would be
so we should be looking for argv which would be the next one in the array which would also be used as the key.
This means we need to re-call for the argv and put it into a new variable to use in the program as the key number. Let’s call this k
int k = argv
This thing is in the requirements we must use an integer as the key so even if a number is inputted it will be considered a ‘string’ because so we need to convert it to a number. This is where atoi comes in.
int k = atoi(argv);
As atoi is declared in stdlib.h library as the HINTS section explains to you in this set I needed to include it into the top bit.
There should also only be 2 arguments in the array anymore would corrupt the algorithm as you only need the program name then the key so I did an if statement argc doesn’t = 2 then the error requirement status would appear stating the format you need to input for the program to work.
if (argc != 2)
printf("Usage: ./caesar k\n");
Then I needed to actually ask for the specific word to encrypt from the user. I did this by using get_string.
string s = get_string("plaintext: "); // get text
Then in order to cypher the word I needed to:
- Iterate through each letter one by one to figure out whether it’s lowercase or uppercase.
- I would do this by converting it into it’s ASCII value and checking if it’s between the smallest & largest value.
- Turning it into ASCII value will also help me shift the alphabet a couple of characters across easier.
- I also needed to keep it within A-Z boundaries so when I shift the whole alphabet and some of them go beyond Z it would need to circle back around and count in from A again.
- I need to minus the lower ASCII value (a or A) so it starts from 0 and goes up to 25 so it’s easier to modulo it by 26
- I need to re-add the ASCII value on to find it’s place in ratio to the beginning of the lower ASCII.
- Any other characters will be kept the same and re-print out without ciphering.
First, I need to figure out each individual character of the string I get from “get_string”.
for (int i = 0, n = strlen(s) ; i < n; i++)
strlen(STRING) is the string length so if n is the total length of the word given then we can iterate n times so that we check out each individual character of the string and then i++ helps move it onto the next one.
Then I needed to figure out whether the individual character is uppercase or lowercase I did so by doing an if statement to show that if it is in between ‘A’ and ‘Z’ or ‘a’ and ‘z’ then it would convert it using the key and print out the new letter. Then the rest that isn’t in the alphabet at all will just print out as it is.
if (s[i] >= 'a' && s[i] <= 'z')
So for this one, I would be doing lowercase as I am using the characters in the context of numerical values it automatically changes to it’s ASCII value. So if I was to move the character say 4 to the right. I would need to add on how many extras it would along in ASCII terms. It usually is the same.
This is where I got REALLY stuck. The pset provided this caesar’s algorithm thing as this equation.
I’m like okay so for my code it would be
new cipher letter = (s[i] + k) % 26
But it wouldn’t work! I decided to put in actual letters to see what would come out. So imagine the key was 2 and I wanted to convert a lowercase b that is 98. We would simply add 98+2 and that would make 100. Then I would 100 % 26 = 22. Um nope.
I did some digging and found this post by Johny Zaguirre and he explains what modulo is in terms of a ‘bucket’. Which was way easier to digest. I was honestly, searching for days what it was. This is what he said…
Imagine we have a bucket that holds 10 cups of water.
Modulo will dump out the water each time it gets full.
If we give module 22 cups, or 22 % 10, modulo will say:
max is 10
filling up 10 out of 10, cup is full so dump it out
filling up 10 out of 10, cup is full so dump it out
filling up to 2...not a full cup so return
giving us 2.
So the same thing in terms of the alphabet is…
2 % 26
fill up to 2...not the entire alphabet so return
giving us 2
Thank you, Johny my gawd. I was racking my brains in trying to understand what purpose modulus had in life. It seems it IS rather useful.
So how would I cipher the text still? Because clearly just doing (text + key) % 26 does not work. Well I’ve somehow worked this out step by step from learning actually what the bloody modulo thing does lol.
I need to work out how many steps from the beginning of the alphabet is the g minus the starting point of the lower ASCII. Then I need to + the key onto that and then modulo that by 26 to make sure we’re not going past the alphabet and that whatever is left over we count back in from the beginning of the alphabet and add on the ASCII equivalent = WTF am I talking about.
Let’s try using some actual letters as examples.
cipher key = 2
letter I want to cipher = g
g in ASCII = 103
we know that g + key = 103 + 2 = 105
What we need to know is where is g in respect to the beginning of the alphabet. As it is lowercase we will be using ‘a’ as the beginning which has the ASCII value of 97 we need to get back to the beginning of the alphabet so we have to minus the ‘a’ to get back to 0.
g - a =
103 - 97 =
Brings us back to the beginning of the alphabet to know how far is g from the start. It is 6 from the start.
Then we want to add the key onto that to see how much it has been shifted.
6 + 2 = 8
Because we want to keep it within the alphabetical boundaries and as there are 26 characters we modulo the 8 by 26. Just incase it goes over 26 we want to know how much extra is left over. If there is any left over then that would be how many characters in from 0 again. Just like how the bucket overflows scenario stated earlier.
8 % 26 = 8
Then because it has been shifted 8 times from the beginning we have to start it off from where ‘a’ starts which isn’t 0 in the ASCII chart. It is 97. So we add that to 97.
8 + 97 = 105
So here you have it…
(s[i] - 'a' + k) % 26) + a
I tried that and it didnt work. FML I think I have to use BODMAS so I rejigged the brackets in the code and it worked HUZZAH!!!!!
(((s[i] - 'a') + k) % 26) + 'a')
This one killed me and I’m only on pset2 of 9. Despite dying over modulo maths I actually love doing this. It’s so fun!
The rest of the code was easy. I printed out the characters that weren’t alphabets and then return 0 and ended the program.
Here is my GitHub which I managed to connect to the cs50 IDE or my code: