Florida Southern Sunset
CSC 3280: Data Structures
(Spring 2025)

Syllabus

LMS

Teachers


Assignments


Other Pages

Project 1:
Pachyderm Lists


Assigned: Wed Jan 22 2025
Due: 11:59:00 PM on Thu Feb 06 2025
Team Size: 1 or 2
Language: Java
Out of: 100 points


In this project, you will use good programming practice and teamwork to build a player for the game of Elephants and Rhinos. In order to do this, you'll need to use ArrayLists. (This is the only project where you won't be coding up the data structure.)

Part 0, 0 points: Check out the online API for the ArrayList class. We'll be using this class a lot, both in this project and future projects. Create a new folder for this project and a new Java file to play around with, e.g. TestingMonkey.java where we can practice using the ArrayList methods. In order to use the ArrayList class, you need to import it at the top of your file. The API tells you which package to import: java.util.ArrayList. In order to import the package, put

import java.util.ArrayList;
at the top of your code. In a main method, create both an ArrayList of integers, and another ArrayList of strings. Practice adding and removing elements. In general, you should get comfortable with all of the following methods:
  • Both versions of add
  • clear
  • contains: test both true and false cases
  • get, using different indices
  • indexOf
  • isEmpty
  • both versions of remove
  • set
  • size

Part 1, 0 points: In this project, you don't have any data structure to write. (I would ask you to implement the basics of the ArrayList class, but generic Java arrays are annoying to work with for some things.) Instead we're going to get directly into playing this project's game: Elephants and Rhinos. Elephants and Rhinos is a game played on a row of spaces. Each space is either empty or has one elephant or rhino in it. (Two pachyderms cannot share a space.) Each turn, a player moves one of their pieces one space forward, if possible. If not, they lose the game. Elephants, controlled by the Left player, move from left to right. Rhinos, controlled by the Right player, move from right to left. Download ElephantsAndRhinos.java to the same folder.

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

Part 3, 0 points: In order to get this class to compile, we need to implement the getMove method in ElephantsAndRhinosPlayer.java that returns a new ElephantsAndRhinos position. We'll start off by adding a stub so that it will compile and we'll fix it later. The header to this is similar to last project's, except that you'll be using ElephantsAndRhinos as the game. Here's a template for the method body that will compile:

... {
    ArrayList<String> spaces = position.getSpaces();

    //your code to modify spaces will go here later

    return new ElephantsAndRhinos(spaces);
}

Part 4, 10 points: Let's write some static methods to make sure we're comfortable with Java ArrayLists. Add a new method with the following Javadoc and signature:

/**
 * Returns whether the given board has an elephant at the given index.
 *
 * @param position  The game state that is being checked.
 * @param index  The index of the space on the board, starting from 0 and going left-to-right.
 * @return True if there is an elephant in the indexeth space of position; false otherwise.
 */
public static boolean hasElephantAt(ElephantsAndRhinos position, int index) {
In order to write this method, you will need to first get a hold of the underlying board from position:
    ArrayList<String> spaces = position.getSpaces();
Every element in the list should be one of only three values: one string for empty, one for an elephant, and one for a rhino. I don't need to remember what the actual values for these are because I set up three constants in ElephantsAndRhinos: EMPTY, ELEPHANT, and RHINO. For example, if I wanted to know whether the seveneth cell of a list called someList held a rhino, I could use this:
String sevenethElement = someList.get(7);
boolean hasRhino = sevenethElement.equals(ElephantsAndRhinos.RHINO);
Use this to finish writing the hasElephantAt method. I wrote some code you can use to test your implementation: 
ArrayList<String> positionSpaces = new ArrayList<>();
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.RHINO);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.RHINO);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
boolean[] hasOne = new boolean[] {false, false, true, false, true, true, false, true, false};

ElephantsAndRhinos position = new ElephantsAndRhinos(positionSpaces);
ElephantsAndRhinosPlayer player = new ElephantsAndRhinosPlayer();

for (int i = 0; i < positionSpaces.size(); i++) {
    assert player.hasElephantAt(position, i) == hasOne[i];
}

Part 5, 0 points: Make sure your hasElephantAt works correctly. You can create a new Elephants and Rhinos position by doing something like this:

ArrayList<String> pachyderms = new ArrayList<String>();
pachyderms.add(ElephantsAndRhinos.EMPTY);
pachyderms.add(ElephantsAndRhinos.ELEPHANT);
pachyderms.add(ElephantsAndRhinos.RHINO);
pachyderms.add(ElephantsAndRhinos.ELEPHANT);
ElephantsAndRhinos game = new ElephantsAndRhinos(pachyderms);
Then the following should be true:
boolean hasElephant = ElephantsAndRhinosPlayer.hasElephantAt(game, 3);
Add a test like this to either your player's main method or inside your testing class. Switch to the framework I showed you in the zeroeth project, then add more tests so that you're certain your method works.

Part 6, 0 points: Now add a hasRhinoAt static method that does a similar thing.

Part 7, 5 points: Add a static hasPachydermAt method that returns true exactly when there is either an elephant or rhino in the specified space. You can write this very easily by invoking both of the other methods you just wrote. Add a bunch of tests so that it's clear it works. Here's some code you can test with:

ArrayList<String> positionSpaces = new ArrayList<>();
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.RHINO);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.RHINO);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
boolean[] hasOne = new boolean[] {false, true, true, true, true, true, false, true, false};

ElephantsAndRhinos position = new ElephantsAndRhinos(positionSpaces);
ElephantsAndRhinosPlayer player = new ElephantsAndRhinosPlayer();

for (int i = 0; i < positionSpaces.size(); i++) {
    assert player.hasPachydermAt(position, i) == hasOne[i];
}

Part 8, 10 points: Let's add another static method to help us out:

public static boolean pachydermCanMove(ElephantsAndRhinos position, int index)
This method should return whether there's a pachyderm at that space and whether it can move. Hint: it may make your code cleaner to first write two helper methods: elephantCanMove and rhinoCanMove. Here's some testing code, but it doesn't check all cases:
ArrayList<String> positionSpaces = new ArrayList<>();
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.RHINO);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.RHINO);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
boolean[] isTrue = new boolean[] {true, false, true, false, false, false, true, false, true, false, false};

ElephantsAndRhinos position = new ElephantsAndRhinos(positionSpaces);
ElephantsAndRhinosPlayer player = new ElephantsAndRhinosPlayer();

for (int i = 0; i < positionSpaces.size(); i++) {
    assert player.pachydermCanMove(position, i) == isTrue[i];
}

Part 9, 15 points: Alright, one more pair of these practice methods: 

public static ArrayList<Integer> moveableElephants(ElephantsAndRhinos position)
This method should return an ArrayList of all indices of spaces in position that have an elephant that can move. You can use this to test some cases:
ArrayList<String> positionSpaces = new ArrayList<>();
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.RHINO);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.RHINO);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
ElephantsAndRhinos position = new ElephantsAndRhinos(positionSpaces);
ElephantsAndRhinosPlayer player = new ElephantsAndRhinosPlayer();
List<Integer> moveable = player.moveableElephants(position);

assert moveable.contains(0);
assert moveable.contains(6);
assert moveable.contains(8);
assert moveable.size() == 3;

Part 10, 0 points: Do the same thing for moveableRhinos. If you want, you can also include moveablePachyderms. Testing code:

ArrayList<String> positionSpaces = new ArrayList<>();
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.RHINO);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.RHINO);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.ELEPHANT);
positionSpaces.add(ElephantsAndRhinos.EMPTY);
positionSpaces.add(ElephantsAndRhinos.RHINO);
ElephantsAndRhinos position = new ElephantsAndRhinos(positionSpaces);
ElephantsAndRhinosPlayer player = new ElephantsAndRhinosPlayer();
List<Integer> moveable = player.moveableRhinos(position);

assert moveable.contains(2);
assert moveable.contains(10);
assert moveable.size() == 2;

Part 11, 0 points: Update your getMove method. Here different players move different pachyderms, so you'll need to do different things depending on whether the current player moves Elephants (Left) or Rhinos(Right). The referee tells you which player's turn it is by specifying the value of the playerId parameter. You can use that by testing against some constants I set up in the CombinatorialGame class. Here's an option for a template: 

... {
    ArrayList<String> spaces = position.getSpaces();

    if (playerId == CombinatorialGame.LEFT) {
        //modify spaces to move an elephant
    } else if (playerId == CombinatorialGame.RIGHT) {
        //modify spaces to move a rhino
    } else {
        //this case should never happen!
        System.out.println("Error!");
    }
    return new ElephantsAndRhinos(spaces);
}
Each element in the array-list of strings can have one of three values, which I've referenced using constants:
  • ElephantsAndRhinos.EMPTY
  • ElephantsAndRhinos.RHINO
  • ElephantsAndRhinos.ELEPHANT
You can check out the code to see how I did this. (Notice I used Javadoc to describe the constants; if you build the Javadoc, you can see the entry for each of them.) The reason for using constants here is that if I decide that I want to change the values for the elements, I can just change those constants instead of changing where I used them in all my other code! You can use my template and the other methods you've already written to move the first Elephant you see on their turn:
    ...
    if (playerId == CombinatorialGame.LEFT) {
        //move the first elephant
        ArrayList<Integer> elephants = moveableElephants(position);
        int first = elephants.get(0);
        spaces.set(first, ElephantsAndRhinos.EMPTY);
        spaces.set(first+1, ElephantsAndRhinos.ELEPHANT);
    }
    ...

Part 12, 20 points: Modify your code so that getMove always returns a legal move, for both players. I usually start by making the easiest move I can think of. You can test your code by using a referee in your testing class. I recommend running a gauntlet of lots of runs and making sure you don't have any forfeits. To test your player in both the Left and Right roles, add it to "both sides" of the referee:

Player<ElephantsAndRhinos> me = new ElephantsAndRhinosPlayer();
Player<ElephantsAndRhinos> random = new RandomPlayer<ElephantsAndRhinos>();
int maxLength = 10;
double density = .3;
PositionFactory<ElephantsAndRhinos> factory = new ElephantsAndRhinos.PositionBuilder(maxLength, density);

//your player as Left
Referee<ElephantsAndRhinos> ref = new Referee<>(me, random, factory);
ref.call();
ref.gauntlet(100);

//your player as Right
ref = new Referee<>(random, me, factory);
ref.call();
ref.gauntlet(100);
Remember:
  • Always make legal moves
  • Don't use randomness
  • Don't use the getOptions() method.

Part 13, 40 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 ≥25%: 10 points
  • Win ≥37%: 15 points
  • Win ≥42%: 25 points
  • Win ≥59%: 30 points
  • Win ≥72%: 40 points
  • Win ≥74%: 45 points
  • Win ≥76%: 50 points

Submitting your Project:

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

  • ElephantsAndRhinosPlayer.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>Project1, 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: kburkeProject1.zip or burkeAndStockProject1.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.