Week 3: The Game of Fifteen – Will

wbTaksGk8AAAAAAASUVORK5CYII=

The Game of Fifteen – Illustration From CS50 Pset 3

Gaming is one of the largest driving forces behind the development of computing hardware. This week in CS50 we were tasked with implementing a simple game, the game of fifteen. The game itself is pretty simple, you must put the numbers in order with the least number of moves. However implementing this was anything but simple. Read on below the break to find out how I did so.


Introduction

This week’s post is going to diverge from the last few in a couple of ways. In past weeks I’ve walked through each challenge (one of three) in vague terms, however this week there is only one challenge. Instead I will be walking you through each method, or section, of the program to give you an idea of how programming works on a deeper level.


init 

Screen Shot 2015-10-04 at 12.59.05 PM

init, is our initialization method, that will fill the board with our numbers. While the Game of Fifteen is normally played on a four by four grid (4 * 4 = 16 spaces, minus one blank) our implementation must be able to handle any size game board from 3×3 to 9×9. We first calculate what is the maximum number we’ll be dealing with, and call it i, by essentially calculating  the area by squaring dimension d. Then we will use a loop to fill a the first space with that number, subtract one and move to the next space and fill that too, until we fill all of the spaces. Finally once we detect that all the spaces are filled we leave the last one blank so the puzzle is actually solvable. Finally, if the board is of an even size (2×2, 4×4, 6×6, 8×8) we must switch the last two positions or the user will not be able to solve the puzzle.


draw

Screen Shot 2015-10-04 at 1.07.21 PM

While init fills the board with digits, we must show these digits, stored in a 2d array, to the user. Despite being the shortest method we will write for this PSET, draw is also the most difficult. We use loops to go to each coordinate in the 2D array and detect what is there, either nothing, a number, or the free space, and print some representation of that for the user. This is essentially a masterclass in formatting printf functions which is something that must become second hand for us at some point. In short the computer can’t just print (show) the user a piece of data, we must tell it what kind of data it is so it knows how to show it. Once we get over the stumbles of printf formatting, we have the start of a working game board as pictured below:

Screen Shot 2015-10-04 at 1.13.29 PM


move

Screen Shot 2015-10-04 at 1.14.56 PM

move is our longest method, however it is also the simplest. There are four possible moves within the game split into two categories, to switch squares to the right, and to switch them to the left. Within each there are two valid moves, switching a bigger square for a smaller, and a smaller for a bigger. When you first approach the game all four of these appear to be identical, however if we dive a little deeper they are distinctly different. The Computer cannot actively recognize the pattern and make all four of these constructs out of a single idea (outside of implementing machine vision). The Computer can only do exactly what we tell it so often writing four almost identical sections is necessary.


won

Screen Shot 2015-10-04 at 1.55.36 PM

won is our final method, and perhaps our most self explanatory. We simply check to see if the user has managed to arrange the numbers in order with a simple loop. We make sure that element i + 1 of the array is great then element i, and so on, and if every item fits this description then the player has one. This is a very simple win method, and our final for this simple Pset.


Postmortem 

Overall, this PSet was the easiest of the set. In lecture this week we were learning about the incredible science of data storage, arrays, sorting, and searching. This is an incredibly fascinating and critical section of computer science. However this problem set touched on almost none of this. We only had to implement one very simple and poorly optimized searching algorithm. I am really struggling to find the motivation behind assigning this PSet. While normally I am exuding with energy around the problems and learnings of the week, this PSet was mainly rehashing old material and really not much of a challenge. The only new element was writing more then one method, but that is really not enough for a whole new Pset around it. I am struggling to understand what I was supposed to get from this week, but I am hopeful this week’s coming PSet will make up for it.

Onto to image creation and modification in week 4!


Addendum: Source Code

Since this week’s Pset solution is unusually approachable to someone with no knowledge of the field, I have replicated my solution below. I implore you to take a look through and see what you can learn.

 /**
 * 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
#define EMPTYSPACE 0 // empty fill space

// board
int board[DIM_MAX][DIM_MAX];

// dimensions
int d;

// prototypes
void clear(void);
void greet(void);
void init(void);
void draw(void);
bool move(int tile);
bool won(void);

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)
{
 int i = d * d - 1;
 
 // fill square in desending order
 
 for(int j = 0; j < d; j++){
 for(int k = 0; k <d; k++){
 board[k][j] = i; // fill that square location with whatever i is (15...1)
 i--; // square filled
 }
 }
 
 if(board[d-1][d-1] == 0){
 board[d-1][d-1] = EMPTYSPACE; 
 }
 
 
 // board solvablity fix as dictated in pset 
 if(d % 2 == 0){ // if the board is of even size
 int tempVal = board[d-1][d-2];
 board[d-1][d-2] = board[d-1][d-3];
 board[d-1][d-3] = tempVal; // switch the last two spaces to make it solvable 
 } 
}

/**
 * Prints the board in its current state.
 */
void draw(void)
{
 printf("\n"); //start with new line
 
 for(int i = 0; i < d; i++){ // establish rows
 for(int j = 0; j < d; j++){
 if(board[i][j] == EMPTYSPACE && j != d - 1 ){
 printf(" _ "); //prints final dash
 }
 else if(board[i][j] == EMPTYSPACE && j == d - 1){
 printf(" _\n "); //print end line
 }
 else if(j == d - 1){
 printf(" %2d \n ", board[i][j]); //new line jump
 } 
 else{
 printf(" %2d ", board[i][j]); //new line jump
 }
 }
 }
}

/**
 * If tile borders empty space, moves tile and returns true, else
 * returns false. 
 */
bool move(int tile)
{
 // moving values of empty and filled block
 
 for(int i = 0; i<d; i++){
 for(int j = 0; j<d; j++){
 if(board[i][j] == tile){
 
 /*
 * This section below, of stepping and checking around the space
 * feels extremely repetative, but I am not sure at all how to 
 * put it into a method. Ideas?
 */ 
 // i stepping
 if(board[i+1][j] == EMPTYSPACE ){
 int tempVal = tile;
 board[i][j] = EMPTYSPACE;
 board[i+1][j] = tempVal;
 return true;
 }
 
 if(board[i-1][j] == EMPTYSPACE ){
 int tempVal = tile;
 board[i][j] = EMPTYSPACE;
 board[i-1][j] = tempVal;
 return true;
 }
 
 // j stepping
 if(board[i][j+1] == EMPTYSPACE ){
 int tempVal = tile;
 board[i][j] = EMPTYSPACE;
 board[i][j+1] = tempVal;
 return true;
 }
 
 if(board[i][j-1] == EMPTYSPACE ){
 int tempVal = tile;
 board[i][j] = EMPTYSPACE;
 board[i][j-1] = tempVal;
 return true;
 }
 
 }
 }
 }
 return false;
}

/**
 * Returns true if game is won (i.e., board is in winning configuration), 
 * else false.
 */
bool won(void)
{
 int lastVal = 0;
 int stepVal = 0;
 
 for(int i = 0; i<d; i++){
 for(int j = 0; j<d; j++){
 if(board[i][j] < lastVal) // if out of order
 return false;
 
 else if(board[i][j] > lastVal){ // if appears to be in order
 stepVal += 1;
 if(stepVal == d * d)
 return true;
 }
 lastVal = board[i][j]; //keep stepping forward
 }
 
 
 }
 
 return false;
}

4 thoughts on “Week 3: The Game of Fifteen – Will

  1. lukasdesimone

    I love the detail you put into this post, this is probably the first time I’ve ever looked at coding in such depth. Even though I didn’t understand half of it, I still feel like I gained a lot from reading it. Great post.

    Reply
  2. randyhimself

    Wow, I tried to think about the logics behind coding this game, and it is no easy task! I think you are making very fast progress. Keep it up! I’m also amazed by how much effort you put in writing these blogs. Workaholic, dude.

    Reply
  3. lwhochbe

    Well, I’m not going to pretend I know what’s going on here. But from the (very) limited knowledge that I have on programming, this looks fascinating! It’s also impressive that you already have the experience to pass some judgement on the assignment;something that is crucial for a student. At this point, some more links would be extremely helpful. What exactly is a PSET, and how does postmortem affect this game?

    Reply
  4. Pingback: Lower School Students Learn to Tynker | In A Class Of Our Own

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s