GameState Class Reference

Describes a single state in the 8-puzzle. More...

#include <GameState.hpp>

Collaboration diagram for GameState:

Public Member Functions
	GameState ()
	Default constructor, everything starts as 0 or NULL. More...
	GameState (string s)
	Creates a GameState from a string, where tile numbers are separated by spaces in a single line. More...
	GameState (const GameState &obj)
	Copy constructor of the class. More...
	GameState (GameState *previous, GameAction action)
	Creates a new state based on a given previous state and applying an action to it. More...
	~GameState ()
	Destructor of GameState. More...
bool	isValid (GameAction action)
	Checks whether an action is valid for this state. More...
bool	operator== (const GameState &other) const
	Checks whether two GameState objects are equal. More...
int	countInversions ()
	Counts the number of inversions in the puzzle. More...
bool	isSolvable ()
	Check if the state is solvable. More...
bool	operator< (const GameState &other) const
	Compares two GameState objects. More...
bool	operator!= (const GameState &other) const
	Inequality operator for GameState. More...
int	getDimension () const
string	to_string () const
	Returns a multi-line string representation of the 8-puzzle board state. More...
string	to_line_string () const
	Returns a single line string representation of the 8-puzzle board state. More...
int *	find (int value)
	Finds the position of a tile in the board. More...
void	setRepresentation (int **representation)
GameState *	getParent () const
int	getDepth () const

Private Member Functions
int *	toIntArray (string s)
	Turns a string representation of an 8-puzzle into an array. More...

Private Attributes
int **	representation
int	depth
int	dimension
GameState *	parent

Detailed Description

Describes a single state in the 8-puzzle.

Definition at line 18 of file GameState.hpp.

Constructor & Destructor Documentation

GameState() [1/4]

GameState::GameState ( )

inline

Default constructor, everything starts as 0 or NULL.

Definition at line 60 of file GameState.hpp.

              {
    depth = dimension = 0;
    representation = NULL;
    parent = NULL;
  }

Here is the caller graph for this function:

GameState() [2/4]

GameState::GameState ( string  s )

inlineexplicit

Creates a GameState from a string, where tile numbers are separated by spaces in a single line.

Parameters

s	string representation on an 8-puzzle state

Definition at line 68 of file GameState.hpp.

                               {
    depth = 0;
    parent = NULL;

    // converts string to int[]
    int *conversion = toIntArray(s);

    // calculates puzzle dimension from array size
    dimension = sizeof(conversion) / sizeof(conversion[0]) + 1;

    // searches for duplicate numbers inside the array
    for (int i = 0; i < dimension * dimension - 1; i ++) {
      for (int j = i + 1; j < dimension * dimension; j ++) {
        if (conversion[i] == conversion[j]) {
          cout << conversion[i] << conversion[j] << i << j;
          throw invalid_argument(s);
        }
      }
    }

    // initializes array of arrays to keep the 8-puzzle state
    representation = new int *[dimension];

    //iterates through rows and columns, adding the numbers converted from the input string
    int val = 0;
    for (int x = 0; x < dimension; x ++) {
      representation[x] = new int[dimension]; // initialize inner arrays

      for (int y = 0; y < dimension; y ++) {
        representation[x][y] = conversion[val ++];
      }
    }

    delete[] conversion;
  }

GameState() [3/4]

GameState::GameState ( const GameState &  obj )

inline

Copy constructor of the class.

Parameters

obj	object that will be copied

Definition at line 106 of file GameState.hpp.

                                  {
    dimension = obj.dimension;
    depth = obj.depth;

    representation = new int *[dimension];

    for (int x = 0; x < dimension; x ++) {
      representation[x] = new int[dimension];

      for (int y = 0; y < dimension; y ++) {
        representation[x][y] = obj.representation[x][y];
      }
    }

    parent = obj.parent;
  }

GameState() [4/4]

GameState::GameState ( GameState *  previous, GameAction  action  )

inline

Creates a new state based on a given previous state and applying an action to it.

Parameters

previous	the previous state
action	the action to be applied to the previous state

Definition at line 126 of file GameState.hpp.

                                                    {
    //dimension is the same, depth is one lower, parent is the state passed in the argument
    dimension = previous->dimension;
    depth = previous->depth + 1;
    parent = previous;
    representation = new int *[dimension];

    // first, copy the state
    for (int x = 0; x < dimension; x ++) {
      representation[x] = new int[dimension];

      for (int y = 0; y < dimension; y ++) {
        representation[x][y] = previous->representation[x][y];
      }
    }

    //find the 0
    int *pos_0 = find(0);
    int x = pos_0[0], y = pos_0[1];
    delete[] pos_0;
    int tmp = 0;

    // validate action
    if (action != RIGHT and action != LEFT and action != UP and action != DOWN)
      throw invalid_argument("No previous action to build the new GameState.");

    if (! isValid(action)) {
      throw invalid_argument("Invalid action for current game state.");
    }

    // move the 0 according to the given action
    // keep the value of the tile where the 0 is being move to in tmp
    switch (action) {
      case RIGHT:tmp = previous->representation[x + 1][y];
        representation[x + 1][y] = 0;
        break;

      case LEFT:tmp = previous->representation[x - 1][y];
        representation[x - 1][y] = 0;
        break;

      case UP:tmp = previous->representation[x][y - 1];
        representation[x][y - 1] = 0;
        break;

      case DOWN:tmp = previous->representation[x][y + 1];
        representation[x][y + 1] = 0;
        break;
    }

    //put the value in tmp where the 0 was
    representation[x][y] = tmp;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

~GameState()

GameState::~GameState ( )

inline

Destructor of GameState.

Definition at line 181 of file GameState.hpp.

               {
    // erase inner arrays
    // since the value of `dimension` is lost, calculate it here
    int dim = sizeof(representation[0]) / sizeof(representation[0][0]) + 1;
    for (int i = 0; i < dim; i ++)
      delete[] representation[i];

    //erase outer array
    delete[] representation;

    representation=NULL;
    parent = NULL;
    depth = dimension = 0;
  }

Member Function Documentation

countInversions()

int GameState::countInversions ( )

inline

Counts the number of inversions in the puzzle.

An inversion occurs whenever a number comes before a smaller number in the puzzle.

Returns

number of inversions in this states of the puzzle

Definition at line 233 of file GameState.hpp.

                        {
    int inv_count = 0;

    int rasterDimension = dimension * dimension;
    int *raster = new int[rasterDimension];

    int current = 0;
    for (int x = 0; x < dimension; x ++) {
      for (int y = 0; y < dimension; y ++) {
        raster[current ++] = representation[x][y];
      }
    }

    for (int i = 0; i < rasterDimension - 1; i ++)
      for (int j = i + 1; j < rasterDimension; j ++)
        if (raster[i] != 0 and raster[j] != 0 and raster[i] > raster[j])
          inv_count ++;

    delete[] raster;

    return inv_count;
  }

Here is the caller graph for this function:

find()

int* GameState::find ( int  value )

inline

Finds the position of a tile in the board.

Parameters

value

the value of the tile to look for

Returns

int array where [0] contains x position and [1] y position of the number

Definition at line 318 of file GameState.hpp.

                       {
    for (int x = 0; x < dimension; x ++) {
      for (int y = 0; y < dimension; y ++) {
        if (representation[x][y] == value) return new int[2]{x, y};
      }
    }

    throw invalid_argument("Inexistent number.");
  }

Here is the caller graph for this function:

getDepth()

int GameState::getDepth ( ) const

inline

Definition at line 339 of file GameState.hpp.

                       {
    return depth;
  }

Here is the caller graph for this function:

getDimension()

int GameState::getDimension ( ) const

inline

Definition at line 284 of file GameState.hpp.

                           {
    return dimension;
  }

Here is the caller graph for this function:

getParent()

GameState* GameState::getParent ( ) const

inline

Definition at line 335 of file GameState.hpp.

                               {
    return parent;
  }

isSolvable()

bool GameState::isSolvable ( )

inline

Check if the state is solvable.

Returns

a state is solvable if the number of inversions in it is even.

Definition at line 258 of file GameState.hpp.

                    {
    return countInversions() % 2 == 0;
  }

Here is the call graph for this function:

isValid()

bool GameState::isValid ( GameAction  action )

inline

Checks whether an action is valid for this state.

Actions are invalid if they'd move the 0 tile outside of the board.

Parameters

action

the action to be validated

Returns

true if the action can be applied in this state, otherwise false

Definition at line 200 of file GameState.hpp.

                                  {
    if (action != RIGHT and action != LEFT and action != UP and action != DOWN)
      return false;

    int *pos_0 = find(0);
    int x = pos_0[0], y = pos_0[1];

    delete[] pos_0;

    return ! (action == RIGHT and x == dimension - 1 ||
        action == LEFT and x == 0 ||
        action == UP and y == 0 ||
        action == DOWN and y == dimension - 1);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

operator!=()

bool GameState::operator!= ( const GameState &  other ) const

inline

Inequality operator for GameState.

This is the negation of the equality operator.

Parameters

other

The GameState to be compared to

Returns

false if equal, otherwise true

Definition at line 280 of file GameState.hpp.

                                                {
    return ! (*this == other);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

operator<()

bool GameState::operator< ( const GameState &  other ) const

inline

Compares two GameState objects.

Tile numbers are compared in order. If this[i,j] < other[i,j], this < other. This operator is useful in case objects need to be sorted inside a data structure, for example.

Parameters

other

The GameState to be compared to

Returns

true if this < other, otherwise false

Definition at line 266 of file GameState.hpp.

                                               {
    if (dimension != other.dimension) throw invalid_argument("Puzzles of different dimensions aren't comparable");

    for (int x = 0; x < dimension; x ++) {
      for (int y = 0; y < dimension; y ++) {
        if (representation[x][y] < other.representation[x][y]) return true;
      }
    }
    return false;
  }

Here is the caller graph for this function:

operator==()

bool GameState::operator== ( const GameState &  other ) const

inline

Checks whether two GameState objects are equal.

They are equal if they have the same board dimensions and the same values in the same positions of their board.

Parameters

other

The GameState to be compared to

Returns

true if equal, otherwise false

Definition at line 219 of file GameState.hpp.

                                                {
    if (dimension != other.dimension) return false;

    for (int x = 0; x < dimension; x ++) {
      for (int y = 0; y < dimension; y ++) {
        if (representation[x][y] != other.representation[x][y]) return false;
      }
    }
    return true;
  }

Here is the caller graph for this function:

setRepresentation()

void GameState::setRepresentation ( int **  representation )

inline

Definition at line 328 of file GameState.hpp.

                                               {
    this->representation = representation;

    //dimension must be recalculated
    dimension = sizeof(representation[0]) / sizeof(representation[0][0]) + 1;
  }

Here is the caller graph for this function:

to_line_string()

string GameState::to_line_string ( ) const

inline

Returns a single line string representation of the 8-puzzle board state.

Returns

single line string representation of the state

Definition at line 304 of file GameState.hpp.

                                {
    string tmp = "";

    for (int x = 0; x < dimension; x ++) {
      for (int y = 0; y < dimension; y ++) {
        tmp.append(std::to_string(representation[x][y])).append(" ");
      }
    }
    return tmp.erase(tmp.find_last_not_of(" \n\r\t") + 1);
  }

to_string()

string GameState::to_string ( ) const

inline

Returns a multi-line string representation of the 8-puzzle board state.

Returns

multi-line string representation of the state

Definition at line 290 of file GameState.hpp.

                           {
    string tmp = "";

    for (int x = 0; x < dimension; x ++) {
      for (int y = 0; y < dimension; y ++) {
        tmp.append(std::to_string(representation[x][y])).append(" ");
      }
      tmp.append("\n");
    }
    return tmp;
  }

toIntArray()

int* GameState::toIntArray ( string  s )

inlineprivate

Turns a string representation of an 8-puzzle into an array.

Parameters

s	string representation of an 8-puzzle

Returns

Pointer to an int array containing the state of the puzzle

Definition at line 28 of file GameState.hpp.

                            {

    //count spaces in string
    int spaces = 1;
    for (int i = 0; i < s.length(); i ++) {
      if (s[i] == ' ') spaces ++;
    }

    //create array
    int *ret = new int[spaces];

    int currentInt = 0;
    string intString = "";
    for (int i = 0; i < s.length(); i ++) {

      //glues it number together until a space is found
      if (s[i] != ' ') {
        intString += s[i];
      }

      //space means end of number, turn it into an int and put it in the return array
      if ((s[i] == ' ') || (i == s.length() - 1)) {
        ret[currentInt ++] = stoi(intString);
        intString = "";
      }
    }
    return ret;
  }

Field Documentation

depth

int GameState::depth

private

Definition at line 22 of file GameState.hpp.

dimension

int GameState::dimension

private

Definition at line 22 of file GameState.hpp.

parent

GameState* GameState::parent

private

Definition at line 23 of file GameState.hpp.

representation

int** GameState::representation

private

Definition at line 21 of file GameState.hpp.

---

The documentation for this class was generated from the following file:

• include/GameState.hpp