<file_sep>/*
Author: <NAME>
*/

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <time.h>
#include <cmath>
#include <queue>
#include <cstdio> //EXIT_SUCESS
using namespace std;
#include "State.h"
#include "Game.h"

int main()
{
    srand (time(NULL));

    cout <<"Hello This program is to get the numbers arranged in a certain order\n"
    //<< "Hello This Program is just uses four basic command u 'up', j 'down', h'left and k'right' \n"
         << " 1 2 3\n"
         << " 4 0 5\n"
         << " 6 7 8\n";
    Game g;
    g.startGame();

    return 0;
}
<file_sep>#ifndef GAME_H
#define GAME_H


const State idealState('w');

class Game
{
public:
    Game() {}
    virtual ~Game() {}
    void startGame();
protected:

private:
    void possibleStates(State);
    bool seqSearch(State);
    void choiceForMove(State&,char);
    void choiceForMove(State&);
    State posFunc(int,State,char);
    State cases(int,int,int,State);

    priority_queue<State> posStates;//Move it to private section
    vector<State> posStore;
};


void Game::startGame()
{
    State alpha;
    // posStates.push_back(alpha);
    int contain=0;
    char cho;
    cout << "Do you want to enter  the numbers yourself(y/n)\n"
    << "NOTE that by pressing n and enter the computer will randomly arrange the numbers\n";
    cin >>cho;
    if (cho=='y')
    alpha.getArr();
    cout << "Hello please input the way you wish to go"<< endl;
    cout << endl;
    posStore.push_back(alpha);
    posStore[0].printBoard();
    char inp;
    int stateNUM=0,moreThanOne;
    // int checc=0;
    State hol;
    for(int k=0; !(alpha==idealState); k++)
    {
        //cin >> inp ;
        alpha.printBoard();


        cout << "Whats Your Next Move ?\n"<<endl;
        cout << "N.B the manhattan distance is " <<alpha.ManCalc()<<endl;
        possibleStates(alpha);
        cout << "Your next possible moves are as follows"<<endl;
        State hol;
        stateNUM=1;
        moreThanOne=0;
        while (!posStates.empty())
        {
            hol=posStates.top();
            hol.printBoard();
            cout << "The manhattan distance for this State is "<< hol.ManCalc()<<"\nState Number is "<<stateNUM;
            cout << " The number of visited states are " << posStore.size() << endl;
            if (!seqSearch(hol)&&!(moreThanOne>=1))
            {
                cout << "\nState Number "<< stateNUM<<" is chosen for being effiecent"<<endl;
                alpha = hol;
                moreThanOne++;
            }
            cout << "------------------\n";
            posStates.pop();
            stateNUM++;

        }
        if (moreThanOne==0)
            alpha=hol;
        posStore.push_back(alpha);
        cout << "\n\n\n";
        while (!posStates.empty())
        {
            posStates.pop();
        }



    }

    while (!posStore.empty())
    {
        posStore.pop_back();
    }
}

void Game::possibleStates(State a)
{
    int ind1,ind2;
    State hold;
    State temp;
    hold=a;
    temp=a;
    a.searchNum(ind1,ind2,0);
    if (ind1>0 && ind2>0)
    {
        choiceForMove(hold,'u');
        posStates.push(hold);
        hold=temp;
        choiceForMove(hold,'h');
        posStates.push(hold);
        hold=temp;
        if (ind1==1&&ind2==1)
        {
            choiceForMove(hold,'j');
            posStates.push(hold);
            hold=temp;
            choiceForMove(hold,'k');
            posStates.push(hold);
            hold=temp;
        }
        else if (ind1<2)
        {
            choiceForMove(hold,'j');
            posStates.push(hold);
            hold=temp;
        }
        else if (ind2<2)
        {
            choiceForMove(hold,'k');
            posStates.push(hold);
            hold=temp;
        }

    }
    else if (ind1 < 2 && ind2 < 2)
    {
        choiceForMove(hold,'j');
        posStates.push(hold);
        hold=temp;
        choiceForMove(hold,'k');
        posStates.push(hold);
        hold=temp;
        if (ind1>0)
        {
            choiceForMove(hold,'u');
            posStates.push(hold);
            hold=temp;
        }
        else if (ind2>0)
        {
            choiceForMove(hold,'h');
            posStates.push(hold);
            hold=temp;
        }
    }
    else if (ind1==2 && ind2==0)
    {
        choiceForMove(hold,'u');
        posStates.push(hold);
        hold=temp;
        choiceForMove(hold,'k');
        posStates.push(hold);
        hold=temp;
    }
    else if (ind1==0 && ind2==2)
    {
        choiceForMove(hold,'j');
        posStates.push(hold);
        hold=temp;
        choiceForMove(hold,'h');
        posStates.push(hold);
        hold=temp;
    }
}


void Game::choiceForMove(State &a,char input)
{
    int x=0,y=0;
    a.searchNum(x,y,0);
    if (x>0 && input =='u')
    {
        swap(a.stateArr[x-1][y],a.stateArr[x][y]);
    }
    else if (x<2 && input == 'j')
    {
        swap(a.stateArr[x+1][y],a.stateArr[x][y]);
    }
    else if (y>0 && input == 'h')
    {
        swap(a.stateArr[x][y-1],a.stateArr[x][y]);
    }
    else if(y<2 && input == 'k')
    {
        swap(a.stateArr[x][y+1],a.stateArr[x][y]);
    }
    else if (input=='c')
    {
        possibleStates(a);
        a=posStates.top();
        while (!posStates.empty())
        {
            posStates.pop();
        }
    }
    else
        cout << "Please input a correct move"<<endl;
}
void Game::choiceForMove(State &a)
{
    int x=0,y=0;
    a.searchNum(x,y,0);
    if (x>0)
    {
        swap(a.stateArr[x-1][y],a.stateArr[x][y]);
    }
    else if (x<2)
    {
        swap(a.stateArr[x+1][y],a.stateArr[x][y]);
    }
    else if (y>0)
    {
        swap(a.stateArr[x][y-1],a.stateArr[x][y]);
    }
    else if(y<2)
    {
        swap(a.stateArr[x][y+1],a.stateArr[x][y]);
    }
    else
        cout << "Please input a correct move"<<endl;
}

bool Game::seqSearch(State item)
{

    for ( vector <State> :: iterator i = posStore.begin(); i != posStore.end(); ++i)
    {
        if (item==*i)
            return true;
    }

    return false;
};

#endif // GAME_H
<file_sep># Assignment-1-Fin
DSA

This program is just a 3 x 3 number game where you don't play at all. It's only purpose it to randomly arrange numbers from 0-8 into that 3 x 3
format to then change systematically change the numbers step by step to the desired arrangement by manhattans distance.
<file_sep>#ifndef STATE_H
#define STATE_H
#include <iostream>
#include <vector>
#include <stdlib.h>     /* srand, rand */
#include <time.h>
using namespace std;
const int listSize=9;
class State
{
public:
    State()
    {
        vector <int> numbComb;//Consider to move it to some function
        for (int i = 0 ; i < listSize ; i ++)
        {
            numbComb.push_back(i);

        }

        int randIndex,holder,begining;
        int randCount=0;
        for (int i = 0 ; i < listSize ; i ++)
        {
            randIndex=rand()%listSize;
            randCount++;
            // cout << "random index " << randIndex <<endl;
            holder=numbComb[randIndex];
            numbComb.erase(numbComb.begin()+randIndex);
            numbComb.insert(numbComb.begin()+1,holder);

            begining=numbComb[0];

            numbComb.erase(numbComb.begin());
            numbComb.insert(numbComb.begin()+randIndex,begining);

        }

        for (int i = 0  ; i < 3 ; i++)
        {
            for (int j = 0 ; j < 3 ; j++)
            {
                stateArr[i][j]=numbComb[3*i+j];
            }
        }
        int h=1;
        for (int i = 0  ; i < 3 ; i++)
        {
            for (int j = 0 ; j < 3 ; j++)
            {
                goal[i][j]=h;
                h++;
            }
        }
        goal[2][2]=0;

    }
    State(char s)
    {
       int z=1;
        for (int i = 0  ; i < 3 ; i++)
        {
            for (int j = 0 ; j < 3 ; j++)
            {
                stateArr[i][j]=z;
                z++;
            }
        }
        stateArr[2][2]=0;
    }

    void printBoard()const;
    bool operator==(const State&) const;
    int ManCalc()const;
    void getArr();
    void searchNum(int&,int&,int)const;
    int stateArr[3][3];
    bool operator<(const State& s)const{
       return s.ManCalc()<ManCalc();
	}
    virtual ~State() {}

protected:

private:
    int goal[3][3];
    bool seqSearchForNum(int a);
    void searchNumGoal(int&,int&,int)const;
};

void State::getArr(){
    int num=0;
     for (int i = 0 ; i < 3 ; i ++)
        for (int j = 0 ; j < 3 ; j++)
            stateArr[i][j]=9;
    for (int i = 0 ; i < 3 ; i ++)
    for (int j = 0 ; j < 3 ;j++){
        do {
        cout << "Please input the array number, You are on number " << i*3+j<<endl;
        cin >> num;
        if (seqSearchForNum(num)){
            system("CLS");
            cout << "ERROR You inputed this number before please try again"<<endl;
        }
        }while(seqSearchForNum(num));
        stateArr[i][j]=num;
    }

}
bool State::operator==(const State& one)const
{
    for (int i = 0 ; i < 3 ; i ++)
        for (int j = 0 ; j < 3 ; j++)
            if (stateArr[i][j]!=one.stateArr[i][j])
                return false;

    return true;
}


void State::printBoard()const
{
    for (int i = 0 ; i < 3 ; i++)
    {
        for (int j = 0 ; j < 3 ; j ++)
            cout << stateArr[i][j]<< " ";
        cout << endl;
    }
}

void State::searchNum(int &x,int &y,int num)const
{
    for (int i = 0; i < 3 ; i ++)
        for (int j = 0 ; j < 3; j++)
        {
            if (stateArr[i][j]==num){
                    x=i;
                    y=j;
                }
        }


}

void State::searchNumGoal(int &x,int &y,int num)const
{
    for (int i = 0; i < 3 ; i ++)
        for (int j = 0 ; j < 3; j++)
        {
            if (goal[i][j]==num){
                    x=i;
                    y=j;
                }
        }


}

int State::ManCalc()const{
    int x2=0,y2=0,x1=0,y1=0;
    int manDis=0;
    for (int i = 0 ; i < 9 ; i++){
        searchNumGoal(x2,y2,i);
        searchNum(x1,y1,i);
        manDis+=(abs((x1-x2))+abs((y1-y2)));
    }
return manDis;
}
bool State::seqSearchForNum(int a)
{

    for ( int i = 0; i < 3; i++)
    {
        for (int j = 0 ; j < 3 ; j++)
        if (a==stateArr[i][j])
            return true;
    }

    return false;
};
#endif // STATE_H
