Skip to content

Instantly share code, notes, and snippets.

@mitrnsplt
Created April 17, 2014 00:59
Show Gist options
  • Save mitrnsplt/10945971 to your computer and use it in GitHub Desktop.
Save mitrnsplt/10945971 to your computer and use it in GitHub Desktop.
This solution to cs50's Game of Fifteen problem uses helper files supplied by the teaching staff
/**
* fifteen.c
*
* Computer Science 50
* Problem Set 3
*
* Implements the 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 [MIN,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>
// board's minimal dimension
#define MIN 3
// board's maximal dimension
#define MAX 9
// board, whereby board[i][j] represents row i and column j
int board[MAX][MAX];
// board's dimension
int d;
// prototypes
void clear(void);
void greet(void);
void init(void);
void draw(void);
bool move(int tile);
bool won(void);
void save(void);
int main(int argc, string argv[])
{
// greet player
greet();
// ensure proper usage
if (argc != 2)
{
printf("Usage: ./fifteen d\n");
return 1;
}
// ensure valid dimensions
d = atoi(argv[1]);
if (d < MIN || d > MAX)
{
printf("Board must be between %i x %i and %i x %i, inclusive.\n",
MIN, MIN, MAX, MAX);
return 2;
}
// initialize the board
init();
// accept moves until game is won
while (true)
{
// clear the screen
clear();
// draw the current state of the board
draw();
// saves the current state of the board (for testing)
save();
// check for win
if (won())
{
printf("ftw!\n");
break;
}
// prompt for move
printf("Tile to move: ");
int tile = GetInt();
// move if possible, else report illegality
if (!move(tile))
{
printf("\nIllegal move.\n");
usleep(500000);
}
// sleep for animation's sake
usleep(500000);
}
// that's all folks
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("GAME OF FIFTEEN\n");
usleep(2000000);
}
/**
* Initializes the game's board with tiles numbered 1 through d*d - 1,
* (i.e., fills board with values but does not actually print them),
* whereby board[i][j] represents row i and column j.
*/
void init(void)
{
// define a counter and populate the array
int c = 1;
for (int i = 0; i < d; i++)
{
for (int j = 0; j < d; j++)
{
// fill the tiles in descending order
board[i][j] = d * d - c;
c++;
}
}
//make the last tile blank
board[d-1][d-1] = 99;
// if there are an odd number of tiles, switch 1 and 2
if ((d * d)%2 == 0)
{
board[d-1][d-2] = 2;
board[d-1][d-3] = 1;
}
}
/**
* Prints the board in its current state.
*/
void draw(void)
{
for (int i = 0; i < d; i++)
{
for (int j = 0; j < d; j++)
if (board[i][j] == 99)
// print the blank tile
printf(" _ ");
else
// the tiles in descending order
printf("%2d ", board[i][j]);
}
printf("\n");
}
}
/**
* If tile borders empty space, moves tile and returns true, else
* returns false.
*/
bool move(int tile)
{
// establish algorithm for checking bordering tiles
for (int i = 0; i < d; i++)
{
for (int j = 0; j < d; j++)
{
if (board[i][j] == tile)
{
//check if the blank is to the right
if (j+1 <= d-1 && board[i][j+1] == 99)
{
board[i][j+1] = tile;
board[i][j] = 99;
return true;
}
// check if the blank is to the left
else if (j-1 >= 0 && board[i][j-1] == 99)
{
board[i][j-1] = tile;
board[i][j] = 99;
return true;
}
// check if the blank is above
else if (i-1 >= 0 && board[i-1][j] == 99)
{
board[i-1][j] = tile;
board[i][j] = 99;
return true;
}
// check if the blank is below
else if (i+1 <= d-1 && board[i+1][j] == 99)
{
board[i+1][j] = tile;
board[i][j] = 99;
return true;
}
}
}
}
return false;
}
/**
* Returns true if game is won (i.e., board is in winning configuration),
* else false.
*/
bool won(void)
{
// check if board is sorted
int n = 1;
// check to see if last tile is blank and return false if it is not
if (board[d-1][d-1] != 99)
return false;
// set up for loops to check if numbers are in ascending order beginning with 1
for (int i = 0; i < d; i++)
{
for (int j = 0; j < d; j++)
{
// check last grid position first, if blank, return true
if (i == d - 1 && j == d - 1)
return true;
// check the numbers on the rest of the tiles
if (n != board[i][j])
return false;
n++;
}
}
return false;
}
/**
* Saves the current state of the board to disk (for testing).
*/
void save(void)
{
// log
const string log = "log.txt";
// delete existing log, if any, before first save
static bool saved = false;
if (!saved)
{
unlink(log);
saved = true;
}
// open log
FILE* p = fopen(log, "a");
if (p == NULL)
{
return;
}
// log board
fprintf(p, "{");
for (int i = 0; i < d; i++)
{
fprintf(p, "{");
for (int j = 0; j < d; j++)
{
fprintf(p, "%i", board[i][j]);
if (j < d - 1)
{
fprintf(p, ",");
}
}
fprintf(p, "}");
if (i < d - 1)
{
fprintf(p, ",");
}
}
fprintf(p, "}\n");
// close log
fclose(p);
}
/**
* find.c
*
* Computer Science 50
* Problem Set 3
*
* Prompts user for as many as MAX values until EOF is reached,
* then proceeds to search that "haystack" of values for given needle.
*
* Usage: ./find needle
*
* where needle is the value to find in a haystack of values
*/
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include "helpers.h"
// maximum amount of hay
const int MAX = 65536;
int main(int argc, string argv[])
{
// ensure proper usage
if (argc != 2)
{
printf("Usage: ./find needle\n");
return -1;
}
// remember needle
int needle = atoi(argv[1]);
// fill haystack
int size;
int haystack[MAX];
for (size = 0; size < MAX; size++)
{
// wait for hay until EOF
printf("\nhaystack[%d] = ", size);
int straw = GetInt();
if (straw == INT_MAX)
{
break;
}
// add hay to stack
haystack[size] = straw;
}
printf("\n");
// sort the haystack
sort(haystack, size);
// try to find needle in haystack
if (search(needle, haystack, size))
{
printf("\nFound needle in haystack!\n\n");
return 0;
}
else
{
printf("\nDidn't find needle in haystack.\n\n");
return 1;
}
}
/**
* generate.c
*
* Computer Science 50
* Problem Set 3
*
* Generates pseudorandom numbers in [0,LIMIT), one per line.
*
* Usage: generate n [s]
*
* where n is number of pseudorandom numbers to print
* and s is an optional seed
*/
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LIMIT 65536
int main(int argc, string argv[])
{
// Make sure the user entered the proper command line arguments
if (argc != 2 && argc != 3)
{
printf("Usage: ./generate n [s]\n");
return 1;
}
// Convert the string to an integer
int n = atoi(argv[1]);
// Generate pseudorandom numbers using the seed, if provided, or no seed if not
if (argc == 3)
{
srand((unsigned int) atoi(argv[2]));
}
else
{
srand((unsigned int) time(NULL));
}
// Print the requested number of pseudorandom numbers
for (int i = 0; i < n; i++)
{
printf("%i\n", rand() % LIMIT);
}
// that's all folks
return 0;
}
/**
* 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.
*/
bool search(int value, int values[], int n)
{
// implement a binary search program
// set the bounds of the list
int beginning = 0;
int end = n-1;
// while the length of the list is more than zero
while (beginning <= end)
{
// define the middle of the list
int middle = (beginning + end) / 2;
// if the middle number is the sought for number, return if true
if (values[middle] == value)
{
return true;
}
// if the middle number is larger than the sought for number, search the left side of the list
else if (values[middle] > value)
{
end = middle - 1;
}
// if the middle number is less than value, search to the right
else
{
beginning = middle + 1;
}
}
return false;
}
/**
* Sorts array of n values.
*/
void sort(int values[], int n)
{
// run the sort as many times as there are numbers
for (int i = 0; i < n; i++)
{
// commit the smallest number to memory
int smallest = i;
// compare the smallest to the rest of the list
for (int j = i + 1; j < n; j++)
{
// determine which number is smallest
if (values[j] < values[smallest])
{
smallest = j;
}
}
// save the smallest number and put the first number in the list in its place
int tmp = values[smallest];
values[smallest] = values[i];
// place the smallest number at the beginning of the list
values[i] = tmp;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment