302a1_from_liu.cpp

#include "algorithm.h"
#include <cstring> // memset
using namespace std;

/*************************** global variables *****************************/
#define MAX_POSSIBILITY 362880
enum Direction{LEFT, RIGHT, UP, DOWN};
bool VisitedList[MAX_POSSIBILITY];
bool ExpandedList[MAX_POSSIBILITY];
bool IsExistInQueue[MAX_POSSIBILITY];

enum pickPref{F_COST, G_COST, H_COST};
/*************************** function prototype ***************************/
void AddNextPuzzle(deque<Puzzle> &enqueue, Puzzle currentPuzzle,
                   Direction direction, heuristicFunction type);
void AddNextPuzzle(deque<Puzzle> &enqueue, Puzzle currentPuzzle, Direction direction);
unsigned long GetCantorIndex(string state);
deque<Puzzle>::iterator FindShotestPath(deque<Puzzle> &enqueue, pickPref di);
deque<Puzzle>::iterator FindShotestPath(deque<Puzzle> &enqueue);
deque<Puzzle>::iterator SearchEnque(deque<Puzzle> &enqueue, Puzzle puzzle);
void AddPuzzle(deque<Puzzle> &enqueue, Puzzle puzzle);
/**************************************************************************/
// require global boolean array "VisitedList"
void AddNextPuzzle(deque<Puzzle> &enqueue, Puzzle currentPuzzle,
                   Direction direction, heuristicFunction type){
    Puzzle *puzzleTemp = new Puzzle(currentPuzzle);
    bool canMove = false;
    switch(direction){
    case LEFT:
        canMove = currentPuzzle.canMoveLeft();
        puzzleTemp = puzzleTemp->moveLeft();
        break;
    case DOWN:
        canMove = currentPuzzle.canMoveDown();
        puzzleTemp = puzzleTemp->moveDown();
        break;
    case RIGHT:
        canMove = currentPuzzle.canMoveRight();
        puzzleTemp = puzzleTemp->moveRight();
        break;
    case UP:
        canMove = currentPuzzle.canMoveUp();
        puzzleTemp = puzzleTemp->moveUp();
        break;
    }

    // update F-cost and Heuristic
    if(type != NONE){
        puzzleTemp->updateHCost(type);
        puzzleTemp->updateFCost();
    }
    //int test = puzzleTemp->getFCost();

    unsigned long index = GetCantorIndex(puzzleTemp->toString());
    switch(type){
    case NONE:
        if(!VisitedList[index] && canMove){
            VisitedList[index] = true;
            enqueue.push_front(*puzzleTemp);
        }
        break;
    default:
        if(!ExpandedList[index] && canMove){
            if(IsExistInQueue[index]){
                deque<Puzzle>::iterator it;
                it = SearchEnque(enqueue, *puzzleTemp);
                if(it == enqueue.end()) return;

                Puzzle temp = *it;
                if(temp.getFCost() > puzzleTemp->getFCost()){
                    enqueue.erase(it);
                    enqueue.push_front(*puzzleTemp);
                }
            }
            enqueue.push_front(*puzzleTemp);
            IsExistInQueue[index] = true;
        }
        break;
    }
}

// Only can be used in breadth first, uniform cost
void AddNextPuzzle(deque<Puzzle> &enqueue, Puzzle currentPuzzle, Direction direction){
    Puzzle *puzzleTemp = new Puzzle(currentPuzzle);
    bool canMove = false;
    switch(direction){
    case LEFT:
        canMove = currentPuzzle.canMoveLeft();
        puzzleTemp = puzzleTemp->moveLeft();
        break;
    case DOWN:
        canMove = currentPuzzle.canMoveDown();
        puzzleTemp = puzzleTemp->moveDown();
        break;
    case RIGHT:
        canMove = currentPuzzle.canMoveRight();
        puzzleTemp = puzzleTemp->moveRight();
        break;
    case UP:
        canMove = currentPuzzle.canMoveUp();
        puzzleTemp = puzzleTemp->moveUp();
        break;
    }

    unsigned long index = GetCantorIndex(puzzleTemp->toString());
    if(!IsExistInQueue[index] && !ExpandedList[index] && canMove)
        AddPuzzle(enqueue, *puzzleTemp);

}

void AddPuzzle(deque<Puzzle> &enqueue, Puzzle puzzle){
    enqueue.push_back(puzzle);
    IsExistInQueue[GetCantorIndex(puzzle.toString())] = true;
}

unsigned long GetCantorIndex(string state){
    const int permSize = 9;
    unsigned long factory[9] = {0, 1, 2, 6, 24, 120,720, 5040, 40320};
    unsigned long result = 0;
    int counted, i, j;
    int val_i, val_j;
    for(i = 0; i < permSize; i++){
        counted = 0;
        val_i = state[i] - '0';
        for(j = i + 1; j < permSize; j++){
            val_j = state[j] - '0';
            if(val_i > val_j){
                counted++;
            }
        }
        result += counted * factory[permSize - i - 1];
    }
    return result;
}

deque<Puzzle>::iterator FindShotestPath(deque<Puzzle> &enqueue, pickPref di){
    deque<Puzzle>::iterator it = enqueue.begin(), shotCostItr;
    shotCostItr = it;
    int shotestPath = 0, currentPath = 0;
    Puzzle temp = *it;

    switch(di){
    case G_COST:
        shotestPath = temp.getPathLength();
        break;
    case H_COST:
        shotestPath = temp.getHCost();
        break;
    default:    // default: di = F_COST
        shotestPath = temp.getFCost();
        break;
    }

    while( it != enqueue.end()){
        temp = *it;
        if(di == G_COST){ currentPath = temp.getPathLength(); }
        else if(di == F_COST){ currentPath = temp.getFCost(); }
        else currentPath = temp.getHCost();

        if (shotestPath > currentPath){
            shotestPath = currentPath;
            shotCostItr = it;
        }
        it++;
    }
    return shotCostItr;
}

// Only can be used in breadth first, uniform cost
deque<Puzzle>::iterator FindShotestPath(deque<Puzzle> &enqueue){
    deque<Puzzle>::iterator it = enqueue.begin();
    return it;
}

deque<Puzzle>::iterator SearchEnque(deque<Puzzle> &enqueue, Puzzle puzzle){
    deque<Puzzle>::iterator it = enqueue.begin();
    while(it != enqueue.end()){
        Puzzle temp = *it;
        if(puzzle.puzzleMatch(temp)){
            return it;
        }
        it++;
    }
    return enqueue.end();
}
/***************************  algorithms **********************************/
///////////////////////////////////////////////////////////////////////////////////////////
//
// Search Algorithm:  Progressive Deepening Search with Visited List
//
////////////////////////////////////////////////////////////////////////////////////////////
string PDS_Visited_List(string const initialState, string const goalState,
                        int &numOfStateExpansions, int& maxQLength,
                        float &actualRunningTime, int ultimateMaxDepth){
    clock_t startTime;
	startTime = clock();

    string path = "";
    maxQLength = 0;
    memset(VisitedList, 0, MAX_POSSIBILITY * sizeof(bool));

    deque<Puzzle> enqueue;
    Puzzle *firstNode = new Puzzle(initialState, goalState);
    enqueue.push_front(*firstNode);
    //cout << "first index: " << GetCantorIndex(firstNode->toString()) << endl;
    VisitedList[GetCantorIndex(firstNode->toString())] = true;  // add first puzzle into visited list
    deque<Puzzle>::iterator itEnqueue;
    bool isGoal = false;
    while(!enqueue.empty()){
        itEnqueue = enqueue.begin();    // pick first node from Q
        Puzzle currentPuzzle = *itEnqueue;

        path = currentPuzzle.getPath();
        if(currentPuzzle.goalMatch()){
            isGoal = true;
            break;
        }
        enqueue.erase(itEnqueue);   // delete expanded node from Q
        //cout<< currentPuzzle.toString() << endl;
        if(currentPuzzle.getDepth() >=ultimateMaxDepth){
            continue;
        }
        heuristicFunction type = NONE;
        AddNextPuzzle(enqueue, currentPuzzle, LEFT, type);
        AddNextPuzzle(enqueue, currentPuzzle, DOWN, type);
        AddNextPuzzle(enqueue, currentPuzzle, RIGHT, type);
        AddNextPuzzle(enqueue, currentPuzzle, UP, type);

        if((int)enqueue.size() >= maxQLength) {maxQLength = enqueue.size();}
        numOfStateExpansions++;
    }
    if(!isGoal) cout << "This search algorithm cannot find solution." << endl;
    //display the time
    actualRunningTime = ((float)(clock() - startTime)/CLOCKS_PER_SEC);

	return path;
}

///////////////////////////////////////////////////////////////////////////////////////////
//
// Search Algorithm:  t Search using the Strict ExpandedList
//
////////////////////////////////////////////////////////////////////////////////////////////
string bestFirstSearch_Visited_List(string const initialState, string const goalState,
                                    int &numOfStateExpansions, int& maxQLength,
                                    float &actualRunningTime){
    clock_t startTime;
	startTime = clock();

    string path = "";
    maxQLength = 0;
    memset(VisitedList, 0, MAX_POSSIBILITY * sizeof(bool));

    deque<Puzzle> enqueue;
    Puzzle *firstNode = new Puzzle(initialState, goalState);
    firstNode->updateHCost(MANHATTANDISTANCE);
    enqueue.push_front(*firstNode);
    //cout << "first index: " << GetCantorIndex(firstNode->toString()) << endl;
    VisitedList[GetCantorIndex(firstNode->toString())] = true;  // add first puzzle into visited list
    deque<Puzzle>::iterator itEnqueue;
    bool isGoal = false;
    while(!enqueue.empty()){
        itEnqueue = FindShotestPath(enqueue,H_COST);
        Puzzle currentPuzzle = *itEnqueue;

        path = currentPuzzle.getPath();
        if(currentPuzzle.goalMatch()){
            isGoal = true;
            break;
        }
        enqueue.erase(itEnqueue);   // delete expanded node from Q
        //cout<< currentPuzzle.toString() << endl;

        heuristicFunction type = MANHATTANDISTANCE;
        AddNextPuzzle(enqueue, currentPuzzle, LEFT, type);
        AddNextPuzzle(enqueue, currentPuzzle, DOWN, type);
        AddNextPuzzle(enqueue, currentPuzzle, RIGHT, type);
        AddNextPuzzle(enqueue, currentPuzzle, UP, type);

        if((int)enqueue.size() >= maxQLength) {maxQLength = enqueue.size();}
        numOfStateExpansions++;
    }
    if(!isGoal) cout << "This search algorithm cannot find solution." << endl;
    //display the time
    actualRunningTime = ((float)(clock() - startTime)/CLOCKS_PER_SEC);

	return path;
}

///////////////////////////////////////////////////////////////////////////////////////////
//
// Search Algorithm:  Uniform Cost Search using the Strict ExpandedList
//
////////////////////////////////////////////////////////////////////////////////////////////
string uniformCost_Exp_List(string const initialState, string const goalState,
                            int &numOfStateExpansions, int &maxQLength,
                            float &actualRunningTime){
    clock_t startTime;
	startTime = clock();

    string path = "";
    maxQLength = 0;
    memset(ExpandedList, 0, MAX_POSSIBILITY * sizeof(bool));
    memset(IsExistInQueue, 0, MAX_POSSIBILITY * sizeof(bool));

    deque<Puzzle> enqueue;
    Puzzle *firstNode = new Puzzle(initialState, goalState);
    AddPuzzle(enqueue, *firstNode);

    deque<Puzzle>::iterator itEnqueue;
    bool isGoal = false;
    while(!enqueue.empty()){
        itEnqueue = FindShotestPath(enqueue);
        Puzzle currentPuzzle = *itEnqueue;

        path = currentPuzzle.getPath();
        if(currentPuzzle.goalMatch()){
            isGoal = true;
            break;
        }
        enqueue.erase(itEnqueue);   // delete expanded node from Q
        //IsExistInQueue[GetCantorIndex(currentPuzzle.toString())] = false;

        //cout<< currentPuzzle.toString() << endl;
        unsigned long index = GetCantorIndex(currentPuzzle.toString());
        if(!ExpandedList[index]){
            ExpandedList[index]=true;
            AddNextPuzzle(enqueue, currentPuzzle, LEFT);
            AddNextPuzzle(enqueue, currentPuzzle, DOWN);
            AddNextPuzzle(enqueue, currentPuzzle, RIGHT);
            AddNextPuzzle(enqueue, currentPuzzle, UP);
        }

        if((int)enqueue.size() >= maxQLength) {maxQLength = enqueue.size();}
        numOfStateExpansions++;
    }
    if(!isGoal) cout << "This search algorithm cannot find solution." << endl;
    //display the time
    actualRunningTime = ((float)(clock() - startTime)/CLOCKS_PER_SEC);

	return path;
}

///////////////////////////////////////////////////////////////////////////////////////////
//
// Search Algorithm:  A* without the ExpandedList
//
////////////////////////////////////////////////////////////////////////////////////////////
string aStar(string const initialState, string const goalState,
             int &numOfStateExpansions, int &maxQLength,
             float &actualRunningTime, heuristicFunction heuristic){
    clock_t startTime;
	startTime = clock();

    string path = "";
    maxQLength = 0;
    memset(IsExistInQueue, 0, MAX_POSSIBILITY * sizeof(bool));

    deque<Puzzle> enqueue;
    Puzzle *firstNode = new Puzzle(initialState, goalState);
    firstNode->updateHCost(heuristic);
    firstNode->updateFCost();
    enqueue.push_front(*firstNode);

    deque<Puzzle>::iterator itEnqueue;
    bool isGoal = false;
    while(!enqueue.empty()){

        itEnqueue = FindShotestPath(enqueue, F_COST);
        Puzzle currentPuzzle = *itEnqueue;

        path = currentPuzzle.getPath();
        if(currentPuzzle.goalMatch()){
            isGoal = true;
            break;
        }
        enqueue.erase(itEnqueue);   // delete expanded node from Q

        //cout<< currentPuzzle.toString() << endl;
        unsigned long index = GetCantorIndex(currentPuzzle.toString());

        AddNextPuzzle(enqueue, currentPuzzle, LEFT, heuristic);
        AddNextPuzzle(enqueue, currentPuzzle, DOWN, heuristic);
        AddNextPuzzle(enqueue, currentPuzzle, RIGHT, heuristic);
        AddNextPuzzle(enqueue, currentPuzzle, UP, heuristic);

        if((int)enqueue.size() >= maxQLength) {maxQLength = enqueue.size();}
        numOfStateExpansions++;
   }
   if(!isGoal) cout << "This search algorithm cannot find solution." << endl;

   //display the time
   actualRunningTime = ((float)(clock() - startTime)/CLOCKS_PER_SEC);

   return path;
}

///////////////////////////////////////////////////////////////////////////////////////////
//
// Search Algorithm:  A* using the Strict ExpandedList
//
////////////////////////////////////////////////////////////////////////////////////////////
string aStar_Exp_List(string const initialState, string const goalState,
                      int &numOfStateExpansions, int &maxQLength,
                      float &actualRunningTime, heuristicFunction heuristic){
    clock_t startTime;
	startTime = clock();

    string path = "";
    maxQLength = 0;
    memset(ExpandedList, 0, MAX_POSSIBILITY * sizeof(bool));
    memset(IsExistInQueue, 0, MAX_POSSIBILITY * sizeof(bool));

    deque<Puzzle> enqueue;
    Puzzle *firstNode = new Puzzle(initialState, goalState);
    firstNode->updateHCost(heuristic);
    firstNode->updateFCost();
    enqueue.push_front(*firstNode);
    IsExistInQueue[GetCantorIndex(firstNode->toString())] = true;

    deque<Puzzle>::iterator itEnqueue;
    bool isGoal = false;
    while(!enqueue.empty()){
        itEnqueue = FindShotestPath(enqueue, F_COST);
        Puzzle currentPuzzle = *itEnqueue;

        path = currentPuzzle.getPath();
        if(currentPuzzle.goalMatch()){
            isGoal = true;
            break;
        }
        enqueue.erase(itEnqueue);   // delete expanded node from Q
        IsExistInQueue[GetCantorIndex(currentPuzzle.toString())] = false;

        //cout<< currentPuzzle.toString() << endl;
        unsigned long index = GetCantorIndex(currentPuzzle.toString());
        if(ExpandedList[index]==false){
            ExpandedList[index]=true;

            AddNextPuzzle(enqueue, currentPuzzle, LEFT, heuristic);
            AddNextPuzzle(enqueue, currentPuzzle, DOWN, heuristic);
            AddNextPuzzle(enqueue, currentPuzzle, RIGHT, heuristic);
            AddNextPuzzle(enqueue, currentPuzzle, UP, heuristic);
        }

        if((int)enqueue.size() >= maxQLength) {maxQLength = enqueue.size();}
        numOfStateExpansions++;
    }
    if(!isGoal) cout << "This search algorithm cannot find solution." << endl;

    //display the time
    actualRunningTime = ((float)(clock() - startTime)/CLOCKS_PER_SEC);

	return path;
}