Craig Rodrigues!

## Jun 15 Learning to Code: Week 5 - Game of Fifteen

#### 6/9/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.
*
* 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! ```/**
* 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);
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!
• 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
```//n is the last index of the array
int arr_sum(int arr[], int n )
{
//base case
if (n == 0)
{
return arr;
}

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;
}```
```#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;
}```
```#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.

#### 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)