Overview: For this assignment we will be creating a game called Top Spin. The pr
ID: 3604248 • Letter: O
Question
Overview: For this assignment we will be creating a game called Top Spin. The premise of the game is fairly simple, you have a circular chain of numbers in some non sorted order.By preforming one of 3 moves you need to place the numbers into order
The three possible moves are:
1. Shifting the chain to the left
2. Shifting the chain to the right
3. Spinning the top
When we spin the top we are placing a subset of 4 numbers into the chain but in reverse order. When we shift left or right we only affect which numbers are available to spin. For example consider the following board
Your task: Your task for this assignment is to implement a c++ version of the TopSpin game.
TopSpin: I have provided a TopSpinADT, it looks like so
#pragma once
class TopSpinADT {
public:
// shifts the pieces 1 to the left
virtual void shiftLeft() = 0;
//shifts the pieces 1 to the right
virtual void shiftRight() = 0;
//reverses the pieces in the spin mechanism, IE if the 4 in the mechanism are
// 1,4,3,6 we will have 6,3,4,1
virtual void spin() = 0;
//checks to see if the puzzle is solved that is to say the pieces are in numerical order 1-20
virtual bool isSolved() = 0;
};
You must create a file TopSpin.h that inherits from TopSpinADT ie class TopSpin :public TopSpinADT. This TopSpin class will also need a destructor and a constructor. The constructor will have the following prototype TopSpin(int size, int spinSize);. Place all function implementations in TopSpin.cpp
The constructor will create a TopSpin object with size numbers(representing size of game) and a spin mechanism of spinSize( default is 4). The numbers should all be placed in order IE if it’s size 20 the numbers will be in the order 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20.
Numbers on the TopSpin board start at 1.
size must be at least 1 and spinSize must be equal or less than size you will check these. If either fails the constructor should use a default value (default value of size should be 20, spinSize should default to 4).
You must also overload the << operator so you can print the board. It will be declared like so std::ostream& operator<< (std::ostream& os, const TopSpin& ts)
Note this should be made outside the class declaration of TopSpin BUT in the TopSpin.h file. *** Google “c++ overload operator<<” to find examples (the MSDN site will really help) ***
Add the following function to TopSpin void random(unsigned int times); this function should perform a random number of leftShifts (from 1 to 19) followed by a spin. It should do both of these steps “times” iterations. It should print the board so that you can clearly see the spin mechanism for example if we had a default board of 20 and the first 4 were in the spin mechanism then the following would suffice
Circular Doubly Linked List: As some of you are probably already thinking this sounds like a job for a Circular Doubly Linked List! Indeed it is! It is your responsibility to implement a Circular Doubly Linked List(CDLL). Start with the LinkedList notes it will describe a LinkedList. It will then describe a Doubly Linked List. From there it should be easy enough to devise a Circular Doubly Linked List( described on pages 82-85 of the LinkedList notes). Your CDLL must be templated. You must use it to IMPLEMENT the TopSpin class. That is to say your TopSpin class will probably have a member variable that is similar to the following CDLL board; Since CDLL is a template, there will be no .cpp file, only a .h with the class declaration and function implementation! CDLL will declare a private class “Node” (see lecture notes) CDLL will have the following functions (no more) Constructor/Destructor (ensure dynamic memory is freed) void addData(Item d) //will add a new node to the end of the linked list with value d void incrementHead() //will advance head to next node void decrementHead() //will move head to previous node void swap(unsigned int src,unsigned int dst) //will swap the data in the 2 nodes (easier than swapping the nodes themselves) Item getData(unsigned int i) const //will return the data associated in the i-th node of the list
Main Program: Finally you are to create a small main method (in a main.cpp file) that does the following - Creates a TopSpin object of size 20 and spinSize 4. - Asks the user for a number of random moves to initialize the puzzle with. A random move is defined as shifting left randomly 1-19 pieces followed by a spin. (See random() function) - The user will then be repeatedly shown the puzzle ( using cout and our << operator) and given a menu which asks if they want to : shift, spin, or quit. (hint cin) You may number your user choices IE cout << "Please choose from the following options enter your choice by entering the corresponding number:" << endl << "1. Shift" << endl << "2. Spin" << endl << "3. Quit" << endl; If the user says Shift, prompt the user for the number of shifts, and the direction of the shift, then execute the requested shift. If the user says Spin, execute the spin. If the user says Quit, exit the loop and finish the program. If the user solves the puzzle, display the current game and the message "CONGRATULATIONS!" to the user, then exit the loop and finish the program.
What to hand in:
1. TopSpin.h, TopSpin.cpp
2. CDLL.h
3. main.cpp
Explanation / Answer
Below is your program
CDLL.h
#pragma once
#include <cstddef>
#include<iostream>
using namespace std;
template <class item>
class CircularDoublyLinkedList {
private:
struct Node {
Node * next; //Refers to next pointer
Node * previous; //Refers to previous pointer
item value;
Node(item item1, Node *head, Node *tail) : value(item1), next(head), previous(tail) {};
};
Node * head;
Node * tail;
unsigned int listSize; //size of linked list
public:
class iterator {
private:
Node * ptr;
public:
iterator() {}
iterator(Node * _ptr)
{
ptr = _ptr;
}
void operator++() //++ overload operator, traverses list to the right
{
ptr = ptr->next;
}
void operator--() //-- overload operator, traverses list to the left
{
ptr = ptr->previous;
}
item getValue()
{
return ptr->value;
}
void setValue(item val)
{
ptr->value = val;
}
bool operator!=(const iterator&b) //!= overload operatror, compares values
{
return ptr != b.ptr;
}
};
iterator begin()
{
return iterator(head);
}
iterator end()
{
return iterator(tail);
}
CircularDoublyLinkedList();
~CircularDoublyLinkedList();
void addHead(item item1);
bool isEmpty()const;
item removeHead();
item retrieveHead ()const;
item size() const;
void addTail(item item1);
item removeTail();
item retrieveTail()const;
void add(unsigned int n, item item1);
item replace(unsigned int n, item Item1);
item remove(unsigned int n);
item retrieve(unsigned int n)const;
};
template <class item>
CircularDoublyLinkedList<item>::CircularDoublyLinkedList() //head and tail point to node null, size is 0
{
head = NULL;
tail = NULL;
listSize = 0;
}
template<class item>
CircularDoublyLinkedList<item>::~CircularDoublyLinkedList() //Delete all nodes, use for loop to delete node one by one
{
Node * here = head, *nextNode;
for (int i=0;i<listSize;i++)
{
nextNode = here->next;
delete here;
here = nextNode;
}
}
template<class item>
void CircularDoublyLinkedList<item>::addHead(item item1) //if size=0, node=tail=null.
{
Node *node = new Node(item1, head, tail);
node->value = item1;
if (listSize == 0) {
head = node;
tail = node;
}
else
{
tail->next = node; //the tail points to the next node, being head
head->previous = node; //The new head points to the previous node, being tail
head = node;
}
listSize++;
}
template<class item>
bool CircularDoublyLinkedList<item>::isEmpty()const //Check if list is empty, return true value (1)
{
return (listSize == 0);
}
template<class item>
item CircularDoublyLinkedList<item>::removeHead()
{
Node * oldNode = head; //Set a temporary node to store the head value
item returnVal = head->value;
head = head->next; //Have head equal to the next node
tail->next = head; //Have tail point to the new head
if (head == NULL)
tail = NULL;
listSize--;
delete oldNode; //Temporary value storing head is deleted
return returnVal; //value is returned
}
template<class item>
item CircularDoublyLinkedList<item>::retrieveHead()const
{
return head->value; //Return head value
}
template<class item>
item CircularDoublyLinkedList<item>::size()const
{
return listSize; //size
}
template<class item>
void CircularDoublyLinkedList<item>::addTail(item item1)
{
if (isEmpty())
addHead(item1); //If the list is empty, adding a tail is identical to adding a head
else
{
Node *node = new Node(item1, head, tail); //Make new node with value that is going to be stored
node->value = item1; //New node value is equal to value inputted
tail->next = node; //new tail is added right of old tail, so old tail now points to new tail
head->previous = node; //head points back to new tail
tail = node; //set tail equal to the new node
listSize++;
}
}
template<class item>
item CircularDoublyLinkedList<item>::removeTail()
{
if (head == tail)
return removeHead(); //if size is 1, then the tail is the same as the head
Node * oldNode = tail; //Make new node set to old tail
item returnVal = tail->value;
tail = tail->previous; //Have tail be the node before the old tail
head->previous = tail; //Head poinst to new tail
if (oldNode->next != head)
oldNode = oldNode->next;
oldNode->next = head; //New node now points to the head
tail->next = head;
listSize--;
delete oldNode;
return returnVal;
}
template<class item>
item CircularDoublyLinkedList<item>::retrieveTail()const
{
return tail->value; //Value at tail node
}
template <class item>
void CircularDoublyLinkedList<item>::add(unsigned int n, item item1)
{
while (n<1 || n>size() + 1)
{
cout << "invalid position, n should be between 1 and size + 1, try again: ";
cin >> n;
}
if (n == 1)
addHead(item1); //If adding at position 1, same to adding head
else if (n == size() + 1)
addTail(item1); //If adding to last position, same as adding a tail
else
{
Node * here = head;
for (unsigned int k = 1;k < n - 1;k++)
here = here->next; //For loop has here point to the new node position
here->next = new Node(item1, here->next, tail); //New node is added in this position and size is incremented
listSize++;
}
}
template<class item>
item CircularDoublyLinkedList<item>::replace(unsigned int n, item Item)
{
item returnValue;
Node * here = head;
for (unsigned int k = 1;k < n;k++)
here = here->next; //For loop has here point to the node being replaced
returnValue = here->value; //Node value is stored
here->value = Item; //Node is replaced by new value
return returnValue;
}
template<class item>
item CircularDoublyLinkedList<item>::remove(unsigned int n)
{
if (n == 1)
return removeHead(); //Removing at position 1 same as removing head
else if (n == size())
{
return removeTail(); //Removing at last position same as removing tail
}
else {
Node * here = head;
Node * before;
for (unsigned int i = 1;i < n;i++)
here = here->next; //Here points to node being removed
Node * kill = here; //Kill represents the value being removed
item returnValue = kill->value; //Value is stored
here = kill->next;
before = kill->previous; //Here points to next and previous value of node being deleted so it doesn't point to null
delete kill;
listSize--;
before->next = here;
here->previous = before;
return returnValue;
}
}
template <class item>
item CircularDoublyLinkedList<item>::retrieve(unsigned int n)const
{
if (n == 1)
return retrieveHead(); //Retreieve at position 1 = retrieve head
else if (n == size())
return retrieveTail(); //Retrieve at last position = retrieve tail
else
{
Node * here = head;
for (unsigned int k = 1;k < n;k++)
here = here->next; //For loop points to value being retrieved and returns it
return here->value;
}
}
TopSpin.h
#pragma once
#include "CDLL.h"
#include <iostream>
class TopSpinADT {
public:
// shifts the pieces 1 to the left
virtual void shiftLeft() = 0;
//shifts the pieces 1 to the right
virtual void shiftRight() = 0;
//reverses the pieces in the spin mechanism, IE if the 4 in the mechanism are
// 1,4,3,6 we will have 6,3,4,1
virtual void spin() = 0;
//checks to see if the puzzle is solved that is to say the pieces are in numerical order 1-20
virtual bool isSolved() = 0;
};
class TopSpin : public TopSpinADT {
private:
int topSize, boardSize;
CircularDoublyLinkedList<int> board;
public:
CircularDoublyLinkedList<int>::iterator xd; //New iterator object "xd" is created
TopSpin(int topsize, int boardsize);
~TopSpin() {};
void shiftLeft(int a);
void shiftLeft() {};
void shiftRight() {};
void shiftRight(int a);
void spin();
bool isSolved();
int getBoard();
void setBoard(int a);
int getTop();
void setTop(int a);
friend std::ostream& operator<< (std::ostream &os, TopSpin &ts) {
//Overload print function using ostream, uses for loop to print out the top surrounded by a box, followed
//By the rest of the list
os << " ";
for (int i = 0; i < ts.topSize; i++, ++(ts.xd))
{
if ((ts.xd.getValue()) >= 10) //If the value is greater than 10, 3 dashes need to be printed to accomodate for
os << "___"; //the 2 digits as well as the space, otherwise only 2 dashes are printed
else
os << "__";
}
for (int i = 0;i < ts.topSize;i++)
{
--(ts.xd); //Since the for loop has the iterator traverse forward through the list, it must traverse backwards
} //an equal number of times
os << "_" << std::endl << "|";
for (int i = 0; i < ts.topSize; i++, ++(ts.xd))
{
if ((ts.xd.getValue()) >= 10)
os << " ";
else
os << " ";
}
for (int i = 0;i < ts.topSize;i++)
{
--(ts.xd);
}
os << " |" << std::endl << "| ";
for (int i = 0; i < ts.topSize; i++, ++(ts.xd))
{
os << ts.xd.getValue() << " "; //Traverses through the list, and prints out the values for the top, based off
} //the top size
os << "| ";
for (int i = ts.topSize; i < ts.boardSize; i++, ++(ts.xd))
{
os << ts.xd.getValue() << " "; //Traverses through the list and prints out the rest of the board values
}
os << std::endl << "|";
for (int i = 0; i < ts.topSize; i++, ++(ts.xd))
{
if ((ts.xd.getValue()) >= 10)
os << "___";
else
os << "__";
}
for (int i = 0;i < ts.topSize;i++)
{
--(ts.xd);
}
os << "_|";
return os;
}
};
TopSpin.cpp
#include "TopSpin.h"
TopSpin::TopSpin(int topsize, int boardsize)
{
this->topSize = topsize; //Allows values for top and board to be modified
this->boardSize = boardsize;
if (boardsize >1 && topsize < boardsize)
{
for (int i = 1;i <= boardsize;i++) //as long as parameter is met, numbers are added to list, otherwise default values of top size 4 and board size 20 are used
{
board.addTail(i);
}
}
else
{
topSize = 4;
boardSize = 20;
for (int i = 1; i <= boardSize;i++)
{
board.addTail(i);
}
}
xd = board.begin(); //Beginning of board is given value to iterator
}
void TopSpin::shiftLeft(int a) //Using an iterator to travere traverse through the circularlist to the left
{ //Based off inputted value to shift a set amount of times
for (int i = 0;i < a;i++)
{
++xd;
}
}
void TopSpin::shiftRight(int a)
{
for (int i = 0; i < a;i++)
{
--xd;
}
}
void TopSpin::spin()
{
CircularDoublyLinkedList<int>::iterator first, second;
first = xd; //Uses iterators to swap one half of the topsize and then the other half
second = xd;
int temp;
for (int i = 1; i < topSize;i++)
{
++second; //First for loop traverses the "Second" iterator to the end of the topsize, reversing the second half of the list
}
for (int i = 0; i < topSize / 2;i++) //Second for loop swaps the values of "first" and "second" for the other half of the list
{
temp = first.getValue(); //Temp stores the value of the first node, and then swaps it with the next node
first.setValue(second.getValue());
second.setValue(temp);
++first;
--second;
}
}
//Uses a while loop to stop new iterator when you get to 1, since list is circular, so that 1234=4123=3412=2341
bool TopSpin::isSolved() //iterator traverses through list and compares each value to the index
{ //To check if the values match, returns true if all values match otherwise returns false
CircularDoublyLinkedList<int>::iterator xp = xd;
bool win;
while (xp.getValue() != 1)
++xp;
for (int i = 1;i <= boardSize;i++)
{
if (i == xp.getValue())
{
win = true;
}
else
{
win = false;
break;
}
++xp;
}
if (win == true)
{
return true;
}
else
{
return false;
}
}
int TopSpin::getBoard()
{
return boardSize;
}
void TopSpin::setBoard(int a)
{
boardSize = a;
}
int TopSpin::getTop()
{
return topSize;
}
void TopSpin::setTop(int a)
{
topSize = a;
}
main.cpp
#include "TopSpin.h"
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
int main() {
int numMoves = 0; //numMoves is used to shuffle the puzzle
int boardSize, topSize;
cout << "Enter board size and top size, make sure board size is greater than the top size Board size: ";
cin >> boardSize;
cout << "Top size: ";
cin >> topSize;
TopSpin a(topSize, boardSize); //New object a is created based off the user inputted parameters
cout << "Enter number of moves to initalize board with: ";
cin >> numMoves;
srand(time(NULL));
for (int i = 0; i < numMoves; ++i)
{
int numShifts = (rand() %19) + 1; //Randomly generates list based off shifts and spins
for (int j = 0; j < numShifts; ++j)
{
a.shiftLeft(j);
}
a.spin();
}
while (a.isSolved()==0)
{
cout << endl << a << endl << endl;
int n;
cout << "PLease choose from the following options, enter your choice by entereing the corresponding number: " << endl;
cout << "1. Shift 2. Spin 3. Quit ";
cin >> n;
switch (n) {
case 1:
int x, y;
cout << " Shift left or right: 1. Left 2. Right ";
cin >> x;
cout << " How many times: ";
cin >> y;
if (x == 1)
{
a.shiftLeft(y); //Shift number of y times
}
else
{
a.shiftRight(y);
}
break;
case 2:
a.spin();
break;
case 3:
return 0;
break;
}
if (a.isSolved()) //If the puzzle is solved, exits from loop
break;
}
cout << endl << a << endl;
if (a.isSolved() == 1)
cout << " CONGRATULATIONS! ";
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.