cmpsc330hw2/dotsandboxes.cxx

// Name: Sandipsinh Rathod
// Email: sdr5549@psu.edu
// Class: CMPSC 330
// Program Dots and Boxes
// Current Date: 11/10/24 7:24 PM
// Due Date: 11/10/24 11:59 PM
//
// Description: This program will take a file as input and
// will play the game of dots and boxes.
//

#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>

#define pt std::cout <<
#define pter std::cerr <<
#define nl "\n"

using namespace std;

// TODO: spam comments

// -------- START PAIR IMPL --------
template<typename T1, typename T2>
struct myPair {
    T1 first;
    T2 second;

    myPair() : first(), second() {
    }

    myPair(const T1 &first, const T2 &second) : first(first), second(second) {
    }
};

// -------- END PAIR IMPL --------

// -------- START HELPER FUNCTIONS --------
void swapChar(char &a, char &b) {
    if (a == b) {
        return;
    }
    a ^= b;
    b ^= a;
    a ^= b;
}

// Recursively reverse a string
void reverseString(string &str, int start, int end) {
    if (start >= end) {
        return;
    }

    swapChar(str[start], str[end]);

    reverseString(str, start + 1, end - 1);
}

string toString(int x) {
    if (!x) return "0";

    string result;
    while (x) {
        result.push_back(x % 10 + '0');
        x /= 10;
    }
    reverseString(result, 0, result.size() - 1);
    return result;
}

int max(int a, int b) {
    return a > b ? a : b;
}

// -------- END HELPER FUNCTIONS --------

// -------- START RAII HELPERS--------

unsigned long allocatedMem = 0;

void *alloc(size_t size) {
    void *ptr = malloc(size);
    if (!ptr) {
        pter "Memory allocation failed" << nl;
        return NULL;
    }
    allocatedMem += 1;
    return ptr;
}

void dealloc(void *ptr) {
    if (ptr) free(ptr);
    allocatedMem -= 1;
}

bool assert_alloc() {
    return !allocatedMem;
}

// -------- END RAII HELPERS--------


// -------- START SIMPLE VEC IMPLEMENTATION --------
template<typename T>
class myVec {
    T *data;
    size_t capacity;
    size_t length;

    void resize() {
        if (length == capacity || !length) {
            capacity = capacity ? capacity << 1 : 1;
            T *newData = static_cast<T *>(alloc(capacity * sizeof(T)));
            for (size_t i = 0; i < length; i++) {
                newData[i] = data[i];
            }
            dealloc(data);
            data = newData;
        }
    }

public:
    myVec() {
        capacity = 0;
        length = 0;
        data = NULL;
    }

    myVec(size_t size) {
        capacity = size;
        length = 0;
        data = static_cast<T *>(malloc(size * sizeof(T)));
    }

    void push_back(const T &val) {
        resize();
        data[length++] = val;
    }

    void pop_back() {
        if (length) {
            length--;
        }
    }

    T &operator[](size_t index) {
        return data[index];
    }

    int size() {
        return length;
    }
};

// -------- END SIMPLE VEC IMPLEMENTATION --------
// Struct to store a move
struct Move {
    char player;
    int moveX;
    int moveY;
};

// Struct to store/serialize the moves
struct Moves {
    int x;
    int y;
    myVec<Move> moves;
};

// Check if the player is valid
bool isValidPlayer(char c) {
    return c >= 'A' && c <= 'Z' && c != 'X';
}

// Serialize the input string
Moves serialize(char *s) {
    Moves result;
    istringstream iss(s);
    iss >> result.x >> result.y;
    if (result.x < 2 || result.y < 2) {
        string err = "Invalid board size: ";
        err.append(toString(result.x));
        err.append("x");
        err.append(toString(result.y));

        throw invalid_argument(err);
    }

    result.x = (result.x << 1) - 1;
    result.y = (result.y << 1) - 1;

    char *player = static_cast<char *>(alloc(4 * sizeof(char)));
    int x, y;
    while (iss >> player >> x >> y) {
        if (!strcmp(player, "END")) break;

        // TODO: move this exceptions to runtime checks
        if (x >= result.x || y >= result.y) {
            string err = "Invalid move by: ";
            err.append(player);
            err.append(" at (x, y): (");
            err.append(toString(x));
            err.append(", ");
            err.append(toString(y));
            err.append(")");
            throw invalid_argument(err);
        }

        if (!isValidPlayer(player[0])) {
            string err = "Invalid player: ";
            err.push_back(player[0]);

            throw invalid_argument(err);
        }
        Move move;
        move.player = player[0];
        move.moveX = x;
        move.moveY = y;
        result.moves.push_back(move);
    }

    dealloc(player);
    return result;
}

// Allocate the board
char **allocBoard(int x, int y) {
    char **board = static_cast<char **>(alloc(x * sizeof(char *)));
    for (int i = 0; i < x; ++i) {
        board[i] = static_cast<char *>(alloc(y * sizeof(char)));
    }
    return board;
}

// Initialize the board by space or dot
void initBoard(char **board, int x, int y) {
    for (int i = 0; i < x; ++i) {
        for (int j = 0; j < y; j++) {
            board[i][j] = (j & 1 || i & 1) ? ' ' : '.';
        }
    }
}

// Allocate and initialize the board
char **allocAndInitBoard(int x, int y) {
    char **board = allocBoard(x, y);
    initBoard(board, x, y);
    return board;
}

// Deallocate the board
void deallocBoard(char **board, int x) {
    for (int i = 0; i < x; ++i) {
        dealloc(board[i]);
    }
    dealloc(board);
}

// Print the board
void printBoard(char **board, int x, int y) {
    pt "   ";
    for (int col = 0; col < y; ++col) {
        if (!(col % 10)) {
            pt (col / 10);
        } else {
            pt " ";
        }
    }
    pt endl;

    pt "   ";
    for (int col = 0; col < y; ++col) {
        pt (col) % 10;
    }
    pt endl;

    // Print the board with row numbers
    for (int row = 0; row < x; ++row) {
        if (!(row % 10)) {
            pt row / 10;
        } else {
            pt " ";
        }
        pt row % 10 << " ";
        for (int col = 0; col < y; ++col) {
            pt board[row][col];
        }
        pt endl;
    }
}

// Convert the character to lower case
char toLowerCase(char c) {
    return c | 32;
}

// Normalize the character to [0, 25)
int normalize(char c) {
    return toLowerCase(c) - 'a';
}

// Print the scores of the players
void printScores(int *points, char blacklist) {
    myPair<char, int> *arr = static_cast<myPair<char, int> *>(alloc(26 * sizeof(myPair<char, int>)));

    for (int i = 0; i < 26; i++) {
        arr[i] = myPair<char, int>(static_cast<char>(i + 'A'), points[i]);
    }

    // Find the maximum score and count the number of players with the maximum score
    int maxScore = -1;
    int maxCount = 0;

    for (int i = 0; i < 26; ++i) {
        if (arr[i].first != blacklist && arr[i].second > maxScore) {
            maxScore = arr[i].second;
            maxCount = 1;
        } else if (arr[i].first != blacklist && arr[i].second == maxScore) {
            maxCount++;
        }
    }

    for (int i = 0; i < 26; i++) {
        if (arr[i].second != -1) {
            pt "Player " << arr[i].first << " has " << arr[i].second
                         << (arr[i].second < 2 ? " box" : " boxes");

            // Handle win/tie logic
            if (arr[i].second == maxScore && arr[i].first != blacklist) {
                if (maxCount == 1) {
                    pt " (win)";
                } else {
                    pt " (tie)";
                }
            }
            pt nl;
        }
    }

    dealloc(arr);
}

// Check if the move is valid
// A move is valid if x%2 != y%2 and the cell is empty
bool isValidMove(int x, int y, char **board) {
    return (x & 1) != (y & 1) && board[x][y] == ' ';
}

// Add a point to the player and update the board
void addPoint(
        int *points,
        char **board,
        int x,
        int y,
        char player
) {
    if (board[x][y] == ' ') {
        if (points[normalize(player)] == -1) {
            points[normalize(player)] = 1;
        } else {
            points[normalize(player)]++;
        }
        board[x][y] = player;
    }
}

// check for any box on the top or bottom of the current move
void solveVertical(
        int moveX,
        int moveY,
        char **board,
        int *points,
        int x,
        int y,
        char player
) {
    // Check for a box below the current vertical move
    if (moveX < x - 2 &&                // Ensure the box below is within bounds
        board[moveX + 2][moveY] != ' ' && // Bottom horizontal line
        board[moveX + 1][moveY - 1] != ' ' && // Left vertical line
        board[moveX + 1][moveY + 1] != ' ') { // Right vertical line
        addPoint(points, board, moveX + 1, moveY, player); // Add point for box below
    }

    // Check for a box above the current vertical move
    if (moveX > 1 &&                    // Ensure the box above is within bounds
        board[moveX - 2][moveY] != ' ' && // Top horizontal line
        board[moveX - 1][moveY - 1] != ' ' && // Left vertical line
        board[moveX - 1][moveY + 1] != ' ') { // Right vertical line
        addPoint(points, board, moveX - 1, moveY, player); // Add point for box above
    }
}

// check for any box on the left or right of the current move
void solveHorizontal(
        int moveX,
        int moveY,
        char **board,
        int *points,
        int y,
        char player
) {
    // Check for a box to the left of the current horizontal move
    if (moveY > 1 &&                    // Ensure the box to the left is within bounds
        board[moveX][moveY - 2] != ' ' && // Left horizontal line
        board[moveX - 1][moveY - 1] != ' ' && // Top vertical line
        board[moveX + 1][moveY - 1] != ' ') { // Bottom vertical line
        addPoint(points, board, moveX, moveY - 1, player); // Add point for box to the left
    }

    // Check for a box to the right of the current horizontal move
    if (moveY < y - 2 &&                // Ensure the box to the right is within bounds
        board[moveX][moveY + 2] != ' ' && // Right horizontal line
        board[moveX - 1][moveY + 1] != ' ' && // Top vertical line
        board[moveX + 1][moveY + 1] != ' ') { // Bottom vertical line
        addPoint(points, board, moveX, moveY + 1, player); // Add point for box to the right
    }
}

// Solve the game
void solve(Moves moves, char **board) {
    int *points = static_cast<int *>(alloc(26 * (sizeof(int))));
    for (int i = 0; i < 26; i++) {
        points[i] = -1;
    }

    for (int i = 0; i < moves.moves.size(); i++) {
        Move move = moves.moves[i];

        int moveX = move.moveX;
        int moveY = move.moveY;
        char player = move.player;

        points[normalize(player)] = max(0, points[normalize(player)]);

        if (!isValidMove(moveX, moveY, board)) {
            pt "Invalid or Repeated move by: " << player << " at (x, y): (" << moveX << ", " << moveY << ")" << nl;
            board[moveX][moveY] = 'X';
            printBoard(board, moves.x, moves.y);

            printScores(points, player);
            pt "Exiting.." << nl;
            return;
        }

        board[moveX][moveY] = toLowerCase(player);

        if (!(moveX & 1) && (moveY & 1)) {
            solveVertical(moveX, moveY, board, points, moves.x, moves.y, player);
        } else if ((moveX & 1) && !(moveY & 1)) {
            solveHorizontal(moveX, moveY, board, points, moves.y, player);
        } else {
            pt "Invalid move by: " << player << " at (x, y): (" << moveX << ", " << moveY << ")" << nl;
            board[moveX][moveY] = 'X';
            printBoard(board, moves.x, moves.y);

            printScores(points, player);
            pt "Exiting.." << nl;
            return;
        }
    }

    printBoard(board, moves.x, moves.y);
    printScores(points, '\0');
    dealloc(points);
}

// Run the game
int run(char *fileName) {
    // --- IO START ---
    FILE *inp = fopen(fileName, "r");
    if (!inp) {
        pter "File not found" << nl;
        return 1;
    }

    fseek(inp, 0L, SEEK_END);
    const long sz = ftell(inp);
    fseek(inp, 0L, SEEK_SET);

    char *fileInpPtr = static_cast<char *>(alloc(sz + 1 * sizeof(char)));
    fileInpPtr[sz] = '\0';

    for (int i = 0; i < sz; ++i) {
        fscanf(inp, "%c", &fileInpPtr[i]);
    }
    // --- IO END ---

    // --- ALGORITHM START ---
    Moves moves = serialize(fileInpPtr);
    char **board = allocAndInitBoard(moves.x, moves.y);
    solve(moves, board);
    // --- ALGORITHM END ---

    // --- MEMORY CLEANUP START ---
    dealloc(fileInpPtr);
    deallocBoard(board, moves.x);
    fclose(inp);

    if (!assert_alloc()) {
        pter "Memory leak detected" << nl;
        return 1;
    }
    // --- MEMORY CLEANUP END ---
    return 0;
}

int main(int argc, char **argv) {
    if (argc < 2) {
        pter "No input file provided" << nl;
        pter "Usage: dotsandboxes /path/to/input.txt" << nl;
        return 1;
    }

    // collect errors at single place
    try {
        return run(argv[1]);
    } catch (const invalid_argument &e) {
        pter e.what() << nl;
        return 1;
    }
}