CS 1037 Assignment 2

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

We can either shift the chain left or right (changing the 4 at the top that can be reversed) or we can turn the top over reversing the numbers at the top. Here is a board if we shifted 2 places to the right

although my paint drawings are quite poor .

If we were then to spin the top we would get something like so

See the following youtube video to see what the game looks like when held and how to play.

https://www.youtube.com/watch?v=6tJZ6dE5Dmw

The following pdf describes some of the math behind the game http://myweb.lmu.edu/cbennett/Math331/TOPSPIN1.PDF

Here is a Downloadable(I believe windows only) version of the game( although theirs uses letters) http://www.zen73904.zen.co.uk/topspin.html

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 its 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

|-------------|

| 1 2 3 4 | 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

|-------------|

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

* Do NOT zip your files, and do not submit any extra files (you will lose marks)!

You will be marked on functionality, adherence to instructions, and good programming style (whitespace, meaningful variable names, consistency and comments).

Code similarities are both violations of Academic Dishonesty for those sharing their code as for those using other's code. As was explained in class, never use or share code! If you wish to help another student, explain concepts in English, draw diagrams, or refer the student to specific reference material.

Similarity detection software will be used on all assignments. Any students who achieve a high score for improbable code similarities will receive a mark of 0. In addition, further Academic Dishonesty reporting may be performed.