In this project, you will implement a Priority Queue and use it to create a player for Greedy Nim. Your version will be called PurePriorityQueue.

Part 0, 0 points: This time, your constructor will take only one argument, a Comparator, so be sure to add an import statement before the class JavaDoc. A comparator is an object that can be used to compare two objects of the specified type using a total order. It has a compare method that returns an integer:

• negative, if the first parameter has higher priority than the second.
• zero, if the priorities of the parameters is equal.
• positive, if the first parameter has lower priority than the second.

For an example, download GreedyNim.java and check out the anonymous Comparator class defined as a constant (MAX) near the top. Which of the two integers does this give priority to? Alternatively, we could have a min comparator: (Where does the code differ between these two?)

Comparator<Integer> min = new Comparator<Integer>() {
    public int compare(Integer left, Integer right) {
        return left.intValue() - right.intValue();
    }
};

You can declare and use this comparator in your main method like this: (I added another one for good measure.)

public static void main(String[] args) {
    //min gives higher priority to the lower number.
    Comparator<Integer> min = new Comparator<Integer>() {
        public int compare(Integer left, Integer right) {
            return left.intValue() - right.intValue();
        }
    };

    //longest gives higher priority to the longer String
    Comparator<String> longest = new Comparator<String>() {
        public int compare(String a, String b) {
            return b.length() - a.length();
        }
    };

    //lexicographical gives higher priority to strings that come first alphabetically
    Comparator<String> lexicographical = new Comparator<String>() {
        public int compare(String a, String b) {
            int minLength = Math.min(a.length(), b.length());
            for (int i = 0; i < minLength; i++) {
                if (a.charAt(i) < b.charAt(i)) return -1;
                if (a.charAt(i) > b.charAt(i)) return 1;
            }
            //one string is a prefix of the other
            return a.length() - b.length();
        }
    };

    PurePriorityQueue<Integer> minQueue = new PurePriorityQueue<Integer>(min);
    PurePriorityQueue<String> longerQueue = new PurePriorityQueue<String>(longest);
    PurePriorityQueue<String> alphabeticalQueue = new PurePriorityQueue<String>(lexicographical);
}

Part 1, 0 points: Write the (one-parameter) constructor. Your class should have two fields: the comparator and some kind of data structure that will hold the elements in this priority queue. You may choose to use any data structure we've used or programmed already. (You can always change it later, too.)

Part 2, 0 points: Write the toString method. It should at least print out all the elements inside the priority queue though I won't grade based on the order. (This is necessary for me to correctly grade the other parts.)

Part 3, 15 points: We only have a few methods to implement for priority queues: add, remove, and element. Implement add first. Once you have it written, don't forget to thoroughly unit test it! (This one can be void unlike the Queue project.) You can test it using this code:

Comparator<String> shorterLength = new Comparator<>() {
    public int compare(String left, String right) {
        return left.length() - right.length();
    }
};
Comparator<String> longerLength = (left, right) -> {
    return right.length() - left.length();
};
Comparator<Integer> minimum = (left, right) -> {
    return left - right;
};

PurePriorityQueue<String> shorter = new PurePriorityQueue<>(shorterLength);
PurePriorityQueue<String> longer = new PurePriorityQueue<>(longerLength);
PurePriorityQueue<Integer> min = new PurePriorityQueue<>(minimum);

shorter.add("monkey");
assert shorter.toString().contains("monkey");
longer.add("monkey");
assert longer.toString().contains("monkey");
min.add(5);
assert min.toString().contains("5");

shorter.add("tamarin");
assert shorter.toString().contains("tamarin");
assert shorter.toString().contains("monkey");
longer.add("tamarin");
assert longer.toString().contains("tamarin");
assert longer.toString().contains("monkey");
min.add(28);
assert min.toString().contains("28");

Part 4, 20 points: Implement element, which returns the item with the highest priority. In your code, this should throw a NoSuchElementException when there are no elements to choose from. You can use this code to test it:

Comparator<String> shorterLength = new Comparator<>() {
    public int compare(String left, String right) {
        return left.length() - right.length();
    }
};
Comparator<String> longerLength = (left, right) -> {
    return right.length() - left.length();
};
Comparator<Integer> minimum = (left, right) -> {
    return left - right;
};

PurePriorityQueue<String> shorter = new PurePriorityQueue<>(shorterLength);
PurePriorityQueue<String> longer = new PurePriorityQueue<>(longerLength);
PurePriorityQueue<Integer> min = new PurePriorityQueue<>(minimum);

boolean exceptionOccurred;
exceptionOccurred = false;
try {
    shorter.element();
} catch (NoSuchElementException e) {
    exceptionOccurred = true;
}
exceptionOccurred = false;
try {
    longer.element();
} catch (NoSuchElementException e) {
    exceptionOccurred = true;
}
exceptionOccurred = false;
try {
    min.element();
} catch (NoSuchElementException e) {
    exceptionOccurred = true;
}

shorter.add("monkey");
assert shorter.element().equals("monkey");
longer.add("monkey");
assert longer.element().equals("monkey");
min.add(5);
assert min.element().equals(5);

shorter.add("tamarin");
assert shorter.element().equals("monkey");
longer.add("tamarin");
assert longer.element().equals("tamarin");
min.add(28);
assert min.element().equals(5);

shorter.add("ape");
assert shorter.element().equals("ape");
longer.add("ape");
assert longer.element().equals("tamarin");
min.add(-12);
assert min.element().equals(-12);

Part 5, 15 points: Implement remove. This should also throw an exception when it's empty. You can test it with this:

Comparator<String> shorterLength = new Comparator<>() {
    public int compare(String left, String right) {
        return left.length() - right.length();
    }
};
Comparator<String> longerLength = (left, right) -> {
    return right.length() - left.length();
};
Comparator<Integer> minimum = (left, right) -> {
    return left - right;
};

PurePriorityQueue<String> shorter = new PurePriorityQueue<>(shorterLength);
PurePriorityQueue<String> longer = new PurePriorityQueue<>(longerLength);
PurePriorityQueue<Integer> min = new PurePriorityQueue<>(minimum);

boolean exceptionOccurred;
exceptionOccurred = false;
try {
    shorter.remove();
} catch (NoSuchElementException e) {
    exceptionOccurred = true;
}
exceptionOccurred = false;
try {
    longer.remove();
} catch (NoSuchElementException e) {
    exceptionOccurred = true;
}
exceptionOccurred = false;
try {
    min.remove();
} catch (NoSuchElementException e) {
    exceptionOccurred = true;
}

shorter.add("monkey");
assert shorter.remove().equals("monkey");
assert !shorter.toString().contains("monkey");
longer.add("monkey");
assert longer.remove().equals("monkey");
assert !longer.toString().contains("monkey");
min.add(5);
assert min.remove().equals(5);
assert !min.toString().contains("5");

shorter.add("monkey");
shorter.add("tamarin");
assert shorter.remove().equals("monkey");
assert !shorter.toString().contains("monkey");
assert shorter.toString().contains("tamarin");
longer.add("monkey");
longer.add("tamarin");
assert longer.remove().equals("tamarin");
assert !longer.toString().contains("tamarin");
assert longer.toString().contains("monkey");
min.add(5);
min.add(28);
assert min.remove().equals(5);
assert !min.toString().contains("5");

Part 6, 0 points: Optional: implement isEmpty.

Part 7, 20 points: It's difficult to test whether two priority queues are equivalent, mostly because it's hard to test whether two comparators are the same (unless they are references to the same object). Thus, instead of an equals method, we'll write a boolean hasSameElementsAs method that takes another PurePriorityQueue as a parameter. Implement this method. Since there is no implicit order on the elements, this may not be as easy as it sounds. After you've gotten this written, I highly recommend testing it on priority queues with these elements (added in the order shown): [5, 1, 5], [1, 5, 5], [1, 5], and [5, 1, 1]. (Only the first two should be equal to each other.) If you can't figure out how to do this one, please come ask me! UPDATE: I've decided to add more about this method, because it's a bit tricky! Some cases I keep forgetting about:

• Even if the lists are sorted, they may not have the same Comparator and might be in different orders.
• Sorting the underlying list of a priority queue might cause trouble if it's kept sorted.

Thus, I recommend the following approach:

1. Create two new ArrayLists.
2. Copy the elements in this into one of those lists and the elements of the other priority queue into the other list.
3. Sort those two lists using the sort method in the Collections class. (It doesn't matter which priority queue's comparator you use.)
4. Iterate through both lists and make sure all the elements are the same. (Or, just use the ArrayList's equals method.)

You can test your code with this, though it is not comprehensive enough:

Comparator<String> shorterLength = new Comparator<>() {
    public int compare(String left, String right) {
        return left.length() - right.length();
    }
};
Comparator<String> longerLength = (left, right) -> {
    return right.length() - left.length();
};

PurePriorityQueue<String> shorter = new PurePriorityQueue<>(shorterLength);
PurePriorityQueue<String> longer = new PurePriorityQueue<>(longerLength);
PurePriorityQueue<Integer> min = new PurePriorityQueue<>(minimum);
assert shorter.hasSameElementsAs(longer);

shorter.add("monkey");
assert shorter.hasSameElementsAs(shorter);
assert !shorter.hasSameElementsAs(longer);
assert !longer.hasSameElementsAs(shorter);
longer.add("tamarin");
assert !shorter.hasSameElementsAs(longer);
assert !longer.hasSameElementsAs(shorter);
shorter.add("tamarin");
assert !shorter.hasSameElementsAs(longer);
assert !longer.hasSameElementsAs(shorter);
longer.add("monkey");
assert shorter.hasSameElementsAs(longer);
assert longer.hasSameElementsAs(shorter);
shorter.add("monkey");
shorter.remove();
assert shorter.hasSameElementsAs(longer);
assert longer.hasSameElementsAs(shorter);
longer.add("monkey");
assert !shorter.hasSameElementsAs(longer);
assert !longer.hasSameElementsAs(shorter);
shorter.add("tamarin");
assert !shorter.hasSameElementsAs(longer);
assert !longer.hasSameElementsAs(shorter);

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 Greedy Nim, which is available here: GreedyNim.java

Part 10, 20 points: Create your own player for Greedy Nim, GreedyNimPlayer.java. Before considering good strategies, focus on creating a player that compiles. The GreedyNim constructor does not take a priority queue as an argument; it takes a List (which could be an ArrayList) instead. It does this because it uses its own priority (choosing the maximum number) and doesn't want to allow a constructor to specify something different. You'll need to write some code to convert your priority queue to an ArrayList before you can create the position your player moves to. Remember:

• Your player should only directly invoke the PurePriorityQueue methods assigned here. I'll be testing your player with my own copy of PurePriorityQueue.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 try it against a random player with code like this:

int numPiles = 5;
int pileSize = 9;
PositionFactory<GreedyNim> factory = new GreedyNim.PositionBuilder(numPiles, pileSize);
Player<GreedyNim> me = new GreedyNimPlayer();
Player<GreedyNim> random = new RandomPlayer<GreedyNim>();
Referee<GreedyNim> ref = new Referee<>(me, random, factory);
ref.call();

ref.gauntlet(10000);

Part 11, 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 ≥53%: 5 points
• Win ≥65%: 10 points
• Win ≥76%: 15 points
• Win ≥98%: 20 points

Submitting your Project:

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

• PurePriorityQueue.java
• GreedyNimPlayer.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>Project5, 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: kburkeProject5.zip or burkeAndStockProject5.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.