****MUST USE CODE PROVIDED****
*****MUST USE THE CODE PROVIDED****
Assignment 1: 15 Puzzle 1 2 3 5 6 7 9 10 11 12 13 15 14 Description For this assignment, you will implement a game board in which the game 15 puzzle can be played. The following link allows you to get an idea of how the game is played http://lorecioni.github.io/fifteen-puzzle game/. The idea of the game is you have a 4 x 4 grid with 15 tiles and one blank spot. Each tile is labeled with a number between 1 and 15. The a tile to the left, above, the right, and below can be moved to fill the gap which then creates a new gap based on which tile was moved. The goal is to get the tiles arranged from 1 - 15, such that the first row contains tiles 1-4, the second row contains tiles 5- 8, the third row contains tiles 9-12, and the last row contains tiles 13-15 and the bottom right spot contains the gap. Of course we could use a a 2D array to implement a grid (or board), but to make things a bit more interesting we will use an array of linked lists to implement a 2D grid. Since it is a 15 puzzle, we will have an array of 4 linked lists and each linked list will have 4 nodes, each node will be labelled 0 - 15, where the number 0 represents the gap in the puzzle. The following header file must be implemented. template
class LL { struct node { Type item; node * next; node * prev; }; public: class iterator { public: friend class LL; iterator: iterator (node*); Type operator*(); iterator operator++(int); iterator operator --(int); bool operator==(const iterator& const; bool operator !=(const iterator& const; I private: node * currenti LLO; LL (const LL&); const LL& operator=(const LL&); -LLO; iterator begin() const; iterator end() const; void headRemove(); void tail Remove ; void removeNode (const iterator&); bool isEmpty() const; void head Insert(const Type&); void tailInsert (const Type&); void update (const iterator&, const Type); private: node * head; node * tail; }; Each member of the iterator class contains/implements the following: node * current - a points to a node in the linked list LL::iterator::iterator() - default constructor that sets current to NULL LL::iterator::iterator (node * pointer) - constructor that assigns current with pointer Type LL::iterator::operator*() - returns the item field of the node that current points to typename LL::iterator LL::iterator::operator++(int) - moves the iterator ob- ject over to the next node in the linked list, i.e. sets current pointer over to the next node typename LL::iterator LL::iterator::operator--(int) - moves the iterator ob- ject over to the previous node in the linked list, i.e. sets current pointer over to the previous node bool LL::iterator::operator==(const iterator& rhs) const - returns true if #this it- erator points to the same node as the rhs object, returns false otherwise bool LL::iterator::operator!=(const iterator& rhs) const - returns false if this it- erator points to the same node as the rhs object, returns true otherwise For the LL class, you are implementing a doubly linked list, element of the list is of type struct node where each node contains some data in its item field and contains a pointer next to the node to the right and a pointer prev that points to the node to the left, the rest of the class contains/implements the following: node * head - pointer that points to the beginning of the linked list node * tail - pointer that points to the end of the linked list LL::LL() - default constructor that assigns NULL to both head and tail LL::LL(const Ll& copy) - copy constructor, performs a deep copy of the copy object to the *this object const LL& LL::operator=(const LL& rhs) - assignment operator, performs a deep copy of the rhs object into the *this object (aka the left hand side object) LL: : -LL) - destructor, deallocates the linked list . typename LL::iterator LL::begin() const - returns an iterator object whose current pointer is assigned with the address in the head pointer typename LL::iterator LL::end() const - returns an iterator object whose current pointer is assigned with the address in the tail pointer void LL: : removeNode (const iterator& it) - removes the node from the linked list that the iterator that is passed into the function is pointing to void LL::headRemove() - removes the front node void LL::tailRemove () - removes the end node bool LL:: isEmpty() const - returns true if the list is empty and returns false if the list is not empty void LL: :headInsert (const Type& element) - inserts a new node to the front of the linked list void LL::tailInsert(const Type& element) - inserts a new node to the end of the linked list void LL:: update(const LL::iterator& it, const Type& element) - assigns the item field of the node that the iterator object points to with the element passed into the function Contents of main 1. Ask the user for an input file, repeat this step as long as an invalid file is given 2. Once a valid file is given, read the contents of the file and build the linked list, the file contains 4 rows where each row contains 4 numbers separated by a space and each line is terminated with an end of line character 3. Output the puzzle (refer to the sample output for formatting) 4. Ask the user to make a move L for left, R for right, U for up, D for down, or Q for quit (the input will be a single character and your program should be case insensitive), repeat this step if invalid input given 5. If Q was read, quit the program 6. If L was read, find where the gap resides in the structure (the node that contains 0), and exchange its value with the node on the right (so we are moving the node to the right of the gap to the left), if the gap is on the rightmost position in the row then do nothing 7. If R was read, find where the gap resides in the structure (the node that contains 0), and exchange its value with the node on the left (so we are moving the node to the left of the gap to the right), if the gap is on the leftmost position in the row then do nothing 8. If U was read, find where the gap resides in the structure (the node that contains 0), and exchange its value with the node below (so we are moving the node below the gap up a level), if the gap is on the bottom row then do nothing 9. If D was read, find where the gap resides in the structure (the node that contains 0), and exchange its value with the node above (so we are moving the node above the gap down a level), if the gap is on the top row then do nothing 10. Output the puzzle after making a move 11. If the game is not over, i.e. user didn't complete the puzzle go back to step 4 12. If the game is over, output that the user won ask them if they wish to continue, they must enter Y or N (case insensitive), repeat this step if Y or N is not entered Specifications Comment your code and your functions No global variables Make sure your program is memory leak free Sample Run A test input file is given that you can use linux redirection, this leads to a winning configuration that is shown in the second run $ g++ main.cpp $./a.out Enter puzzle file: 15 puzzle.txt Enter puzzle file: board.txt Enter puzzle file: scrambled.txt 7 5 11 14 4 1 3 10 8 12 9 2 13 6 15 Please make your choice, (L) eft, (R)ight, (Up, (D) own, (Q) uit: u 8 7 5 11 14 4 1 3 10 15 2 13 12 9 6 Please make your choice, (L) eft, (R)ight, (Up, (D) own, (Quit: r 1 5 11 14 4 8 3 12 9 7 2 13 6 10 15 Please make your choice, (L) eft, (R)ight, (u)p, (D) own, (Quit: r 5 1 11 8 3 12 9 7 2 13 14 4 10 15 6 Assignment 1: 15 Puzzle 1 2 3 5 6 7 9 10 11 12 13 15 14 Description For this assignment, you will implement a game board in which the game 15 puzzle can be played. The following link allows you to get an idea of how the game is played http://lorecioni.github.io/fifteen-puzzle game/. The idea of the game is you have a 4 x 4 grid with 15 tiles and one blank spot. Each tile is labeled with a number between 1 and 15. The a tile to the left, above, the right, and below can be moved to fill the gap which then creates a new gap based on which tile was moved. The goal is to get the tiles arranged from 1 - 15, such that the first row contains tiles 1-4, the second row contains tiles 5- 8, the third row contains tiles 9-12, and the last row contains tiles 13-15 and the bottom right spot contains the gap. Of course we could use a a 2D array to implement a grid (or board), but to make things a bit more interesting we will use an array of linked lists to implement a 2D grid. Since it is a 15 puzzle, we will have an array of 4 linked lists and each linked list will have 4 nodes, each node will be labelled 0 - 15, where the number 0 represents the gap in the puzzle. The following header file must be implemented. template class LL { struct node { Type item; node * next; node * prev; }; public: class iterator { public: friend class LL; iterator: iterator (node*); Type operator*(); iterator operator++(int); iterator operator --(int); bool operator==(const iterator& const; bool operator !=(const iterator& const; I private: node * currenti LLO; LL (const LL&); const LL& operator=(const LL&); -LLO; iterator begin() const; iterator end() const; void headRemove(); void tail Remove ; void removeNode (const iterator&); bool isEmpty() const; void head Insert(const Type&); void tailInsert (const Type&); void update (const iterator&, const Type); private: node * head; node * tail; }; Each member of the iterator class contains/implements the following: node * current - a points to a node in the linked list LL::iterator::iterator() - default constructor that sets current to NULL LL::iterator::iterator (node * pointer) - constructor that assigns current with pointer Type LL::iterator::operator*() - returns the item field of the node that current points to typename LL::iterator LL::iterator::operator++(int) - moves the iterator ob- ject over to the next node in the linked list, i.e. sets current pointer over to the next node typename LL::iterator LL::iterator::operator--(int) - moves the iterator ob- ject over to the previous node in the linked list, i.e. sets current pointer over to the previous node bool LL::iterator::operator==(const iterator& rhs) const - returns true if #this it- erator points to the same node as the rhs object, returns false otherwise bool LL::iterator::operator!=(const iterator& rhs) const - returns false if this it- erator points to the same node as the rhs object, returns true otherwise For the LL class, you are implementing a doubly linked list, element of the list is of type struct node where each node contains some data in its item field and contains a pointer next to the node to the right and a pointer prev that points to the node to the left, the rest of the class contains/implements the following: node * head - pointer that points to the beginning of the linked list node * tail - pointer that points to the end of the linked list LL::LL() - default constructor that assigns NULL to both head and tail LL::LL(const Ll& copy) - copy constructor, performs a deep copy of the copy object to the *this object const LL& LL::operator=(const LL& rhs) - assignment operator, performs a deep copy of the rhs object into the *this object (aka the left hand side object) LL: : -LL) - destructor, deallocates the linked list . typename LL::iterator LL::begin() const - returns an iterator object whose current pointer is assigned with the address in the head pointer typename LL::iterator LL::end() const - returns an iterator object whose current pointer is assigned with the address in the tail pointer void LL: : removeNode (const iterator& it) - removes the node from the linked list that the iterator that is passed into the function is pointing to void LL::headRemove() - removes the front node void LL::tailRemove () - removes the end node bool LL:: isEmpty() const - returns true if the list is empty and returns false if the list is not empty void LL: :headInsert (const Type& element) - inserts a new node to the front of the linked list void LL::tailInsert(const Type& element) - inserts a new node to the end of the linked list void LL:: update(const LL::iterator& it, const Type& element) - assigns the item field of the node that the iterator object points to with the element passed into the function Contents of main 1. Ask the user for an input file, repeat this step as long as an invalid file is given 2. Once a valid file is given, read the contents of the file and build the linked list, the file contains 4 rows where each row contains 4 numbers separated by a space and each line is terminated with an end of line character 3. Output the puzzle (refer to the sample output for formatting) 4. Ask the user to make a move L for left, R for right, U for up, D for down, or Q for quit (the input will be a single character and your program should be case insensitive), repeat this step if invalid input given 5. If Q was read, quit the program 6. If L was read, find where the gap resides in the structure (the node that contains 0), and exchange its value with the node on the right (so we are moving the node to the right of the gap to the left), if the gap is on the rightmost position in the row then do nothing 7. If R was read, find where the gap resides in the structure (the node that contains 0), and exchange its value with the node on the left (so we are moving the node to the left of the gap to the right), if the gap is on the leftmost position in the row then do nothing 8. If U was read, find where the gap resides in the structure (the node that contains 0), and exchange its value with the node below (so we are moving the node below the gap up a level), if the gap is on the bottom row then do nothing 9. If D was read, find where the gap resides in the structure (the node that contains 0), and exchange its value with the node above (so we are moving the node above the gap down a level), if the gap is on the top row then do nothing 10. Output the puzzle after making a move 11. If the game is not over, i.e. user didn't complete the puzzle go back to step 4 12. If the game is over, output that the user won ask them if they wish to continue, they must enter Y or N (case insensitive), repeat this step if Y or N is not entered Specifications Comment your code and your functions No global variables Make sure your program is memory leak free Sample Run A test input file is given that you can use linux redirection, this leads to a winning configuration that is shown in the second run $ g++ main.cpp $./a.out Enter puzzle file: 15 puzzle.txt Enter puzzle file: board.txt Enter puzzle file: scrambled.txt 7 5 11 14 4 1 3 10 8 12 9 2 13 6 15 Please make your choice, (L) eft, (R)ight, (Up, (D) own, (Q) uit: u 8 7 5 11 14 4 1 3 10 15 2 13 12 9 6 Please make your choice, (L) eft, (R)ight, (Up, (D) own, (Quit: r 1 5 11 14 4 8 3 12 9 7 2 13 6 10 15 Please make your choice, (L) eft, (R)ight, (u)p, (D) own, (Quit: r 5 1 11 8 3 12 9 7 2 13 14 4 10 15 6
