/**
 *
 * Homework 4 - Water Jug Problem
 * author: @rgadhia - Raj Gadhia and Albert Chen
 * Pledge: I pledge my honor that I have abided by the Stevens Honor System.
 * Date: 10/08/19
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <list>

using namespace std;

// Struct to represent state of water in the jugs.
struct State {
    int a, b, c;
    vector<string> directions;

    State(int _a, int _b, int _c) : a(_a), b(_b), c(_c) { }

    // String representation of state in tuple form.
    string to_string() {
        ostringstream oss;
        oss << "(" << a << ", " << b << ", " << c << ")";
        return oss.str();
    }
};

//if been visited already, dont put it in the queue
//break outta queue while not empty loop when u find the goal
//if the queue is empty, return 0
//function that returns a vector that contains all the possible states u can go from current
//vectors of strings in the state class: add the vector after every move

//[email protected]

//returns a vector of the possible moves for that state
vector<State> possiblepours(State s, int capA, int capB, int capC) {
    vector<State> possible;
    //C to A
    if (s.a != capA && s.c != 0)
    {
        State temp(s.a,s.b,s.c);
        int pamount;
        temp.directions = s.directions;
        if (temp.c + temp.a <= capA)
        {
            pamount = temp.c;
            temp.a += pamount;
            temp.c = 0;
        }
        else
        {
            pamount = capA - temp.a;
            temp.a += pamount;
            temp.c -= pamount;
        }
        if(pamount == 1){
            temp.directions.push_back("Pour " + std::to_string(pamount)+ " gallon from C to A. " + "(" + std::to_string(temp.a) + ", " + std::to_string(temp.b) + ", " + std::to_string(temp.c) + ")\n");
        } else {
            temp.directions.push_back("Pour " + std::to_string(pamount)+ " gallons from C to A. " + "(" + std::to_string(temp.a) + ", " + std::to_string(temp.b) + ", " + std::to_string(temp.c) + ")\n");
        }
        possible.push_back(temp);
    }
    //B to A
    if (s.a != capA && s.b != 0)
    {
        State temp(s.a,s.b,s.c);
        temp.directions = s.directions;
        int pamount;
        if (temp.b + temp.a <= capA)
        {
            pamount = temp.b;
            temp.a += pamount;
            temp.b = 0;
        }
        else
        {
            pamount = capA - temp.a;
            temp.a += pamount;
            temp.b -= pamount;
        }
        if(pamount == 1){
            temp.directions.push_back("Pour " + std::to_string(pamount)+ " gallon from B to A. " + "(" + std::to_string(temp.a) + ", " + std::to_string(temp.b) + ", " + std::to_string(temp.c) + ")\n");
        } else {
            temp.directions.push_back("Pour " + std::to_string(pamount)+ " gallons from B to A. " + "(" + std::to_string(temp.a) + ", " + std::to_string(temp.b) + ", " + std::to_string(temp.c) + ")\n");
        }
        possible.push_back(temp);
    }
    //C to B
    if (s.b != capB && s.c != 0)   // (0,0,8) -> (0,5,3)
    {
        State temp(s.a,s.b,s.c);
        temp.directions = s.directions;
        int pamount;
        if (temp.c + temp.b <= capB)
        {
            pamount = temp.c;
            temp.b += pamount;
            temp.c = 0;
        }
        else
        {
            pamount = capB - temp.b;
            temp.b += pamount;
            temp.c -= pamount;
        }
        if(pamount == 1){
            temp.directions.push_back("Pour " + std::to_string(pamount)+ " gallon from C to B. " + "(" + std::to_string(temp.a) + ", " + std::to_string(temp.b) + ", " + std::to_string(temp.c) + ")\n");
        } else {
            temp.directions.push_back("Pour " + std::to_string(pamount)+ " gallons from C to B. " + "(" + std::to_string(temp.a) + ", " + std::to_string(temp.b) + ", " + std::to_string(temp.c) + ")\n");
        }
        possible.push_back(temp);
    }
    //A to B
    if (s.b != capB && s.a != 0)
    {
        State temp(s.a,s.b,s.c);
        temp.directions = s.directions;
        int pamount;
        if (temp.a + temp.b <= capB)
        {
            pamount = temp.a;
            temp.b += pamount;
            temp.a = 0;
        }
        else
        {
            pamount = capB - temp.b;
            temp.b += pamount;
            temp.a -= pamount;
        }
        if(pamount == 1){
            temp.directions.push_back("Pour " + std::to_string(pamount)+ " gallon from A to B. " + "(" + std::to_string(temp.a) + ", " + std::to_string(temp.b) + ", " + std::to_string(temp.c) + ")\n");
        } else {
            temp.directions.push_back("Pour " + std::to_string(pamount)+ " gallons from A to B. " + "(" + std::to_string(temp.a) + ", " + std::to_string(temp.b) + ", " + std::to_string(temp.c) + ")\n");
        }
        possible.push_back(temp);
    }
    //B to C
    if (s.c != capC && s.b != 0)
    {
        State temp(s.a,s.b,s.c);
        temp.directions = s.directions;
        int pamount;
        if (temp.b + temp.c <= capC)
        {
            pamount = temp.b;
            temp.c += pamount;
            temp.b = 0;
        }
        else
        {
            pamount = capC - temp.c;
            temp.c += pamount;
            temp.b -= pamount;
        }
        if(pamount == 1){
            temp.directions.push_back("Pour " + std::to_string(pamount)+ " gallon from B to C. " + "(" + std::to_string(temp.a) + ", " + std::to_string(temp.b) + ", " + std::to_string(temp.c) + ")\n");
        } else {
            temp.directions.push_back("Pour " + std::to_string(pamount)+ " gallons from B to C. " + "(" + std::to_string(temp.a) + ", " + std::to_string(temp.b) + ", " + std::to_string(temp.c) + ")\n");
        }
        possible.push_back(temp);
    }
    //A to C
    if (s.c != capC && s.a != 0)
    {
        State temp(s.a,s.b,s.c);
        int pamount;
        temp.directions = s.directions;
        if (temp.a + temp.c <= capC)
        {
            pamount = temp.a;
            temp.c += pamount;
            temp.a = 0;
        }
        else
        {
            pamount = capC - temp.c;
            temp.c += pamount;
            temp.a -= pamount;
        }
        if(pamount == 1){
            temp.directions.push_back("Pour " + std::to_string(pamount)+ " gallon from A to C. " + "(" + std::to_string(temp.a) + ", " + std::to_string(temp.b) + ", " + std::to_string(temp.c) + ")\n");
        } else {
            temp.directions.push_back("Pour " + std::to_string(pamount)+ " gallons from A to C. " + "(" + std::to_string(temp.a) + ", " + std::to_string(temp.b) + ", " + std::to_string(temp.c) + ")\n");
        }
        possible.push_back(temp);
    }
    return possible;
}

State breadthSearch (vector<int> nums) {
    int cols = nums[0]+1;
    int rows = nums[1]+1;
    bool** visited = new bool*[rows];
    // go through rows filling / visiting
    for (int i=0; i<rows; i++)
    {
        visited[i] = new bool[cols];
        fill(visited[i], visited[i] + cols, false);
    }

    list<State> queue;
    vector<State> moves;
    State start(0, 0, nums[2]);
    State goal(nums[3], nums[4], nums[5]);
    State current(0, 0, 0);
    queue.push_back(start);
    while (!(queue.empty())) {
        current = queue.front(); //extracts first element of queue
        queue.pop_front(); //pops it out

        if (current.a == goal.a && current.b == goal.b && current.c == goal.c)
        {
            queue.push_back(current);
            break;
        }
        else
        {
            moves = possiblepours(current, nums[0], nums[1], nums[2]);
            for (int i = 0; i < (int)moves.size(); i++)
            {
                current = moves[i];
                if (current.a == goal.a && current.b == goal.b && current.c == goal.c)
                {

                    for (int i = 0; i < cols; i++)
                    {
                        delete [] visited[i];
                    }
                    delete [] visited;

                    return current;
                }
                if (visited[current.a][current.b] == false)
                {
                    queue.push_back(current);
                    visited[current.a][current.b] = true;
                }
            }
        }
    }
    for (int i = 0; i < cols; i++) {
        delete [] visited[i];
    }

    delete [] visited;

    if (queue.empty()) {
        return State(-1, -1, -1);
    }
    return current;
}

int main(int argc, char * const argv[]) {
    vector<int> nums;

    //user input should only have seven arguments
    if (argc != 7)
    {
        cout << "Usage: ./waterjugpuzzle <cap A> <cap B> <cap C> <goal A> <goal B> <goal C>" << endl;
        return 0;
    }

   // ensure there is no error for integer capacity of jugs
   // whenever there is no error, we pushback the capacity and goals into the nums vector
    for (int i = 1; i < 4; i++) {
        istringstream iss(argv[i]);
        int isnum;
        // if assigning iss to isnum fails, that means it's not an integer
        if (!(iss>>isnum) || isnum <= 0)
        {
            if (i == 1)
            {
                 cout << "Error: Invalid capacity '" << argv[i] << "' for jug A." << endl;
            }
            if (i == 2)
            {
                 cout << "Error: Invalid capacity '" << argv[i] << "' for jug B." << endl;
            }
            if (i == 3)
            {
                 cout << "Error: Invalid capacity '" << argv[i] << "' for jug C." << endl;
            }
            iss.clear();
            return 1;
        }
        nums.push_back(isnum);
        iss.clear();
    }
    for (int i = 4; i < 7; i++)
    {
        istringstream iss(argv[i]);
        int isnum;
        if (!(iss>>isnum) || isnum < 0)
        {
            if (i == 4)
            {
                 cout << "Error: Invalid goal '" << argv[i] << "' for jug A." << endl;
            }
            if (i == 5)
            {
                 cout << "Error: Invalid goal '" << argv[i] << "' for jug B." << endl;
            }
            if (i == 6)
            {
                 cout << "Error: Invalid goal '" << argv[i] << "' for jug C." << endl;
            }
            iss.clear();
            return 1;
        }
        nums.push_back(isnum);
        iss.clear();
    }
    for (int i = 4; i < 7; i++)
    {
        if (nums[i-1] > nums[i-4])
        {
            if (i == 4)
            {
                cout << "Error: Goal cannot exceed capacity of jug A." << endl;
            }
            if (i == 5)
            {
                cout << "Error: Goal cannot exceed capacity of jug B." << endl;
            }
            if (i == 6)
            {
                cout << "Error: Goal cannot exceed capacity of jug C." << endl;
            }
            return 1;
        }
    }
    if (!(nums[3] + nums[4] + nums[5] == nums[2]))
    {
        cout << "Error: Total gallons in goal state must be equal to the capacity of jug C." << endl;
        return 0;
    }

    //----------------------------------------------------------------------------------------------------
    // Do the BFS if there are no errors

    State found = breadthSearch(nums);

    if(found.a < 0){
        cout << "No solution.";
        return 1;
    }

    cout << "Initial state. (0, 0, " << nums[2] <<")" << endl;

    for (int i = 0; i < (int) found.directions.size(); i++) {
        cout << found.directions[i];
    }

    return 0;
}