**6/9/16**

- Finished getting to test my sort function.
**Doesn’t work right yet at all.**Probably since my function doesn’t return anything! Oops. - Figured out I don’t need to do constant swapping to get my insertion sort to work. No more swap function and fixed my insertion sort function.
- Visualization: https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
- Tried to implement a Binary Search function. It didn’t work the first time so I used GDB to debug it and found out that my midpoint function was (max-min)/2 when it should be (max+min)/2. God dammit.
- https://www.reddit.com/r/cs50/comments/340zgi/pset_3_recursive_binary_search/
- http://cs50.stackexchange.com/questions/9691/pset3-binary-search-problems
- The Stack Exchange link above gave me a EUREKA moment.
- I read it 3-4 times before I finally understood that I was missing
**return**from my functions just like the guy in the question had done. **I didn’t understand that the function had to return itself rather than just execute itself to work!**- Was bashing my head against the desk on that one since it just threw the same error over and over and always seemed to return false if I ended up adding a return at the end. (duh)

- helpers.c is now correct: https://gist.github.com/CraigRodrigues/1848dadcb83a2fcc7eee0624dbf436e5

/** * 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; }

- Finished questions.txt for Game of Fifteen
- Implemented init, draw, search, legalmove functions in my Fifteen.c program

**6/10/16**

**Continuing work on Fifteen.c**- Implemented
**swaptile**function.- I forgot to change the location of the blank tile so it wasn’t working at first.
- That was an easy fix and now the game seems to be complete except I need to make the
**won**function work. - Also I had the search function be
**int search(int tile)**when it actually doesn’t need to return anything so I changed that to void. - Not sure what I was thinking yesterday. It just needs to search, not return.

- Worked on
**won**function for a long time. I understood the implementation easy enough, just kept running into small errors and mistakes and it took a lot longer than I though to get it right! - I didn’t implement it this way, but I did see a cool little algorithm to determine that the tiles are in fact in the correct place on StackExchange afterwards: http://cs50.stackexchange.com/questions/1317/pset3-won-function-works-only-with-3x3-board-where-am-i-wrong/1320#1320
- So the number at position board[i][j] should be equal to ((d*i) + (j+1)). That’s pretty cool.
- I don’t think it makes much difference, but all I did was add a check to see if the counter was correct AND if the final tile was zero.
- Both conditions had to be true to consider the game won.

- See my solution in action below!

**Uploaded pset3 and did pset3 final questions.***Click Here For My Solution Gist*

/** * fifteen.c * * Computer Science 50 * Problem Set 3 * * Implements Game of Fifteen (generalized to d x d). * * Usage: fifteen d * * whereby the board's dimensions are to be d x d, * where d must be in [DIM_MIN,DIM_MAX] * * Note that usleep is obsolete, but it offers more granularity than * sleep and is simpler to use than nanosleep; `man usleep` for more. */ #define _XOPEN_SOURCE 500 #include <cs50.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> // constants #define DIM_MIN 3 #define DIM_MAX 9 // board int board[DIM_MAX][DIM_MAX]; // dimensions int d; int tile_i; int tile_j; int blank_i; int blank_j; // prototypes void clear(void); void greet(void); void init(void); void draw(void); bool move(int tile); bool won(void); void search(int tile); bool legalmove(void); void swaptile(int tile); int main(int argc, string argv[]) { // ensure proper usage if (argc != 2) { printf("Usage: fifteen d\n"); return 1; } // ensure valid dimensions d = atoi(argv[1]); if (d < DIM_MIN || d > DIM_MAX) { printf("Board must be between %i x %i and %i x %i, inclusive.\n", DIM_MIN, DIM_MIN, DIM_MAX, DIM_MAX); return 2; } // open log FILE* file = fopen("log.txt", "w"); if (file == NULL) { return 3; } // greet user with instructions greet(); // initialize the board init(); // accept moves until game is won while (true) { // clear the screen clear(); // draw the current state of the board draw(); // log the current state of the board (for testing) for (int i = 0; i < d; i++) { for (int j = 0; j < d; j++) { fprintf(file, "%i", board[i][j]); if (j < d - 1) { fprintf(file, "|"); } } fprintf(file, "\n"); } fflush(file); // check for win if (won()) { printf("ftw!\n"); break; } // prompt for move printf("Tile to move: "); int tile = GetInt(); // quit if user inputs 0 (for testing) if (tile == 0) { break; } // log move (for testing) fprintf(file, "%i\n", tile); fflush(file); // move if possible, else report illegality if (!move(tile)) { printf("\nIllegal move.\n"); usleep(500000); } // sleep thread for animation's sake usleep(500000); } // close log fclose(file); // success return 0; } /** * Clears screen using ANSI escape sequences. */ void clear(void) { printf("\033[2J"); printf("\033[%d;%dH", 0, 0); } /** * Greets player. */ void greet(void) { clear(); printf("WELCOME TO GAME OF FIFTEEN\n"); usleep(2000000); } /** * Initializes the game's board with tiles numbered 1 through d*d - 1 * (i.e., fills 2D array with values but does not actually print them). */ void init(void) { // Need to know the number of slots needed int n = (d*d) - 1; // Loop through 2D array with columns then rows for (int i = 0; i < d; i++) { for (int j = 0; j < d; j++) { board[i][j] = n; n--; } printf("\n"); } // Check if the number of tiles is odd. If so swap the 1 and 2 tiles. if (((d*d) - 1) % 2 != 0) { int temp = board[d-1][d-2]; board[d-1][d-2] = board[d-1][d-3]; board[d-1][d-3] = temp; } // Mark position of blank tile (bottom right) blank_i = d-1; blank_j = d-1; } /** * Prints the board in its current state. */ void draw(void) { // Prints the board, but if the value is 0 print an underscore instead. for (int i = 0; i < d; i++) { for (int j = 0; j < d; j++) { if (board[i][j] < 10) //formatting for single digits is different. { if (board[i][j] == 0) //checking if value is 0 to print a blank tile. { printf(" [_] "); } else { printf(" [%d] ", board[i][j]); } } else { printf("[%d] ", board[i][j]); } } printf("\n"); //space between each line } } /** * If tile borders empty space, moves tile and returns true, else * returns false. */ bool move(int tile) { // check if tile actually exists if (tile > (d*d)-1 || tile < 1) return false; // Linear search for the tile user gives us search(tile); // Once tile has been found see if blank tile is adjacent to it // Check if adjacent tile is a legit tile, then check if is blank if (legalmove()) { swaptile(tile); // if legal move swap blank tile with tile return true; } else return false; return false; } /** * Returns true if game is won (i.e., board is in winning configuration), * else false. */ bool won(void) { // linear search through array and check if increments in order int counter = 1; for (int i = 0; i < d; i++) { for (int j = 0; j < d; j++) { if (board[i][j] == counter) counter++; } } if (counter == d*d && board[d-1][d-1] == 0) return true; else return false; } // linear searches for the selected tile's location. no need for faster search. void search(int tile) { for (int i = 0; i < d; i++) { for (int j = 0; j < d; j++) { if (board[i][j] == tile) { tile_i = i; tile_j = j; } } } } // check if the blank tile is next to the tile bool legalmove(void) { // check if on top row. If so check up for 0 if (tile_i > 0 && board[tile_i - 1][tile_j] == 0) return true; // bottom if (tile_i < d-1 && board[tile_i + 1][tile_j] == 0) return true; // left if (tile_j > 0 && board[tile_i][tile_j - 1] == 0) return true; // right if (tile_j < d-1 && board[tile_i][tile_j + 1] == 0) return true; else return false; } // swaps tile with blank tile void swaptile(tile) { int temp = board[tile_i][tile_j]; board[tile_i][tile_j] = board[blank_i][blank_j]; board[blank_i][blank_j] = temp; // update location of blank tile blank_i = tile_i; blank_j = tile_j; }

- Found this website for Big O notation studying: http://bigocheatsheet.com/
- Build your knowledge of Data Structures through visualizations and practice!

**6/11/16**

Didn’t get much of anything done today, had a powerlifting meet. However, Jeff was kind enough to link this place in Atlanta called GreaterSum. It is a curriculum and internship/apprenticeship to create developers.

They seem to have coaching services that has code reviews and an apprenticeship that doesn’t pay much, but does allow for earning money while learning!

I will be attending their June 23rd workshop that is an introduction to Javascript.

**6/12/16**

- My Grokking Algorithms book arrived. I started reading it. So far I’m on chapter 2.
- Chapter 1: Binary search and Big O notation and Traveling Salesman problem.
- Chapter 2: Arrays and Linked lists. Selection sort.
- Chapter 3: Recursion

- All the examples in the book are written in Python and so far I can already tell by trying to rewrite the examples in C that Python is a much easier/cooler language!
- So for instance I’ve noticed so far that you don’t need to end a line with a ; nor do you need to use { } at all!
- Also in a for loop you can just say
**for i in range(1, len(arr))**instead of for**(int i; i < sizeofarray, i++)**. - Much less typing involved!

- Also in a for loop you can just say
- I just read python doesn’t use arrays, but instead just lists? Like linked lists or? What’s the difference?

**6/13/16**

*Grokking Algorithms*:**Chapter 4 QUICKSORT**: Divide and Conquer, Quicksort, brief look at Inductive Proofs, Big O notation revisisted, Mergesort vs Quicksort, Avg Case vs Worst Case**Chapter 5 HASH TABLES**: Hash functions, Use cases, Collisions, Caching, Performance, Load Factor

4.1 Recursive Sum Function in C

//n is the last index of the array int arr_sum(int arr[], int n ) { //base case if (n == 0) { return arr[0]; } return (arr[n] + arr_sum(arr,n-1)); } int main(void) { int arr[] = {1,2,3,4,5}; int sum; sum = arr_sum(arr,4); printf("\nsum is:%d\n",sum); return 0; }

4.2 Recursive Counting Function in C (used repl.it)

#include "stdio.h" //n is the last index of the array int arr_count(int count, int n) { //base case if (n == 0) { return count; } return (count + arr_count(count,n-1)); } int main(void) { // Disable stdout buffering setvbuf(stdout, NULL, _IONBF, 0); int arr[] = {1,2,3,4,5,6,7,8,9}; int count = 1; count = arr_count(count, 8); printf("\ncount is: %d\n", count); return 0; }

4.3 Recursive Max Function in C

#include "stdio.h" // find the max number in a list/array // n is the last index of the array int arr_max(int arr[], int max, int n) { //base case if (n == 0) { if (arr[n] > max) max = arr[n]; return max; } else { if (arr[n] > max) max = arr[n]; return arr_max(arr, max, n-1); } } int main(void) { // Disable stdout buffering setvbuf(stdout, NULL, _IONBF, 0); int arr[] = {33,2,3,11,5,6,7,8,9}; int max = 0; max = arr_max(arr, max, 8); printf("\nMax is: %d\n", max); return 0; }

- The standard C library already has a quicksort function called qsort!
- How does quicksort differ from mergesort? (answered 3 pages later in book)

**6/14/16**

Wasn’t able to get much done today at all.

Discovered website: http://codepad.org/

A few books to add to my reading list:

- C Programming Absolute Beginner's Guide (3rd Edition)
- C Programming For Beginners: The Simple Guide to Learning C Programming Language Fast!
- C by Example (Cambridge Computer Science Texts)

**6/15/16**

Study resources: https://github.com/dargaCode/WebDevStudyResources

- Watched Week 4 Lecture 1
- How to swap variables without using a temporary placeholder.

void int(swap) { a = a ^ b; b = a ^ b; a = a ^ b; }

*Why does the above work though?*

- CS50’s getString() function only returns the ADDRESS LOCATION of the first letter in memory, and not the actual string.
- So comparing strings to each other will never be the same.
- So far have been using variables to store strings, but from now on we will use
**char***

- Podcast: http://softwareengineeringdaily.com/category/podcast/ (It’ll go over my head I’m sure)
- Watched Week 4 Lecture 2
- Struct = custom data type! Cool.
- Strcmp = string compare function already in C.
- To pass address of variables into a function you have to use &. Example: swap(&x, &y)