Created
April 17, 2014 00:59
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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