solution

Solutions to CS50 Problem Set 4 Filter & Recover Problems (2022)

Disclaimer: These answers are only for educational purposes only. Please do not use them for cheating. Cheating doesn’t do any good for you!

In this post, I’m giving you my solutions to CS50 Problem Set 4 Filter (less comfortable / more comfortable) Problems and Recover problems. Hope these solutions will help you to better understand the problems and be a guide for your solutions too.

The Solution to CS50 Psets 4 Filter Problem – Less Comfortable (2022)

For this problem, we just have to implement a program that applies filters to BMPs. And a bunch of files were provided for us. We have to implement some functions in helpers.c to apply greyscale, Sepia, reflection, and blur filters to the given images.

The greyscale function turns the input image into a black-and-white version of it

// Convert image to grayscale
void grayscale(int height, int width, RGBTRIPLE image[height][width])
{
    // Iterate through each column of pixel
    for (int i = 0; i < height; i++)
    {
        // Iterate through each raw of pixel in each column
        for (int j = 0; j < width; j++)
        {
            // Get into the 2D array, obtain value of each color
            int red = image[i][j].rgbtRed;
            int blue = image[i][j].rgbtBlue;
            int green = image[i][j].rgbtGreen;

            // Calculate the rounded avarage of each pixel
            int average = round(((float)red + (float)blue + (float)green) / 3);

            // Set the calculated value to be the new value of each pixel
            image[i][j].rgbtRed = image[i][j].rgbtBlue = image[i][j].rgbtGreen = average;
        }
    }
}

The sepia function turns the input image into sepia version of the same image

// Convert image to sepia
void sepia(int height, int width, RGBTRIPLE image[height][width])
{
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            int red = image[i][j].rgbtRed;
            int blue = image[i][j].rgbtBlue;
            int green = image[i][j].rgbtGreen;

            // New sapia values
            int sepiaRed = round(0.393 * red + 0.769 * green + 0.189 * blue);

            if (sepiaRed > 255)
            {
                image[i][j].rgbtRed = 255;
            }
            else
            {
                image[i][j].rgbtRed = sepiaRed;
            }

            int sepiaBlue = round(0.272 * red + 0.534 * green + 0.131 * blue);

            if (sepiaBlue > 255)
            {
                image[i][j].rgbtBlue = 255;
            }
            else
            {
                image[i][j].rgbtBlue = sepiaBlue;
            }

            int sepiaGreen = round(0.349 * red + 0.686 * green + 0.168 * blue);

            if (sepiaGreen > 255)
            {
                image[i][j].rgbtGreen = 255;
            }
            else
            {
                image[i][j].rgbtGreen = sepiaGreen;
            }
        }
    }
}

The reflect function takes the image and reflects in horizontally

// Reflect image horizontally
void reflect(int height, int width, RGBTRIPLE image[height][width])
{
    for (int i = 0; i < height; i++)
    {
        // Iterate through the array until you get the mid point
        for (int j = 0; j < (width / 2); j++)
        {
            RGBTRIPLE temp = image[i][j];

            image[i][j] = image[i][width - (j + 1)];
            image[i][width - (j + 1)] = temp;
        }
    }
    return;
}

The blur function takes an image and turns it into a box-blurred version of the image

// Blur image
void blur(int height, int width, RGBTRIPLE image[height][width])
{
    //create a temporary image to implement blurred algorithm on it.
    RGBTRIPLE temp[height][width];

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            int sumRed, sumBlue, sumGreen;
            sumRed = sumBlue = sumGreen = 0;
            float counter = 0.00;

            //Get the neighbouring pexels
            for (int c = -1; c < 2; c++)
            {
                for (int r = -1; r < 2; r++)
                {
                    int currentX = i + c;
                    int currentY = j + r;

                    //check for valid neighbouring pexels
                    if (currentX < 0 || currentX > (height - 1) || currentY < 0 || currentY > (width - 1))
                    {
                        continue;
                    }

                    //Get the image value
                    sumRed += image[currentX][currentY].rgbtRed;
                    sumGreen += image[currentX][currentY].rgbtGreen;
                    sumBlue += image[currentX][currentY].rgbtBlue;

                    counter++;
                }

                //do the average of neigbhouring pexels
                temp[i][j].rgbtRed = round(sumRed / counter);
                temp[i][j].rgbtGreen = round(sumGreen / counter);
                temp[i][j].rgbtBlue = round(sumBlue / counter);
            }
        }

    }

    //copy the blurr image to the original image
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            image[i][j].rgbtRed = temp[i][j].rgbtRed;
            image[i][j].rgbtGreen = temp[i][j].rgbtGreen;
            image[i][j].rgbtBlue = temp[i][j].rgbtBlue;
        }
    }
    return;
}

Full code of helpers.c file

#include "helpers.h"
#include <math.h>

// Convert image to grayscale
void grayscale(int height, int width, RGBTRIPLE image[height][width])
{
    // Iterate through each column of pixel
    for (int i = 0; i < height; i++)
    {
        // Iterate through each raw of pixel in each column
        for (int j = 0; j < width; j++)
        {
            // Get into the 2D array, obtain value of each color
            int red = image[i][j].rgbtRed;
            int blue = image[i][j].rgbtBlue;
            int green = image[i][j].rgbtGreen;

            // Calculate the rounded avarage of each pixel
            int average = round(((float)red + (float)blue + (float)green) / 3);

            // Set the calculated value to be the new value of each pixel
            image[i][j].rgbtRed = image[i][j].rgbtBlue = image[i][j].rgbtGreen = average;
        }
    }
}

// Convert image to sepia
void sepia(int height, int width, RGBTRIPLE image[height][width])
{
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            int red = image[i][j].rgbtRed;
            int blue = image[i][j].rgbtBlue;
            int green = image[i][j].rgbtGreen;

            // New sapia values
            int sepiaRed = round(0.393 * red + 0.769 * green + 0.189 * blue);

            if (sepiaRed > 255)
            {
                image[i][j].rgbtRed = 255;
            }
            else
            {
                image[i][j].rgbtRed = sepiaRed;
            }

            int sepiaBlue = round(0.272 * red + 0.534 * green + 0.131 * blue);

            if (sepiaBlue > 255)
            {
                image[i][j].rgbtBlue = 255;
            }
            else
            {
                image[i][j].rgbtBlue = sepiaBlue;
            }

            int sepiaGreen = round(0.349 * red + 0.686 * green + 0.168 * blue);

            if (sepiaGreen > 255)
            {
                image[i][j].rgbtGreen = 255;
            }
            else
            {
                image[i][j].rgbtGreen = sepiaGreen;
            }
        }
    }
}

// Reflect image horizontally
void reflect(int height, int width, RGBTRIPLE image[height][width])
{
    for (int i = 0; i < height; i++)
    {
        // Iterate through the array until you get the mid point
        for (int j = 0; j < (width / 2); j++)
        {
            RGBTRIPLE temp = image[i][j];

            image[i][j] = image[i][width - (j + 1)];
            image[i][width - (j + 1)] = temp;
        }
    }
    return;
}


// Blur image
void blur(int height, int width, RGBTRIPLE image[height][width])
{
    //create a temporary image to implement blurred algorithm on it.
    RGBTRIPLE temp[height][width];

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            int sumRed, sumBlue, sumGreen;
            sumRed = sumBlue = sumGreen = 0;
            float counter = 0.00;

            //Get the neighbouring pexels
            for (int c = -1; c < 2; c++)
            {
                for (int r = -1; r < 2; r++)
                {
                    int currentX = i + c;
                    int currentY = j + r;

                    //check for valid neighbouring pexels
                    if (currentX < 0 || currentX > (height - 1) || currentY < 0 || currentY > (width - 1))
                    {
                        continue;
                    }

                    //Get the image value
                    sumRed += image[currentX][currentY].rgbtRed;
                    sumGreen += image[currentX][currentY].rgbtGreen;
                    sumBlue += image[currentX][currentY].rgbtBlue;

                    counter++;
                }

                //do the average of neigbhouring pexels
                temp[i][j].rgbtRed = round(sumRed / counter);
                temp[i][j].rgbtGreen = round(sumGreen / counter);
                temp[i][j].rgbtBlue = round(sumBlue / counter);
            }
        }

    }

    //copy the blurr image to the original image
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            image[i][j].rgbtRed = temp[i][j].rgbtRed;
            image[i][j].rgbtGreen = temp[i][j].rgbtGreen;
            image[i][j].rgbtBlue = temp[i][j].rgbtBlue;
        }
    }
    return;
}

The Solution to CS50 Psets 4 Filter Problem – More Comfortable (2022)

For this problem also, we have to implement a program that applies filters to BMPs. And a bunch of files were provided for us. We have to implement some functions in helpers.c to apply greyscale, reflection, blur, and edge filters to the given images.

The greyscale function should take an image and turn it into a black-and-white version of the same image.

// Convert image to grayscale
void grayscale(int height, int width, RGBTRIPLE image[height][width])
{
    // Iterate though each column
    for (int i = 0; i < height; i++)
    {
        // Iterate through each raw of pixel in each column
        for (int j = 0; j < width; j++)
        {
            // Get into 2D array and obtain value of each color
            int red = image[i][j].rgbtRed;
            int blue = image[i][j].rgbtBlue;
            int green = image[i][j].rgbtGreen;

            // Calculate the rounded avarage of each pixel
            int average = round(((float)red + (float)blue + (float)green) / 3);

            // Set the calculated value to be the new value of each pixel
            image[i][j].rgbtRed = image[i][j].rgbtBlue = image[i][j].rgbtGreen = average;
        }
    }
    return;
}

The reflection function should take an image and reflect it horizontally

// Reflect image horizontally
void reflect(int height, int width, RGBTRIPLE image[height][width])
{
    for (int i = 0; i < height; i++)
    {
        // Iterate through the array until you get the mid point
        for (int j = 0; j < (width / 2); j++)
        {
            RGBTRIPLE temp = image[i][j];

            image[i][j] = image[i][width - (j + 1)];
            image[i][width - (j + 1)] = temp;
        }
    }
    return;
}

The blur function takes and image and turns it into a box-blurred version of the same image.

// Blur image
void blur(int height, int width, RGBTRIPLE image[height][width])
{
    //create a temporary image to implement blurred algorithm on it.
    RGBTRIPLE temp[height][width];

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            int sumRed, sumBlue, sumGreen;
            sumRed = sumBlue = sumGreen = 0;
            float counter = 0.00;

            //Get the neighbouring pexels
            for (int c = -1; c < 2; c++)
            {
                for (int r = -1; r < 2; r++)
                {
                    int currentX = i + c;
                    int currentY = j + r;

                    //check for valid neighbouring pexels
                    if (currentX < 0 || currentX > (height - 1) || currentY < 0 || currentY > (width - 1))
                    {
                        continue;
                    }

                    //Get the image value
                    sumRed += image[currentX][currentY].rgbtRed;
                    sumGreen += image[currentX][currentY].rgbtGreen;
                    sumBlue += image[currentX][currentY].rgbtBlue;

                    counter++;
                }

                //do the average of neigbhouring pexels
                temp[i][j].rgbtRed = round(sumRed / counter);
                temp[i][j].rgbtGreen = round(sumGreen / counter);
                temp[i][j].rgbtBlue = round(sumBlue / counter);
            }
        }

    }

    //copy the blurr image to the original image
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            image[i][j].rgbtRed = temp[i][j].rgbtRed;
            image[i][j].rgbtGreen = temp[i][j].rgbtGreen;
            image[i][j].rgbtBlue = temp[i][j].rgbtBlue;
        }
    }
    return;
}

The edges function takes an image and highlight the edges between objects, according to the sobel operator.

// Detect edges
void edges(int height, int width, RGBTRIPLE image[height][width])
{
    RGBTRIPLE temp[height][width];

    int gx[3][3] = {{-1, 0, 1}, {-2, 0, 2}, {-1, 0, 1}};
    int gy[3][3] = {{-1, -2, -1}, {0, 0, 0}, {1, 2, 1}};

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            float gxRed = 0;
            float gyRed = 0;
            float gxGreen = 0;
            float gyGreen = 0;
            float gxBlue = 0;
            float gyBlue = 0;

            for (int col = -1; col < 2; col++)
            {
                for (int row = -1; row < 2; row++)
                {
                    if (i + col < 0 || i + col > height - 1)
                    {
                        continue;
                    }
                    if (j + row < 0 || j + row > width - 1)
                    {
                        continue;
                    }

                    gxRed += image[i + col][j + row].rgbtRed * gx[col + 1][row + 1];
                    gyRed += image[i + col][j + row].rgbtRed * gy[col + 1][row + 1];
                    gxGreen += image[i + col][j + row].rgbtGreen * gx[col + 1][row + 1];
                    gyGreen += image[i + col][j + row].rgbtGreen * gy[col + 1][row + 1];
                    gxBlue += image[i + col][j + row].rgbtBlue * gx[col + 1][row + 1];
                    gyBlue += image[i + col][j + row].rgbtBlue * gy[col + 1][row + 1];
                }
            }

            int red = round(sqrt(gxRed * gxRed + gyRed * gyRed));
            int green = round(sqrt(gxGreen * gxGreen + gyGreen * gyGreen));
            int blue = round(sqrt(gxBlue * gxBlue + gyBlue * gyBlue));

            // Cap at 255
            if (red > 255)
            {
                red = 255;
            }
            if (green > 255)
            {
                green = 255;
            }
            if (blue > 255)
            {
                blue = 255;
            }

            // Assign new values to pixels
            temp[i][j].rgbtRed = red;
            temp[i][j].rgbtGreen = green;
            temp[i][j].rgbtBlue = blue;
        }
    }

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

    return;
}

Full solution to cs50 psets 4 filter – more comfortable problem

#include "helpers.h"
#include <math.h>

// Convert image to grayscale
void grayscale(int height, int width, RGBTRIPLE image[height][width])
{
    // Iterate though each column
    for (int i = 0; i < height; i++)
    {
        // Iterate through each raw of pixel in each column
        for (int j = 0; j < width; j++)
        {
            // Get into 2D array and obtain value of each color
            int red = image[i][j].rgbtRed;
            int blue = image[i][j].rgbtBlue;
            int green = image[i][j].rgbtGreen;

            // Calculate the rounded avarage of each pixel
            int average = round(((float)red + (float)blue + (float)green) / 3);

            // Set the calculated value to be the new value of each pixel
            image[i][j].rgbtRed = image[i][j].rgbtBlue = image[i][j].rgbtGreen = average;
        }
    }
    return;
}

// Reflect image horizontally
void reflect(int height, int width, RGBTRIPLE image[height][width])
{
    for (int i = 0; i < height; i++)
    {
        // Iterate through the array until you get the mid point
        for (int j = 0; j < (width / 2); j++)
        {
            RGBTRIPLE temp = image[i][j];

            image[i][j] = image[i][width - (j + 1)];
            image[i][width - (j + 1)] = temp;
        }
    }
    return;
}

// Blur image
void blur(int height, int width, RGBTRIPLE image[height][width])
{
    //create a temporary image to implement blurred algorithm on it.
    RGBTRIPLE temp[height][width];

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            int sumRed, sumBlue, sumGreen;
            sumRed = sumBlue = sumGreen = 0;
            float counter = 0.00;

            //Get the neighbouring pexels
            for (int c = -1; c < 2; c++)
            {
                for (int r = -1; r < 2; r++)
                {
                    int currentX = i + c;
                    int currentY = j + r;

                    //check for valid neighbouring pexels
                    if (currentX < 0 || currentX > (height - 1) || currentY < 0 || currentY > (width - 1))
                    {
                        continue;
                    }

                    //Get the image value
                    sumRed += image[currentX][currentY].rgbtRed;
                    sumGreen += image[currentX][currentY].rgbtGreen;
                    sumBlue += image[currentX][currentY].rgbtBlue;

                    counter++;
                }

                //do the average of neigbhouring pexels
                temp[i][j].rgbtRed = round(sumRed / counter);
                temp[i][j].rgbtGreen = round(sumGreen / counter);
                temp[i][j].rgbtBlue = round(sumBlue / counter);
            }
        }

    }

    //copy the blurr image to the original image
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            image[i][j].rgbtRed = temp[i][j].rgbtRed;
            image[i][j].rgbtGreen = temp[i][j].rgbtGreen;
            image[i][j].rgbtBlue = temp[i][j].rgbtBlue;
        }
    }
    return;
}

// Detect edges
void edges(int height, int width, RGBTRIPLE image[height][width])
{
    RGBTRIPLE temp[height][width];

    int gx[3][3] = {{-1, 0, 1}, {-2, 0, 2}, {-1, 0, 1}};
    int gy[3][3] = {{-1, -2, -1}, {0, 0, 0}, {1, 2, 1}};

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            float gxRed = 0;
            float gyRed = 0;
            float gxGreen = 0;
            float gyGreen = 0;
            float gxBlue = 0;
            float gyBlue = 0;

            for (int col = -1; col < 2; col++)
            {
                for (int row = -1; row < 2; row++)
                {
                    if (i + col < 0 || i + col > height - 1)
                    {
                        continue;
                    }
                    if (j + row < 0 || j + row > width - 1)
                    {
                        continue;
                    }

                    gxRed += image[i + col][j + row].rgbtRed * gx[col + 1][row + 1];
                    gyRed += image[i + col][j + row].rgbtRed * gy[col + 1][row + 1];
                    gxGreen += image[i + col][j + row].rgbtGreen * gx[col + 1][row + 1];
                    gyGreen += image[i + col][j + row].rgbtGreen * gy[col + 1][row + 1];
                    gxBlue += image[i + col][j + row].rgbtBlue * gx[col + 1][row + 1];
                    gyBlue += image[i + col][j + row].rgbtBlue * gy[col + 1][row + 1];
                }
            }

            int red = round(sqrt(gxRed * gxRed + gyRed * gyRed));
            int green = round(sqrt(gxGreen * gxGreen + gyGreen * gyGreen));
            int blue = round(sqrt(gxBlue * gxBlue + gyBlue * gyBlue));

            // Cap at 255
            if (red > 255)
            {
                red = 255;
            }
            if (green > 255)
            {
                green = 255;
            }
            if (blue > 255)
            {
                blue = 255;
            }

            // Assign new values to pixels
            temp[i][j].rgbtRed = red;
            temp[i][j].rgbtGreen = green;
            temp[i][j].rgbtBlue = blue;
        }
    }

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

    return;
}

The Solution to CS50 Psets 4 Recover Problem (2022)

For this problem, we have to implement a C program that will recover JPEG images from a forensic images. So we have to write our code in recover.c file. So here is my solution to this problem.

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


int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        printf("Usage: ./recover card.raw\n");
        return 1;
    }
    // Open file for read
    FILE *i = fopen(argv[1], "r");
    //If fail to open input file retun error message "Could not open file"
    if (i == NULL)
    {
        printf("Could not open file");
        return 2;
    }

    //declare a variable to unsigned char to store 512 chunks array
    unsigned char buffer[512];

    //declare a variable to count image later in the loop
    int c = 0;

    //file pointer use to output data gotten from input file
    FILE *o = NULL;

    char *f = malloc(8 * sizeof(char));
    // char file[8];

    //Read 512 bytes from input file and store on the buffer
    while (fread(buffer, sizeof(char), 512, i))
    {
        //check if bytes are from a JPEG
        if (buffer[0] == 0xff && buffer[1] == 0xd8 && buffer[2] == 0xff && (buffer[3] & 0xf0) == 0xe0)
        {
            //write jpeg inot file name in form 001.jpg, 002.jpg and so on
            sprintf(f, "%03i.jpg", c);

            //open output file for writing
            o = fopen(f, "w");

            //count number of images found
            c++;
        }

        //Check if output have been used for valid input
        if (o != NULL)
        {
            fwrite(buffer, sizeof(char), 512, o);
        }
    }

    free(f);
    fclose(o);
    fclose(i);
}

Hope these code solutions help you to solve your problems little bit easier. If it helps consider sharing with your friends that will need these solutions.

The Solution to CS50 Lab 04 Volume Problem (2022)
We can use C language to modify audio files. In this lab 4 problem, we have to write a C program to increase the volume of an audio file. The input audio file is given to us in .wav format (INPUT.wav). We need to write the program so that when the user executes the following command in the terminal will provide another .wav file which includes the Audio increased output.
```
$ ./volume INPUT.wav OUTPUT.wav 2.0
```
Here “volume” is the program that executes. “OUTPUT.wav” is the output file. And 2.0 is the factor in which the volume should be increased of the input file.

Solution for the cs50 lab 04

We have two tasks to do in this lab. The first one is to copy the header from input files to output files. The second task is to read samples from the input file and write updated data to the output file.

Copy the header from input file to output file
```
    uint8_t header[HEADER_SIZE];
    fread(&header, HEADER_SIZE, 1, input);
    fwrite(&header, HEADER_SIZE, 1, output);
```
Read samples from the input file and write updated data to the output file.
```
    int16_t buffer;
    while (fread(&buffer, sizeof(int16_t), 1, input))
    {
        // Apply factor to the output file
        buffer *= factor;
        fwrite(&buffer, sizeof(int16_t), 1, output);
    }
```
Full 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]);

    // TODO: 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);

    // TODO: Read samples from input file and write updated data to output file
    int16_t buffer;
    while (fread(&buffer, sizeof(int16_t), 1, input))
    {
        // Apply factor to the output file
        buffer *= factor;
        fwrite(&buffer, sizeof(int16_t), 1, output);
    }

    // Close files
    fclose(input);
    fclose(output);
}
```
Hope this helps! Leave a comment if you want more clarification on this!

The Solution to CS50 psets 3 Tideman Problem (2022)

In this problem set, we have to write a code that runs the Tideman election as shown in below code snippet.

$ ./tideman Alice Bob Charlie
Number of voters: 5
Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Charlie
Rank 2: Alice
Rank 3: Bob

Charlie

In the previous posts, I gave you the solution to the cs50 psets 3 plurality problem, and cs50 psets 3 runoff problem.

So the plurality election system and runoff election system have their own advantages and disadvantages. Now, let’s see what is the Tideman election system.

Tideman Election System

Tideman method is also known as the Ranked pairs method. This system was developed in 1987 by Nicolaus Tideman. This system selects a single winner using votes that express preferences. This method can also be used to create a sorted list of winners.

So, let’s get back to the problem set, an initial code is given to us.

1. The vote function

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(name, candidates[i]) == 0)
        {
            ranks[rank] = i;
            return true;
        }
    }
    return false;
}

2. The record_preferences function

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            preferences[ranks[i]][ranks[j]]++;
        }
    }
    return;
}

3. The add_pairs function

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            if (preferences[i][j] > preferences[j][i])
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pair_count++;
            }
            else if (preferences[i][j] < preferences[j][i])
            {
                pairs[pair_count].winner = j;
                pairs[pair_count].loser = i;
                pair_count++;
            }
        }
    }
    return;
}

4. The sort_pairs function

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    // TODO
    for (int i = 0; i < pair_count; i++)
    {
        int max = i;
        for (int j = i; j < pair_count; j++)
        {
            if (preferences[pairs[j].winner][pairs[j].loser] > preferences[pairs[max].winner][pairs[max].loser])
            {
                max = j;
            }
        }
        pair temp = pairs[i];
        pairs[i] = pairs[max];
        pairs[max] = temp;
    }
    return;
}

5. The cycle function

// Check for cycle by checking arrow coming into each candidate
bool cycle(int cycle_end, int cycle_start)
{
    // Return true if there is a cycle
    if (cycle_end == cycle_start)
    {
        return true;
    }

    // Loop through all the candidates
    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[cycle_end][i])
        {
            if (cycle(i, cycle_start))
            {
                return true;
            }
        }
    }
    return false;
}

6. The lock_pairs function

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // TODO
    for (int i = 0; i < pair_count; i++)
    {
        if (!cycle(pairs[i].loser, pairs[i].winner))
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
    return;
}

7. The print_winner function

// Print the winner of the election
void print_winner(void)
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        bool loser = false;
        for (int j = 0; j < candidate_count; j++)
        {
            if (locked[j][i])
            {
                loser = true;
                break;
            }
        }
        if (loser)
        {
            continue;
        }
        if (!loser)
        {
            printf("%s\n", candidates[i]);
        }
    }
    return;
}

Full Code

here is the full code that includes all the functions,

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

// Max number of candidates
#define MAX 9

// preferences[i][j] is number of voters who prefer i over j
int preferences[MAX][MAX];

// locked[i][j] means i is locked in over j
bool locked[MAX][MAX];

// Each pair has a winner, loser
typedef struct
{
    int winner;
    int loser;
}
pair;

// Array of candidates
string candidates[MAX];
pair pairs[MAX * (MAX - 1) / 2];

int pair_count;
int candidate_count;

// Function prototypes
bool vote(int rank, string name, int ranks[]);
void record_preferences(int ranks[]);
void add_pairs(void);
void sort_pairs(void);
void lock_pairs(void);
void print_winner(void);
bool cycle(int cycle_end, int cycle_start);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2)
    {
        printf("Usage: tideman [candidate ...]\n");
        return 1;
    }

    // Populate array of candidates
    candidate_count = argc - 1;
    if (candidate_count > MAX)
    {
        printf("Maximum number of candidates is %i\n", MAX);
        return 2;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        candidates[i] = argv[i + 1];
    }

    // Clear graph of locked in pairs
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            locked[i][j] = false;
        }
    }

    pair_count = 0;
    int voter_count = get_int("Number of voters: ");

    // Query for votes
    for (int i = 0; i < voter_count; i++)
    {
        // ranks[i] is voter's ith preference
        int ranks[candidate_count];

        // Query for each rank
        for (int j = 0; j < candidate_count; j++)
        {
            string name = get_string("Rank %i: ", j + 1);

            if (!vote(j, name, ranks))
            {
                printf("Invalid vote.\n");
                return 3;
            }
        }

        record_preferences(ranks);

        printf("\n");
    }

    add_pairs();
    sort_pairs();
    lock_pairs();
    print_winner();
    return 0;
}

// Update ranks given a new vote
bool vote(int rank, string name, int ranks[])
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(name, candidates[i]) == 0)
        {
            ranks[rank] = i;
            return true;
        }
    }
    return false;
}

// Update preferences given one voter's ranks
void record_preferences(int ranks[])
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            preferences[ranks[i]][ranks[j]]++;
        }
    }
    return;
}

// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        for (int j = i + 1; j < candidate_count; j++)
        {
            if (preferences[i][j] > preferences[j][i])
            {
                pairs[pair_count].winner = i;
                pairs[pair_count].loser = j;
                pair_count++;
            }
            else if (preferences[i][j] < preferences[j][i])
            {
                pairs[pair_count].winner = j;
                pairs[pair_count].loser = i;
                pair_count++;
            }
        }
    }
    return;
}

// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{
    // TODO
    for (int i = 0; i < pair_count; i++)
    {
        int max = i;
        for (int j = i; j < pair_count; j++)
        {
            if (preferences[pairs[j].winner][pairs[j].loser] > preferences[pairs[max].winner][pairs[max].loser])
            {
                max = j;
            }
        }
        pair temp = pairs[i];
        pairs[i] = pairs[max];
        pairs[max] = temp;
    }
    return;
}

// Check for cycle by checking arrow coming into each candidate

bool cycle(int cycle_end, int cycle_start)
{
    // Return true if there is a cycle
    if (cycle_end == cycle_start)
    {
        return true;
    }

    // Loop through all the candidates
    for (int i = 0; i < candidate_count; i++)
    {
        if (locked[cycle_end][i])
        {
            if (cycle(i, cycle_start))
            {
                return true;
            }
        }
    }
    return false;
}

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // TODO
    for (int i = 0; i < pair_count; i++)
    {
        if (!cycle(pairs[i].loser, pairs[i].winner))
        {
            locked[pairs[i].winner][pairs[i].loser] = true;
        }
    }
    return;
}

// Print the winner of the election
void print_winner(void)
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        bool loser = false;
        for (int j = 0; j < candidate_count; j++)
        {
            if (locked[j][i])
            {
                loser = true;
                break;
            }
        }
        if (loser)
        {
            continue;
        }
        if (!loser)
        {
            printf("%s\n", candidates[i]);
        }
    }
    return;
}

Hope this helps you, Good luck!

CS50 psets 3 runoff problem my solution with code (2022)

This is my solution to cs50 psets 3 runoff problem. In this problem set, we have to create a program that runs a program of the runoff election.

In the previous post, I brought you my solution to the CS50 psets 3 plurality problem. But that program follows a very simple algorithm to determine the winner of an election. It is simply every voter gets one vote and the candidate with the most votes wins.

But what if two candidates get the same amount of votes? the above program does not have a solution for that. In this runoff, the method gives a solution to that problem. So in this method, each voter gets 3 chances to vote and rank their favorite candidate.

When you read the full description of psets 3 you’ll understand what is runoff method and how it solve the voting problem. I’m not going to explain it here again.

Let’s see what is my solution to the cs50 psets 3 runoff problem. Here is my code,

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

// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9

// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES];

// Candidates have name, vote count, eliminated status
typedef struct
{
    string name;
    int votes;
    bool eliminated;
}
candidate;

// Array of candidates
candidate candidates[MAX_CANDIDATES];

// Numbers of voters and candidates
int voter_count;
int candidate_count;

// Function prototypes
bool vote(int voter, int rank, string name);
void tabulate(void);
bool print_winner(void);
int find_min(void);
bool is_tie(int min);
void eliminate(int min);

int main(int argc, string argv[])
{
    // Check for invalid usage
    if (argc < 2)
    {
        printf("Usage: runoff [candidate ...]\n");
        return 1;
    }

    // Populate array of candidates
    candidate_count = argc - 1;
    if (candidate_count > MAX_CANDIDATES)
    {
        printf("Maximum number of candidates is %i\n", MAX_CANDIDATES);
        return 2;
    }
    for (int i = 0; i < candidate_count; i++)
    {
        candidates[i].name = argv[i + 1];
        candidates[i].votes = 0;
        candidates[i].eliminated = false;
    }

    voter_count = get_int("Number of voters: ");
    if (voter_count > MAX_VOTERS)
    {
        printf("Maximum number of voters is %i\n", MAX_VOTERS);
        return 3;
    }

    // Keep querying for votes
    for (int i = 0; i < voter_count; i++)
    {

        // Query for each rank
        for (int j = 0; j < candidate_count; j++)
        {
            string name = get_string("Rank %i: ", j + 1);

            // Record vote, unless it's invalid
            if (!vote(i, j, name))
            {
                printf("Invalid vote.\n");
                return 4;
            }
        }

        printf("\n");
    }

    // Keep holding runoffs until winner exists
    while (true)
    {
        // Calculate votes given remaining candidates
        tabulate();

        // Check if election has been won
        bool won = print_winner();
        if (won)
        {
            break;
        }

        // Eliminate last-place candidates
        int min = find_min();
        bool tie = is_tie(min);

        // If tie, everyone wins
        if (tie)
        {
            for (int i = 0; i < candidate_count; i++)
            {
                if (!candidates[i].eliminated)
                {
                    printf("%s\n", candidates[i].name);
                }
            }
            break;
        }

        // Eliminate anyone with minimum number of votes
        eliminate(min);

        // Reset vote counts back to zero
        for (int i = 0; i < candidate_count; i++)
        {
            candidates[i].votes = 0;
        }
    }
    return 0;
}

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

// Tabulate votes for non-eliminated candidates
void tabulate(void)
{
    // TODO
    for (int i = 0; i < voter_count; i++)
    {
        for (int j = 0; j < candidate_count; j++)
        {
            if (candidates[preferences[i][j]].eliminated == false)
            {
                candidates[preferences[i][j]].votes += 1;
                break;
            }
        }
    }
    return;
}

// Print the winner of the election, if there is one
bool print_winner(void)
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        string most_votes = candidates[i].name;
        if (candidates[i].votes > voter_count / 2)
        {
            printf("%s\n", most_votes);
            return true;
        }
    }
    return false;
}

// Return the minimum number of votes any remaining candidate has
int find_min(void)
{
    // TODO
    int min_votes = voter_count;
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].eliminated == false && candidates[i].votes < min_votes)
        {
            min_votes = candidates[i].votes;
        }
    }
    return min_votes;
}

// Return true if the election is tied between all candidates, false otherwise
bool is_tie(int min)
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].eliminated == false && candidates[i].votes != min)
        {
            return false;
        }
    }
    return true;
}

// Eliminate the candidate (or candidates) in last place
void eliminate(int min)
{
    // TODO
    for (int i = 0; i < candidate_count; i++)
    {
        if (candidates[i].votes == min)
        {
            candidates[i].eliminated = true;
        }
    }
    return;
}

Hope this helps you!

The solution to cs50 labs 2 scrabble problem (2022)

In this problem, we have to create a game of Scrabble. In this game, players create words to score points. The number of points is the sum of the point values of each letter in the word.

So here is my solution for the cs50 labs 2 scrabble problem.

#include <ctype.h>
#include <cs50.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};

// ASCII values for upercase letters
int uc_letters[] = {65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90};

// ASCII values for lowercase letters
int lc_letters[] = {97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122};

int temp_point[] = {};

int compute_score(string word);

int main(void)
{
    // Get input words from both players
    string word1 = get_string("Player 1: ");
    string word2 = get_string("Player 2: ");

    // Score both words
    int score1 = compute_score(word1);
    int score2 = compute_score(word2);

    // TODO: 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 compute_score(string word)
{
    // TODO: Compute and return score for string
    int score = 0;

    for (int i = 0; i < strlen(word); i++)
    {
        if (isupper(word[i]))
        {
            for (int j = 0; j < sizeof(uc_letters); j++)
            {
                if (word[i] == uc_letters[j])
                {
                    temp_point[i] = POINTS[j];
                    score += temp_point[i];
                }
            }
        }
        else if (islower(word[i]))
        {
            for (int k = 0; k < sizeof(lc_letters); k++)
            {
                if (word[i] == lc_letters[k])
                {
                    temp_point[i] = POINTS[k];
                    score += temp_point[i];
                }
            }
        }
        else
        {
            i++;
        }
    }

    return score;
}

November 7, 2022

The solution to cs50 psets 1 credit problem (2022)

In this problem cs50 psets 1 credit, we have to implement a program called “credit.c” that prompts the user for a credit card number. Then prints out whether it is a valid American Express, Mastercard, or Visa card number by checking in the digits of the input number.

So, to solve this problem we should use Luhn’s algorithm. If you are looking at this post, I’m guessing that you already know what this formula is and how we should implement the algorithm and build the program.

I’ll give you my solution for this cs50 psets 1 credit problem.

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

//AMERX 15 STRT 34 OR 37
//MC 16 STRT 51, 52, 53, 54, 55
//VZA 13 OR 16 STRT 4

int main(void)
{
    long creditNumber;

    do
    {
        creditNumber = get_long("Number: ");
    }
    while (creditNumber <= 0);

    long creditCard = creditNumber;
    int sum = 0;
    int count =0;
    long divider = 10;

    while (creditCard > 0)
    {
        int lastDigit = creditCard % 10;
        sum = sum + lastDigit;
        creditCard = creditCard / 100;
    }

    creditCard = creditNumber / 10;
    while (creditCard > 0)
    {
        int lastDigit = creditCard % 10;
        int byTwo = lastDigit * 2;
        sum = sum + (byTwo % 10) + (byTwo / 10);
        creditCard = creditCard / 100;
    }

    creditCard = creditNumber;
    while (creditCard != 0)
    {
        creditCard = creditCard / 10;
        count++;
    }

    for (int i = 0; i < count - 2; i++)
    {
        divider = divider * 10;
    }

    int firstDigit = creditNumber / divider;
    int firstTwoDigits = creditNumber / (divider / 10);

    if ((sum % 10) == 0)
    {
        if (firstDigit == 4 && (count == 13 || count == 16))
        {
            printf("VISA\n");
        }
        else if ((firstTwoDigits == 34 || firstTwoDigits == 37) && count == 15)
        {
            printf("AMEX\n");
        }
        else if ((firstTwoDigits > 50 && firstTwoDigits < 56) && count == 16)
        {
            printf("MASTERCARD\n");
        }
        else
        {
            printf("INVALID\n");
        }
    }
    else {
        printf("INVALID\n");
    }
}

If you found this post useful, give it a share!

you may also like to read: The solution to CS50 psets 1 cash problem (2022)

February 4, 2025

Tag: solution