Revised - Game of Fifteen

Question

This is a revised version of a previous post. I attempted to address each aspect of the feedback provided. The key changes are as follows:

• Replace the deprecated usleep() with nanosleep()
• Removed the dependency on CS50 library header by pulling out the relevant pieces.
• I followed pacmaninbw's advice in avoiding globals by creating a struct Game_data, which contains the global variables from the prior implementation.
• I attempted to follow the MVC pattern by creating new files (game_model, view, game_controller, and helpers), limiting responsibility with respect to MVC.

• forsvarir pointed out a bug with valid_mode(), which he explained:

  Give two lines of grid:

  13 12 11 15 9

  _ 8 7 6 10

  If I input 9, the 9 will move into the _ position:

  13 12 11 15 _

  9 8 7 6 10

  Similarly, after the move, if I input 9 again, the _ and 9 will again swap positions.

  I fixed this by adding a check that the current empty tile row is equal to the row of the index being moved to.

• I paid closer attention to how I was using static and made an effort to use it correctly.

---

Here's a repeat of the details from the original post:

This task was to implement Game of Fifteen aka 15 Puzzle. Project details here.

Implemented as an interactive console game. The board is initialized with "tiles" as descending values with the objective being to reorder as ascending by swapping the empty tile (represented as _) with adjacent tiles. Valid movements are similar to a rook in chess (can't move diagonal) but can only swap tiles that are touching. Here's a demo:

---

fifteen.c

/**
 * Usage: fifteen d
 *
 * whereby the board's dimensions are to be d x d,
 * where d must be in [DIM_MIN,DIM_MAX]
 */

#include <stdio.h>
#include <stdlib.h>

#include "game_model.h"
#include "game_controller.h"
#include "helpers.h"
#include "view.h"

static Game_data game;

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        printf("Usage: fifteen d\n");
        return 1;
    }

    game.dim = atoi(argv[1]);
    if (game.dim < DIM_MIN || game.dim > 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;
    }

    init_game_data(&game);
    greet();
    init_board(&game);
    play_game(&game);

    return 0;
}

game_model.c

#include "game_model.h"

void init_game_data(Game_data *game)
{
    game->num_tiles = game->dim * game->dim;
    game->last_row = (game->num_tiles - 1) / game->dim;
    game->last_col = game->dim - 1;
    game->empty_tile_index = game->num_tiles - 1;
}

game_model.h

#ifndef GAME_MODEL_H
#define GAME_MODEL_H

#include <stdbool.h>

#define DIM_MIN (3)
#define DIM_MAX (9)

enum {
    EMPTY_SPACE = -1,
    ONE_OFFSET = 2,
    TWO_OFFSET = 3,
};

typedef struct {
    int dim;
    int num_tiles;
    int board[DIM_MAX][DIM_MAX];
    int empty_tile_index;
    int last_row;
    int last_col;
} Game_data;

void init_game_data(Game_data *game);

#endif /* end of include guard: GAME_MODEL_H */

game_controller.c

#include "game_controller.h"
#include "helpers.h"
#include "view.h"

static bool won(Game_data *game);
static bool valid_move(int index, Game_data *game);

/**
 * Initializes the game's board with tiles numbered 1 through dim*dim - 1
 * (i.e., fills 2D array with values but does not actually print them).
 *
 * Note we're in descending tile order relative to increasing index:
 *
 *     |15|14|13|12|
 *     |11|10| 9| 8|
 *     | 7| 6| 5| 4|
 *     | 3| 1| 2| _| <-- Note: we swap 2 & 1 when dimensions are even
 *
 */
void init_board(Game_data *game)
{
    for (int i = 0, num = game->num_tiles-1; i < game->num_tiles; i++, num--) {
        game->board[get_row(i, game->dim)][get_col(i, game->dim)] = num;
    }

    /* Per rules, if dimensions are even, tiles 1 & 2 must be swapped */
    if (game->dim % 2 == 0) {
        swap(game->num_tiles - ONE_OFFSET, game->num_tiles - TWO_OFFSET, game);
    }

    game->board[game->last_row][game->last_col] = EMPTY_SPACE;
}

/**
 * Plays the game until the user wins or enters 0
 */
void play_game(Game_data *game) {
    while (true)
    {
        clear();
        draw(game);

        if (won(game))
        {
            display_winner();
            return;
        }

        display_input_prompt();
        int tile = get_int();

        // quit if user inputs 0
        if (tile == 0)
        {
            return;
        }

        if (!move(tile, game))
        {
            display_illegal_move();
            animation_sleep();
        }

        animation_sleep();
    }
}

/**
 * Returns true if game is won (i.e., board is in winning configuration),
 * else false.
 */
static bool won(Game_data *game)
{
    if (game->board[game->last_row][game->last_col] != EMPTY_SPACE) {
        return false;
    }

    for (int i = 0; i < game->num_tiles-1; i++) {
        if (game->board[get_row(i, game->dim)][get_col(i, game->dim)] != i+1) {
            return false;
        }
    }

    return true;
}

/**
 * If tile borders empty space, moves tile and returns true, else
 * returns false.
 */
bool move(int tile, Game_data *game)
{
    int tile_index = get_index(tile, game);

    if (!valid_index(tile_index, game->num_tiles)) {
        return false;
    }

    if (!valid_move(tile_index, game)) {
        return false;
    }

    bool swapped = swap(tile_index, game->empty_tile_index, game);
    game->empty_tile_index = tile_index;

    return swapped;
}

/**
 * Validate a move using the given tile's index by comparing
 * to potential moves indexes depicted in the figure below:
 *
 * Valid moves exist in a + shape around the empty tile:
 *
 *     | |o| |
 *     |o|_|o|
 *     | |o| |
 *
 * Returns true if valid, otherwise false.
 */
static bool valid_move(int index, Game_data *game)
{
    int curr_row = get_row(game->empty_tile_index, game->dim);

    int row_above_index = game->empty_tile_index - game->dim;
    int row_below_index = game->empty_tile_index + game->dim;
    int col_left_index  = game->empty_tile_index - 1;
    int col_right_index = game->empty_tile_index + 1;

    if (index == row_above_index) {
        return true;
    } else if (index == row_below_index) {
        return true;
    } else if (index == col_left_index &&
            curr_row == get_row(col_left_index, game->dim)) {
        return true;
    } else if (index == col_right_index &&
            curr_row == get_row(col_right_index, game->dim)) {
        return true;
    } else {
        return false;
    }
}

/**
 * Swap the board elements at index1 & index2
 * Returns false on error, else true.
 */
bool swap(int index1, int index2, Game_data *game)
{
    if (!valid_index(index1, game->num_tiles) ||
            !valid_index(index2, game->num_tiles)) {
        return false;
    }

    int row1 = get_row(index1, game->dim);
    int col1 = get_col(index1, game->dim);

    int row2 = get_row(index2, game->dim);
    int col2 = get_col(index2, game->dim);

    int tmp = game->board[row1][col1];
    game->board[row1][col1] = game->board[row2][col2];
    game->board[row2][col2] = tmp;

    return true;
}

game_controller.h

#ifndef GAME_CONTROLLER_H
#define GAME_CONTROLLER_H

#include "game_model.h"

bool move(int tile, Game_data *game);
bool swap(int index1, int index2, Game_data *game);
void init_board(Game_data *game);
void play_game(Game_data *game);

#endif /* end of include guard: GAME_CONTROLLER_H */

view.c

#include <time.h>
#include <stdio.h>
#include <stdbool.h>

#include "helpers.h"
#include "view.h"

/**
 * Clears screen using ANSI escape sequences.
 */
void clear()
{
    printf("\033[2J");
    printf("\033[%d;%dH", 0, 0);
}

void greet()
{
    clear();
    puts("WELCOME TO GAME OF FIFTEEN");
    animation_sleep();
}

void display_input_prompt()
{
    printf("Tile to move: ");
}

void display_winner()
{
    puts("Solved! Ya did good, kid.");
}

void display_illegal_move()
{
    puts("\nIllegal move.");
}

/**
 * Displays the board in its current state.
 */
void draw(Game_data *game)
{
    int tile;
    bool is_end_of_row;

    for (int i = 0; i < game->num_tiles; i++) {
        is_end_of_row = (i % game->dim == game->dim - 1);
        tile = game->board[get_row(i, game->dim)][get_col(i, game->dim)];

        if (tile == EMPTY_SPACE) {
            printf("%2c ", '_');
        } else {
            printf("%2d ", tile);
        }

        if (is_end_of_row) {
            puts("\n");
        }
    }
}

void animation_sleep()
{
    nanosleep((const struct timespec[]){{0, 500000000L}}, NULL);
}

view.h

#ifndef VIEW_H
#define VIEW_H

#include "game_model.h"

void animation_sleep(void);
void clear(void);
void display_illegal_move(void);
void display_input_prompt(void);
void display_winner(void);
void draw(Game_data *game);
void greet(void);

#endif /* end of include guard: VIEW_H */

helpers.c

/* Note: get_int() and get_string() reused via
 * https://mirror.cs50.net/library50/c/cs50-library-c-1.1.6/cs50.c
 * Authors:
 * Glenn Holloway
 * David J. Malan
 *   Copyright (c) 1998, Regents of the University of California
 *   All rights reserved.
*/

#include <stdbool.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#include "helpers.h"

#define CAPACITY (128)

/**
 * Linear search to retrieve index of needle in haystack.
 * Returns index of value if it exists, else -1.
 */
int get_index(int tile, Game_data *game)
{
    for (int i = 0; i < game->num_tiles; ++i) {
        if (game->board[get_row(i, game->dim)][get_col(i, game->dim)] == tile) {
            return i;
        }
    }

    return -1;
}

/**
 * Returns false if the given index is less than the size
 * else true.
 */
bool valid_index(int index, int size)
{
    return (index >= 0 && index < size);
}

int get_row(int index, int dimension)
{
    return index / dimension;
}

int get_col(int index, int dimension)
{
    return index % dimension;
}

/* Reused via https://mirror.cs50.net/library50/c/cs50-library-c-1.1.6/cs50.c
 *
 * Reads a line of text from standard input and returns it as an
 * int in the range of [-2^31 + 1, 2^31 - 2], if possible; if text
 * does not represent such an int, user is prompted to retry.  Leading
 * and trailing whitespace is ignored.  For simplicity, overflow is not
 * detected.  If line can't be read, returns INT_MAX.
 */
int get_int(void)
{
    // try to get an int from user
    while (true)
    {
        // get line of text, returning INT_MAX on failure
        char *line = get_string();
        if (line == NULL)
            return INT_MAX;

        // return an int if only an int (possibly with
        // leading and/or trailing whitespace) was provided
        int n; char c;
        if (sscanf(line, " %d %c", &n, &c) == 1)
        {
            free(line);
            return n;
        }
        else
        {
            free(line);
            printf("Retry: ");
        }
    }
}

/* Reused via https://mirror.cs50.net/library50/c/cs50-library-c-1.1.6/cs50.c
 *
 * Reads a line of text from standard input and returns it as a string,
 * sans trailing newline character.  (Ergo, if user inputs only "\n",
 * returns "" not NULL.)  Leading and trailing whitespace is not ignored.
 * Returns NULL upon error or no input whatsoever (i.e., just EOF).
 */
char *get_string()
{
    // growable buffer for chars
    char *buffer = NULL;

    // capacity of buffer
    unsigned int capacity = 0;

    // number of chars actually in buffer
    unsigned int n = 0;

    // character read or EOF
    int c;

    // iteratively get chars from standard input
    while ((c = fgetc(stdin)) != '\n' && c != EOF)
    {
        // grow buffer if necessary
        if (n + 1 > capacity)
        {
            // determine new capacity: start at CAPACITY then double
            if (capacity == 0)
                capacity = CAPACITY;
            else if (capacity <= (UINT_MAX / 2))
                capacity *= 2;
            else
            {
                free(buffer);
                return NULL;
            }

            // extend buffer's capacity
            char* temp = realloc(buffer, capacity * sizeof(char));
            if (temp == NULL)
            {
                free(buffer);
                return NULL;
            }
            buffer = temp;
        }

        // append current character to buffer
        buffer[n++] = c;
    }

    // return NULL if user provided no input
    if (n == 0 && c == EOF)
        return NULL;

    // minimize buffer
    char* minimal = malloc((n + 1) * sizeof(char));
    strncpy(minimal, buffer, n);
    free(buffer);

    // terminate string
    minimal[n] = '\0';

    // return string
    return minimal;
}

helpers.h

#ifndef HELPERS_H
#define HELPERS_H

#include "game_model.h"

bool valid_index(int index, int size);
char *get_string(void);
int get_col(int index, int dim);
int get_index(int tile, Game_data *game);
int get_int(void);
int get_row(int index, int dim);

#endif /* end of include guard: HELPERS_H */

Answer 1

Functions that do not modify the referenced data should be made const to indicate that in fact, the code does not change things. It also allows some optimizations, that a weaker compile may not use.

// static bool won(Game_data *game);
static bool won(const Game_data *game);

Order of include. If "" include files need <> include files, they should code that themselves. OP's code first coding <> include files can hide that dependency. Recommend swapping order. See C header file order

// #include <stdio.h>
// #include <stdlib.h>

#include "game_model.h"
#include "game_controller.h"
#include "helpers.h"
#include "view.h"

#include <stdio.h>
#include <stdlib.h>

No harm, but () are not needed with simply constants.

// #define DIM_MIN (3)
// #define DIM_MAX (9)
#define DIM_MIN 3
#define DIM_MAX 9

Non-intuitive function names. Where is move() defined? I suppose one could search through all the .h files. Consider a uniform name prefix like Game_. At least we know Game_move() is in some Game*.h file. Think of Game_... code being part of a much larger code base.

// Game.h 
bool Game_move(int tile, Game_data *game);
bool Game_swap(int index1, int index2, Game_data *game);
void Game_init_board(Game_data *game);
void Game_play(Game_data *game);

Leading space not needed. Same functionality. "%d" itself consumes leading white-space.

// if (sscanf(line, " %d %c", &n, &c) == 1)
if (sscanf(line, "%d %c", &n, &c) == 1)

Unclear why code uses unsigned rather than size_t for memory allocation. size_t is the best for array indexing and the type expected with allocations.

char *get_string() {
    ...
    //unsigned int capacity = 0;
    //unsigned int n = 0;
    size_t capacity = 0;
    size_t n = 0;

Robust test against "too large a buffer", yet suggest a slight mod for this extraordinary case.

        else if (capacity <= (SIZE_MAX / 2)) capacity *= 2;
        else capacity = SIZE_MAX;

Missing include. game_controller.c does not include a file that directly defines Game_data. Code depends on 1 of the 3 files, as a side effect, to include the header file containing the definition of Game_data.

#include "game_controller.h"
#include "helpers.h"
#include "view.h"

static bool won(Game_data *game);  // Which file defines `Game_data`?

Answer 2

I like the improvements you've made, so I've only got a few mostly cosmetic points:

• I don't like dim as a variable name. I think it's probably a hangover from working with BASIC, I'd prefer side_length or dimensions
• In init_game_data you do: game->last_row = (game->num_tiles - 1) / game->dim. This could be set the same way you set last_col as game->last_row = (game->dim - 1). Your play area is a square, so last_row is always going to equal last_col.
• In init_board, you always set the board to the same pattern. Is this part of the requirements you're working to? If not, then shuffling the pattern instead of setting it the way you are might make for a more varied challenge.
• All of your core variables are ints. It's not really valid for any of them to be negative, consider indicating this by having them be unsigneds instead.

• I'm not really sure how important your animation_sleep calls are, but if move returns false, you're calling animation_sleep twice in a row. The inner one probably isn't needed:

  if (!move(tile, game))
  {
      display_illegal_move();
      animation_sleep();
  }
  animation_sleep();
  

Answer 3

More helper function

Maybe the following piece of logic (in a least 4 places):

game->board[get_row(i, game->dim)][get_col(i, game->dim)]

could be extracted in a function on its own to just call:

get_tile(game, i);

For instance:

int get_tile(Game_data * game, int i)
{
    return game->board[get_row(i, game->dim)][get_col(i, game->dim)];
}

User interface

Instead of having a user input the number of the tile to move, a different idea could be to input the direction to slide (up, down, left, right). Then it could be played with the arrows of the keyboard.

Also, this may simplify parts of your logic.