Reference no: EM132586611

Lab : Circle Markers Goals

Practice working with a C++ list

Explore the trade-offs between working with linked list (list) vs array-based (vector) structures

Overview

For this lab, we are going to use C++'s list class (which encapsulates a doubly-linked list data structure) to solve a very peculiar game, the rules for which are below. We've provided some starter code to let you focus on the data structure-y aspects of the problem.
The Game

This game, which can be played by an arbitrary number of players, involves the placement and removal of a markers, of which there are also an arbitrary number, in a circle. The markers are numbered sequentially, starting from 0, and are played in order by their number.

First, the marker numbered 0 is placed in the circle. This marker is designated the current marker.
Even though there is just one marker, we consider it a circle of markers; the marker is both clockwise and counter-clockwise from itself.

Now, each player takes a turn placing the next (lowest-numbered) remaining marker into the circle. This marker is placed between the markers that are 1 and 2 markers clockwise of the current marker.
(When the circle is large enough, this means that there is one marker between the marker that was just placed and the current marker.) The marker that was just placed then becomes the current marker.

An illustration might help; suppose we've played the game now for 4 turns. At this point, the circle looks like this:

Circle after 4 plays

The '4' marker is shaded to represent that it is the current marker. The next player takes the '5' marker and plays it. According to the rule, it should go between the '2' marker and the '1' marker, like so:

Circle after 5 plays

The '5' marker is now the current marker. Play continues in this fashion for a while.
However, if the marker that is about to be placed has a number which is a multiple of 23, something entirely different happens.

First, the current player keeps the marker they would have placed, adding it to their pile.
In addition, the marker 7 markers counter-clockwise from the

current marker is removed from the circle and also added to the current player's pile.
Finally, the marker located immediately clockwise of the marker that was removed becomes the new current marker.

For example, this rule would first come into play on move 23. The circle would look like this before the move:

Circle after 22 plays

The next player would normally play marker '23', but instead they keep it for themselves. Then the marker 7 positions counter-clockwise from '22', which is the '9', would also be removed from the circle and added to the player's pile of markers. The '19' marker is the new current marker:

Circle after 23 plays

A player's score is the sum of the numbers on the markers in their pile. The goal is to be the player with the highest score after the last marker is played.

Assuming the example above ends after the marker numbered '25', the winning score is 23 + 9 = 32 (because one player got to keep marker '23' and removed marker '9', while no other player got any points in this very short example game). By the way, if there were 9 players (numbered starting with '1'), the winning player was player 5.

Here are a few more examples:

10 players; last marker is worth 1618 points: high score is 8317 (player 10)
13 players; last marker is worth 7999 points: high score is 146373 (player 12)
17 players; last marker is worth 1104 points: high score is 2764 (player 16)
21 players; last marker is worth 6111 points: high score is 54718 (player 5)
30 players; last marker is worth 5807 points: high score is 37305 (player 20)

Instructions

Complete the code provided in the starter code to simulate a game of Circle Markers. Test it to be sure it matches the results listed above. Then, answer the quiz in Canvas.
Implementation Notes

There are a couple of approaches to simulating a move in Circle Markers using a linked list that we would suggest you consider. In both cases, the list will represent the circle of markers, with the end of the list "connecting" to the start of the list to form the circle.
Approach 1: Point to the current marker

One approach you can take is to simply always keep track of the current marker. Since we don't have access to the true linked list

underlying the list data structure for our circle, we must use iterators instead. We've seen iterators used for simple purposes before, such as passing in as parameters to the sort() function, or for iterating on a set. This time, we're going to take advantage of the fact that iterators on a list object can move both forwards and backwards.

To start the game, you can simply set the current marker iterator using the begin() method of the list object. To move clockwise, use the ++ operator on the iterator, and to move counter-clockwise, use -
-. The only trick is, if you get to the end of the list (going clockwise), or the beginning of the list (going counter-clockwise), you need to transition to the other end of the list.

Remember that you can obtain the value of the current marker by "dereferencing" the iterator using *. Also, look in the list documentation for how to use insert() or erase() to modify the list. Approach 2: Rotate the circle so that the current marker is always up front

A different approach is to use the fact that a linked list allows for very efficient operations at the ends of the list. In this approach, we will treat our list object pretty much like a deque. Instead of pointing to the current marker with an iterator, we will "rotate" the list using push and pop operations such that, at the end of each turn, the current marker is the marker at the front of the list.

This approach is a bit easier, so we're not going to give you any more hints than that!