In this project, you will implement the stack data structure and use it to create a player for Tower Nim. Since we are only going to implement very basic stack operations, we'll name the class PureStack. In this project, you are not allowed to use any pre-defined Java classes that already implement stack functionality (such as java.util.Stack.)

Part 0, 0 points: Set the class signature for PureStack. We're going to use generic types, so that your stack can hold objects of any single type. Thus, the header should look something like this:

public class PureStack<E> {

Part 1, 10 points: Decide what field(s) you want your class to have. Hint, hint. This field will be super important. For many of the PureStack methods you're going to write, you're going to want to call relevant methods on your field. If you get stuck, you might want to browse the methods for your field's class and see if any of those might help. (If you're using another data structure (hint, hint) you might want to think about which end the top of your stack will be at: the front or the back.) Write the constructor to initialize your fields. It should take no parameters.

Part 2, 0 points: Write a toString method. (Start by writing the Javadoc, naturally.) My toString prints out all the elements and indicates at which end the top is. I use mine like the following: (You haven't written push yet, so you can't run this entire test yet.)

PureStack<String> stringStack = new PureStack<String>();
stringStack.push("Hi");
stringStack.push("yo");
stringStack.push("Animal!");
System.out.println(stringStack);

The last line prints out something like this:

Top --> [Animal!, yo, Hi] <-- Bottom

or this:

Bottom --> [Hi, yo, Animal!] <-- Top

Part 3, 15 points: Implement push. (Javadoc first!) This should be a void method that takes one parameter of type E and adds it on top of your stack. Here are some sample tests:

PureStack<String> strings = new PureStack<>();

strings.push("monkey");
assert strings.toString().contains("monkey");

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

Remember that my tests will be more comprehensive.

Part 4, 10 points: Implement pop. This method could throw a NoSuchElementException. That line of code will look something like this:

throw new NoSuchElementException("Use a better string than this.");

When should your code throw the exception? Code up your solution. You can test that your code works by catching the exception, doing something like this:

boolean isCorrect;

PureStack<String> alpacas = new PureStack<>();
try {
    alpacas.pop();
    //if the code reaches this point, the exception didn't get thrown!
    isCorrect = false;
} catch (NoSuchElementException e) {
    //the exception was thrown; the method worked correctly!
    isCorrect = true;
}
assert isCorrect;

I found a little exception tutorial in case you'd like more background on exceptions. (I can also answer any questions you have about this, of course!) Hint to finishing the method: in the code, there are two ways to test for when you should throw your exception: either use a conditional or catch another possible exception that would be thrown. Here's my full example unit test:

PureStack<String> alpacas = new PureStack<>();
try {
    alpacas.pop();
    //if the code reaches this point, the exception didn't get thrown!
    isCorrect = false;
} catch (NoSuchElementException e) {
    //the exception was thrown; the method worked correctly!
    isCorrect = true;
}
assert isCorrect;

alpacas.push("Emily");
String s = alpacas.pop();
assert s.equals("Emily");

alpacas.push("Kaylee");
alpacas.push("Rayne");
s = alpacas.pop();
assert s.equals("Rayne");
assert alpacas.toString().contains("Kaylee");
s = alpacas.pop();
assert s.equals("Kaylee");

Part 5, 10 points: Implement peek. Consider: should this ever throw an exception? Once you figure that out, there's a really elegant way to do this using methods you've already written. Here's some tests:

PureStack<String> alpacas = new PureStack<>();
try {
    alpacas.peek();
    //if the code reaches this point, the exception didn't get thrown!
    isCorrect = false;
} catch (NoSuchElementException e) {
    //the exception was thrown; the method worked correctly!
    isCorrect = true;
}
assert isCorrect;

alpacas.push("Emily");
String s = alpacas.peek();
assert s.equals("Emily");

alpacas.push("Kaylee");
assert alpacas.peek().equals("Kaylee");
alpacas.push("Rayne");
s = alpacas.peek();
assert s.equals("Rayne");
s = alpacas.peek();
assert s.equals("Rayne");
alpacas.pop();
assert alpacas.peek().equals("Kaylee");

Part 6, 10 points: Implement isEmpty. This should take no arguments and return a boolean. Here are some tests:

PureStack<String> monkeys = new PureStack<>();
assert monkeys.isEmpty();

monkeys.push("tamarin");
assert !monkeys.isEmpty();

monkeys.pop();
assert monkeys.isEmpty();

monkeys.push("tamarin");
assert !monkeys.isEmpty();
monkeys.push("capucin");
assert !monkeys.isEmpty();

monkeys.pop();monkeys.pop();assert monkeys.isEmpty();

Part 7, 20 points: We need to be able to test whether two Stacks are equivalent. Next, we'll implement equals. Just as in previous projects, we need to at least have a version of this that takes an Object parameter. Take a good look at how you did this in the Pair project and follow that plan. Extra Hint: Take a good look at the methods available to your field. I think you can write this method in one line! Do not just check that the toStrings are the same! Here are some tests:

PureStack<String> strings = new PureStack<>();
PureStack<String> strings2 = new PureStack<>();
assert strings.isEmpty();
assert strings.equals(strings);
assert strings.equals(strings2);
strings.push("monkey");
assert strings.equals(strings);
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.push("monkey");
assert strings.equals(strings2);
assert !strings.isEmpty();
assert strings.toString().contains("monkey");
String s = strings.peek();
assert !strings.isEmpty();
assert s.equals("monkey");
strings.pop();
assert strings.isEmpty();
assert strings.equals(strings);
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.pop();
assert strings.equals(strings2);

strings.push("monkey");
assert !strings.isEmpty();
strings.push("tamarin");
assert strings.equals(strings);
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.push("monkey");
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.push("tamarin");
assert strings.equals(strings2);
assert !strings.isEmpty();
assert strings.toString().contains("monkey");
assert strings.toString().contains("tamarin");
s = strings.peek();
assert !strings.isEmpty();
assert s.equals("tamarin");
strings.pop();
s = strings.peek();
assert !strings.isEmpty();
assert s.equals("monkey");
strings.pop();
assert strings.isEmpty();
strings2.pop();
strings2.pop();

strings.push("monkey");
assert !strings.isEmpty();
strings.push("tamarin");
assert !strings.isEmpty();
strings.push("macaque");
assert !strings.isEmpty();
assert strings.toString().contains("monkey");
assert strings.toString().contains("tamarin");
assert strings.toString().contains("macaque");
assert strings.equals(strings);
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.push("macaque");
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.push("tamarin");
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.push("monkey");
assert !strings.equals(strings2);
assert !strings2.equals(strings);
strings2.pop();
strings2.pop();
strings2.pop();
strings2.push("monkey");
strings2.push("tamarin");
strings2.push("macaque");
assert strings2.equals(strings);
s = strings.peek();
assert !strings.isEmpty();
assert s.equals("macaque");
strings.pop();
s = strings.peek();
assert !strings.isEmpty();
assert s.equals("tamarin");
strings.pop();
s = strings.peek();
assert !strings.isEmpty();
assert s.equals("monkey");
strings.pop();
assert strings.isEmpty();

Part 8, 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 9, 0 points: The game for this project is Tower Nim, available here: TowerNim.java if you want to download it.

Part 10, 10 points: Create your own Tower Nim player class, TowerNimPlayer.java. The code for this will look very similar to the player for the last project, except you'll be dealing with TowerNim objects. When using those objects, invoke only the methods I asked you to write in this project (I will test with my version of the data structure, so using extra methods will break your player). Your code should not make use of any of the players I've provided you with. Make sure your player compiles and always makes legal moves. Remember:

• Your player should only directly invoke the PureStack methods assigned here. I'll be testing your player with my own copy of PureStack.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<TowerNim> factory = new TowerNim.PositionBuilder(numPiles, pileSize);
Player<TowerNim> me = new TowerNimPlayer();
Player<TowerNim> random = new RandomPlayer<TowerNim>();
Referee<TowerNim> ref = new Referee<>(me, random, factory);
ref.call();

ref.gauntlet(10000);

Note: In this project, I will be testing using factory parameters that I think are very specialized for TowerNim. You will want to consider which parameters are hardest on your player, because those are probably what I'm going to use.

Part 11, 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 ≥51%: 5 points
• Win ≥64%: 10 points
• Win ≥80%: 15 points
• Win ≥98%: 25 points

Submitting your Project:

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

• PureStack.java
• TowerNimPlayer.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>Project3, 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: kburkeProject3.zip or burkeAndStockProject3.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.