#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
// #include <conio.h>

struct Coordinate
{
    int x;
    int y;
};

// Printing the field
void printChar(char, int);
void printField(int*, int, int); // field, row, column
void printFieldLine(int, int); // column, space
//

int getIntLength(int);
void makeField(int*, int, int, struct Coordinate*);

char getAction();
int moveCell(int*, struct Coordinate*, int, int, char, int); // field, row, column, coordinate, action, count
void indexFromCoordinate(struct Coordinate*, int*, int);
void randomizeField(int*, int, int, struct Coordinate*);
int checkField(int* field, int row, int column);


int main()
{
    int row, column, move_counter = 0;
    struct Coordinate emptycell;
    srand(time(NULL));
    //srand(295837);

    printf("Input format is: a, b\n"
           "where a and b are integers.\n\n");

    printf("Enter row and column length: ");
    scanf("%d, %d", &row, &column);

    int* field = (int*) malloc(row * column * sizeof(int));
    makeField(field, row, column, &emptycell);
    randomizeField(field, row, column, &emptycell);

    clock_t begin = clock();
    clock_t end;
    while (1)
    {
        printField(field, row, column);
        printf("Move count: %d\n", move_counter);
        if (checkField(field, row, column))
        {
            break;
        }
        move_counter += moveCell(field, &emptycell, row, column, getAction(), 1);
	system("clear");
       	//system("cls");
    }
    end = clock();
    printf("begin= %Lf, end= %Lf\n", (long double) begin / CLOCKS_PER_SEC, (long double) end / CLOCKS_PER_SEC);
    long double time_spent = (long double) (end - begin) / CLOCKS_PER_SEC;
    printf("Play time = %lf seconds\n\n", time_spent);
}

int checkField(int* field, int row, int column)
{
    int i;
    for (int x = 0 ; x < row; x++)
    {
        for (int y = 0; y < column; y++)
        {
            i = (column*x) + y;
            if (i == (row * column) - 1){return 1;}
            if (field[i] != i + 1){return 0;}
        }
    }
    return 0;
}

void makeField(int* field, int row, int column, struct Coordinate* emptycell)
{
    for (int x = 0 ; x < row; x++)
    {
        for (int y = 0; y < column; y++)
        {
            field[(column*x) + y] = (column*x) + y + 1;
        }
    }
    field[(column*row) - 1] = 0;
    (*emptycell).x = column;
    (*emptycell).y = row;
}

int getIntLength(int num)
{
    int length = 0;
    if (num == 0){ return 1; }
    while(num > 0)
    {
        num = floor(num / 10); length++;
    }
    return length;
}

void printChar(char symbol, int count)
{
    for (int i = 0; i < count; i++)
    {
        printf("%c", symbol);
    }
}

void printField(int* field, int row, int column)
{
    int space = 3;
    printFieldLine(column, space);

    for (int x = 0; x < row; x++)
    {
        for (int y = 0; y < column; y++)
        {
            if (field[(column*x) + y] == 0){ printf("|"); printChar(' ', space); continue; }
            printf("|%d", field[(column*x) + y]);
            printChar(' ', space - getIntLength(field[(column*x) + y]));
        }
        printf("|\n");
        printFieldLine(column, space);
    }
}

void printFieldLine(int column, int space)
{
    for (int i = 0; i < column; i++)
    {
        printf("+");
        printChar('-', space);
    }
    printf("+\n");
}

char getAction()
{
    char action;
    fflush(stdin);
    printf("Enter an action (w, a, s, d for movement. t to quit): ");
    //action = getche();
    action = getchar();
    printf("%c", '\n');
    return action;
}

void indexFromCoordinate(struct Coordinate* emptycell, int* num, int column)
{
    *num = (((*emptycell).y - 1) * column) + ((*emptycell).x - 1);
}

int moveCell(int* field, struct Coordinate* emptycell, int row, int column, char action, int count)
{
    int emptycell_index, move_counter = 0;
    indexFromCoordinate(emptycell, &emptycell_index, column);
    switch (action)
    {
        case 's':
            if ((*emptycell).y > 1)
            {
                if (count < 0){moveCell(field, emptycell, row, column, 'w', -count);}
                while (count > 0){
                field[emptycell_index] = field[emptycell_index - column];
                field[emptycell_index - column] = 0;
                (*emptycell).y -= 1;
                indexFromCoordinate(emptycell, &emptycell_index, column);
                count--; move_counter++;}
                return move_counter;
            }
            else {return 0;}
        case 'd':
            if ((*emptycell).x > 1)
            {
                if (count < 0){moveCell(field, emptycell, row, column, 'a', -count);}
                while(count > 0){
                    field[emptycell_index] = field[emptycell_index - 1];
                    field[emptycell_index - 1] = 0;
                    (*emptycell).x -= 1;
                    indexFromCoordinate(emptycell, &emptycell_index, column);
                    count--; move_counter++;
                }
                return move_counter;
            }
            else {return 0;}
        case 'w':
            if ((*emptycell).y < row)
            {
                if (count < 0){moveCell(field, emptycell, row, column, 's', -count);}
                while(count > 0){
                    field[emptycell_index] = field[emptycell_index + column];
                    field[emptycell_index + column] = 0;
                    (*emptycell).y += 1;
                    indexFromCoordinate(emptycell, &emptycell_index, column);
                    count--; move_counter++;
                }
                return move_counter;
            }
            else {return 0;}
        case 'a':
            if ((*emptycell).x < column)
            {
                if (count < 0){moveCell(field, emptycell, row, column, 'd', -count);}
                while(count > 0){
                    field[emptycell_index] = field[emptycell_index + 1];
                    field[emptycell_index + 1] = 0;
                    (*emptycell).x += 1;
                    indexFromCoordinate(emptycell, &emptycell_index, column);
                    count--; move_counter++;
                }
                return move_counter;
            }
            else {return 0;}
        case 't':
            exit(0);
        default:
            return 0;
    }
}

void randomizeField(int* field, int row, int column, struct Coordinate* emptycell)
{
    char actions[4] = {'w', 'a', 's', 'd'};
    char last_action = 'n', new_action;
    for (int i = 0; i < row*column*50; i++)
    {
        do{
        new_action = actions[rand() % 4];
        } while (last_action == new_action);
        moveCell(field, emptycell, row, column, new_action, 1);
        last_action = new_action;
    }
}