CS50 Week 1: Walkthroughs

The walkthroughs start off simple then quickly become challenging.

Hello(c)

How do you create a program that prints to the terminal window when run? Zamyla Chan walks us through our first challenge.

~/workspace/pset1/ $ ./hello 
Hello, world!

Some things to note here are the “int” part of “int main(void),” which is saying “hey at the end of the program i’m returning an integer.” Remember this means you actually have to return some value yourself within the program. Zero is the common value for a successfully run program. You don’t actually see the integer returned, although linux does save this value known as an “exit code.” You can see the value by echoing it out. The special syntax for the previous exit code is “$?.” Here is what that looks like:

~/workspace/pset1/ $ ./hello 
Hello, world!
~/workspace/pset1/ $ echo $?
0

Sometimes the host environment has a different exit code. In this case you can use the EXIT_SUCCESS macro which figures out what the environment’s success code is, and becomes that integer constant.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
 printf("Hello, world!\n");
 return EXIT_SUCCESS;
}

Keep in mind EXIT_SUCCESS is a utility in “stdlib.h” so you have to include that library to use it.

The first include at the top, “stdio.h,” allows me to use the printf function. This is what allows me to show text in the terminal window. If I ran printf with just “Hello, world” there would not be a line break at the end which is a formatting problem. The “\n” solves this problem since it represents a line break. This is called an escape sequence. There are many types of escape sequences for tabs, newlines, and even alerts (beep noises). Just to give some credit to the people who made C, understand the “\n” isn’t actually a line break but a sort of wrapper that figures out the ascii value your system uses for a line break. So maybe “\n” on your system is the ASCII value 0x0a, C will take “\n” and make it that ASCII value, and if you sent it to another computer with a different host environment, it would figure out on the other end. Subtle but important for portability.

Mario, less comfortable

The goal is to take the user’s input from the CL (command line), and print a Mario Brothers style half pyramid.

This challenge helped me understand why a do while loop is an elegant method of validating user input. Also notice how CS50 goes from hello world to something much more challenging? I felt pretty good about this one from the start, so I was able to write this fairly quickly. Under an hour give or take.

~/workspace/examples/ $ ./mario_less 
Enter a number between 0 and 24: 4
   ##
  ###
 ####
#####
~/workspace/examples/ $

Because this program begins with user input, we know the input has to happen at least once before we continue. So the do while loop is elegant in how it allows something to happen after the do statement at least once with no condition attached, then afterwards starts up a while loop that checks a condition, in this case the user’s input.

A simple while loop would require a condition before any input, which you would have to arbitrarily create to be false before user input, then check the user input and change the arbitrary value to true. Not very elegant at all compared to the do while loop.

// some pseudo code showing user input with a while loop

int height = -1;
int spaces, hashes;

while (height < 0 || height > 23)
{
    height = get_int("Enter a number between 0 and 24: ");
}

I tried to keep the functions nice and tidy so there wouldn’t be any nested for loops. It turns out because of this abstraction the next challenge was very simple to implement.

Mario, more comfortable

Because this challenge builds off of the previous one, it brings up an important lesson, which is why programs built using tidy, encapsulated functions can be easier to modify. This challenged me to create the full Mario Brothers pyramid

Since I encapsulated printing hashes and n spaces I only needed to print 2 spaces and run the print_hashes function a second time.

Creating your own functions in C can be done by declaring and defining the function body at the top before main, or how i’ve done it, which is declaring the function and arguments at the top and defining the body of the function below the main program.

Note that you don’t actually have to put the argument names when declaring the function, only the argument types are required. Example:

void print_spaces(int);
void print_hashes(int);

Totally valid.

Greedy

This was fairly easy to figure out using while loops, but challenging using the modulo operator. Greedy challenges us to figure out the least number of coins to return based on a dollar amount given by the user.

While Loop Version:

First we take the user’s input into a variable that is of type float. So long as the user inputted a number greater than 0, we proceed.

I originally thought the user input needed to be rounded, multiplied by 100 and stored in a variable of type integer. Turns out, after playing around in a cloud based repl,  the round function wasn’t doing anything I actually needed.

I’ve found using a repl really helpful for testing small pieces of code.

It’s important to understand what happens when a float is stored in a variable of type integer. This is known as type casting, when you take a variable of some data type and save it in another. In my case i’m doing an implicit conversion or standard conversion as opposed to explicit, which would look more like this:

change = (int) user_input * 100;

Let’s say the user inputted 1.86, and we want to make it an integer because floating point arithmetic is not precise for our needs due to rounding errors.

Casting a float to an int is like putting that float in a guillotine, because it just chops off or truncates whatever is on the right side of that decimal point. Before we chop that side off we want to bring whatever is over there 2 decimal points deep and push it over to the left of the decimal. That is why we multiply by 100.

1.86 enter the guillotine!
.86 was cut off!
you are left with 1
---------------------------
1.86 * 100 = 186.00
Enter the guillotine!
.00 was cut off!
you are left with 186

186 is now in the variable change

So now we have our integer and it’s time to start collecting coins. We have a declared variable already called num_of_coins, so we start with 0 coins.

In this case we start with the largest possible coin and test to see if the change variable is greater than or equal to the coin value. First up is the quarter

is 186 (change variable) greater or equal to 25
yes
ok, subtract 25 and add one to the num_of_coins(1)
now loop back and test the change variable again

is 161 (change variable) greater or equal to 25
yes
ok, subtract 25 and add one to the num_of_coins(2)
now loop back and test the change variable again

So we do this until it isn’t true. Then change pass through each while statement testing smaller and smaller coins until the change variable is zero.

Finally we print out the num_of_coins to complete our challenge.

Modulo Version:

The modulo version is confusing to me because I don’t have a long running history using this operator. It wasn’t something I was taught in school like plus, minus, multiply, and division operators. The idea is modulo will return the remainder of 2 numbers that are divided.

5 / 2 = 2.5 (division)
5 % 2 = 1 (modulo)

2 + 2 = 4
2 can't go into 5 anymore so 
5 - 4 = 1

Frst we do some slick tricks on our num_of_coins variable

num_of_coins += change / 25

Taking our original example amount of 186 for the change variable, and let’s start with num_of_coins as zero.

0 += 186 / 25

186 divided by 25 is 7.44, but we are dealing with integer data types, which means the guillotine is going to truncate anything on the right side of the decimal. In truth we really don’t need those numbers anyway, we are asking “how many times can this number give me a quarter?” The answer isn’t 7.44, it’s just 7. We can get 7 quarters. Finally we add that to num_of_coins

num_of_coins += 7
num_of_coins is now 7!

num_of_coins = num_of_coins + 7;
num_of_coins is now 7!

The addition assignment operator += is a quicker, cleaner way to add something to a variable. Remember we don’t want to lose whatever is in that variable. As it continues down the num_of_coins needs to remember what value it has already from previous coins.

Finally to reduce the change variable we use the modulo operator. So no loop required here, this is a one shot operation. Modulo, in the case of a quarter, is going to say if I divide change (186) by 25, don’t give me 7.44, just hit that number with as many quarters I can get out of it, and return back whatever was left over. So we can get to 175 in quarters, which leaves us with:

186 - 175 = 11

Now change is instantly 11, will pass on and attempt the same expressions but with 10 (dimes), and so on until change is 0.

Credit

Run a checksum on the user input and determine what type of credit card they’ve inputted if the checksum passes. Sound complicated? It is. Programming in some situations is more like solving a puzzle than just going through some task list of what to code. I studied other students code to eventually create my own interpretation that made me comfortable.

Unfortunately the code is confusing to look at now. It’s been a little over a week since I wrote this program. I guess I should work on comments to help me I have to explain them in the blog.

We start off declaring the long long data type. In C you have to think about the data type being used when dealing with big numbers. Our CC numbers might go beyond what an int can handle and give us weird results.

You can take a look at all the data types here. The wiki page also includes all the printf format specifiers, for example long long is going to be %li instead of the int type %d.

I’ve created 3 long long types because user_input will be tested in two different ways and I like naming my variables things that make sense to me when I come back days later to read it. I am sure this has been done using only 1 long long variable, however this worked and i’m well aware there are better ways to write a program like this!

A checksum is the what you get after running some algorithm and a programmer can create this unique value which others can use to test on their computers, making sure no one has altered the code in any way, like after you’ve downloaded a program for example.

A super simple example is let’s say I have the number 1005. If the algorithm, or cryptographic hash function in this case, is just to add up each digit from left to right I would end up with:

1 + 0 + 0 + 5 = 6

checksum value is 6

Now could I change this number, and still get 6? Yes I could just move the 1 or the 5 to a different position like this:

0 + 1 + 0 + 5 = 6
checksum is still 6. You've been hacked!

Imagine this was code that was changed by a hacker to watch everything you typed. You’d have no idea because the checksum would be the same.

How could I make this harder to crack? Maybe add a rule to introduce a letter for each digit if greater than zero:

1 + 0 + 0 + 5 = 6
a + 0 + 0 + e = a00e

combine both results
a00e6

// lets try to hack it now
0 + 1 + 0 + 5 = 6
0 + a + 0 + e = 0a0e

combine both results
0a0e6
HACK FAILED!

Now if I wrote a huge program, and ran this algorithm, i’d have a unique checksum that I could maybe post on my website, and if anyone downloaded my program they could run a test to see if they get the same checksum, otherwise the code was tampered with and could be malicious!

There are more secure checksum algorithms like the one in this credit card challenge.

To validate the credit card we first have to:

  1. start from the second-to-last digit
    1. multiply every other number by 2
    2. take those products and add them together
  2. start from the last digit
    1. get the sum of adding every other digit
  3. Add together the sums of step 1 and step 2
  4. Determine if last digit is 0. If true than the number is valid

If you look at the github gist of my code i’ve created a while loop on line 30. This keeps running while cc_num_test_1 is greater than zero. I created separate variables to hold each individual number that was being calculated, and picked apart the user’s credit card by removing each digit off the end of the credit card. Using the modulo operator it’s easy to get the value at the end by doing {cc number} % 10.

example:

12345 % 10 = 5

Getting to the next to last digit is easy by dividing by 10. Since the number is of type integer this operation just chops off the last number, in this case 5 is chopped off so we’re left with 1234, which we can just modulo like the first expression.

example:

// Keep in mind 12345 is of type int
12345 / 10 = 1234

// Then we can use the modulo operator on the result
1234 % 10 = 4

Looking back I really wish I used a repl (read – eval – print – loop) more often.

Sometimes the answer is really simple but while coding you get wrapped up in a line of thinking that is overly complicated. Your mind is running on all cylinders trying to prepare for a complex series of calculations when it’s much more simple in reality.

Here is a perfect example:

// This was on line 43 of my credit program
sum_of_n2_products += (n2_t2 - (n2_t2 % 10)) / 10;

// I changed it to this which was all that I needed
sum_of_n2_products += n2_t2 / 10;

I won’t go into every line of code, but one other challenge I had in this part of the cc number test was on line 39:

if ( (n2 * 2) > 9)

if the second to last numbers, multiplied by 2, were double digits then I had to break those up into their individual values and add those to the total sum. For example if somewhere in the cc number I encountered a 6, than multiplying that by 2 would give me 12, and from the challenge spec I can’t just add that to the sum, I have to add the 1 and the 2 separately.

Part 2 of the challenge was to figure out what type of credit card the person had entered if it was a valid card starting on line 56:

if ( (sum_of_n1 + sum_of_n2_products) % 10 == 0)

This won’t run if the card is invalid. Looking back now it may have made more sense to create a conditional within a more readable named variable:

bool valid_cc =(sum_of_n1 + sum_of_n2_products) % 10 == 0;

if (valid_cc);

I used this kind of writing when creating boolean conditions for each card type. Since you have to keep the numbers within certain bounds, and there are multiple bounds in some cases, it’s nice to separate the complex conditions from the actual logic.

example:

amex = 
 (cc_num_test_2 >= 340000000000000 && cc_num_test_2 < 350000000000000) || 
 (cc_num_test_2 >= 370000000000000 && cc_num_test_2 < 380000000000000);
 
 if (amex)
 printf("AMEX\n");

Just to be clear about the conditions, if I needed a number to always start with the digits 3 and 4 and I was given this cc number how could I express that in a condition?

The number has to be equal to or greater than 34000… and less than 35000…

since 35999… + 1 would give me 36000… that breaks the rule, so we set a condition to guard that from being allowed.

In the case of amex I also have to do this with numbers starting with 37 or 38, so I used the logical OR operator and add the second set of conditions.

Notice the line breaks, this allows the code to not run on which to me looks more difficult to understand.

Final Thoughts

Reviewing this code has made me realize there were probably better ways to have coded these solutions up. For me, at this point, the biggest observation is a lot of code I wrote and went back to was hard to understand. If I had wrapped pieces of code in readable functions, with comments I think that would definitely improve my ability to return to code and understand what is going on. Maybe main is like “the main idea” and you make a bunch of functions describing what is happening in a readable way.

Leave a Reply

avatar
  Subscribe  
Notify of