In this project, you will implement a Linked List (without using the Java built-in Linked List class). Your class will be very versatile, so we'll use it to play a new game: Myopic Col.

Part 0, 0 points: Other programmers should be able to create PureLinkedLists like the following:

PureLinkedList<Mouse> meeses = new PureLinkedList<Mouse>(new Mouse("Jerry"));

What will the class signature look like? Will you need to include a generic type?

You: Kyle, are you giving me this line of code so I can copy-paste it directly into my project somewhere?

Me: Um... no. This is for how the class will be used, not any internal code that will make it work.

You: Then why are you telling me this?

Me: There are a bunch of things you should learn from this, including:

• The number of Generic Types your code should have
• The name of the class you're creating (though you probably already got that from the filename).
• Those first two things should tell you what the signature line of the class will look like, e.g. public class ....
• The number of parameters the constructor will take, and
• The types of the parameters the constructor will take.

If you're unsure about any of those parts, please ask about them!

Part 1, 0 points: Your class should have only two fields, like so:

//the value at the head of this list
private YourGenericVariable value;

//the tail of this list
private PureLinkedList<YourGenericVariable> tail;

Add these fields to your class. (Naturally, you should use a different name than YourGenericVariable.)

Part 2, 0 points: Create a one-parameter constructor. This will create a PureLinkedList with a single node. There are two fields in your class, so you'll want to assign values to both of them. Those two lines will probably be your only two lines of code inside the constructor. Definitely assign something (non-null) to the field this.value. There is no parameter for the this.tail field; it should start out as null.

Part 3, 0 points: As always, after implementing a constructor, you should implement toString. I've provided this recursive version for you:

public String toString() {
    if (this.tail == null) {
        return "[" + this.value + "]";
    } else {
        String tailString = this.tail.toString();
        String tailMinusLeftBracket = tailString.substring(1);
        return "[" + this.value + ", " + tailMinusLeftBracket;
    }
}

I recommend reading through this so that it makes sense to you. Which part is the base case?

Part 4, 0 points: Check out the code for the toString method again. Do you understand what's happening here? If you're not sure about any part of this, I recommend asking for help.

Part 5, 20 points: Write the add method. This takes a single parameter of your generic type and adds it to the end of the linked list in a new node (thus increasing the length by 1). Hint: should this method be recursive? You can run this code to make sure things are working so far:

PureLinkedList<String> linked = new PureLinkedList<>("monkey");
assert linked.toString().trim().equals("[monkey]");
linked.add("tamarin");
assert linked.toString().trim().equals("[monkey, tamarin]");
linked.add("macaque");
assert linked.toString().trim().equals("[monkey, tamarin, macaque]");

Part 6, 0 points: Write the isLast method. This should take no parameters and return whether this is the last element in the list.

Part 7, 20 points: Write the length method, which returns an int, the number of elements in this list. Fun fact: Recursion is Awesome! Here's some testing code you can use:

PureLinkedList<String> linked = new PureLinkedList<>("monkey");
assert linked.length() == 1;
linked.add("tamarin");
assert linked.length() == 2;
linked.add("macaque");
assert linked.length() == 3;

Part 8, 5 points: Let's do some really simple getters and setter. Write the getFirst method, which returns the first element in the list. You can test your code with this:

PureLinkedList<String> linked = new PureLinkedList<>("monkey");
assert linked.getFirst().equals("monkey");
linked.add("tamarin");
assert linked.getFirst().equals("monkey");
linked.add("macaque");
assert linked.getFirst().equals("monkey");

Part 9, 5 points: Write the setFirst method, which takes a single parameter and changes the first item in the list to be that value (instead of whatever it previously was). This operation does not change the length of the list. Here's some code you can use to test that:

PureLinkedList<String> linked = new PureLinkedList<>("monkey");
assert linked.getFirst().equals("monkey");
linked.setFirst("ape");
assert linked.getFirst().equals("ape");
linked.add("tamarin");
linked.add("macaque");
assert linked.getFirst().equals("ape");

Part 10, 5 points: Write the getTail method. This should return a linked list with one less element, which contains everything except for the first element. (This is probably easier than you think. Like, it's super easy. One line.) Here's some testing code:

PureLinkedList<String> linked = new PureLinkedList<>("monkey");
PureLinkedList<String> tail = linked.getTail();
assert tail == null;
linked.add("tamarin");
tail = linked.getTail();
assert tail.getFirst().equals("tamarin");
linked.add("macaque");
tail = linked.getTail();
assert tail.getFirst().equals("tamarin");

Part 11, 5 points: Write a setTail method. This void method should take one PureLinkedList<Something> parameter, and change the subject by resetting it's tail to be the argument. For example, if I have two linked lists of Integer objects, narwhal, [1, 4, -45], and beluga, [7, 1, 32], then after executing:

narwhal.setTail(beluga);

narwhal would be [1, 7, 1, 32]. Here's some testing code:

PureLinkedList<String> linked = new PureLinkedList<>("monkey");
linked.add("tamarin");
linked.add("macaque");
PureLinkedList<String> otherList = new PureLinkedList<>("spider");
otherList.add("mandrill");
otherList.add("capuchin");
linked.setTail(otherList);
assert linked.length() == 4;
assert linked.toString().contains("capuchin");

Part 12, 20 points: Write the get method. This takes a single int parameter and returns the element at that index. There are four things to look out for in the method call:

• If the index is negative, you want to throw an IndexOutOfBoundsException. You can throw one of these with a statement like this:

  throw new IndexOutOfBoundsException("Your index is a skunky monkey!");

  (Don't actually use that message.)
• If the index is zero, then you know you're looking at the correct node.
• If your index is too big, you want to throw an index exception
• If the index is greater than zero (but not too big) then you want to make the recursive call, which is slightly tricky.

This method should not modify the list in any way. (Seriously, make sure it doesn't modify the list by testing it!) Hint: the base case here is not going to be when the tail is null, but instead when the parameter is zero. Here's some code you can use to test that will also test the exceptions:

PureLinkedList<String> linked = new PureLinkedList<>("monkey");
linked.add("tamarin");
linked.add("macaque");
assert linked.get(0).equals("monkey");
assert linked.get(1).equals("tamarin");
assert linked.get(2).equals("macaque");

boolean goodException = false;
try {
    linked.get(-1);
} catch (IndexOutOfBoundsException e) {
    goodException = true;
}
assert goodException;

goodException = false;
try{
    linked.get(3);
} catch (IndexOutOfBoundsException e) {
    goodException = true;
}
assert goodException;

Part 13, 20 points: Write the set method. The signature for this should look something like:

public void set(int index, E element)

It should change the indexeth element in the list to equal the element parameter. Just like before, this should throw an IndexOutOfBoundsException if the index is too low or too high. Here are some tests:

PureLinkedList<String> linked = new PureLinkedList<>("monkey");
linked.add("tamarin");
linked.add("macaque");
assert linked.get(0).equals("monkey");
linked.set(0, "ape");
assert linked.get(0).equals("ape");
linked.set(2, "capuchin");
assert linked.get(1).equals("tamarin");
assert linked.get(2).equals("capuchin");

boolean goodException = false;
try {
    linked.set(-3, "lemur");
} catch (IndexOutOfBoundsException e) {
    goodException = true;
}
assert goodException;

goodException = false;
try{
    linked.set(8, "raccoon");
} catch (IndexOutOfBoundsException e) {
    goodException = true;
}
assert goodException;

Part 14, 25 points: The next one is a bit tough: the equals method. As always, it should take a single Object parameter and return a boolean. There are ways to write this recursively and non-recursively, but I find the recursive version far easier. (I prefer to write two versions, one that takes an Object and the other that takes a LinkedList<?> as we did in Project 0.) Here is some testing code:

PureLinkedList<String> linked = new PureLinkedList<>("monkey");
assert linked.equals(linked);
PureLinkedList<String> second = new PureLinkedList<>("lemur");
assert second.equals(second);
assert !linked.equals(second);
assert !second.equals(linked);
second.setFirst("monkey");
assert linked.equals(second);
assert second.equals(linked);

linked.add("tamarin");
assert !linked.equals(second);
assert !second.equals(linked);

linked.add("macaque");
assert !linked.equals(second);
assert !second.equals(linked);

second.add("raccoon");
assert !linked.equals(second);
assert !second.equals(linked);

second.add("macaque");
assert !linked.equals(second);
assert !second.equals(linked);

second.set(1, "tamarin");
assert linked.equals(second);
assert second.equals(linked);

Part 15, 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 16, 0 points: Time to test out your code with the game rules, which are available here: PathMyopicCol.java

Part 17, 15 points: Create a new class for your own player, PathMyopicColPlayer.java. Implement the getMove method:

public PathMyopicCol getMove(PathMyopicCol position, int playerId)

You'll again need to use the playerId parameter, which should have value either CombinatorialGame.LEFT or CombinatorialGame.RIGHT. Left colors spaces Blue; Right colors them Red. The "colors" are encoded using these same values. So a blue space actually has integer value CombinatorialGame.LEFT and CombinatorialGame.RIGHT for right. If a node is uncolored, it will have value PathMyopicCol.UNCOLORED .) A Path Myopic Col state includes a bunch of path-graphs, so when you get the state of the game, you actually get a collection of linked lists. You can use position.getPath() to get the PureLinkedList. At this point it's not necessary to make a strategically good move, but your method should always make a legal one from here on out. Remember:

• Your player should only directly invoke the PureLinkedList methods assigned here. I'll be testing your player with my own copy of PureLinkedList.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 minLength = 3;
int maxLength = 6;
double colorDensity = .1;
PositionFactory<PathMyopicCol> factory = new PathMyopicCol.PositionBuilder(minLength, maxLength, colorDensity);
Player<PathMyopicCol> me = new PathMyopicColPlayer();
Player<PathMyopicCol> random = new RandomPlayer<PathMyopicCol>();
Referee<PathMyopicCol> ref = new Referee<>(me, random, factory);
ref.call();

ref.gauntlet(10000);

Part 18, 10 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 ≥35%: 5 points
• Win ≥61%: 10 points
• Win ≥75%: 15 points
• Win ≥87%: 20 points

Submitting your Project:

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

• PureLinkedList.java
• PathMyopicColPlayer.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>Project2, 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: kburkeProject2.zip or burkeAndStockProject2.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.