Craig Rodrigues!

Learning to Code: Week 4 - Algorithms

6/1/16 - Continued

6/2/16

  • Shawn helped me look into making a function for the water.c program. I worked on it for a bit.
  • Error 1 - 0 arguments instead of 2.

image08

  • Error 2 - variable bottles but nothing there. Call the function INTO that variable?

image28

  • Boom, got it to work. That was pretty cool.
    • Now I can account for variable shower heads.
    • I think the input question could be better to explain what the metric is for waterflow etc.
  • I didn’t think of rounding errors.

Code Here: https://gist.github.com/CraigRodrigues/aeff70c00abf8fd4628f19e57c837a55

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

// function that returns the number of 16oz bottles used
int getBottles(int time, int showerflow)
{
    return (time * showerflow)/16;
}

int main(void)
{
    printf("How long did you shower today? (minutes)\n");
    int time = GetInt();

    printf("What is your showerhead flow? (oz/minute)\n");
    int showerflow = GetInt();

    int bottles = getBottles(time, showerflow);
    printf("Minutes Showered: %i\n16oz Bottles Used: %i\n", time, bottles);
}

I put a function in Caesar.c!

Code Here: https://gist.github.com/CraigRodrigues/6e3724fbe3bd5fed9d05d2cafcedbc5c

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

/**
 * Caesar.c
 * A program that encrypts messages using Caesar’s cipher. Your program must
 * accept a single command-line argument: a non-negative integer. Let’s call it
 * k for the sake of discussion. If your program is executed without any
 * command-line arguments or with more than one command-line argument, your
 * program should yell at the user and return a value of 1.
 * 
 * */

 // function that encrypts a character based on the key submitted
 int encryptCode(char code, int key)
 {
    if islower(code)
    {
        code = ((((code + key) - 97) % 26) + 97);
        return code; 
    }
    else if isupper(code)
    {
        code = ((((code + key) - 65) % 26) + 65);
        return code;
    }   

    //if neither then just return whatever it is
    else
        return code;
 }

 int main(int argc, string argv[])
 {
    // check for 2 arguments only
    if (argc != 2)
    {
        printf("Nope\n");
        return 1;
    }

    // once I check for correct argv put key into an int k
    int k = atoi(argv[1]);

    // check if the integer is non-negative
    if (k < 0)
    {
        printf("Nope\n");
        return 1;
    }
    else
    {
        // prompt user for a code to encrypt
        string code = GetString();

        for (int i = 0, n = strlen(code); i < n; i++)
            {
                printf("%c", encryptCode(code[i], k););
            }
            printf("\n");
            return 0;
    }
 }
  • Not sure about the names of the variables though. I think it works okay.
  • Also not sure if functions should be in printf or on a separate line going into another variable?
    • Example: printf("%c", encryptCode(code[i], k));
printf("%c", encryptCode(code[i], k));

6/3/16

  • Got stuck in a few places on Credit but eventually solved it after working on it for an hour this morning. I need to extract a few functions to make the program really the way I want it, but right now it functionally is correct!
  • That one was tough. I decided to use arrays, but I’m not sure if that is ideal. I feel like there are easier ways to manipulate digits of a number without putting each digit into a slot in an array.
  • So far I am using a massive number of printf statements inside my program to be able to check if things are working. Don’t know of a better way at the moment.
  • See below for what I did.

image07

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

// calculates the number of digits in the card number
int getCardDigits(long long card_num)
{
    int card_digits = (int)log10(card_num) + 1;
    return card_digits;
}

int main(void)
{
    // get card number from user
    printf("Number: ");
    long long card_num = GetLongLong();

    // use digits function
    int card_digits = getCardDigits(card_num);

    // if not a valid credit card length print invalid immediately    
    if (card_digits != 13 && card_digits != 15 && card_digits != 16)
    {
        printf("INVALID\n");
        return 0;
    }

    // storing the individual digits in an array
    int numberArray[card_digits];
    long long count = card_num;
    int i = 0;

    while (count != 0)
    {
        numberArray[card_digits - 1 - i] = count % 10;
        count = count/10;
        i++;
    }

    // Every other number starting from the second to last in array
    int numberArray2[card_digits/2];
    int k = 2;
    int l = 0;

    while ((card_digits - k) > -1)
    {
        numberArray2[l] = 2 * numberArray[card_digits - k];
        k = k + 2;
        l++;
    }

    int digit_times_two = 0;

    for (int j = 0; j < card_digits/2; j++)
    {
        if (numberArray2[j] > 9)
        {
            int split_digit = 0;
            digit_times_two = digit_times_two + (numberArray2[j] % 10);
            split_digit = numberArray2[j]/10;
            digit_times_two = digit_times_two + split_digit;
        }
        else
        {
            digit_times_two = digit_times_two + numberArray2[j];
        }
    }

    // the remainging digits added together after put in 3rd array
    int numberArray3[card_digits - (card_digits/2)];
    int m = 1;
    int n = 0;

    while ((card_digits - m) > -1)
    {
        numberArray3[n] = numberArray[card_digits - m];
        m = m + 2;
        n++;
    }

    int other_digit_count = 0;

    for (int j = 0; j < (card_digits - (card_digits/2)); j++)
    {
        other_digit_count = other_digit_count + numberArray3[j];
    }

    int companyId;
    int companyId2;

    // validating Luhn algorithm
    if ((digit_times_two + other_digit_count) % 10 == 0)
    {
        companyId = numberArray[0];
        companyId2 = numberArray[1];
    }
    else
    {
        printf("INVALID\n");
        return 0;
    }

    // checking which card company
    if (card_digits == 15 && companyId == 3 && (companyId2 == 4 || companyId2 == 7))
    {
        printf("AMEX\n");
    }
    else if (card_digits == 16 && companyId == 5 && (companyId2 >= 1 && companyId2 <= 5))
    {
        printf("MASTERCARD\n");
    }
    else if ((card_digits == 13 || card_digits == 16) && companyId == 4)
    {
        printf("VISA\n");
    }
    else
    {
        printf("INVALID\n");
    }

    return 0;
}

STEPS:

  1. Prompt user for credit card number. (long long)
  2. Check length of the card #. If not valid print INVALID.
  3. Function: cardLength to get the number of digits in a card number using Log10 + 1.
  4. Put the digits into an array by using % and a loop and /10 etc.
  5. Loop from the back to the front of the new array of digits and take every other digit.
  6. Multiply the results of 5 by 2.
  7. Add the individual digits together (what do you do about double digits?)
  8. Add to #7 the sum of the remaining digits.
  9. If answer to #8's final digit is a zero then the card number is legit.
  10. Check the card's first digit(s) to get the card company.
  11. If #9 & #10 are true then print out what card company it is and return 0.

NOTES/THOUGHTS:

  • Had to do a bit of research for the questions I had such as how to find out the number of digits in an integer and how to put the individual digits of a number into an array. Once I found those it was just a matter of piecing the puzzle together doing down the list of steps above.
  • One loop I had initialized the counter i inside the loop itself so it actually never incremented. That took a while to see, yet it was such a simple problem!
  • I had to figure out how to reverse a loop to put the digits into it back to front instead of front to back.
  • Put "return 1" in a couple of places when the program really wanted "return 0" regardless.
  • Need to remember that using the data type int only takes the integer portion not anything after the decimal. Useful to remember for this problem set.
  • Bought the Grokking Algorithms book as next lecture begins to talk about them and big O notation.

6/4/16

Nothing today 😢

6/5/16

Week 3 - Lecture 1

  • Bubble sort: Taking two things and comparing them then moving through the array. If not sorted after that doing it again. Pretty damn slow.
  • Selection sort: going through the list and selecting the next smallest element and moving it to the front.
  • Insertion sort: Go through the list and insert the smallest number where it should be, pushing everything else forward. Don’t have to go back through the list more than once.
  • Big O describes the upper bound on an algorithm. Bubble Sort, selection and insertion sort big O is n2.
  • Big O = worst case scenario.
  • Binary Search has a Big O of n.
  • Binary search: Divide and conquer (phone book example) is O = log n since the list gets half as small every time.
  • Ω (omega) is the lower bound on an algorithm. Best case scenario.
  • Video: What Different Sorting Algorithms Sound Like
  • Video: Why Study Algorithms?

Week 3 - Lecture 2

image12

6/6/16

Very cool blog posts from someone who successfully followed the path I want to (also very intimidating):

If you’re struggling to understand a concept in a book or on Wikipedia, look up Youtube videos of people explaining it in different ways until you get it. I’ve found this strategy amazingly effective.

SECTION VIDEOS & SHORTS

  • GDB
  • Computational Complexity
  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Linear Search
  • Binary Search
  • Algorithms Summary
  • Asymptotic Notation
  • Quicksort

Click Here for my Handwritten Notes

6/7/16

  • Worked on pset 3 Game of Fifteen.
  • Binary Search Trees
  • Another video on debugging with GDB (23 min). Incredibly useful video.
  • An unsigned int is just an int that cannot be negative.
  • Finished generate.c by adding comments to distribution code.
  • https://reference.cs50.net/stdlib.h/drand48 was a useful resource.

6/8/16

/**
 * helpers.c
 *
 * Computer Science 50
 * Problem Set 3
 *
 * Helper functions for Problem Set 3.
 */

#include <cs50.h>

#include "helpers.h"

/**
 * Returns true if value is in array of n values, else false.
 * 
 * Re-write search in such a way that it uses linear search, 
 * returning true if value is in values and false if value is not in values.
 * Take care to return false right away if n isn’t even positive.
 */
bool search(int value, int values[], int n)
{
    // linear search algorithm
    for (int i = 0; i < n; i++)
    {
        if (values[i] == value)
            return true;
    }

    return false;
}

/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    // TODO: implement an O(n^2) sorting algorithm
    return;
}
  • Worked on implementing Insertion sort - pseudocode from wikipedia really helped me visualize how to get it to work.

image09

/**
 * helpers.c
 *
 * Computer Science 50
 * Problem Set 3
 *
 * Helper functions for Problem Set 3.
 */

#include <cs50.h>

#include "helpers.h"

/**
 * Returns true if value is in array of n values, else false.
 * 
 * Re-write search in such a way that it uses linear search, 
 * returning true if value is in values and false if value is not in values.
 * Take care to return false right away if n isn’t even positive.
 * 
 * Implement sort so that the function actually sorts, from smallest to largest,
 * the array of numbers that it’s passed, in such a way that its running time is
 * in O(n2), where n is the array’s size.
 */

// linear search algorithm
// bool search(int value, int values[], int n)
// {
//    for (int i = 0; i < n; i++)
//    {
//        if (values[i] == value)
//            return true;
//    }
//    
//    return false;
// }

bool binarySearch(int value, int values[], int min, int max)
{
    int midpoint = 0;

    if (max < min)
        return false;
    else
        midpoint = (max + min)/2;

    if (values[midpoint] < value)
        return binarySearch(value, values, midpoint + 1, max);
    else if (values[midpoint] > value)
        return binarySearch(value, values, min, midpoint - 1);
    else if (value == values[midpoint])
        return true;
    else
        return false;
}

// binary search algorithm
bool search(int value, int values[], int n)
{
    return binarySearch(value, values, 0, n-1);
}

/**
 * Sorts array of n values.
 * 
 *  Holds current value in a temporary block and compares that to the left of
 *  it in the array. If j-1 is less than the temp then move j-1 to one to the right.
 *  Do that until you find a value that is less than the temp. Insert temp right
 *  where you stopped.
 * 
 */
void sort(int values[], int n)
{
    // insertion sort algorithm

    for (int i = 1; i < n; i++)
    {

        int temp = values[i];
        int j = i;

        while (j > 0 && (values[j-1] > temp))
        {
            values[j] = values[j-1];
            j--;
        }
        values[j] = temp;
    }
    return;
}

If you somehow stumbled upon my blog and read this far and have questions just hit me up on Twitter or just email me!

Learning to Code: Week 5 - Game of Fifteen

Learning to Code: Week 3 - Vigenere Cipher