#include <iostream>
#include <fstream>

using namespace std;

enum piece {NONE,X,O};

struct board {
    enum piece piece[9];
    int value;
    struct board* next[9];
};

void presentBoard(ostream& out, struct board board) {
    out << "cout ";
    for(int i=0; i<9; i++) {
	if ((i % 3) == 0)
	    out << "<< \"";

	if (board.piece[i] == NONE)
	    out << i+1;
	else if (board.piece[i] == X)
	    out << "X";
	else // if (board.piece[i] == O)
	    out << "O";

	if (((i+1) % 3) == 0)
	    if (i==8)
	        out << "\" << endl; " << endl;
            else
	        out << "\" << endl " << endl << "     ";
    }
}

bool wins(struct board board, enum piece winner) {
    for(int i=0; i<9; i+=3) {
        int j;
	for(j=0; j<3; j++)
            if (board.piece[i+j] != winner)
                break;
        if (j >= 3)
            return true;
    }
    for(int i=0; i<9; i++) {
        int j;
	for(j=0; j<9; j+=3)
            if (board.piece[i+j] != winner)
                break;
        if (j >= 9)
            return true;
    }
    int j;
    for(j=0; j<9; j+=4)
	if (board.piece[j] != winner)
	    break;
    if (j >= 9)
	return true;
    for(j=2; j<8; j+=2)
	if (board.piece[j] != winner)
	    break;
    if (j >= 8)
	return true;

    return false;
}

bool boardFull(struct board board) {
    for(int i=0; i<9; i++)
        if (board.piece[i] == NONE)
            return false;
    return true;
}

int getBestComputerMove(struct board board) {
    for (int i=0; i<9; i++) 
        if (board.next[i] && wins(*board.next[i], O))
            return i;
    for (int i=0; i<9; i++) 
        if (board.next[i] && board.next[i]->value == board.value)
            return i;
    return 0; // Won't get here
}

void humanTurn(ostream& out, struct board board);

void computerTurn(ostream& out, struct board board) {
    int bestMove = getBestComputerMove(board);
    board = *board.next[bestMove];
    if (wins(board, O)) {
	presentBoard(out, board);
	out << "cout << \"You lose!\" << endl;" << endl;
    } else if (boardFull(board)) {
	presentBoard(out, board);
	out << "cout << \"You draw.\" << endl;" << endl;
    } else {
	presentBoard(out, board);
	humanTurn(out, board);
    }
}

void humanTurn(ostream& out, struct board board) {
    out << "cout << \"Please enter your move: \";" << endl;
    out << "switch(getchar()) {" << endl;
    struct board* nextBoard;
    for (int i=0; i<9; i++) {
	if (board.piece[i] == NONE) {
	    out << "case '" << i+1 << "':" << endl;
            out << "getchar();" << endl;
	    nextBoard = board.next[i];
            if (wins(*nextBoard, X)) {
                presentBoard(out, *nextBoard);
	        out << "cout << \"You win!\" << endl;" << endl;
            } else if (boardFull(*nextBoard)) {
                presentBoard(out, *nextBoard);
                out << "cout << \"You draw.\" << endl;" << endl;
            } else {
	        computerTurn(out, *nextBoard);
            }
	    out << "break;" << endl;
	}
    }
    out << "default:" << endl;
    out << "cout << \"Invalid choice. Please restart the game.\" << endl;" << endl;
    out << "return -1;" << endl;
    out << "}" << endl;
}

void generateGameTree(struct board* board, bool isHumansTurn) {
    if (wins(*board, X)) {
        board->value = 100;
        return;
    } else if (wins(*board, O)) {
        board->value = -100;
        return;
    } else if (boardFull(*board)) {
        board->value = 0;
        return;
    }

    for(int i=0; i<9; i++) {
        if (board->piece[i] != NONE)
            continue;
        struct board* newBoard = new struct board;
        board->next[i] = newBoard;
        memset(newBoard, 0, sizeof(newBoard));
	for (int j=0; j<9; j++)
            newBoard->piece[j] = board->piece[j];
        if (isHumansTurn)
            newBoard->piece[i] = X;
        else
            newBoard->piece[i] = O;
        generateGameTree(newBoard, !isHumansTurn);
    }

    if (isHumansTurn) {
	int max=-100;
	for (int i=0; i<9; i++)
	    if (board->next[i] && board->next[i]->value > max)
		max = board->next[i]->value;
	board->value = max;
    } else {
	int min = 100;
	for (int i=0; i<9; i++)
	    if (board->next[i] && board->next[i]->value < min)
		min = board->next[i]->value;
	board->value = min;
    }
}

int main() {
    struct board initialBoard;
    for (int i=0; i<9; i++) {
	initialBoard.piece[i] = NONE;
        initialBoard.next[i] = NULL;
	initialBoard.value = -1;
    }
    generateGameTree(&initialBoard, true);

    ofstream out("tttflat.cpp");
    out << "#include <stdio.h>" << endl
       	<< "#include <iostream>" << endl << endl
        << "using namespace std;" << endl << endl
        << "// This is a version of Tic-Tac-Toe that always wins and never uses" << endl
        << "// any variables, loops, or function calls (besides basic I/O)." << endl << endl
	<< "int main() {" << endl;
    presentBoard(out, initialBoard);
    humanTurn(out, initialBoard);
    out << "}" << endl;
}