In this project, you will implement the Queue data structure and use it to create a player for Rotisserie Nim. Since we are only going to implement very basic Queue operations, we'll name the class PureQueue.

Part 0, 0 points: Write a no-parameter constructor. While doing this (if you haven't already) you'll probably decide that it's time to add a field; a different data structure to use as your underlying data. You can't use one of Java's premade Queues, but you could try using something you've already seen... If you do use an ArrayList, which ends will represent the front and back?

Part 1, 0 points: Write a toString method. Afterwards, write a main method to be a unit test for your class. Test your constructor and toString.

Part 2, 15 points: Implement add. You can test it by running this code with asserts enabled:

PureQueue<String> strings = new PureQueue<>();
strings.add("monkey");
assert strings.toString().contains("monkey");

strings.add("tamarin");
assert strings.toString().contains("monkey");
assert strings.toString().contains("tamarin");

strings.add("macaque");
assert strings.toString().contains("monkey");
assert strings.toString().contains("tamarin");
assert strings.toString().contains("macaque");

Part 3, 15 points: Implement remove, which removes (and returns) the next element. (It returns the same element it removes.) There are times when this should throw a NoSuchElementException. When should it throw this exception? There are two ways to check for when you should throw an exception: either use a conditional or catch another possible exception and throw the right one in that handling-code. You can use this to test your code:

PureQueue<String> strings = new PureQueue<>(); 
strings.add("monkey"); 
String s = strings.remove(); 
assert !strings.toString().contains("monkey"); 
assert s.equals("monkey"); 
 
strings.add("monkey"); 
strings.add("tamarin"); 
s = strings.remove(); 
assert s.equals("monkey"); 
assert strings.toString().contains("tamarin"); 
assert !strings.toString().contains("monkey"); 
strings.add("monkey"); 
s = strings.remove(); 
assert s.equals("tamarin"); 
assert !strings.toString().contains("tamarin"); 
assert strings.toString().contains("monkey"); 
 
strings.add("tamarin"); 
strings.add("macaque"); 
s = strings.remove(); 
assert s.equals("monkey"); 
s = strings.remove(); 
assert s.equals("tamarin"); 
s = strings.remove(); 
assert s.equals("macaque"); 
 
boolean exceptionHit = false; 
 
try { 
    s = strings.remove(); 
} catch (NoSuchElementException e) { 
    exceptionHit = true; 
} 
assert exceptionHit;

Part 4, 15 points: Implement element, which returns the next element, but doesn't remove it. When should this throw an exception? You can test your solution with this code:

PureQueue<String> strings = new PureQueue<>();
strings.add("monkey");
String s = strings.element();
assert s.equals("monkey");
assert strings.element().equals("monkey");
assert strings.toString().contains("monkey");
strings.remove();

strings.add("monkey");
strings.add("tamarin");
s = strings.element();
assert s.equals("monkey");
assert strings.element().equals("monkey");
strings.remove();
s = strings.element();
assert s.equals("tamarin");
assert strings.element().equals("tamarin");
strings.remove();

boolean exceptionHit = false;

try {
    s = strings.element();
} catch (NoSuchElementException e) {
    exceptionHit = true;
}
assert exceptionHit;

Part 5, 10 points: Implement isEmpty, which returns whether the queue is empty. You can use this to test your code:

PureQueue<String> strings = new PureQueue<>();
assert strings.isEmpty();
strings.add("monkey");
assert !strings.isEmpty();
String s = strings.element();
assert !strings.isEmpty());
strings.remove();
assert strings.isEmpty();

strings.add("monkey");
assert !strings.isEmpty();
strings.add("tamarin");
assert !strings.isEmpty();
s = strings.element();
assert !strings.isEmpty();
strings.remove();
s = strings.element();
assert !strings.isEmpty();
strings.remove();
assert strings.isEmpty();

Part 6, 20 points: Implement equals. Just like last time, the signature of this method should look like:

public boolean equals(Object other) 

Implement this method. Again, be careful not to just test whether the toStrings are equal! You can use this to test your code:

PureQueue<String> strings = new PureQueue<>();
PureQueue<String> strings2 = new PureQueue<>();
assert strings.equals(strings);
assert strings.equals(strings2);

strings.add("monkey");
assert strings.equals(strings);
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.add("monkey");
assert strings.equals(strings2);
strings.remove();
assert strings.equals(strings);
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.remove();
assert strings.equals(strings2);

strings.add("monkey");
strings.add("tamarin");
assert strings.equals(strings);
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.add("monkey");
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.add("tamarin");
assert strings.equals(strings2);
strings.remove();
strings.remove();
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.remove();
strings2.remove();

Part 7, 0 points: Let's test your code out during actual game play. To compile and run the code locally, you'll need these:

• Abstract CG class: download and compile CombinatorialGame.java.
• Player classes: Player.java and RandomPlayer.java.
• Abstract class for generation of game states: PositionFactory.java.
• Referee: Referee.java.

Part 8, 0 points: The game for this project is RotisserieNim, which you can find here: RotisserieNim.java.

Part 9, 10 points: Create a new class for your own Rotisserie Nim player, RotisserieNimPlayer.java. Before considering good strategies, focus on creating a player that makes any legal move. Your player should never make any forfeits. Remember:

• Your player should only directly invoke the PureQueue methods assigned here. I'll be testing your player with my own copy of PureQueue.java, so if you call other methods, your player won't compile and you won't earn any points for it.
• Don't use randomness in your player. (Randomness is a really powerful tool. If you're interested in writing a player that uses randomness, we should definitely talk after this course is finished!)
• Don't call the getOptions method.
• Make sure your player decides its move in a reasonable amount of time. (If it runs too long, I'll have to kill the process. Exponential-time players are probably not going to earn points.)
• Add a toString method if you want to give your player an interesting name. (Highly recommended.)

You can set up a competition with a random player like this:

int numPiles = 5;
int pileSize = 9;
PositionFactory<RotisserieNim> factory = new RotisserieNim.RotisserieFactory(numPiles, pileSize);
Player<RotisserieNim> me = new RotisserieNimPlayer();
Player<RotisserieNim> random = new RandomPlayer<RotisserieNim>();
Referee<RotisserieNim> ref = new Referee<>(me, random, factory);
ref.call();

ref.gauntlet(10000);

Part 10, 15 points: Modify your strategy so that your player does well against my random player. You will earn points depending on how often you win in my tests. Warning: I won't tell you the parameters of those tests. I recommend chatting with other teams about the factory parameters they're using and going with the hardest ones. Important: do not copy code from any outside sources, but:

• It's okay to search online for strategies and info about this game, as long as you're not getting code (in any programming language) or pseudocode.
• It's okay to talk to other people about strategies so long as you're not sharing code.
• It's okay to challenge me to a game if that would help!

Here's how many points you earn based on how your player does when I test it:

• Win ≥47%: 10 points
• Win ≥73%: 15 points
• Win ≥89%: 20 points
• Win ≥97%: 25 points

Submitting your Project:

The files I'm looking for in this project are:

• PureQueue.java
• RotisserieNimPlayer.java

Please make sure to remove scaffolding from your code so that it doesn't print a ton when executed. Your team name is your username if you're working alone or your members' last names with "And" between them if you're working with a teammate. (For example, alone my teamname would be "kburke", but when working with Stacey Stock it would be "burkeAndStock".) Put completed working files you have in a folder named <YourTeamName>Project4, then zip the folder and upload the resulting .zip file to the assignment's canvas page so I can grade it. (E.g., for me: kburkeProject4.zip or burkeAndStockProject4.zip.) If you do it before the deadline and want me to run it through my tester to see how it does against the random players, send me a message and I'll do it. If you upload it after the deadline, please send me a message so I can grade it ASAP. Please please please name the folder correctly, then zip it; don't rename the zip file, or you'll have to resubmit and may incur a lateness penalty.