Tris

#include <iostream>
#include <string>
#include <time.h>
#include <windows.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

//dichiarazione lato della matrice a tutto il programma
char** allocateChar(int x, int y) {
    char **a = new char*[y];
    for(int i = 0; i < y; i++)
        a[i] = new char[x];
    return a;
}
int** allocateInt(int y, int x) {
    int **a = new int*[y];
    for (int i = 0; i < y; i++)
        a[i] = new int[x];
    return a;
}

char** cloneChar(char **m, int l, int w) {
    //cout << "Cloning char matrix\n";
    char **ret = allocateChar(l, w);
    for (int y = 0; y < w; y++) {
        for (int x = 0; x < l; x++) {
            ret[x][y] = m[x][y];
        }
    }
    return ret;
}

void fillCharMatrix(char **m, int l, char c) {
    for (int i = 0; i < l; i++)
        for (int j = 0; j < l; j++)
            m[i][j] = c;
}

bool verifyCoor(int x, int y, char **m) {
    return m[x][y] == '-';
}

bool oob(int coor) {
    return coor < 0 || coor > 2;
}

//funzione di clear della console
void clear_screen(char fill = ' ') {
    COORD tl = {0,0};
    CONSOLE_SCREEN_BUFFER_INFO s;
    HANDLE console = GetStdHandle(STD_OUTPUT_HANDLE);
    GetConsoleScreenBufferInfo(console, &s);
    DWORD written, cells = s.dwSize.X * s.dwSize.Y;
    FillConsoleOutputCharacter(console, fill, cells, tl, &written);
    FillConsoleOutputAttribute(console, s.wAttributes, cells, tl, &written);
    SetConsoleCursorPosition(console, tl);
}

void tutorial_matrice() {
    //tutorial
    cout << "    [0] [1] [2]" << endl;
    cout << "[0]  -   -   -" << endl;
    cout << "[1]  -   -   -" << endl;
    cout << "[2]  -   -   -" << endl << endl;

    //istruzioni
    cout << "Per indicare una posizione inserisci il numero relativo alla riga, premi invio e digita il numero relativo alla colonna, poi premi di nuovo invio" << endl;
}

void stampa_matrice(char **m, int l) {
    for (int i = 0; i < l; i++){
        cout << endl;
        for (int j = 0; j < l; j++)
            cout << m[i][j] << "\t";
    }
}

//funzione di ricerca c su una colonna
int numero_c(char **m, int l, int colonna, char c) {
    int numerox = 0;
    for (int i = 0; i < l; i++)
        if (m[i][colonna] == c) numerox++;
    return numerox;
}

//funzione di ricerca c su una riga
int numero_r(char **m, int l, int riga, char c) {
    int numerox = 0;
    for (int i = 0; i < l; i++)
        if (m[riga][i] == c) numerox++;
    return numerox;
}

//funzione di ricerca c sulla diagonale principale
int numero_cp(char **m, int l, char c) {
    int numerox = 0;
    for (int i = 0; i < l; i++)
        if (m[i][i] == c) numerox++;
    return numerox;
}

//funzione di ricerca c sulla diagonale secondaria
int numero_cs(char **m, int l, char c) {
    int numerox = 0, j = 2;
    for (int i = 0; i < l; i++)
        if (m[i][j--] == c) numerox++;
    return numerox;
}

bool fillLine(char **m, int l, char c) {
    bool trovato = false;

    for (int k = 0; (k < 3) && !trovato; k++) {
        if (numero_r(m, l, k, c) == 2) //riga
            for (int j = 0; j < l; j++)
                if (verifyCoor(k, j, m)) {
                    m[k][j] = 'O';
                    trovato = true;
                }
        if (!trovato && numero_c(m, l, k, c) == 2) //colonna
            for (int j = 0; j < 3; j++)
                if (verifyCoor(j, k, m)) {
                    m[j][k] = 'O';
                    trovato = true;
                }
    }
    if (!trovato && (numero_cp(m, l, c) == 2)) //diagonale principale
        for (int j = 0; j < 3 ; j++)
            if (verifyCoor(j, j, m)) {
                m[j][j] = 'O';
                trovato = true;
            }
    if (!trovato && (numero_cs(m, l, c) == 2)) { //diagonale secondaria
        int ind = 2;
        for (int controllod = 0; controllod < 3; controllod++) {
            if (verifyCoor(controllod, ind, m)) {
                m[controllod][ind] = 'O';
                trovato = true;
            }
            ind--;
        }
    }
    return trovato;
}

int getDiagonalCoordinate(int x, int y, int **d) {
    //cout << "Generating diagonal [" << x << ", " << y << "]\n";
    int i = 0, xc, yc;
    for (int xs = -1; xs < 2; xs++) {
        for (int ys = -1; ys < 2; ys++) {
            xc = x + xs;
            yc = y + ys;
            while (!(oob(xc) || oob(yc) || ((xs == 0) && (ys == 0)))) {
                //cout << xc << "XC " << yc << "YC " << xs << "XS " << ys << "YS\n";
                d[i][0] = xc;
                d[i][1] = yc;
                //cout << " X:" << d[i][0] << " Y:" << d[i][1] << "\n";
                xc += xs;
                yc += ys;
                i++;
            }
        }
    }
    return i;
}

int checkCollision(int **d1, int d1length, int **d2, int d2length, int **result) {
    int i = 0;
    //cout << "Checking for collision\n";
    for (int d1c = 0; d1c < d1length; d1c++) {
        for (int d2c = 0; d2c < d2length; d2c++) {
            //cout << d1[d1c][0] << "xd1 " << d2[d2c][0] << "xd2 " << d1[d1c][1] << "yd1 " << d2[d2c][1] << "yd2\n";
            if ((d1[d1c][0] == d2[d2c][0]) && (d1[d1c][1] == d2[d2c][1])) {
                result[i][0] = d1[d1c][0];
                result[i][1] = d1[d1c][1];
                i++;
            }
        }
    }
    return i;
}

char **mergePath(char **m, int **p, char c) {
    //cout << "Merging path\n";
    char **ret = cloneChar(m, 3, 3);
    for (int i = 0; i < 3; i++) if (verifyCoor(p[i][0], p[i][1], ret)) ret[p[i][0]][p[i][1]] = c;
    return ret;
}

bool pathIsValid(char **m, int **p) {
    //cout << "Checking if path is valid\n";
    char **idealPath = mergePath(m, p, 'O');
    int valid = 0;
    for (int i = 0; i < 3; i++) {
        if ((numero_c(idealPath, 3, i, 'O') == 2) && (numero_c(idealPath, 3, i, 'X') == 0)) valid++;
        if ((numero_r(idealPath, 3, i, 'O') == 2) && (numero_r(idealPath, 3, i, 'X') == 0)) valid++;
    }
    if ((numero_cp(idealPath, 3, 'O') == 2) && (numero_cp(idealPath, 3, 'X') == 0)) valid++;
    if ((numero_cs(idealPath, 3, 'O') == 2) && (numero_cs(idealPath, 3, 'X') == 0)) valid++;
    return valid >= 2;
}

bool findThirdPoint(int **p, char **m) {
    int **d1 = allocateInt(8, 2), **d2 = allocateInt(8, 2), **collision = allocateInt(8, 2);
    int d1Length = getDiagonalCoordinate(p[0][0], p[0][1], d1), d2Length = getDiagonalCoordinate(p[1][0], p[1][1], d2);
    int collisionlength = checkCollision(d1, d1Length, d2, d2Length, collision), i = 0;
    bool found = false;
    //cout << "Selecting the third point\n Collision length = " << collisionlength << "\n";
    while (i < collisionlength && !found) {
        if (verifyCoor(collision[i][0], collision[i][1], m)) {
            p[2][0] = collision[i][0];
            p[2][1] = collision[i][1];
            if (pathIsValid(m, p)) {
                //cout << "Third point [" << p[2][0] << "," << p[2][1] << "]\n";
                found = true;
            }
        }
        i++;
    }
    return found;
}

bool newPath(char **m, int **p) {
    int totalAttemps = 8;
    srand(time(NULL));
    do {
        for (int i = 0; i < 2; i++) {
            do {
                p[i][0] = rand() % 3;
                p[i][1] = rand() % 3;
                //cout << "Placing point " << i << " [" << p[i][0] << ", " << p[i][1] << "]\n";
            } while (!verifyCoor(p[i][0], p[i][1], m));
        }
    } while ((((p[0][0] == p[1][0]) && (p[0][1] == p[1][1])) || !findThirdPoint(p, m)) && (totalAttemps-- > 0));
    return totalAttemps > 0;
}

int getPlacedCoordinate(char **m, int **p, char c) {
    //cout << "Getting point already placed\n";
    int i = 0;
    for(int x = 0; x < 3; x++)
        for(int y = 0; y < 3; y++)
            if (m[x][y] == c) {
                p[i][0] = x;
                p[i][1] = y;
                i++;
            }
    return i;
}

bool regeneratePath(char **m, int **p, char c) {
    srand(time(NULL));
    int **oldPosition = allocateInt(5, 2);
    int oldPositionLength = getPlacedCoordinate(m, oldPosition, c), totalAttemps = 8;
    //cout << "Regenerating coordinate from " << oldPositionLength << " points\n";
    do {
        if (oldPositionLength <= 2) {
            p[0][0] = oldPosition[0][0];
            p[0][1] = oldPosition[0][1];
            if (oldPositionLength == 1) {
                p[1][0] = rand() % 3;
                p[1][1] = rand() % 3;
                //cout << "p1 [" << p[1][0] << ", " << p[1][1] << "]\n";
            } else {
                p[1][0] = oldPosition[1][0];
                p[1][1] = oldPosition[1][1];
            }
        } else {
            int n;
            for (int i = 0; i < 2; i++) {
                n = rand() % oldPositionLength;
                p[i][0] = oldPosition[n][0];
                p[i][1] = oldPosition[n][1];
                //cout << "p" << i << " [" << p[1][0] << ", " << p[1][1] << "]\n";
            }
        }
    } while ((((p[0][0] == p[1][0]) && (p[0][1] == p[1][1])) || !findThirdPoint(p, m)) && (totalAttemps-- > 0));
    return totalAttemps > 0;
}

void placeRandomPoint(char **m, char c) {
    int x, y;
    do {
        x = rand() % 3;
        y = rand() % 3;
    } while (!verifyCoor(x, y, m));
    //cout << "Placing random point [" << x << ", " << y << "]\n";
    m[x][y] = c;
}


void attacco(char **m, int l, char c, int **path, bool *pathStatus, int *pathIndex) {
//ci pensa sorace

//Sorace says: mori.

    /*
        (Per creare un nuovo path)
            Controlla se esiste già un path
                NO: Crea un path
                        Piazza posizione 1 e 2 (Controllando se cella è vuota)
                        Piazza posizione 3 su intersezioni
                            Genera tutte le linee passanti per i punti 1 e 2
                            Trova tutte le intersezioni di queste linee
                            posizione 3 = prima intersezione libera
                        Controlla se è valido
                    Creato un path con successo?
                        SI: Piazza posizione 0
                        NO: Piazza un punto a caso
                SI: Controlla se è valdo
                        SI: Prova a piazzare posizione pathIndex
                                La posizione pathIndex è libera?
                                    SI: Piazza
                                Incrementa pathIndex
                                Se non è stato piazzato niente ripeti fino a che pathIndex < 2
                                Se non è stato piazzato ancora niente, piazza un cerchio a caso
                        NO: Ottieni le coordinate di tutti i cerchi già piazzati
                            Genera un nuovo path dai cerchi già piazzati

        (Per controllare se è valido)
            Unisce la matrice con il path in una nuova matrice
                Clona la matrice
                Piazza coordinate prese dal path solo se la casella è vuota
            Conta per ogni riga/colonna/diagonale se ci sono 2 cerchi e nessuna X
            Se ci sono almeno due "corrispondenze" riguardo a quello che si cercava sopra, il path è valido

        (Per rigenerare un path)
            Trova tutti i cerchi piazzati
            Se è stato piazzato un solo cerchio genera la seconda posizione a caso
            Se sono stati piazzati 2 cerchi usali come le prime due posizioni
            Se sono stati piazzati più di 2 cerchi prendine due a caso e usali come prime due posizioni
            Genera la terza posizione
    */
    srand(time(NULL));
    if (!*pathStatus) {
        //cout << "Generating new path\n";
        *pathStatus = newPath(m, path);
        if (*pathStatus) {
            //cout << "Path generated successfully\n";
            m[path[*pathIndex][0]][path[*pathIndex][1]] = c;
            (*pathIndex)++;
        } else placeRandomPoint(m, c);
    } else {
        if (pathIsValid(m, path)) {
            bool b;
            do {
                b = verifyCoor(path[*pathIndex][0], path[*pathIndex][1], m);
                if(b) m[path[*pathIndex][0]][path[*pathIndex][1]] = c;
                (*pathIndex)++;
            } while (!b && (*pathIndex < 3));
            if (!b) placeRandomPoint(m, 'O');
        } else {
            if (regeneratePath(m, path, c)) {
                if (*pathIndex > 3) *pathIndex = 3;
                //cout << "Path regenerated successfully\n";
                m[path[*pathIndex][0]][path[*pathIndex][1]] = c;
            } else placeRandomPoint(m, c);
        }
    }
}

int getR() {
    //lettura riga e assegnazione valore posizione
    int input;
    do {
        cout << "Inserisci la riga: ";
        cin >> input;
    } while (oob(input));
    return input;
}
int getC() {
    //lettura colonna e assegnazione valore posizione
    int input;
    do {
        cout << "Inserisci la colonna: ";
        cin >> input;
    } while (oob(input));
    return input;
}

void turno_giocatore(char **m, int l, char ch) {
    int r, c;
    cout << endl << endl << "Dove vuoi inserire una '" << ch << "'?" << endl;

    do{
        r = getR();
        c = getC();
    }while (!verifyCoor(r, c, m));

    m[r][c] = ch;
    cout << endl << endl;
    clear_screen ();
    stampa_matrice (m, l);
}

bool getPlayerWin(char **m, char c) {
    bool win = false;
    for (int i = 0; (i < 3) && !win; i++) {
        win = win || (numero_c(m, 3, i, c) == 3);
        win = win || (numero_r(m, 3, i, c) == 3);
    }
    win = win || (numero_cp(m, 3, c) == 3);
    return win || (numero_cs(m, 3, c) == 3);
}

int partita_IA(char **m, int l) {
    //dichiarazione variabili necessarie
    bool turni = true, pathStatus = false;
    int risultato = 0, caselle_libere = 9, pathIndex = 0;
    int **path = allocateInt(3, 2);

    while ((caselle_libere > 0) && (risultato == 0)){
        turni = !turni;

        if (turni) { //turno del giocatore
            cout << endl;
            stampa_matrice ( m, l );
            turno_giocatore ( m, l, 'X' );
            if (getPlayerWin(m, 'X')) risultato = 2;

        } else { //turno dell'IA
            cout << endl << "Ora tocca alla IA" << endl;
            if (!fillLine(m, l, 'O')) { //he attacc
                if (!fillLine(m, l, 'X')) //he defense
                    attacco(m, l, 'O', path, &pathStatus, &pathIndex); //but most importantly: he do some doppi giocc
            } else risultato = 1;
        }
        caselle_libere--;
    }
    stampa_matrice(m, l);
    return risultato;
}

// partita 2 giocatori
int partita_G(char **m, int l) {
    bool turno = true;
    int caselle_libere = 9, vittoria = 0;
    stampa_matrice (m, l);

    while ((vittoria == 0) && (caselle_libere > 0)){
        turno = !turno;
        cout << "Turno del giocatore: " << turno << endl;
        char c = 'X';
        if (turno) c = 'O';
        turno_giocatore(m, l, c);
        if (getPlayerWin(m, c)) vittoria = turno + 1;
        caselle_libere--;
    }
    return vittoria;
}

void main() {
    /*int **d = allocateInt(6, 2);
    getDiagonalCoordinate(0, 1, d);
    return;*/
    //dichiarazione di tutte le variabili necessarie
    int l = 3, risposta;
    char **m = allocateChar(l, l);
    bool risultato;
    fillCharMatrix(m, l, '-');

    //lettura e controllo delle opzioni di gioco
    cout << "Partita a Tris? Contro chi vuoi giocare?" << endl << endl;
    do{
        cout << "[0] IA" << endl << "[1] Amico" << endl << endl;
        cin >> risposta;
    } while ((risposta != 0) && (risposta != 1));

    //stampa della matrice e tutorial
    clear_screen();
    tutorial_matrice();

    //in base alla scelta si gioca contro l'avversario scelto
    switch(risposta) {
        case 0: {
            switch (partita_IA(m, l)) {
                case 0: {
                    cout << "Parità!\n";
                    break;
                }
                case 1: {
                    cout << "Hai perso!\n";
                    break;
                }
                case 2: {
                    cout << "Hai vinto!\n";
                    break;
                }
            }
            break;
        }
        case 1: {
            int result = partita_G(m, l);
            if (result > 0)
                cout << "Vince giocatore: " << result << endl;
            else
                cout << "Parità!" << endl;
            break;
        }
    }
}