Craig Rodrigues!

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!

Game of Fifteen

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

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

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:

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

6/15/16

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

image10

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

Learning to Code: Week 6 - Codecademy

Learning to Code: Week 4 - Algorithms