Blog

On DJing, music, productivity, professional growth, and personal journey

Super Mario pyramids in Python

Starting this week in the CS50 course, I am now transitioning from C to Python, learning syntax and all the fundamentals of this new language. To kick things off, I have rewritten my very first program, Super Mario pyramids in C. Feels quite nostalgic!

My first attempt in Python looked like this:

def main():
    height = get_height()
    for i in range(1, height + 1):
        print_row(height, i)


# Prompt user for input
def get_height():
    MIN_HEIGHT = 1
    MAX_HEIGHT = 8
    while True:
        try:
            n = int(input("Height: "))
            if MIN_HEIGHT <= n <= MAX_HEIGHT:
                return n
        except ValueError:
            print("Enter a number from 1 to 8")


# Printing columns of the pyramid
def print_row(height, length):
    # Printing the spaces on the left
    spaces = height - length
    print(" " * spaces, end="")

    # Printing hashes for the left side of the pyramid
    print("#" * length, end="")

    # Printing the gap between the sides of the pyramid
    print("  ", end="")

    # Printing hashes for the right side of the pyramid
    print("#" * length)


main()

Then I decided to shrink the print_row function into a single print:

# Printing columns of the pyramid
def print_row(height, length):
    spaces = height - length
    print(" " * spaces + "#" * length + "  " + "#" * length)

But looking at that piece of code, I realised that I don’t need a separate function for this at all. The concatenation of strings within a single print function in Python is amazing!

I’ve also added a condition to check whether the user input is numeric, which might be an overkill for this case, but still good for practice.

So here is my final code:

def main():

    height = get_height()

    # Print pyramid
    for i in range(1, height + 1):
        spaces = height - i
        print(" " * spaces + "#" * i + "  " + "#" * i)


# Prompt user for input
def get_height():

    MIN_HEIGHT = 1
    MAX_HEIGHT = 8

    while True:
        height_str = input("Height: ")

        if height_str.isnumeric():
            height = int(height_str)
            if MIN_HEIGHT <= height <= MAX_HEIGHT:
                return height
            else:
                print("Number must be between 1 and 8, inclusive.")
        else:
            print("Invalid input. Please enter a number.")


if __name__ == '__main__':
    main()

That ending felt a bit weird, but as I’ve learned from Google, it seems like a rule of thumb to finish the program with that line to ensure it can be executed only when the file runs as a script, but not through importing as a module.

 No comments    30   6 d   CS50   Programming   Python

Image filters in C

Another task in the CS50’s problem set 4 was to apply filters to BMP images. Luckily, the core functionality was provided by the staff, so I had to only implement four functions: grayscale, sepia, reflect, and blur.

Let me share my walkthrough for each function.

Grayscale

First, I need to loop through each pixel in the image. I do this by using two nested loops, one for the height and another for the width, to access each pixel individually:

for (int i = 0; i < height; i++)
{
    for (int j = 0; j < width; j++)
    {
        // Pixel processing will be done here
    }
}

For each pixel, I calculate the average value of its red, green, and blue components. I add up the red, green, and blue values and divide the sum by 3.0 to get the average.

int average =
    round((image[i][j].rgbtRed + image[i][j].rgbtGreen + image[i][j].rgbtBlue) / 3.0);

This new average value represents the intensity of the grayscale colour for that pixel.

Why do I divide by 3.0 instead of 3, you may ask? It’s a decision related to data types and precision. When you divide by an integer (e. g., 3), the result will also be an integer, potentially causing a loss of precision in the calculation.

By using 3.0, we explicitly specify that we want floating-point division. In C, if at least one of the operands in a division operation is a floating-point number (like 3.0), the result will be a floating-point number. This is important for obtaining a more accurate average, especially when dealing with colour values that might have fractional parts after the division.

Consider this example:

int result_int = 5 / 3;    // Result is 1, as it's integer division
float result_float = 5 / 3.0;  // Result is 1.66667, as it's floating-point division

Now, I update the red, green, and blue values of the pixel with the calculated average. This makes all three colour components of the pixel equal, resulting in a grayscale effect:

image[i][j].rgbtRed = average;
image[i][j].rgbtGreen = average;
image[i][j].rgbtBlue = average;

And since these steps are inside the nested loop, the entire image is converted to grayscale.

Here is my full code and the result:

// Convert image to grayscale
void grayscale(int height, int width, RGBTRIPLE image[height][width])
{
    // Loop over all pixels
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            // Take average of red, green, and blue
            // Take average of red, green, and blue
            int average =
                round((image[i][j].rgbtRed + image[i][j].rgbtGreen + image[i][j].rgbtBlue) / 3.0);

            // Update pixel values
            image[i][j].rgbtRed = average;
            image[i][j].rgbtGreen = average;
            image[i][j].rgbtBlue = average;
        }
    }

    return;
}
Grayscale filter Original image

Sepia

Similar to the grayscale function, I start by looping through each pixel in the image using nested loops for height and width:

for (int i = 0; i < height; i++)
{
    for (int j = 0; j < width; j++)
    {
        // Pixel processing will be done here
    }
}

I extract the original red, green, and blue values of the current pixel to variables for easier manipulation:

int original_red = image[i][j].rgbtRed;
int original_green = image[i][j].rgbtGreen;
int original_blue = image[i][j].rgbtBlue;

Using specific weighted averages, I calculate new values for red, green, and blue to achieve the sepia tone effect. The formula involves multiplying each original colour component by a specific constant and summing them up:

int sepia_red = (int)fmin(
    255, round(0.393 * original_red + 0.769 * original_green + 0.189 * original_blue));
int sepia_green = (int)fmin(
    255, round(0.349 * original_red + 0.686 * original_green + 0.168 * original_blue));
int sepia_blue = (int)fmin(
    255, round(0.272 * original_red + 0.534 * original_green + 0.131 * original_blue));

Note that I use fmin(255, ...) to cap the values at 255 to ensure they don’t exceed the maximum intensity.

Finally, I update the red, green, and blue values of the pixel with the calculated sepia values:

image[i][j].rgbtRed = sepia_red;
image[i][j].rgbtGreen = sepia_green;
image[i][j].rgbtBlue = sepia_blue;

Here is my full code and the result:

// Convert an image to sepia
void sepia(int height, int width, RGBTRIPLE image[height][width])
{
    // Loop over all pixels
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            // Compute sepia values
            int original_red = image[i][j].rgbtRed;
            int original_green = image[i][j].rgbtGreen;
            int original_blue = image[i][j].rgbtBlue;

            // Calculate sepia values, rounding to the nearest integer and capping at 255
            int sepia_red = (int) fmin(
                255, round(0.393 * original_red + 0.769 * original_green + 0.189 * original_blue));
            int sepia_green = (int) fmin(
                255, round(0.349 * original_red + 0.686 * original_green + 0.168 * original_blue));
            int sepia_blue = (int) fmin(
                255, round(0.272 * original_red + 0.534 * original_green + 0.131 * original_blue));

            // Update pixel with sepia values
            image[i][j].rgbtRed = sepia_red;
            image[i][j].rgbtGreen = sepia_green;
            image[i][j].rgbtBlue = sepia_blue;
        }
    }
}
Sepia filter Original image

Reflect

For this function, I start by looping through each row of the image using a single loop for the height:

for (int i = 0; i < height; i++)
{
    // Row processing will be done here
}

Within each row, I use two pointers, start and end, to swap pixels from the outer edges towards the centre. The start pointer begins at the first pixel (index 0), and the end pointer begins at the last pixel:

int start = 0;
int end = width - 1;

I use a while loop to continue swapping pixels until the start pointer is no longer less than the end pointer. Within the loop, I use a temporary variable to do the swapping:

while (start < end)
{
    // Swap pixels using a temporary variable
    RGBTRIPLE temp = image[i][start];
    image[i][start] = image[i][end];
    image[i][end] = temp;

    // Move the pointers towards the centre
    start++;
    end--;
}

The entire process is repeated for each row of the image, making the reflection apply to the whole image.

Here is my full code and the result:

// Reflect image horizontally
void reflect(int height, int width, RGBTRIPLE image[height][width])
{
    // Loop over all rows
    for (int i = 0; i < height; i++)
    {
        // Use two pointers to swap pixels from the outer edges towards the centre
        int start = 0;
        int end = width - 1;

        while (start < end)
        {
            // Swap pixels using a temporary variable
            RGBTRIPLE temp = image[i][start];
            image[i][start] = image[i][end];
            image[i][end] = temp;

            // Move the pointers towards the centre
            start++;
            end--;
        }
    }
}
Reflected image Original image

Blur

So, first, I create a temporary image to store the blurred result. This temporary image has the same dimensions as the original image:

RGBTRIPLE temp[height][width];

I then loop through each pixel in the original image using nested loops for height and width:

for (int i = 0; i < height; i++)
{
    for (int j = 0; j < width; j++)
    {
        // Pixel processing will be done here
    }
}

For each pixel, I initialize variables to calculate the average colour values: red_sum, green_sum, blue_sum, and count. These variables will be used to accumulate the colour values of neighbouring pixels:

int red_sum = 0;
int green_sum = 0;
int blue_sum = 0;
int count = 0;

Next, I use nested loops to iterate over a 3x3 grid centred around the current pixel. I use row and col to determine the position of the neighbouring pixels relative to the current pixel:

for (int row = -1; row <= 1; row++)
{
    for (int col = -1; col <= 1; col++)
    {
        // Neighboring pixel calculation will be done here
    }
}

For each neighbouring pixel, I calculate its position using newRow and newCol variables. I then check if it is within the bounds of the image. If it is, I accumulate the colour values (red_sum, green_sum, and blue_sum) and increment the count variable:

int newRow = i + row;
int newCol = j + col;

if (newRow >= 0 && newRow < height && newCol >= 0 && newCol < width)
{
    red_sum += image[newRow][newCol].rgbtRed;
    green_sum += image[newRow][newCol].rgbtGreen;
    blue_sum += image[newRow][newCol].rgbtBlue;
    count++;
}

After iterating over the neighbouring pixels, I calculate the average colour values for the current pixel using the accumulated sums and the count of valid neighbouring pixels and use the round function to round the result to the nearest integer:

temp[i][j].rgbtRed = round((float)red_sum / count);
temp[i][j].rgbtGreen = round((float)green_sum / count);
temp[i][j].rgbtBlue = round((float)blue_sum / count);

Once all pixels have been processed and the temporary image contains the blurred result, I copy the contents of the temporary image back to the original image:

for (int i = 0; i < height; i++)
{
    for (int j = 0; j < width; j++)
    {
        image[i][j] = temp[i][j];
    }
}

I must admit, this one was a bit tough, and it took me some time to figure out!

Here is my full code and the result:

// Blur image
void blur(int height, int width, RGBTRIPLE image[height][width])
{
    // Create a temporary image to store the blurred result
    RGBTRIPLE temp[height][width];

    // Loop over all pixels
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            // Initialize variables to calculate the average colour values
            int red_sum = 0;
            int green_sum = 0;
            int blue_sum = 0;
            int count = 0;

            // Loop over neighboring pixels (3x3 grid centered around the current pixel)
            for (int row = -1; row <= 1; row++)
            {
                for (int col = -1; col <= 1; col++)
                {
                    int newRow = i + row;
                    int newCol = j + col;

                    // Check if the neighboring pixel is within the image bounds
                    if (newRow >= 0 && newRow < height && newCol >= 0 && newCol < width)
                    {
                        // Accumulate colour values
                        red_sum += image[newRow][newCol].rgbtRed;
                        green_sum += image[newRow][newCol].rgbtGreen;
                        blue_sum += image[newRow][newCol].rgbtBlue;
                        count++;
                    }
                }
            }

            // Calculate average colour values
            temp[i][j].rgbtRed = round((float) red_sum / count);
            temp[i][j].rgbtGreen = round((float) green_sum / count);
            temp[i][j].rgbtBlue = round((float) blue_sum / count);
        }
    }

    // Copy the blurred image back to the original image
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            image[i][j] = temp[i][j];
        }
    }
}
Blurred image Original image
 No comments    18   6 d   C   CS50   Programming

Volume changing program in C

As I continue learning computer science, here is my walkthrough of week 4’s problem:

Complete the implementation of volume.c, such that it changes the volume of a sound file by a given factor.

The program should accept three command-line arguments. The first is input, which represents the name of the original audio file. The second is output, which represents the name of the new audio file that should be generated. The third is factor, which is the amount by which the volume of the original audio file should be scaled. For example, if factor is 2.0, then your program should double the volume of the audio file in input and save the newly generated audio file in output.

Your program should first read the header from the input file and write the header to the output file.

Your program should then read the rest of the data from the WAV file, one 16-bit (2-byte) sample at a time. Your program should multiply each sample by the factor and write the new sample to the output file. You may assume that the WAV file will use 16-bit signed values as samples. In practice, WAV files can have varying numbers of bits per sample, but we’ll assume 16-bit samples for this problem.

Your program, if it uses malloc, must not leak any memory.

Let me explain what this program does. It’s a simple C program that modifies the volume of an audio file in the WAV format. The user needs to provide three command-line arguments when running the program: the input audio file name, the output audio file name, and a scaling factor for adjusting the volume.

First, I check if the user provided the correct number of command-line arguments. If not, I print a message explaining the correct usage and exit the program with an error code:

// Check command-line arguments:
if (argc != 4)
{
    printf("Usage: ./volume input.wav output.wav factor\n");
    return 1;
}

Next, I open the input (in the read mode) and output (in the write mode) audio files specified by the user. If the input file cannot be opened, an error message is displayed, and the program exits. Similarly, if the output file cannot be opened, I print an error message and exit the program. The third command-line argument is converted from a string to a floating-point number, representing the scaling factor:

// Open files and determine scaling factor:
FILE *input = fopen(argv[1], "r");
if (input == NULL)
{
    printf("Could not open input file.\n");
    return 1;
}

FILE *output = fopen(argv[2], "w");
if (output == NULL)
{
    printf("Could not open output file.\n");
    return 1;
}

float factor = atof(argv[3]);

Here, I copy the 44-byte WAV header from the input file to the output file:

// Copy WAV Header:
uint8_t header[HEADER_SIZE];
fread(header, HEADER_SIZE, 1, input);
fwrite(header, HEADER_SIZE, 1, output);

A me from a week ago wouldn’t know what this is, so let me elaborate a bit more. I use the data type uint8_t to create an array called header that is 44 elements in size. Each element in this array represents one byte of data. The reason I chose uint8_t is because it is an unsigned (meaning it can only represent non-negative values) 8-bit integer data type.

The WAV file format uses bytes to store information in its header. Using an 8-bit data type ensures that each element of the header array corresponds to one byte of data. This is essential for accurately copying the header, as the header size is 44 bytes, so I’ll assign the value of 44 to this global constant HEADER_SIZE.

Next, I declare a variable buffer to hold a single audio sample:

// Create buffer for a single sample:
int16_t buffer;

Notice the int16_t data type here. In digital audio processing, an audio sample represents the amplitude of a sound wave at a specific point in time. The int16_t data type is a 16-bit signed integer, which means it can represent both positive and negative values using 16 bits (or 2 bytes) of storage. And the choice of int16_t corresponds to the standard bit depth used in many audio files, including WAV files.

Now, I need to read audio samples one by one from the input file, multiply each sample by the scaling factor to adjust the volume, and then modify the sample to write it to the output file. For that task, I use a while loop that continues until the fread function returns 0, indicating that there are no more samples to read:

// Modify Volume and Write to Output:
while (fread(&buffer, sizeof(int16_t), 1, input) != 0)
{
    buffer *= factor;
    fwrite(&buffer, sizeof(int16_t), 1, output);
}

Finally, I close both the input and output files to ensure that all changes are saved. The program has now processed the audio file, adjusted its volume, and saved the modified version to a new file.

Here is my final code:

// Modifies the volume of an audio file

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

// Number of bytes in .wav header
const int HEADER_SIZE = 44;

int main(int argc, char *argv[])
{
    // Check command-line arguments
    if (argc != 4)
    {
        printf("Usage: ./volume input.wav output.wav factor\n");
        return 1;
    }

    // Open files and determine scaling factor
    FILE *input = fopen(argv[1], "r");
    if (input == NULL)
    {
        printf("Could not open file.\n");
        return 1;
    }

    FILE *output = fopen(argv[2], "w");
    if (output == NULL)
    {
        printf("Could not open file.\n");
        return 1;
    }

    float factor = atof(argv[3]);

    // Copy header from input file to output file
    uint8_t header[HEADER_SIZE];
    fread(header, HEADER_SIZE, 1, input);
    fwrite(header, HEADER_SIZE, 1, output);

    // Create a buffer for a single sample
    int16_t buffer;

    // Read single sample from input into buffer while there are samples left to read
    while (fread(&buffer, sizeof(int16_t), 1, input) != 0)
    {
        // Update volume of sample
        buffer *= factor;

        // Write updated sample to new file
        fwrite(&buffer, sizeof(int16_t), 1, output);
    }

    // Close files
    fclose(input);
    fclose(output);
}
 No comments    22   7 d   C   CS50   Programming

Rave Podcast 149

The March episode of Rave Podcast is here, and this time we start with banging 140 BPM straight away! A lot of hard grooves in the first half and a cosmic trance towards the end.

Tracklisting:

00:00 David Moleon — Back To Moleon (Original Mix) Transfiguration Recordings
05:14 Introversion — Nostalgia (Original Mix) Arts
07:56 Name_Less, JBILO — Blaze (Original Mix) Tronic
10:04 Sera J — Rainbow (Original Mix) Warg
12:45 Faster Horses — 21 (Original Mix) Dancefloor Impact Research
16:57 Moes — Aftermath (Original Mix) DistroKid
20:02 Regent — Encoder (Original Mix) Mutual Rytm
23:48 Alan Backdrop — Dysfunctional Reality (Original Mix) Not On Label
29:12 Raffaele Attanasio — Aogiri Tree (Original Mix) Mutual Rytm
31:38 Sko Raw — Moe’s Dream (Original Mix) Note Recordings
34:16 Miju — Metatron (Bliss Inc Remix) Headroom Rec
37:50 Dusty Tech, Parsa Jafari — Surafil (Original Mix) The Acid Mind
40:55 Hypnocoustics — Satori In Pokhara (Original Mix) Nano Records
45:20 Kineta — Scorpius (Original Mix) UTE
49:41 Sioc — Eternity (Original Mix) Proxima
53:33 Oprofessionell — Psy-TB (Original Mix) UTE

Runoff, votes program in C

By the end of my second week of learning programming, there was a problem to solve which admittedly took me some time to figure out as the level of complexity from the previous problem jumped quite significantly.

The problem description is pretty lengthy, so instead of writing it all here, let me just put a video walkthrough that explains what needs to be done. They also provided the distribution code that has the main function already pre-written. If you’d like to dive deeper into the problem or perhaps even try solving it yourself, definitely start with that video and the source code.

The task was to complete the six functions named vote, tabulate, print_winner, find_mind, is_tie, and eliminate.

As always, if you are an experienced programmer, your feedback would be appreciated. The whole point of this post is for me to get a better understanding of what I’ve learnt for the past week or so.

Vote

So, the first function, vote, should update the global preferences array to indicate that the voter has that candidate as their preference.

I’ll start with writing a pseudocode:

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    // If candidate name is found and not eliminated, update the voter preference and return true
    // If candidate name not found or eliminated, return false
}

To check all votes, I need to iterate through all candidates using the global candidate_count variable:

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    for (int i = 0; i < candidate_count; i++)
    {
    // If candidate name is found and not eliminated, update the voter preference and return true
    }
    
    // If candidate name not found or eliminated, return false
}

To check whether the candidate’s name matches, I’ll use the strcmp function to compare the string name (which is the input parameter of the vote function) with the name field of the ith candidate struct. And I’ll check whether the candidate is eliminated in the same if statement, like so:

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(candidates[i].name, name) == 0 && !candidates[i].eliminated)
        {
            // Record the vote preference

            return true;
        }
    }

    // Candidate name not found or eliminated, vote is invalid
    return false;
}

The most challenging part for me was to figure out how to record the vote preference, the actual action inside this loop and the sole purpose of this function.

Let me share my thought process. What does ‘record (or update) the vote preference’ actually mean? Well, preferences is a two-dimensional array used to store the voting preferences of each voter. It represents a grid where each row corresponds to a voter, and each column corresponds to a rank of preference for a candidate. The vote function also takes two inputs: voter, which represents the index of the current voter in the array of voters, and ranks, which represents the index of the preference rank for the current candidate.

Putting it all together, it means that for the current voter at index voter, at the given preference rank rank, the candidate at index i in the array of candidates is chosen as the preference. So the final code of this function is the following:

// Record preference if vote is valid
bool vote(int voter, int rank, string name)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(candidates[i].name, name) == 0 && !candidates[i].eliminated)
        {
            // Record the vote preference
            preferences[voter][rank] = i;
            return true;
        }
    }

    // Candidate name not found or eliminated, vote is invalid
    return false;
}

I still wrap my head around this line preferences[voter][rank] = i;, so let me provide additional explanation for future me reading this blog.

Let’s say, we have three candidates named Alice, Bob, and Charlie, indexed as 0, 1, and 2 in the candidates’ array respectively. We also have three voters indexed as 0, 1, and 2 too. And, as an example, let’s say the first voter ranked their candidate preferences in the ballot in the following order: Charlie, Alice, Bob.

Now if we look back at that line of code again, it effectively stores the index of the chosen candidate in the preferences array, like so:

  Rank [0] Rank [1] Rank [2]
Voter [0] 2 0 1

I hope it explains!

Tabulate

The next function, tabulate, should update the number of votes each candidate has at this stage in the runoff. Recall that at each stage in the runoff, every voter effectively votes for their top-preferred candidate who has not already been eliminated.

I’ll start with a pseudocode again to outline the general logic of this function:

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    // Iterate through each voter
        // Iterate through each rank until a valid vote is cast
            // Get the index of the preferred candidate for this rank

            // Check if the preferred candidate is not eliminated
                // Update the vote count for the preferred candidate and break out of the loop
}

So the function iterates through each voter, considering their ranked preferences. For each voter, it iterates through each rank until it finds a valid vote for a non-eliminated candidate. For that purpose, I’ll a basic loop-within-the-loop construction:

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    // Iterate through each voter
    for (int i = 0; i < voter_count; i++)
    {
        // Iterate through each rank until a valid vote is cast
        for (int j = 0; j < candidate_count; j++)
        {
            // Get the index of the preferred candidate for this rank

            // Check if the preferred candidate is not eliminated
        }
    }
}

It seems I’m going to need a new integer variable to store the index of the candidate preferred by the current voter at the given rank, which I could later use to incrementally update the vote count.

And here is the final code for this function:

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    // Iterate through each voter
    for (int i = 0; i < voter_count; i++)
    {
        // Iterate through each rank until a valid vote is cast
        for (int j = 0; j < candidate_count; j++)
        {
            // Get the index of the preferred candidate for this rank
            int preferred_candidate_index = preferences[i][j];

            // Check if the preferred candidate is not eliminated
            if (!candidates[preferred_candidate_index].eliminated)
            {
                // Update the vote count for the preferred candidate and break
                // out of the loop
                candidates[preferred_candidate_index].votes++;
                break;
            }
        }
    }
}

Just to clarify, preferences[i][j] retrieves the index of the candidate preferred by the voter at index i for the current rank j. This index is then stored in the preferred_candidate_index variable.

This line candidates[preferred_candidate_index].votes+ increments the votes field for the candidate with the index preferred_candidate_index. It means that the voter’s vote at the current rank has been cast for this candidate, and we update the candidate’s vote count accordingly.

Print winner

The print_winner should print the winner’s name If any candidate has more than half of the vote, and don’t print anything if nobody has won the election:

// Print the winner of the election, if there is one
bool print_winner(void)
{
    // Check each candidate's votes
    
        // If a candidate has more than half of the votes, they are the winner


    // No winner found, return false
}

So I’ll iterate through each candidate again and check if their votes exceed half of the total votes. To see whether the candidate has the majority of votes, I’ll check if their votes are greater than the half of total voters:

// Print the winner of the election, if there is one
bool print_winner(void)
{
    // Check each candidate's votes
    for (int i = 0; i < candidate_count; i++)
    {
        // If a candidate has more than half of the votes, they are the winner
        if (candidates[i].votes > voter_count / 2)
        {
            printf("%s\n", candidates[i].name);
            return true;
        }
    }

    // No winner found
    return false;
}

Find min

The function should return the minimum vote total for any candidate who is still in the election. For that, I’ll loop through the candidates to find the one who is both still in the election and has the fewest number of votes.

And my first instinct was to write this:

// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
    int min = 0;

    // Loop through each candidate to find the one with the fewest votes and is
    // still in the election
    for (int i = 0; i < candidate_count; i++)
    {
        if (!candidates[i].eliminated &&
            (candidates[i].votes < min || min == 0))
        {
            min = candidates[i].votes;
        }
    }

    return min;
}

It’s only later I realised that this code has a potential flaw that might lead to a wrong outcome in certain cases. Can you guess what it is?

The potential issue in that version is related to the initialisation of the min variable with a value of 0. In some scenarios, the condition //(candidates[i].votes < min || min == 0)// will always be true for the first candidate in the loop, and //min// will be updated to the candidate's votes. This would result in the function returning 0, even though it's not the minimum number of votes any remaining candidate has.

This is pretty obvious now – the min variable should be initialised with a voter_count + 1:

// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
    int min = voter_count + 1;

    // Loop through each candidate to find the one with the fewest votes and is
    // still in the election
    for (int i = 0; i < candidate_count; i++)
    {
        if (!candidates[i].eliminated && candidates[i].votes < min)
        {
            min = candidates[i].votes;
        }
    }

    return min;
}

Here’s an example to compare both versions of the function:

Suppose we have three candidates, and initially, they have the following votes: Candidate A (2 votes), Candidate B (3 votes), Candidate C (1 vote). After some eliminations, only Candidate A and Candidate B remain in the election.

  • In version 1, min is initialised to 0, and the condition (candidates[i].votes < min || min == 0) will be true for the first candidate (Candidate A) with 2 votes, updating min to 2. Therefore, the function would incorrectly return 2 as the minimum number of votes.
  • In version 2, min is initialised to a value greater than the maximum possible votes (voter_count + 1), and the correct minimum number of votes (1 in this case) will be returned. A pretty subtle, but important difference!

The rest of the functions are pretty straightforward, so I’ll just put my final code for each function:

Is tie

// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
    // Loop through each candidate
    for (int i = 0; i < candidate_count; i++)
    {
        // Check if the candidate is still in the election and has a different
        // number of votes than the minimum
        if (!candidates[i].eliminated && candidates[i].votes != min)
        {
            // Not a tie as at least one candidate has a different number of
            // votes
            return false;
        }
    }

    // All remaining candidates have the same number of votes, it's a tie
    return true;
}

Eliminate

// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
    for (int i = 0; i < candidate_count; i++)
    {
        if (!candidates[i].eliminated && candidates[i].votes == min)
        {
            candidates[i].eliminated = true;
        }
    }
}
 No comments    45   14 d   C   CS50   Programming

A substitution cipher in C

To finish off my first week of learning programming, I’ve completed another task which summed up pretty much everything I’ve learned so far about the basics: variables, operators, loops, functions, arrays, and such.

Here is the problem description:

In a substitution cipher, we “encrypt” (i.e., conceal in a reversible way) a message by replacing every letter with another letter. To do so, we use a key: in this case, a mapping of each of the letters of the alphabet to the letter it should correspond to when we encrypt it. To “decrypt” the message, the receiver of the message would need to know the key, so that they can reverse the process: translating the encrypt text (generally called ciphertext) back into the original message (generally called plaintext).

A key, for example, might be the string NQXPOMAFTRHLZGECYJIUWSKDVB. This 26-character key means that A (the first letter of the alphabet) should be converted into N (the first character of the key), B (the second letter of the alphabet) should be converted into Q (the second character of the key), and so forth.

A message like HELLO, then, would be encrypted as FOLLE, replacing each of the letters according to the mapping determined by the key.

Create a program that enables you to encrypt messages using a substitution cipher. At the time the user executes the program, they should decide, by providing a command-line argument, on what the key should be in the secret message they’ll provide at runtime.

Your program must accept a single command-line argument, the key to use for the substitution. The key itself should be case-insensitive, so whether any character in the key is uppercase or lowercase should not affect the behavior of your program. If your program is executed without any command-line arguments or with more than one command-line argument, your program should print an error message of your choice (with printf) and return from main a value of 1 (which tends to signify an error) immediately. If the key is invalid (as by not containing 26 characters, containing any character that is not an alphabetic character, or not containing each letter exactly once), your program should print an error message of your choice (with printf) and return from main a value of 1 immediately.

Your program must output plaintext: (without a newline) and then prompt the user for a string of plaintext (using get_string). Your program must output ciphertext: (without a newline) followed by the plaintext’s corresponding ciphertext, with each alphabetical character in the plaintext substituted for the corresponding character in the ciphertext; non-alphabetical characters should be outputted unchanged. Your program must preserve case: capitalized letters must remain capitalized letters; lowercase letters must remain lowercase letters. After outputting ciphertext, you should print a newline. Your program should then exit by returning 0 from main.

Phew, that’s a pretty bulky description! I’ll start by outlining the big steps I would need to solve the problem as follows:

  1. Get key
  2. Validate key
  3. Get plaintext
  4. Encipher
  5. Print ciphertext

As I’ve just learned, the program can receive command-line arguments, so I can use the main function with two new input parameters: integer argc and array argv. The key that the program should receive is the second word in the command line (after the file name), so keeping arrays’ zero-indexing in mind, I start with this:

#include <cs50.h>
#include <stdio.h>

int main(int argc, string argv[])
{
    // Get key
    string key = argv[1];
}

Now the key is stored in the key variable. Next, I’ll get the key length, which is pretty easy now as I know about the strlen function, and also check whether the length equals 26:

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(int argc, string argv[])
{
    // Get key
    string key = argv[1];

  // Get key length
    int key_length = strlen(key);

    // Check key length
    if (key_length != 26)
    {
        printf("Key must contain 26 characters.\n");
        return 1;
    }
}

I don’t quite like the ‘magic number’ 26 in the if condition, so I’ll move it out as a global constant. I also feel that I need to make the key variable global (though I’m not sure whether it’s a good idea):

#include <cs50.h>
#include <stdio.h>
#include <string.h>

// Constant
const int valid_key_length = 26;

string key;

int main(int argc, string argv[])
{
    // Get key
    key = argv[1];

  // Get key length
    int key_length = strlen(key);

    // Check key length
    if (key_length != valid_key_length)
    {
        printf("Key must contain 26 characters.\n");
        return 1;
    }
}

I guess I could have created a separate function for checking the key length, but would it be worth it given that the whole code is literally just one if and one printf? Let me know in the comments!

Next, I’m going to check whether the key only consists of alphabetic characters, and this is where a separate function definitely should be a good idea. So, I’ll create a function called is_key_alphabetic that can take a string as input and give me a boolean as output – whether the key consists of alphabetical is true or false.

Inside the function, I need a loop that keeps checking the string character by character until it’s not equal to nul, which in plain English means ‘until the end of the word’s length’. You may wonder, why making such an extravagant condition of the loop, and to be honest, it’s just for the sake of exercising. I find it pretty interesting that all arrays in C are ‘secretly’ end with null to indicate the end of the string.

So, here is the first function:

bool is_key_alphabetic(string s)
{
    for (int i = 0; s[i] != '\0'; i++)
    {
        if (!isalpha(s[i]))
        {
            return false;
        }
    }
    return true;
}

Now upon coming back to my program and writing this blog post, I realised that the naming here is a bit messy. I mean, the function is called is_key_alphabetic, whereas inside the loop there is an if statement checking whether a character is not alphabetic, and in that it case returns false, and then the whole function returns true. Apart from the variable name s which I admit isn’t very informative, is there any anything else I could improve here?

In the meantime, I’ll create another function to check for any repeated characters in the key. From a logical perspective, identifying a repeated character should be as easy as checking whether it’s equal to itself. However, in the code, I don’t know a better solution than doing a loop within a loop:

bool is_key_repeated(string s)
{
    for (int i = 0; s[i] != '\0'; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (s[i] == s[j])
            {
                printf("Key must not contain repeated characters.\n");
                return false;
            }
        }
    }
    return true;
}

Once again, upon writing this blog post, I already spotted some things I could’ve done better. For example, including printf in this function probably wasn’t a good idea.

Next, I’ll create another function to encipher plaintext. It seems I need to make some sort of mapping to assign each letter of the plaintext to according letter of the key. And thanks to the previous problem, Scrabble, I now know how to do it!

So, I’ll call the function encipher, which is going to take the input text, iterate through each character, replace it with the corresponding character from the provided key while preserving the case, and then print the resulting ciphertext.

void encipher(string text)
{
    int length = strlen(text);
    for (int i = 0; i < length; i++)
    {
        if (isupper(text[i]))
        {
            text[i] = toupper(key[text[i] - 'A']);
        }
        else if (islower(text[i]))
        {
            text[i] = tolower(key[text[i] - 'a']);
        }
    }
    // Print ciphertext
    printf("ciphertext: %s\n", text);
}

All I need from now is just to get a plaintext input using the get_string function, and then call all three functions I’ve created above in the main function. And so here is my final code:

// A program in C that enables you to encrypt messages using a substitution cipher.

#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>

// Constant
const int valid_key_length = 26;

// Function prototypes
bool is_key_alphabetic(string key);
bool is_key_repeated(string key);
void encipher(string text);

string key;

// Main
int main(int argc, string argv[])
{

    // Check if there's a key provided
    if (argc != 2)
    {
        printf("Usage: ./substitution KEY\n");
        return 1;
    }

    // Get key
    key = argv[1];

    // Get key length
    int key_length = strlen(key);

    // Check key length
    if (key_length != valid_key_length)
    {
        printf("Key must contain 26 characters.\n");
        return 1;
    }

    // Check key contains only alphabetic characters
    if (!is_key_alphabetic(key))
    {
        printf("Key must only contain alphabetical characters.\n");
        return 1;
    }

    // Check key doesn't contain repeated characters
    if (!is_key_repeated(key))
    {
        printf("Key must not contain repeated characters.\n");
        return 1;
    }

    // Get plaintext
    string plaintext = get_string("plaintext ");

    // Encipher
    encipher(plaintext);

    // Print ciphertext
    printf("\n");
    return 0;
}

bool is_key_alphabetic(string s)
{
    for (int i = 0; s[i] != '\0'; i++)
    {
        if (!isalpha(s[i]))
        {
            return false;
        }
    }
    return true;
}

bool is_key_repeated(string s)
{
    for (int i = 0; s[i] != '\0'; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (s[i] == s[j])
            {
                printf("Key must not contain repeated characters.\n");
                return false;
            }
        }
    }
    return true;
}

void encipher(string text)
{
    int length = strlen(text);
    for (int i = 0; i < length; i++)
    {
        if (isupper(text[i]))
        {
            text[i] = toupper(key[text[i] - 'A']);
        }
        else if (islower(text[i]))
        {
            text[i] = tolower(key[text[i] - 'a']);
        }
    }
    // Print ciphertext
    printf("ciphertext: %s\n", text);
}
 1 comment    74   21 d   C   CS50   Programming

Scrabble in C

In the second week of CS50, I was introduced to the notion of arrays and then given the following problem to solve as a practice:

In the game of Scrabble, players create words to score points, and the number of points is the sum of the point values of each letter in the word. For example, if we wanted to score the word “CODE”, we would note that the ‘C’ is worth 3 points, the ‘O’ is worth 1 point, the ‘D’ is worth 2 points, and the ‘E’ is worth 1 point. Summing these, we get that “CODE” is worth 7 points.

Implement a program in C that determines the winner of a short Scrabble-like game. Your program should prompt for input twice: once for “Player 1” to input their word and once for “Player 2” to input their word. Then, depending on which player scores the most points, your program should either print “Player 1 wins!”, “Player 2 wins!”, or “Tie!” (in the event the two players score equal points).

First, I outlined the general steps needed to solve this problem:

  1. Get text inputs from the user;
  2. Calculate the score of each input;
  3. Show the winner.

For the first step, I’ll create two variables named word1 and word2 respectively, and assign each to the value of the respective user input using the get_string function from the CS50 library:

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    // Prompt the user for two words
    string word1 = get_string("Player 1: ");
    string word2 = get_string("Player 2: ");

    // Compute the score of each word

    // Print the winner
}

That was easy. The trickiest part here, of course, is the second step, which is to assign each letter of the alphabet its unique score points value.

Here are the values:

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
1 3 3 2 1 4 2 4 1 8 5 1 3 1 1 3 10 1 1 1 1 4 4 8 4 10

Now that I know about arrays, I can create an array called points with a size of 26 and the type of integer, and assign values as follows:

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    // Prompt the user for two words
    string word1 = get_string("Player 1: ");
    string word2 = get_string("Player 2: ");

    // Compute the score of each word
    int points[] = {1, 3, 3, 2, 1, 4, 2, 4, 1, 8, 5, 1, 3, 1, 1, 3, 10, 1, 1, 1, 1, 4, 4, 8, 4, 10};

    // Print the winner
}

I don’t quite like the length of that like, but it seems there is not much to do about it since all values are set by the rules of the game.

Now that I know a little bit about functions too, I’ll create a separate function for computing the score. This should make the code more efficient and better designed, especially since I need to use it twice for calculating the score for each word.

I’ll call this function calculate_score, with one input parameter of the type of string, and output of integer. I can also straight away create a variable called score with the type of integer, as this is ultimately what I want to get from this function:

int calculate_score(string word)
{
    int score = 0;

    return score;
}

Now, the big question is how to assign each letter a corresponding score value. Well, turns out that every string is basically just an array of characters. Let’s take the word CODE as an example. We can imagine it as an array as follows, keeping in mind the zero-based indexing of arrays, i.e. starting counting from 0:

c word[i]
word[0] = C
word[1] = O
word[2] = D
word[3] = E

Knowing this, I can create a loop to ‘scan’ through the word character by character. For this loop to work, I would to know the length of the word, and luckily such a function already exists in the string.h library and is called strlen:

for (int i = 0; i < strlen(word); i++)
{
}

What I don’t quite like about this loop though, is that every time it works, it makes the function repeat that many times. To optimise this, let me create another variable called len with its value equal to the length of a word, and then use this variable as the condition of the loop:

for (int i = 0, len = strlen(word); i < len; i++)
{
}

Now, how to make the loop ‘know’ which score value corresponds to each letter? There is actually a trick that still blows my mind even after completing this task. Since every character has its numeric value in the ASCII code, we can use this information to ‘offset’ characters from one array to another and this way map them together.

Let’s take the capital letter ‘C’ from the word CODE as I used the example. Its numeric value in ASCII is 67, and the trick is to subtract the value of the letter A, which equals 65. Why A? Because it’s the first letter of the alphabet, and if we subtract it from another letter, we’ll know its place in the array. So 67 – 65 = 2, and that is exactly the index number we need from the points array.

To make it more visual, here is a similar exercise for all letters of the word CODE:

Letter ASCII Index Points
C 67 67 – 65 = [2] 3
O 79 79 – 65 = [14] 1
D 68 68 – 65 = [3] 2
E 69 69 – 65 = [4] 1

... which means the word CODE gives the Scrabble score of 7 (as 3 + 1 + 2 +1), and that is indeed correct. It works like a charm!

To make array indexing a little more obvious, I’ll add it to the score table too:

Letter: 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
Score: 1 3 3 2 1 4 2 4 1 8 5 1 3 1 1 3 10 1 1 1 1 4 4 8 4 10
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

This system doesn’t quite work for the lowercase letters though, because the ASCII values of the lowercase letters are different from the capital letters. However, it simply means that we need to subtract the value of the lowercase letter ‘a’ instead of the capital ‘A’.

So it seems I need an if statement within the loop to calculate the score depending on the case of the letters using isupper and islower functions from the ctype.h library, which I’ll include in the header too:

int calculate_score(string word)
{
    // Keep track of the score
    int score = 0;

    // Compute the score for each character
    for (int i = 0, len = strlen(word); i < len; i++)
    {
        if (isupper(word[i]))
        {
            score += points[word[i] - 'A'];
        }
        else if (islower(word[i]))
        {
            score += points[word[i] - 'a'];
        }
    }
    return score;
}

Since I’m using the points array in this function, I need to move it out from the main’s local scope to the global scope. The rest is easy: all I need to do is to call the function calculate_score (twice, for each word) and then compare players’ scores to determine the winner.

And here is my final code:

#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>

// points assigned to each letter of the alphabet
int points[] = {1, 3, 3, 2, 1, 4, 2, 4, 1, 8, 5, 1, 3, 1, 1, 3, 10, 1, 1, 1, 1, 4, 4, 8, 4, 10};

int calculate_score(string word);

int main(void)
{
    // Prompt the user for two words
    string word1 = get_string("Player 1: ");
    string word2 = get_string("Player 2: ");

    // Compute the score of each word
    int score1 = calculate_score(word1);
    int score2 = calculate_score(word2);

    // Print the winner
    if (score1 > score2)
    {
        printf("Player 1 wins!\n");
    }
    else if (score1 < score2)
    {
        printf("Player 2 wins!\n");
    }
    else
    {
        printf("Tie!\n");
    }
}

int calculate_score(string word)
{
    // Keep track of the score
    int score = 0;

    // Compute the score for each character
    for (int i = 0, len = strlen(word); i < len; i++)
    {
        if (isupper(word[i]))
        {
            score += points[word[i] - 'A'];
        }
        else if (islower(word[i]))
        {
            score += points[word[i] - 'a'];
        }
    }
    return score;
}
 No comments    47   22 d   C   CS50   Programming

Credit card validation in C

I keep learning programming, and today I share my baby walkthrough of the second homework from the CS50 course titled Credit.

As a quick disclaimer, I used only tools I’ve learned from the two lessons I had so far.

Here is the problem to solve:

A credit (or debit) card, of course, is a plastic card with which you can pay for goods and services. Printed on that card is a number that’s also stored in a database somewhere, so that when your card is used to buy something, the creditor knows whom to bill. There are a lot of people with credit cards in this world, so those numbers are pretty long: American Express uses 15-digit numbers, MasterCard uses 16-digit numbers, and Visa uses 13- and 16-digit numbers. And those are decimal numbers (0 through 9), not binary, which means, for instance, that American Express could print as many as 10^15 = 1,000,000,000,000,000 unique cards! (That’s, um, a quadrillion.)

Actually, that’s a bit of an exaggeration, because credit card numbers actually have some structure to them. All American Express numbers start with 34 or 37; most MasterCard numbers start with 51, 52, 53, 54, or 55 (they also have some other potential starting numbers which we won’t concern ourselves with for this problem); and all Visa numbers start with 4. But credit card numbers also have a “checksum” built into them, a mathematical relationship between at least one number and others. That checksum enables computers (or humans who like math) to detect typos (e. g., transpositions), if not fraudulent numbers, without having to query a database, which can be slow. Of course, a dishonest mathematician could certainly craft a fake number that nonetheless respects the mathematical constraint, so a database lookup is still necessary for more rigorous checks.

Write a program that prompts the user for a credit card number and then reports (via printf) whether it is a valid American Express, MasterCard, or Visa card number, per the definitions of each’s format herein. So that we can automate some tests of your code, we ask that your program’s last line of output be AMEX\n or MASTERCARD\n or VISA\n or INVALID\n, nothing more, nothing less. For simplicity, you may assume that the user’s input will be entirely numeric (i.e., devoid of hyphens, as might be printed on an actual card) and that it won’t have leading zeroes. But do not assume that the user’s input will fit in an int! Best to use get_long from CS50’s library to get users’ input.

First, I’ll prompt a user to input a number using the get_long function from the CS50 library:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    long card_number = get_long("Number: ");
}

Next, I’ll do what seems to be the most challenging part of the problem, which is to calculate the checksum of a credit card. In the problem description, they provide additional information on Luhn’s Algorithm that determines the validity of a card as follows:

  1. Multiply every other digit by 2, starting with the number’s second-to-last digit, and then add those products’ digits together.
  2. Add the sum to the sum of the digits that weren’t multiplied by 2.
  3. If the total’s last digit is 0, the number is valid!

Let’s take the card number 4003600000000014 as an example. For the sake of visibility, let me underline every other digit, starting with the number’s second-to-last digit:

4 0 0 3 6 0 0 0 0 0 0 0 0 0 1 4

How to extract those digits from a number in C? Turns out, in maths, there is a great operation that can give us the remainder after dividing one number by another, and it’s called modulo, or mod. You can totally start laughing here, but honestly, I never heard of it before. For example, 1234 % 10 = 4 (with modulo operation being expressed by the percent sign), since 4 is the last digit in the number 1234.

Okay, that was the last digit. But how to get to the second-to-last digit, and then get every other digit from there? This might be not as obvious (at least it wasn’t at first to me), but since we’re dealing with whole numbers, a simple division by 10 basically moves us to one character in a number at a time. For example, 1234 / 10 = 123,4, but since the integer numbers get truncated, the result is actually 123.

Pretty cool, huh? Now let’s try to get every second number using the combination of division and modulo operations in the code:

#include <cs50.h>
#include <stdio.h>

long card_number;
int main(void)
{
    // Prompting a user to input a credit card number
    card_number = get_long("Number: ");

    // Calculating checksum
    int last_digit;
    int second_to_last_digit;

    while (card_number > 0)
    {
        // Removing the last digit
        last_digit = card_number % 10;
        card_number /= 10;

        // Removing the second last digit
        second_to_last_digit = card_number % 10;
        card_number /= 10;
        printf("%i", second_to_last_digit);
    }
    printf("\n");
}

This code prints 10000604, which are exactly the digits we need from the card number 4003600000000014. Keep in mind it’s not a number ten million six hundred four, but individual digits printed one after another. The order of digits is reversed, though it’s irrelevant in this case.

Next, according to Luhn’s Algorithm, I need to multiply each digit by 2 and get the sum of all of them combined. And I haven’t found a better solution than again using the same modulo and division operations, but this time on the extracted digits:

#include <cs50.h>
#include <stdio.h>

long card_number;
int main(void)
{
    // Prompting a user to input a credit card number
    card_number = get_long("Number: ");

    // Calculating checksum
    int every_second_digit = 0;
    int last_digit;
    int second_to_last_digit;
    int digit1;
    int digit2;

    while (card_number > 0)
    {
        // Removing the last digit and adding to every_other_digit
        last_digit = card_number % 10;
        card_number /= 10;

        // Removing the second last digit
        second_to_last_digit = card_number % 10;
        card_number /= 10;

        // Mupliplying second last digit
        second_to_last_digit *= 2;

        // Adding digits together to get the sum of every_second_digit
        digit1 = second_to_last_digit % 10;
        digit2 = second_to_last_digit / 10;
        every_second_digit += digit1 + digit2;
    }
    printf("%i", every_second_digit);
    printf("\n");
}

I’m pretty sure it could be done more elegantly, but I’m using only the knowledge I have so far from the first week of introduction to programming. Importantly, this code works, providing the result of the number 13, as you would expect from the sum of digits 2 + 1 + 2 + 8. Yay!

Lastly, to finish off the checksum, I’m going to find every other digit, add them together, and then add both sums in the final checksum variable:

#include <cs50.h>
#include <stdio.h>

long card_number;
int main(void)
{
    // Prompting a user to input a credit card number
    card_number = get_long("Number: ");

    // Calculating checksum
    int every_second_digit = 0;
    int every_other_digit = 0;
    int checksum = 0;
    int last_digit;
    int second_to_last_digit;
    int digit1;
    int digit2;

    while (card_number > 0)
    {
        // Removing the last digit and adding to every_other_digit
        last_digit = card_number % 10;
        card_number /= 10;
        every_other_digit += last_digit;

        // Removing the second last digit
        second_to_last_digit = card_number % 10;
        card_number /= 10;

        // Mupliplying second last digit
        second_to_last_digit *= 2;

        // Adding digits together to get the sum of every_second_digit
        digit1 = second_to_last_digit % 10;
        digit2 = second_to_last_digit / 10;
        every_second_digit += digit1 + digit2;
    }

    // Getting checksum
    checksum = every_second_digit + every_other_digit;

    printf("%i\n", checksum);
}

This code now prints the number 20, which is exactly the kind of value I want from a valid credit card. The hardest part is done!

Next, I’ll calculate the number of digits in the card number using a simple loop:

// Counting the number of digits in the card number
    long n = card_number;
    int number_of_digits = 0;
    do
    {
        n /= 10;
        number_of_digits++;
    }
    while (n != 0);

To keep the value of that card_number intact, I added a new variable called n and assigned its value to card_number, so I can do the maths with the n instead. In plain English, that loop says the following: while the card number is not equal to zero, divide the card number by 10, and for every division increase the number of number_of_digits variable which I use as a counter by one.

For example, if I were to type in the number 1234, it would go as follows:

  1. 1234 / 10 = 123; the counter increases from 0 to 1;
  2. 123,4 / 10 = 12; the counter increases from 1 to 2;
  3. 12,34 / 10 = 1; the counter increases from 2 to 3;
  4. 1 / 0 = 10; the counter increases from 3 to 4;

Now the card number gets equal to zero, and the loop ends with the counter equal to 4, which is the correct number of digits in the number 1234.

Next, I’ll make another counter to get the first two digits of the card number using pretty much the same logic:

// Getting the first two digits of the card number
    int first_two_digits = 0;
    long i = card_number;
    while (i > 100)
    {
        i /= 10;
        first_two_digits = i;
    }

Lastly, I’ll check the validity of the checksum and then check what credit company the card belongs to based of the card number length and starting digits.

So here is my final code:

// A program in C that checks the validity of a given credit card number

#include <cs50.h>
#include <stdio.h>

long card_number;
int main(void)
{
    // Prompting a user to input a credit card number
    card_number = get_long("Number: ");

    // Counting the number of digits in the card number
    long n = card_number;
    int number_of_digits = 0;
    do
    {
        n /= 10;
        number_of_digits++;
    }
    while (n != 0);

    // Getting first two digits of the card number
    int first_two_digits = 0;
    long i = card_number;
    while (i > 100)
    {
        i /= 10;
        first_two_digits = i;
    }

    // Calculating checksum
    int every_second_digit = 0;
    int every_other_digit = 0;
    int checksum = 0;
    int last_digit;
    int second_to_last_digit;
    int digit1;
    int digit2;

    while (card_number > 0)
    {
        // Removing last digit and adding to every_other_digit
        last_digit = card_number % 10;
        card_number /= 10;
        every_other_digit += last_digit;

        // Removing the second last digit
        second_to_last_digit = card_number % 10;
        card_number /= 10;

        // Mupliplying the second last digit
        second_to_last_digit *= 2;

        // Adding digits together to get the sum of every_second_digit
        digit1 = second_to_last_digit % 10;
        digit2 = second_to_last_digit / 10;
        every_second_digit += digit1 + digit2;
    }

    // Getting checksum
    checksum = every_second_digit + every_other_digit;

    // Checking for the card validity
    int validity = checksum % 10;
    if (validity == 0)
    {
        if ((number_of_digits == 15) && (first_two_digits == 34 || first_two_digits == 37))
        {
            printf("AMEX\n");
        }
        else if ((number_of_digits == 16) && (first_two_digits >= 51 && first_two_digits <= 55))
        {
            printf("MASTERCARD\n");
        }
        else if ((number_of_digits == 16 || number_of_digits == 13) && (first_two_digits / 10 == 4))
        {
            printf("VISA\n");
        }
        else
        {
            printf("INVALID\n");
        }
    }
    else
    {
        printf("INVALID\n");
    }
}

Update

A week later after posting this solution, I decided to get back to this problem and see if I could improve the code, particularly focusing on the checksum part as it’s essentially the main part.

Here is my updated code for this function:

// Calculate checksum using Luhn's Algorithm
int calculate_checksum(long long number)
{
    int sum = 0;
    int digit;
    bool is_second_digit = false;

    while (number > 0)
    {
        digit = number % 10; // Get the last digit
        number /= 10; // Reduce the number by one digit

        if (is_second_digit)
        {
            digit *= 2;
            sum += digit % 10 + digit / 10; // Split double numbers into single digits, e.g. 12 into 1 and 2
        }
        else
        {
            sum += digit;
        }

        // Switch the boolean, alternating between odd and even digits
        is_second_digit = !is_second_digit;
    }

    return sum;
}
 No comments    50   22 d   C   CS50   Programming

Super Mario pyramids in C

Just to give a heads-up to the regular readers of my blog, this post is quite different from the usual topics that I write about.

Long story short, I decided to start learning programming, and as I’ve learned many times throughout the years of running this blog, there is no better way to learn something than by explaining it to others! After all, systemizing knowledge is one of the reasons I run my blog, so don’t be surprised to see some ‘weird’ posts here from now on.

In this post, I’ll give my walkthrough of solving the problem as a way to reinforce what I’ve learned. If by any chance you are a seasoned programmer, you are more than welcome to point out any mistakes or ways to improve for a newbie like me. However, if programming isn’t quite your thing, feel free to simply scroll through!

So, a couple of days ago I started by taking a course on computer science, and one of the first little homework I had was the following:

Toward the beginning of World 1-1 in Nintendo’s Super Mario Brothers, Mario must hop over adjacent pyramids of blocks. Implement a program in C that recreates that pyramid, using hashes (#) for bricks, as in the below:

...#  #
..##  ##
.###  ###
####  ####

And let’s allow the user to decide just how tall the pyramids should be by first prompting them for a positive number between, say, 1 and 8, inclusive.

Super Mario game on Nintendo

So, I’ll start by creating a variable with a type integer called height and the value equal to the return of the get_int function, which prompts a user for a number input. In case you wonder, get_int is a custom function defined in the CS50 library, so I included it in the header:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    int height = get_int("Height: ");
}

Next, I’m adding validation of the user input since we need to accept only a specific range of numbers. To do so, I chose Do While Loop. Why this particular type of loop over the others? From my understanding so far, here are the best use cases for each type of loop:

  • For Loop works best when we know the exact number of repetitions, e. g. in some sort of counter;
  • While Loop works best when the number of repetitions is unknown;
  • Do While is pretty much the same as While Loop, but it’s guaranteed to trigger at least once.

So, here is the code, which in plain English says “Ask for input and keep asking while the provided number is less than one or greater than eight”:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    do
    {
        int height = get_int("Height: ");
    }
    while (height < 1 || height > 8);
}

Now the problem is when I’m trying to compile the program, I get the following error: use of undeclared identifier ‘height’. This is happening because the variable height is defined within the Do part of the loop, so the While part doesn’t know about it. Basically, everything defined within the curly brackets stays within the curly brackets. This is a known problem of scope.

To solve the scope issue, I simply need to declare the height variable before the loop and outside its curly brackets:

#include <cs50.h>
#include <stdio.h>

int height;
int main(void)
{
    do
    {
        height = get_int("Height: ");
    }
    while (height < 1 || height > 8);
}

Note that I don’t need to assign any value to the variable, this is why a simple line int height; does the job. Also, note that in the curly brackets, height no longer needs int before, as I already defined the type of this variable as an integer at the top, and here I’m only assigning this variable a value.

Now this program works, and it only accepts numbers from 1 to 8 inclusive, as per the task description. If I type any negative number, zero, a character, or a number greater than 8, then the program is going to keep asking for another number, thanks to the Do While Loop.

Although this is correct, I don’t quite like the explicit usage of numbers 1 and 8 in the While expression. Why these particular numbers, and not 20 or 50, for example? Well, I surely know this from the problem description, but let’s say if I share this program with a colleague, it might be not so obvious to them. Numbers that appear in code seemingly out of the blue are called Magic Numbers.

To avoid Magic Numbers, I’m going to replace 1 and 8 with two variables, minHeight and maxHeight respectively. Keeping the scope in mind, I declare these variables at the top of the file, and since their values are set by the task rules, I’m giving them the type of const just to indicate that these numbers are the contestants and won’t change:

#include <cs50.h>
#include <stdio.h>

int height;
const int minHeight = 1;
const int maxHeight = 8;
int main(void)
{
    do
    {
        height = get_int("Height: ");
    }
    while (height < minHeight || height > maxHeight);
}

Functionally, this is exactly the same program as above, but I think it now has a slightly better design.

Next, I need to find a way of printing the hashes. If you think about it for a moment, what is a pyramid according to the problem set, for example, 3×3? It’s basically a brick with a length and height of 3, like so:

###
###
###

This obviously isn’t a pyramid shape yet, but we’ll get to it. Let’s think about how to print that brick first. The easiest way would be to simply repeat the printf function that many number of times:

printf("###\n");
printf("###\n");
printf("###\n");

You can see that the rows are identical, and whenever there is something copy-pastable, it might be a good indicator that there is a better solution. The first step would be to replace the rows by For Loop expression:

for (int i = 0; i < 3; i++)
{
    printf("###\n");
}

In this loop, I created a variable named i with a value of 0, and if i is less than three, then it prints the hashes, then it incrementally increases the value of і by 1, and then it checks it again until the expression of i is less than 3 is no longer true. In other words, this code does exactly the same as above – printing three rows of hashes – but in a more clever way.

But even though I’m printing rows dynamically, the number of columns is still set to a very specific number of hashes (three in this case), so I can go further to improve this. To do this, I’ll create another For Loop within that loop using a different variable j:

for (int i = 0; i < 3; i++)
{
    for (int j = 0; j < 3, j++)
    {
        printf("#");
    }
    printf("\n");
}

Note that now I can type only one hash in the printf function, and the rest is calculated mathematically. This nested structure of a loop within another loop seems exactly what I need for printing the pyramid, conceptually.

However, because the pyramid I need requires a few more parameters to get the actual pyramid shape, I think making this structure would be too large and hard to read. To slightly simplify the process, I’m going to move out the loop that prints rows into its own separate function.

To do so, I’ll add a new function called print_row. What kind of input it should take? It must be a number of hashes in a row to modify the length, so I’ll add one input parameter of a type integer that I call length. And it shouldn’t return any value, it just prints things on the screen, so I’ll keep its return value as void, which basically means nothing.

Going back to my main code now, here is what it looks like now:

#include <cs50.h>
#include <stdio.h>

int height;
const int minHeight = 1;
const int maxHeight = 8;
int main(void)
{
    do
    {
        height = get_int("Height: ");
    }
    while (height < minHeight || height > maxHeight);
}

void print_row(int length)
{

}

Nothing happens as the function literally does nothing so far, but I can work on that now. When I use this function print_row, I can pass in some number, and I can loop it that many times.

#include <cs50.h>
#include <stdio.h>

int height;
const int minHeight = 1;
const int maxHeight = 8;
int main(void)
{
    do
    {
        height = get_int("Height: ");
    }
    while (height < minHeight || height > maxHeight);
}

void print_row(int length)
{
    for (int i = 0; i < length; i++)
    {
        printf("#");
    }
    printf("\n");
}

This is basically the loop I created earlier in the brick example, but I still can’t see its result because this function is not used anywhere yet. Now I can try to use print_row after the Do While loop, and also to pass it the number that a user inputs in the program:

#include <cs50.h>
#include <stdio.h>

void print_row(int length);
int height;
const int minHeight = 1;
const int maxHeight = 8;
int main(void)
{
    do
    {
        height = get_int("Height: ");
    }
    while (height < minHeight || height > maxHeight);
    print_row(height);
}

void print_row(int length)
{
    for (int i = 0; i < length; i++)
    {
        printf("#");
    }
    printf("\n");
}

Note that I had to add the prototype of the print_row function at the top of my file again to solve the scope issue, similar to how I’ve done previously with my variables. In plain English, this program now asks a user to input a number from 1 to 8 and then prints that exact number of hashes in a single line. Why only a single line? Because when I use the print_row function, it gets only one number that a user types in, the variable height, and that’s it.

So now I need to make the print_row function repeat itself some number of times, just like I did earlier in the nested loops example, and kind of wrap it around another loop. How many times the loop should be repeated? As many as the number that I get from a user:

#include <cs50.h>
#include <stdio.h>

void print_row(int length);
int height;
const int minHeight = 1;
const int maxHeight = 8;
int main(void)
{
    do
    {
        height = get_int("Height: ");
    }
    while (height < minHeight || height > maxHeight);

    for (int i = 0; i < height; i++)
    {
        print_row(height);
    }
}

void print_row(int length)
{
    for (int i = 0; i < length; i++)
    {
        printf("#");
    }
    printf("\n");
}

It works, and now I get a brick of size x×x. For example, if I type in number 4, I get this:

####
####
####
####

... and I type in number 8, I get this:

########
########
########
########
########
########
########
########

So I’m getting close, but for now, it’s still a square brick. How to make the rows more dynamic, i.e. print only one hash on the first row, two hashes on the second row, and so forth? I guess instead of using height as my input parameter in print_row(height);, I can replace it with some other variable. I think I can use the variable i, which I use for counting the number of repetitions, however, since it starts with 0, I would get zero hashes on the first line, one hash on the second line, and so on. So to offset this, I’ll tell my program to start counting by i + 1, like so:

#include <cs50.h>
#include <stdio.h>

void print_row(int length);
int height;
const int minHeight = 1;
const int maxHeight = 8;
int main(void)
{
    do
    {
        height = get_int("Height: ");
    }
    while (height < minHeight || height > maxHeight);

    for (int i = 0; i < height; i++)
    {
        print_row(i + 1);
    }
}

void print_row(int length)
{
    for (int i = 0; i < length; i++)
    {
        printf("#");
    }
    printf("\n");
}

And this now produces the following result, for example, if I type in 8:

#
##
###
####
#####
######
#######
########

Half of the pyramid is done, yay! Almost there. The next question is how to add another half of the pyramid and what’s the difference between them.

Let me draw the left half of the pyramid just to look at it for a moment, let’s say with a height of 4:

...#
..##
.###
####

So it seems that I need to calculate not only the number of hashes but also the number of spaces (dots in this case, for the sake of visibility) to offset the hashes on each line.

To do so, I’ll add another input to my print_row function, an integer named spaces, not forgetting to mirror it in the function prototype at the top. Then inside the function, I need to adjust what is printed on every row. According to the pyramid shape, it must be some number of dots (spaces) first, then hashes for the left side of the pyramid, then a gap, and then hashes for the right side of the pyramid. For the right side, no extra spaces are needed after hashes since they won’t be visible anyway.

Also, there is a curious relationship between a row number and the amount of spaces needed to offset the hashes. For example, for the 8th row, no spaces are needed; for the 7th row, only 1 space is needed, and so forth. So my For Loop representing spaces, I’m going to assign the variable i a value of height, and then count downwards, incrementally decreasing the number of spaces by 1.

Lastly, need to not forget to add the second input when I’m calling the print_row function to print both hashes and spaces in each column.

And here is the final code:

// A program in C that recreates the pyramid from Mario using hashes (#) for bricks

#include <cs50.h>
#include <stdio.h>

void print_row(int spaces, int length);
int height;
const int minHeight = 1;
const int maxHeight = 8;
int main(void)
{
    // Prompting a user to input a number to define the height of the pyramid, accepting only numbers from 1 to 8, inclusive
    do
    {
        height = get_int("Height: ");
    }
    while (height < minHeight || height > maxHeight);

    // Printing columns of the pyramid
    for (int i = 0; i < height; i++)
    {
        print_row(i + 1, i + 1);
    }
}

// Printing rows of the pyramid
void print_row(int spaces, int length)
{
    // Printing the dots (spaces) on the left
    for (int i = height; i > spaces; i--)
    {
        printf(" ");
    }

    // Printing hashes for the left side of the pyramid
    for (int i = 0; i < length; i++)
    {
        printf("#");
    }

    // Printing the gap between the sides of the pyramid
    printf("  ");

    // Printing hashes for the right side of the pyramid
    for (int i = 0; i < length; i++)
    {
        printf("#");
    }

    printf("\n");
}

Update

As kindly pointed out by Sergey Khivuk after I published the post, there are at least a few ways to improve the code. I’ll leave his feedback below:

  • Instead of passing two identical parameters to void print_row(int spaces, int length), just pass one and replace spaces with length. The pyramid is always square in terms of width and height anyway.
  • Instead of:
for (int i = 0; i < height; i++)
{
  print_row(i + 1);
}

...just use:

for (int i = 1; i <= height; i++)
{ 
  print_row(i);
}

There will be no need to calculate the parameter every time the function is called.

 1 comment    83   25 d   C   CS50   Programming

Dark Entity (Hypnotic Mix) is out now

An ever darker version of my collaboration with Enlusion

Some interesting backstory. In 2021, Enlusion and I collaborated to create ‘Dark Entity’. While the original mix was a heavy-hitting dancefloor banger, I also wanted to have a more stripped-down version and that is how we made the ‘Heads-down Mix’.

Fast-forward to 2024, upon relistening to those versions I realised that I want something even more heads-down, more... hypnotic. So I sent a message to Kirill, and our dialogue went something like that:

— me: Let’s get rid of those acids, BXR-style snares and other extra sounds?
— Kirill: Hmm okay. But we’re going to add new melodies and a new bassline then, right?... Right?
— me: 😎

So there you go guys, Dark Entity (Hypnotic Mix) is out now, and Kirill is probably still mad that we didn’t add five more layers of extra melodies!

Preview:

Earlier Ctrl + ↓
© Daniel Sokolovskiy, 2024
Powered by Aegea