Ultimate Tic-Tac-Toe in C

Question

Here is my attempt at the UTTT code-challenge (in response to the the Weekend-Challenge Reboot). Here is what I would like critiqued:

I tested the code a few times for bugs, but I may have missed some.
I feel like I have duplicated code in some places (with only minor changes being the difference), refining them down a bit would be nice.
Better parsing of input

But any and all suggestions are acceptable. If you are interesting in looking at some occasionally updated versions of this code, take a look the the Github repository that houses the code (feel free to send fork and send pull requests).

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

#define ROWS 9
#define COLS 9

typedef char Board[ROWS][COLS];
typedef char MetaBoard[ROWS / 3][COLS / 3];
typedef enum {VALID, NOT_A_DIGIT, NOT_IN_BOARD, SPACE_OCCUPIED, OUT_OF_BOUNDS} MoveStatus;

void fillSubBoard(Board board, int x, int y, char c)
{
    for (; (x % 3) != 0; x--); // quickly set x to left bound of sub-board
    for (; (y % 3) != 0; y--); // quickly set y to upper bound of sub-board
    for (int rowMax = x + 2, row = x; row <= rowMax; row++)
    {
        for (int columnMax = y + 2, column = y; column <= columnMax; column++)
        {
            board[row][column] = c;
        }
    }
}

int getRowBound(int row)
{
    switch (row)
    {
        case 0 ... 2:
            return 0;
        case 3 ... 5:
            return 1;
        case 6 ... 8:
            return 2;
        default:
            return -1;
    }
}

int getColumnBound(int column)
{
    switch (column)
    {
        case 0 ... 2:
            return 0;
        case 3 ... 5:
            return 1;
        case 6 ... 8:
            return 2;
        default:
            return -1;
    }
}

void printBoard(Board board)
{
    printf("\n=============||===========||=============\n");
    for (int row = 0; row < ROWS; row++)
    {
        printf("||");
        for (int column = 0; column < COLS; column++)
        {
            if (board[row][column] == '-') printf("%d,%d|", row, column);
            else printf(" %c |", board[row][column]);
            if (0 == (column+1) % 3) printf("|");
        }
        if ((row+1) % 3 == 0) printf("\n=============||===========||=============\n");
        else printf("\n-----|---|---||---|---|---||---|---|-----\n");
    }
}

static int checkMeta(MetaBoard meta)
{
    const int xStart[ROWS - 1] = {0,  0,  0,  0,  1,  2,  0,  0};
    const int yStart[COLS - 1] = {0,  1,  2,  0,  0,  0,  0,  2};
    const int xDelta[ROWS - 1] = {1,  1,  1,  0,  0,  0,  1,  1};
    const int yDelta[COLS - 1] = {0,  0,  0,  1,  1,  1,  1,  1};
    static int startx, starty, deltax, deltay;
    for (int trip = 0; trip < ROWS - 1; trip++)
    {
        startx = xStart[trip];
        starty = yStart[trip];
        deltax = xDelta[trip];
        deltay = yDelta[trip];
        // main logic to check if a subboard has a winner
        if (meta[startx][starty] != '-' &&
            meta[startx][starty] == meta[startx + deltax][starty + deltay] &&
            meta[startx][starty] == meta[startx + deltax + deltax][starty + deltay + deltay]) return 1;
    }
    return 0;
}

static int checkBoard(Board board, MetaBoard meta, int player, int row, int column)
{
    const int xStart[ROWS - 1] = {0,  0,  0,  0,  1,  2,  0,  0};
    const int yStart[COLS - 1] = {0,  1,  2,  0,  0,  0,  0,  2};
    const int xDelta[ROWS - 1] = {1,  1,  1,  0,  0,  0,  1,  1};
    const int yDelta[COLS - 1] = {0,  0,  0,  1,  1,  1,  1,  1};
    static int startx, starty, deltax, deltay, status = 0;

    for (; (row % 3) != 0; row--); // quickly set row to left bound of sub-board
    for (; (column % 3) != 0; column--); // quickly set column to upper bound of sub-board

    for (int trip = 0; trip < ROWS - 1; trip++)
    {

        startx = row + xStart[trip];
        starty = column + yStart[trip];
        deltax = xDelta[trip];
        deltay = yDelta[trip];
        if (board[startx][starty] != '-' &&
            board[startx][starty] == board[startx + deltax][starty + deltay] &&
            board[startx][starty] == board[startx + deltax + deltax][starty + deltay + deltay])
        {
            fillSubBoard(board, row, column, (player == 1) ? 'X' : 'O');
            meta[getRowBound(row)][getColumnBound(column)] = (player == 1) ? 'X' : 'O';
            status = 1;
        }
    }
    return (status + checkMeta(meta)); // always check if the game has a winner
}

MoveStatus validCoords(Board board, int row, int column, int rowBound, int columnBound)
{
    if (!isdigit((char)(((int)'0') + row)) && !isdigit((char)(((int)'0') + column))) return NOT_A_DIGIT; // supplied coordinates aren't digits 1-9
    else if (row > ROWS - 1 || column > COLS - 1) return NOT_IN_BOARD; // supplied coordinates aren't within the bounds of the board
    else if (board[row][column] != '-') return SPACE_OCCUPIED; // supplied coordinates are occupied by another character
    else if (rowBound == -1 && columnBound == -1) return VALID; // supplied coordinates can move anywhere
    else if (((row > rowBound * 3 + 2 || column > columnBound * 3 + 2) ||
              (row < rowBound * 3 || column < columnBound * 3)) &&
             (rowBound > 0 && columnBound > 0)) return OUT_OF_BOUNDS; // coordinates aren't within the sub-board specified by the previous move
    else return VALID; // didn't fail anywhere else, so coords are valid
}

int main(void)
{
    int winner = 0, row = 0, column = 0, rowBound = -1, columnBound = -1, invalid = 0;
    char tempRow = '\0', tempColumn = '\0';
    Board board;
    MetaBoard meta;
    // initialize boards and fill with '-'
    memset(board, '-', ROWS * COLS * sizeof(char));
    memset(meta, '-', (ROWS / 3) * (COLS / 3) * sizeof(char));

    // game loop
    for (int turn = 0; turn < ROWS * COLS && !winner; turn++)
    {
        int player = (turn % 2) + 1;
        printBoard(board);
        printf("Player %d, enter the coordinates (x, y) to place %c: ", player, (player==1) ? 'X' : 'O');
        do
        {
            scanf("%c, %c", &tempRow, &tempColumn);
            for(; getchar() != '\n'; getchar()); // pick up superfluous input so we don't run into problems when we scan for input again
            row = abs((int) tempRow - '0');
            column = abs((int) tempColumn - '0');
            invalid = 0;
            switch (validCoords(board, row, column, rowBound, columnBound))
            {
                case NOT_A_DIGIT:
                    printf("Invalid input.  Re-enter: ");
                    invalid = 1;
                    break;
                case NOT_IN_BOARD:
                    printf("Out of board's bounds. Re-enter: ");
                    invalid = 2;
                    break;
                case SPACE_OCCUPIED:
                    printf("There is already an %c there.  Re-enter: ", board[row][column]);
                    invalid = 3;
                    break;
                case OUT_OF_BOUNDS:
                    printf("Your move was in the wrong sub-board.  Re-enter: ");
                    invalid = 4;
                    break;
                default:
                    break;
            }
        } while (invalid);

        board[row][column] = (player == 1) ? 'X' : 'O';
        switch(checkBoard(board, meta, player, row, column))
        {
            case 1:
                // next move can be anywhere
                rowBound = -1;
                columnBound = -1;
                break;
            case 2:
                winner = player;
                break;
            default:
                rowBound = row % 3;
                columnBound = column % 3;
                break;
        }
    }
    printBoard(board);

    if(!winner) printf("The game is a draw\n");
    else printf("Player %d has won\n", winner);

    return 0;
}

I think if you move the game logic out the main is better. Something like while (isGameRunning ()) do game logic manage input etc. All with functions. — Marco Acierno, Commented Mar 5, 2014 at 0:10

syb0rg · Accepted Answer · 2014-07-27 16:37:44Z

A few comments:

[ ... ]

for (; (x % 3) != 0; x--); // quickly set x to left bound of sub-board
for (; (y % 3) != 0; y--); // quickly set y to upper bound of sub-board

I think I'd move the code to round to a multiple of three into a function of its own. I think I'd implement that something like this:

int round3(int in) { return (in/3)*3; }

[ ... ]

int getRowBound(int row)
{
    switch (row)
    {
        case 0 ... 2:
            return 0;
        case 3 ... 5:
            return 1;
        case 6 ... 8:
            return 2;
        default:
            return -1;
    }
}

int getColumnBound(int column)
{
    switch (column)
    {
        case 0 ... 2:
            return 0;
        case 3 ... 5:
            return 1;
        case 6 ... 8:
            return 2;
        default:
            return -1;
    }
}

These two functions (getRowBound and getColumnBound) are identical--and not just by coincidence either, so I think I'd merge them into a single function:

int getBound(int in) { 
    return (unsigned)in < 9 ? in / 3 : -1;
}

[ ... ]

for (; (row % 3) != 0; row--); // quickly set row to left bound of sub-board
for (; (column % 3) != 0; column--); // quickly set column to upper bound of sub-board

These should be calls to the round3 (or whatever name you prefer) mentioned previously.

[ ... ]

Although some disagree (vehemently in some cases) I'd personally prefer to get rid of some of the conditionals like these:

        fillSubBoard(board, row, column, (player == 1) ? 'X' : 'O');
        meta[getRowBound(row)][getColumnBound(column)] = (player == 1) ? 'X' : 'O';

...and instead have something like:

static const char marks[] = {'X', 'O'};

// ...
fillSubBoard(board, row, column, marks[player]);
meta[getBound(row)][getBound(column)] = marks[player];

[ ... ]

MoveStatus validCoords(Board board, int row, int column, int rowBound, int columnBound)
{
    if (!isdigit((char)(((int)'0') + row)) && !isdigit((char)(((int)'0') + column))) return NOT_A_DIGIT; // supplied coordinates aren't digits 1-9

Any user input that you pass to isdigit (or any of the other isXXX functions/macros from ctype.h) should be cast to unsigned char first. Passing a negative number (other than EOF) to isXXX gives undefined behavior. In a typical case, any character outside the basic US-ASCII set (e.g., any letter that's not used in English, plus anything with a diacritic mark) will have a negative value when stored in a char.

[ ... ]

int winner = 0, row = 0, column = 0, rowBound = -1, columnBound = -1, invalid = 0;

Though some disagree, I think most programmers would prefer each variable in a separate definition. If (for some reason) you prefer not to do that, I'd at least format each variable onto a separate line.

        for(; getchar() != '\n'; getchar()); // pick up superfluous input so we don't run into problems when we scan for input again

This looks buggy. In the condition you're calling getchar(), and checking the return value--but then in the increment part of the loop, you're calling getchar() again without checking the return value.

I think you probably want something more like:

while (getchar() != '\n')
    ;

[ ... ]

        switch (validCoords(board, row, column, rowBound, columnBound))
        {
            case NOT_A_DIGIT:
                printf("Invalid input.  Re-enter: ");
                invalid = 1;
                break;
            case NOT_IN_BOARD:
                printf("Out of board's bounds. Re-enter: ");
                invalid = 2;
                break;
            case SPACE_OCCUPIED:
                printf("There is already an %c there.  Re-enter: ", board[row][column]);
                invalid = 3;
                break;
            case OUT_OF_BOUNDS:
                printf("Your move was in the wrong sub-board.  Re-enter: ");
                invalid = 4;
                break;

Here (again) I think I'd probably use the return value to index into an array:

static char const *errors[] = {
    "Invalid Input.",
    "Out of board's bounds",
    "That space is already used",
    "Your move was in the wrong sub-board"
};

int error;
while (0 != (error=validCoords(...))) {
    printf("%s Re-enter:", errors[error]);
    getinput();
}

This does require that you keep the list of errors in synch with the error numbers, but the payoff outweighs the extra burden (IMO).

[ ... ]

    board[row][column] = (player == 1) ? 'X' : 'O';

Again, I'd use the marks mentioned earlier, so this would end up like:

board[row][column] = marks[player];

What purpose does the cast to unsigned serve in function getBound? — Morwenn, Commented Jun 14, 2017 at 12:26
It eliminates a comparison. We want to return -1 for any number <0 or >8. The cast to unsigned converts negative numbers to large positive numbers (guaranteed much greater than 8) so we only compare to 8, rather than to both 0 and 8. — Jerry Coffin, Commented Jun 14, 2017 at 14:09
Ok, that's pretty much what I thought. I guess it at least deserves a comment; I'd probably scratch my head or accidentally remove the unsigned if I didn't pay attention :p — Morwenn, Commented Jun 14, 2017 at 14:13

AJ Henderson · Accepted Answer · 2014-03-05 05:10:23Z

One quick observation I have is about the way you are storing the playable spaces. While a 9 by 9 grid is a simple way to do it, it isn't the most clear way to store and ends up requiring some complicated addressing logic to get each sub-board.

Your options to deal with it are a bit limited by C, but there is support for nesting types. You can use this to define a MainBoard type that takes a 3 by 3 matrix of SubBoard types and a SubBoard type that takes a 3 by 3 grid of playable squares (characters).

typedef char SubBoard[ROWS][COLS];
typedef SubBoard MainBoard[ROWS][COLS];

I'm not 100% sure on the syntax since my C is a bit rusty, but this should allow you to use much simpler addressing. If the player uses space 1,3 on the sub-board they are playing, you can then get board 1,3 for the next play.

Morwenn · Accepted Answer · 2017-06-13 09:52:30Z

In this piece of code:

int getRowBound(int row)
{
    switch (row)
    {
        case 0 ... 2:
            return 0;
        case 3 ... 5:
            return 1;
        case 6 ... 8:
            return 2;
        default:
            return -1;
    }
}

The ellipsis ... is a GCC extension to the C programming language known as Case Ranges. Using it hinders portability since not all compilers support it (as for most of the extensions). If you want to get rid of it, you should use the function getBound proposed by Jerry Coffin:

int getBound(int in) { 
    return (unsigned)in < 9 ? in / 3 : -1;
}

aragaer · Accepted Answer · 2014-03-05 09:59:45Z

6

for (; (row % 3) != 0; row--); // quickly set row to left bound of sub-board
for (; (column % 3) != 0; column--); // quickly set column to upper bound of sub-board

Why not just

row -= row % 3;
column -= column % 3;

And it should be actually call to something like

static inline int round3(int x) {
    return x - x % 3;
}

answered Mar 5, 2014 at 9:59

aragaer

1614 bronze badges

Add a comment |

Stack Exchange Network

Ultimate Tic-Tac-Toe in C

4 Answers 4

Your Answer

Not the answer you're looking for? Browse other questions tagged
performance
c
game
tic-tac-toe
community-challenge
or ask your own question.

Hot Network Questions

Ultimate Tic-Tac-Toe in C

4 Answers 4

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged performancecgametic-tac-toecommunity-challenge or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
performance
c
game
tic-tac-toe
community-challenge
or ask your own question.