#include <iostream>
#include <fstream>
#include <string>
#include <deque>
#include <vector>
#include <ctime>
using namespace std;

/* Number of food pellets that must be eaten to win. */
const int kMaxFood = 20;

/* Constants for the different tile types. */
const char kEmptyTile = ' ';
const char kWallTile = '#';
const char kFoodTile = '$';
const char kSnakeTile = '*';

/* Chance to turn in each step. */
const double kTurnRate = 0.2;

/* Time to pause between frames. */
const double kWaitTime = 0.1;


/* A struct encoding a point in a two-dimensional grid. */
struct pointT
{
    int row, col;
};

/* A struct containing relevant game information. */
struct gameT
{
    vector<string> world; // The playing field
    int numRows, numCols; // Size of the playing field
    deque<pointT> snake;  // The snake body
    int dx, dy;           // The snake direction
    int numEaten;         // How much food we've eaten.
};

pointT makePoint(int row, int col) {
    pointT result;
    result.row = row;
    result.col = col;
    return result;
}

void loadWorld(gameT& game, ifstream& input) {
    input >> game.numRows >> game.numCols;
    game.world.resize(game.numRows);

    input >> game.dx >> game.dy;

    string dummy;
    getline(input, dummy);

    for (int row = 0; row < game.numRows; ++row) {
        getline(input, game.world[row]);
        size_t col = game.world[row].find(kSnakeTile);
        if (col != string::npos) {
            game.snake.push_back(makePoint(row, col));
        }
    }
    game.numEaten = 0;
}

void openUserFile(ifstream& input) {
    while (true) {
        string filename;
        cout << "Enter filename: ";
        getline(cin, filename);

        input.open(filename.c_str());
        if (input.is_open()) break;

        cout << "Sorry, I can't find the file " << filename << endl;
    }
}

void initializeGame (gameT& game) {
    /* Seed the randomizer */
    srand(static_cast<unsigned int>(time(NULL)));

    ifstream input;
    openUserFile(input);
    loadWorld(game, input);
}

bool randomChance(double probability) {
    return (rand() / (RAND_MAX + 1.0)) < probability;
}

void pause() {
    clock_t startTime = clock(); // clock_t is a type which holds clock ticks

    /* This loop does nothing except loop and check how much time is left. */
    while(static_cast<double>(clock() - startTime) / CLOCKS_PER_SEC < kWaitTime);
}

/* The string used to clear the display before printing the game board.
 * Windows should use "CLS"; Linux and Mac OS X users should use "clear".
 */
const string kClearCommand = "CLS";

void printWorld(gameT& game) {
    system(kClearCommand.c_str());
    for (int row = 0; row < game.numRows; ++row) {
        cout << game.world[row] << endl;
    }
    cout << "Food eaten: " << game.numEaten << endl;
}

void displayResult(gameT& game) {
    printWorld(game);
    if (game.numEaten == kMaxFood)
        cout << "The snake wins!" << endl;
    else
        cout << "Oh no! The snake crashed!" << endl;
}

pointT getNextPosition (gameT& game, int dx, int dy) {
    /* Get the head position */
    pointT result = game.snake.front();

    /* Increment the head position by the current direction */
    result.row += dy;
    result.col += dx;
    return result;
}

bool inWorld(pointT& pt, gameT& game) {
    return pt.col >= 0 && pt.row >= 0 && pt.col < game.numCols && pt.row < game.numRows;
}

bool crashed(pointT headPos, gameT& game) {
    return !inWorld(headPos, game) || game.world[headPos.row][headPos.col] == kSnakeTile
            || game.world[headPos.row][headPos.col] == kWallTile;
}

void placeFood(gameT& game) {
    while(true) {
        int row = rand() % game.numRows;
        int col = rand() % game.numCols;

        /* If the specified position is empty, place the food there */
        if (game.world[row][col] == kEmptyTile) {
            game.world[row][col] = kFoodTile;
            return;
        }
    }
}

bool moveSnake(gameT& game) {
    pointT nextHead = getNextPosition(game, game.dx, game.dy);
    if (crashed(nextHead, game))
        return false;

    bool isFood = (game.world[nextHead.row][nextHead.col] == kFoodTile);

    game.world[nextHead.row][nextHead.col] = kSnakeTile;
    game.snake.push_front(nextHead);

    if (!isFood) {
        game.world[game.snake.back().row][game.snake.back().col] = kEmptyTile;
        game.snake.pop_back();
    } else {
        ++game.numEaten;
        placeFood(game);
    }
    return true;
}

void performAI (gameT& game) {
    /* Figure out where we will be after we move this turn */
    pointT nextHead = getNextPosition(game, game.dx, game.dy);

    /* If that puts us in a wall or we randomly decide to, turn the snake */
    if (crashed(nextHead, game) || randomChance(kTurnRate)) {
        int leftDx = -game.dy;
        int leftDy = game.dx;

        int rightDx = game.dy;
        int rightDy = -game.dx;

        /* Check if turning left or right will cause snake to crash */
        bool canLeft = !crashed(getNextPosition(game, leftDx, leftDy), game);
        bool canRight = !crashed(getNextPosition(game, rightDx, rightDy), game);

        bool willTurnLeft = false;
        if (!canLeft && !canRight)
            return;
        else if (canLeft && !canRight)
            willTurnLeft = true;
        else if (!canLeft && canRight)
            willTurnLeft = false;
        else
            willTurnLeft = randomChance((0.5));

        game.dx = willTurnLeft ? leftDx : rightDx;
        game.dy = willTurnLeft ? leftDy : rightDy;
    }
}

void runSimulation(gameT& game) {
    /* Keep looping while we have not eaten too much */
    while (game.numEaten < kMaxFood) {
        printWorld(game);      // Display the board
        performAI(game);       // Have the AI choose the action

        if (!moveSnake(game))  // Move the snake and stop if we crashed
            break;

        pause();               // Pause so we can see what's going on
    }
    displayResult(game);       // Tell the user what happened
}

/* The main program. Initializes the world, then runs the simulation. */
int main()
{
    gameT game;
    initializeGame(game);
    runSimulation(game);
    return 0;
}