In this project, you will implement a Graph with values on the vertices and then write a player for Col on grid-shaped graphs.

Part 0, 0 points: There are two parts to creating the Data Structure in this project. First we'll need to create a class for the vertices: Vertex.java. Each vertex will need to keep track of three things: the (generic-typed) value stored there, its own id (int), and a collection of its neighbors (Vertex objects), which should begin empty, but initialized. Create the file and the two-parameter contructor:

    public Vertex(YourGenericType value, int id) {

Part 1, 5 points: Add an appropriate toString method. I found it helpful to print out the value, id, and the ids of each of the neighbors. You can test what you've got so far with this:

Vertex<String> jiggly = new Vertex<>("Jigglypuff", 39);
String s = jiggly.toString();
assert s.contains("Jigglypuff") && s.contains("39");

Vertex<Integer> five = new Vertex<>(5, 0);
s = five.toString();
assert s.contains("5") && s.contains("0");

Part 2, 5 points: Add an appropriate getValue method. You can test it with this:

Vertex<String> jiggly = new Vertex<>("Jigglypuff", 39);
assert jiggly.getValue().equals("Jigglypuff");

Vertex<Integer> five = new Vertex<>(5, 0);
assert five.getValue() == 5;

Part 3, 5 points: Add an appropriate setValue method. You can test it with this:

Vertex<String> jiggly = new Vertex<>("Jigglypuff", 39);
jiggly.setValue("Wigglytuff");
assert jiggly.getValue().equals("Wigglytuff");

Vertex<Integer> five = new Vertex<>(5, 0);
five.setValue(10);
assert five.getValue() == 10;

Part 4, 5 points: Add an appropriate getId method. You can test your code with this:

Vertex<String> jiggly = new Vertex<>("Jigglypuff", 39);
assert jiggly.getId() == 39;

Vertex<Integer> five = new Vertex<>(5, 0);
assert five.getId() == 0;

Part 5, 10 points: Add an addEdge method:

    public void addEdge(Vertex<Generic> other) {

This should take another vertex and add them both as each others' neighbors if they aren't already. After you get this working, write a getNeighbors method that returns a List (List<Vertex<Generic>>) of the neighbors. After you create both of these, you can run these tests:

Vertex<String> jiggly = new Vertex<>("Jigglypuff", 39);
List<Vertex<String>> neighbors = jiggly.getNeighbors();
assert neighbors.size() == 0;

Vertex<String> wiggly = new Vertex<>("Wigglytuff", 40);
jiggly.addEdge(wiggly);
neighbors = jiggly.getNeighbors();
assert neighbors.size() == 1;
assert neighbors.contains(wiggly);

neighbors = wiggly.getNeighbors();
assert neighbors.size() == 1;
assert neighbors.contains(jiggly);

Vertex<String> charm = new Vertex<>("Charmander", 4);
jiggly.addEdge(charm);
neighbors = jiggly.getNeighbors();
assert neighbors.size() == 2;
assert neighbors.contains(wiggly);
assert neighbors.contains(charm);

neighbors = wiggly.getNeighbors();
assert neighbors.size() == 1;
assert neighbors.contains(jiggly);
neighbors = charm.getNeighbors();
assert neighbors.size() == 1;
assert neighbors.contains(jiggly);

charm.addEdge(jiggly); //shouldn't add anything
neighbors = charm.getNeighbors();
assert neighbors.size() == 1;

Part 6, 10 points: We need to write a separate helper method before we write the equals method. Implement equalsIgnoreIndividualNeighbors(Vertex<Generic> other), which checks three things:

• Both vertices have the same number of neighbors.
• Both vertices have the same value, and
• Both vertices have the same id.

It should not check whether the neighbors each have the same attributes. Here's some testing code:

Vertex<Integer> noNeighbs = new Vertex<>(0, 0);
Vertex<Integer> neighbs = new Vertex<>(0,0);
Vertex<Integer> neighbor = new Vertex<>(1, 1);
Vertex<Integer> sameId = new Vertex<>(1,0);
Vertex<Integer> sameValue = new Vertex<>(0,1);
Vertex<String> ditto = new Vertex<>("Ditto", 132);

assert noNeighbs.equalsIgnoreIndividualNeighbors(noNeighbs);
assert noNeighbs.equalsIgnoreIndividualNeighbors(neighbs);
assert neighbs.equalsIgnoreIndividualNeighbors(noNeighbs);

assert !noNeighbs.equalsIgnoreIndividualNeighbors(sameValue);
assert !sameValue.equalsIgnoreIndividualNeighbors(noNeighbs);


assert !noNeighbs.equalsIgnoreIndividualNeighbors(sameId);
assert !sameId.equalsIgnoreIndividualNeighbors(noNeighbs);


assert !noNeighbs.equalsIgnoreIndividualNeighbors(neighbor);
assert !neighbor.equalsIgnoreIndividualNeighbors(noNeighbs);
assert !jiggly.equalsIgnoreIndividualNeighbors(ditto);
assert !ditto.equalsIgnoreIndividualNeighbors(jiggly);
assert !jiggly.equalsIgnoreIndividualNeighbors(charm);
assert !charm.equalsIgnoreIndividualNeighbors(jiggly);
assert !charm.equalsIgnoreIndividualNeighbors(ditto);
assert !ditto.equalsIgnoreIndividualNeighbors(charm);


neighbs.addEdge(neighbor);
assert !noNeighbs.equalsIgnoreIndividualNeighbors(neighbs);
assert !neighbs.equalsIgnoreIndividualNeighbors(noNeighbs);

noNeighbs.addEdge(sameValue); 
assert noNeighbs.equalsIgnoreIndividualNeighbors(neighbs);
assert neighbs.equalsIgnoreIndividualNeighbors(noNeighbs);

Part 7, 5 points: Write hasNeighbor(Vertex<Generic>) method, which checks to see if the subject has the passed vertex as a neighbor. (Hint: your code should use the method you just wrote instead of calling equals in the search.) Here is some testing code:

Vertex<Integer> noNeighbs = new Vertex<>(0, 0);
Vertex<Integer> neighbs = new Vertex<>(0,0);
Vertex<Integer> neighbor = new Vertex<>(1, 1);
Vertex<Integer> neighbor2 = new Vertex<>(1,2);

assert !noNeighbs.hasNeighbor(noNeighbs);
assert !noNeighbs.hasNeighbor(neighbor);

neighbs.addEdge(neighbor);
assert neighbs.hasNeighbor(neighbor);
assert neighbor.hasNeighbor(neighbs);

neighbs.addEdge(neighbor2);
assert neighbs.hasNeighbor(neighbor2);
assert neighbor2.hasNeighbor(neighbs);
assert !neighbor.hasNeighbor(neighbor2);
assert !neighbor2.hasNeighbor(neighbor);

neighbs.addEdge(neighbor);
assert neighbs.hasNeighbor(neighbor);
assert neighbor.hasNeighbor(neighbs);

Part 8, 10 points: Now you should easily be able to write the equals method(s). The following code can be used to test things:

Vertex<Integer> sameValue = new Vertex<>(0,1);
assert sameValue.equals(sameValue);

Vertex<String> jiggly = new Vertex<>("Jigglypuff", 39);
Vertex<String> charm = new Vertex<>("Charmander", 4);
jiggly.addEdge(charm);
assert jiggly.equals(jiggly);

Vertex<String> jiggly2 = new Vertex<>("Wigglytuff", 39);
assert !jiggly.equals(jiggly2);
jiggly2.addEdge(charm);
assert !jiggly.equals(jiggly2);
jiggly2.setValue("Jigglypuff");
assert jiggly.equals(jiggly2);
assert jiggly2.equals(jiggly);

Vertex<String> ditto = new Vertex<>("Ditto", 132);
assert !ditto.equals(charm);
assert !jiggly.equals(ditto);
jiggly.addEdge(ditto);
assert !jiggly.equals(jiggly2);
assert !jiggly2.equals(jiggly);

Vertex<String> bulby = new Vertex<>("Bulbasaur", 1);
jiggly2.addEdge(bulby);
assert !jiggly.equals(jiggly2);
assert !jiggly2.equals(jiggly);

Vertex<String> eevee = new Vertex<>("Eevee", 133);
jiggly.addEdge(eevee);
assert !jiggly.equals(jiggly2);
assert !jiggly2.equals(jiggly);

jiggly.addEdge(bulby);
jiggly2.addEdge(eevee);
ditto.addEdge(jiggly2);
assert jiggly.equals(jiggly2);
assert jiggly2.equals(jiggly);

Vertex<String> squirtle = new Vertex<>("Squirtle", 7);
Vertex<String> squirtleClone = new Vertex<>("Squirtle", 7);
jiggly.addEdge(squirtle);
jiggly2.addEdge(squirtleClone);
assert jiggly.equals(jiggly2);
assert jiggly2.equals(jiggly);

Part 9, 0 points: Now we can create Graph.java. You need your graph class to have a field that holds a bunch of vertices. I recommend using a collection of them:

private Collection<Vertex<WhateverYourGenericTypeIs>> vertices;

Add a field to your class.

Part 10, 15 points: The constructor should take an Iterable<Vertex<T>> (or whatever you want to name your generic type) and add it to it's own collection of vertices. That means we should be able to create a graph with some code like this:

ArrayList<Vertex<String>> stringVertices = new ArrayList<Vertex<String>>();
stringVertices.add(new Vertex("hi", 0));
stringVertices.add(new Vertex("bananarama", 35));
Graph<String> strings = new Graph<String>(stringVertices);

Before it adds each one, it should check to make sure it doesn't already have a vertex with that ID. I did this by first making a set of the IDs and making sure there were no duplicates. If there is a duplicate, I throw an IllegalArgumentException. For example, the following code will throw and catch the exception:

ArrayList<Vertex<String>> stringVertices = new ArrayList<Vertex<String>>();
stringVertices.add(new Vertex("hi", 52));
stringVertices.add(new Vertex("bananarama", 52));
try {
    Graph<String> strings = new Graph<String>(stringVertices);
    System.out.println("This line should never print!");
} catch (IllegalArgumentException e) {
    System.out.println("Threw and caught the IllegalArgumentException.  Good!");
}

Write the constructor. You can test your code with this:

Vertex<String> jiggly = new Vertex<>("Jigglypuff", 39);
Vertex<String> charm = new Vertex<>("Charmander", 4);
jiggly.addEdge(charm);

Vertex<String> ditto = new Vertex<>("Ditto", 132);
jiggly.addEdge(ditto);

List<Vertex<String>> vertices = new LinkedList<>();
vertices.add(jiggly);
vertices.add(ditto);
vertices.add(charm);
Graph<String> pokes = new Graph<String>(((Iterable<Vertex<String>>) vertices));

Vertex<String> jiggly2 = new Vertex<>("Wigglytuff", 39);
jiggly2.addEdge(ditto);
jiggly2.addEdge(charm);

boolean goodException = false;
try {
    vertices.add(jiggly2);
    pokes = new Graph<String>(((Iterable<Vertex<String>>) vertices));
} catch (IllegalArgumentException e) {
    goodException = true;
}
assert goodException;

Part 11, 0 points: Add a meaningful toString method. My version includes the value and ID of each node (in a separate line) as well as the IDs of each neighbor.

Part 12, 5 points: Add a getter for the vertices: public Collection<Vertex<T>> getVertices(). We want this to be a Collection and not just an Iterable because we will want to be able to invoke the size method later on. Here's some testing code:

Vertex<String> jiggly = new Vertex<>("Jigglypuff", 39);
Vertex<String> charm = new Vertex<>("Charmander", 4);
jiggly.addEdge(charm);

Vertex<String> ditto = new Vertex<>("Ditto", 132);
jiggly.addEdge(ditto);

List<Vertex<String>> vertices = new LinkedList<>();
vertices.add(jiggly);
Graph<String> pokes = new Graph<String>(((Iterable<Vertex<String>>) vertices));
Collection<Vertex<String>> vertices2 = pokes.getVertices();
assert vertices2.size() == 1;
assert vertices2.contains(jiggly);

vertices.add(ditto);
pokes = new Graph<String>(((Iterable<Vertex<String>>) vertices));
vertices2 = pokes.getVertices();
assert vertices.size() == 2;
assert vertices.contains(jiggly);
assert vertices.contains(ditto);

vertices.add(charm);
pokes = new Graph<String>(((Iterable<Vertex<String>>) vertices));
vertices2 = pokes.getVertices();
assert vertices.size() == 3;
assert vertices.contains(jiggly);
assert vertices.contains(ditto);
assert vertices.contains(charm);

Part 13, 10 points: Graphs don't necessarily keep track of the vertices in an ordered list (though you might be doing this under-the-hood). Thus, it's not appropriate to have a get(int index) method. Instead we'll include a getVertexById(int id). Write this method. If no such ID is included by a vertex, your method should throw a NoSuchElementException. You can use this code to test yours:

Vertex<String> jiggly = new Vertex<>("Jigglypuff", 39);
Vertex<String> charm = new Vertex<>("Charmander", 4);
jiggly.addEdge(charm);
Vertex<String> ditto = new Vertex<>("Ditto", 132);
jiggly.addEdge(ditto);
List<Vertex<String>> vertices = new LinkedList<>();
vertices.add(jiggly);
vertices.add(ditto);
vertices.add(charm);
Graph<String> pokes = new Graph<String>(((Iterable<Vertex<String>>) vertices));

Vertex<String> result = pokes.getVertexById(39);
assert result.equals(jiggly);
result = pokes.getVertexById(4);
assert result.equals(charm);
result = pokes.getVertexById(132);
assert result.equals(ditto);

boolean goodException = false;
try {
    result = pokes.getVertexById(1);
} catch (NoSuchElementException e) {
    goodException = true;
}
assert goodException;

Part 14, 25 points: Time for equals! The things to check here are whether the two graphs have the same number of vertices and whether those vertices are equal. The two lists of vertices may not be in the same order, so use getVertexById to "index" into the other graph (instead of just traversing the other graph's data structure of vertices). Here's some code you can test that with:

Vertex<String> jiggly = new Vertex<>("Jigglypuff", 39);
Vertex<String> charm = new Vertex<>("Charmander", 4);
jiggly.addEdge(charm);
Vertex<String> ditto = new Vertex<>("Ditto", 132);
jiggly.addEdge(ditto);
List<Vertex<String>> vertices = new LinkedList<>();
vertices.add(jiggly);
vertices.add(ditto);
vertices.add(charm);
Graph<String> pokes = new Graph<>(((Iterable<Vertex<String>>) vertices));

Vertex<String> jiggly2 = new Vertex<>("Jigglypuff", 39);
List<Vertex<String>> vertices2 = new ArrayList<>();
vertices2.add(jiggly2);
Graph<String> pokes2 = new Graph<>(((Iterable<Vertex<String>>) vertices2));
assert !pokes.equals(pokes2);

Vertex<String> charm2 = new Vertex<>("Charmander", 4);
Vertex<String> ditto2 = new Vertex<>("Ditto", 132);
jiggly2.addEdge(ditto2);
vertices2.add(ditto2);
pokes2 = new Graph<>(((Iterable<Vertex<String>>) vertices2));
assert !pokes.equals(pokes2);

vertices2.add(charm2);
pokes2 = new Graph<>(((Iterable<Vertex<String>>) vertices2));
assert !pokes.equals(pokes2);

jiggly2.addEdge(charm2);
pokes2 = new Graph<>(((Iterable<Vertex<String>>) vertices2));
assert pokes.equals(pokes2);

You can use a ref that uses Java Swing components like in the prior project too!

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 play the game! This uses two files, Col, which is available here: Col.java, and the subclass GridCol (as well as some of the extra stuff from last time) GridCol.java, RefereeWithSwingDisplay.java, SwingDisplayable.java and GridColPanel.java. Try compiling and then run the unit test in GridCol.java. Ensure that everything is working happily before continuing.

Part 17, 25 points: Now (finally) we're ready to start thinking about writing our own player for Grid Col. As with every single other project we've done, first concentrate on making a legal move. As in previous projects, there are three color constants you can use:

• Col.BLUE
• Col.RED
• Col.UNCOLORED

Remember:

• Your player should only directly invoke the Vertex and Graph methods assigned here. I'll be testing your player with my own copy of Vertex and Graph.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 code like this:

int minWidth = 3;
int maxWidth = 5;
int minHeight = 2;
int maxHeight = 4;
double colorDensity = .2;
PositionFactory<GridCol> factory = 
    new GridCol.PositionBuilder(minWidth, 
                                maxWidth, 
                                minHeight, 
                                maxHeight, 
                                colorDensity);
Player<GridCol> me = new GridColPlayer();
Player<GridCol> random = new RandomPlayer<GridCol>();
Referee<GridCol> ref = new Referee<>(me, random, factory);
ref.call();
ref.gauntlet(10000);

Part 18, 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 ≥22%: 5 points
• Win ≥30%: 10 points
• Win ≥59%: 15 points
• Win ≥79%: 20 points
• Win ≥83%: 25 points
• Win ≥91%: 30 points

Submitting your Project:

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

• Vertex.java
• Graph.java
• GridColPlayer.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>Project8, 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: kburkeProject8.zip or burkeAndStockProject8.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.