I just successfully finished pset3 at CS50. It was pretty challenging! The final product is the “game of 15” one inputs a number for how size the board is, then it produces a board with all numbers and it allows the player to select a tile to move (must be adjacent to blank to work) replicating the “switching” that one does in the actual physical game. 🙂

Things I learned / internalized:

• Arrays on C must have a declared size, and this can’t really be adjusted later. An array is a string of memory, and you can’t just print an array like you do on python. To print it you need to do a loop that prints each individual term of the declared Array.
• One needs to be careful not to try access parts of memory not allocated not to get segmentation fault errors.
• Did my first C recursive program and loved it.
• Getting more and more comfortable with the initialization of variables 🙂

Lastly, this blog is being invaluable for me to keep track of where I am, what I have done etc… 1000 times better than taking notes on separate words or on paper or whatever. I am loving it.

 

Today I took a breadk, and discovered checkio.org a site that looks pretty interesting. It basically challenges you with different problems that you need to solve with code, and you earn points etc…

As a side note, the language used there is python. OMG… after doing C for some time coding in python feels like cheating :D! Is like you have a pre-defined function for everything already, seriously XD!

The fun continues.

 

Don’t code before you have conceptualized what you want to code

Binary Search

I am so happy. I have coded binary search from scratch, and this time it feel much much smoother, much quicker even if it was probably the most complex algorithm I have programmed till now.

The main difference is that instead of trying to directly write code, I first of all conceptualized the problem on a word file, and then solved the most complex parts of the algorythm in paper there itslef. Then I only had to pass the code to proper form on the IDE:.

This is how I solved some of the most tricky part. Above you can see what happens when you have an array, and check middle value … how long are the remaining two halfs? This is extremely hard to visualize unless you write it like that. If you do it you realize that, taking advantage of integer division (remainder is lost), you can generalize both halfs to an expression DEPENDING IF the original array is EVEN or ODD.

Below you can also see how I find that integer division can also be used to check if a number is odd or even. This I learned from some of the previous MIT 6.00 classes :). It is great. With integer division you know a number is odd if: (n+1)/2 = n/2 // (remember that in integer division remainder disappears)

And this is how it looked when I passed the code from WORD to my IDE:

And this is my final code. Enjoy :D!

bool binary_search(int value, int values[], int n)
{
    while (n > 0)
    {
        int middle_position = n/2;
        int middle_value = values[middle_position];
        int size_right;
        int size_left;
        
        if (middle_value == value)
        {
            return true;
        }
        else if (value > middle_value)
        {
            if (is_even(n))
            {
                size_right = ((n - 1) / 2);
            }
            else
            {
                size_right = (n / 2);
            }
            
            int values_right [size_right];
            
            for (int i = 0; i < size_right; i++)
            {
                values_right [i] = values [(middle_position) + 1 + i];
            }
            binary_search (middle_value, values_right, size_right);
        }
        else if (value < middle_value)
        {
            size_left = (n / 2);
            int values_left [size_left];
            
            for (int i = 0; i < size_left; i++)
            {
                values_left [i] = values [i];
            }
            binary_search (middle_value, values_left, size_left);
        }
        
    }
    return false;
}


// Function to check if an integer is even or odd

bool is_even(int n)
{
    if ( ((n + 1) / 2) == (n / 2) )
    {
        return true;
    }
    else 
    {
        return false;
    }
}

I have finished the first part of pset3.

It took me some time to implement selection sort. Arrays in C are def. harder than arrays on Python (Or lists). The interesting thing is that in Python you can print an array and see it how it looks and what is inside. In C you can’t do that, and so to see what’s inside of an array you need to print through a loop!

Hence the concept of “array” that I had is different. In C the important thing to keep in mind is that:

• Arrays have a determined size that you need to provide and you must declare this.
  • Will be interesting how to deal with arrays of unknown size… size will I guess be a variable that changes if you need to add more things in I guess?
• You need to be careful as if you look into parts of array not allocated, you will get segmentation errors (as you are touching parts of memory you shouldn’t)