Data Structures

Overview

In this Lab, you will work with a simple Cat Island game made using object oriented programming, in order to gain confidence working with objects.

The world of “Cat Island” is made using Objects to represent Cats, Islands, Tiles on the island, and Colors. The Cat class for this lab is different than the one shown above.

Each Island object contains a 2D array of Tile objects. Each tile can represent either land or water. If the Tile is land, it can be empty, contain either a yarn, or contain a cat. Cat objects exist on a tile on a Island, and contain attributes representing their (row, col) coordinates. Cats contain .moveLeft(), .moveRight(), .moveUp(), and .moveDown() methods

After reading the rest of the description, click “Play Intro” in the CatIsland Driver to see a demonstration of the CatIsland world and methods.

Provided Classes

In CatIsland, everything is represented by Objects. This includes Cats, Islands, and the Tiles (which makeup each island). In the project folder, you are provided the java files for these classes, Cat.java, Island.java, and Tile.java, and will work with each in CatIsland.java to solve each island.

Cat.java: This class represents a Single cat. This is the class you will be working with most to solve Islands 1-5 in CatIsland.java. Don’t edit this file.

• Attributes:
  • name, a String variable holding this cats name
  • yarnCollected, and int variable holding how much yarn this cat has collected. Starts at 0.
  • homeIsland, and Island variable holding the island this cat is on.
  • coords, a Coordinate variable which holds the int row and int col values for this cat.
  • color, a Color variable which can be 1 of 5 colors defined in constants/Color.java
  • NOTE: All of these are private variables, meaning you cannot access them directly. Instead, you’ll need to use the getter method for each variable. See the methods section below.
    • Private variables are used to control access, and in this case, make the values read-only
• Methods:
  • public Cat(String name, Island home, int row, int col, Color color), the constructor for this cat. It takes in necessary information about the cat, and then sets the above attributes accordingly. You must call this constructor with the new keyword. i.e. Cat c = new Cat(“CatsName”, fakeIsland, 2, 3);
    
  • moveLeft() which moves the cat left on its island (column -= 1)
  • moveRight() which moves the cat right on its island (column += 1)
  • moveUp() which moves the cat up on its island (row -= 1)
  • moveDown() which moves the cat down on its island (row += 1)
  • numStepsTaken() returns and int equal to the total moves this cat has made.
  • Getter Methods: These methods simply get and return the value of private attributes.
    
    • getName(), getColor(), getRow(), getCol(), getIsland(), numYarnCollected()
  • NOTE: These are all instance methods (aka not static), meaning you need to call these on an object. So you’ll need to make a new Cat, then call these methods on that cat.
    • i.e. Cat c = new Cat(“CatsName”, fakeIsland, 2, 3);       THEN       c.moveLeft();

Island.java: This class represents an Island. Cats deal with the island itself when moving, but in solveIsland4() you will work with the island directly. Don’t edit this file.

• Attributes:
  • island, a 2D array of Tile objects. You can visualize this as a chess board with either green (land) or blue (water) tiles, in any arrangement.
    • This is accessed by island[row][col], which is why we refer to coordinates as (row, col) instead of (x, y)
    • island[0][0] is the top left tile on the island when visualizing in the Driver.
• Methods:
  • public Island(Tile[][] island), the constructor for this island. It takes in a string array of tiles and creates an island for them. This method is only used in the Island class itself, as in the next lab we use the Island.createIsland() method instead (shown below).
    
  • public Tile[][] getTiles(), this is the getter method for the tile array. This is how you will acces and modify the island for solveIsland4()
  • public static Island createIsland(String[][] toParse) this is a static method which creates an island based on an input array. You will use this method in the next lab, but not this one.
  • public static Island copyIsland(Island s) this is a static method which returns an exact copy of the given island s.

Tile.java: This class represents a single tile on an island. The Island class stores a 2D array of these to represent an island. Don’t edit this file.

• Attributes:
  • type, a String variable which will either equal “L” for land or “W” for water.
  • hasYarn, a boolean variable which is true if this tile is Land and contains a yarn ball. If it is false, this tile does not contain a yarn ball.
  • cat, a Cat variable which holds the cat on this tile if there is one. If there is no cat on this tile, then it is equal to null (representing nothing).
  • row, an int representing what row this tile is in on its island.
  • col, an int representing what column this tile is on its island.
• Methods:
  • public Tile(String type, boolean yarn, int row, int col), the constructor for this Tile. It takes in necessary information about the cat, and then sets the above attributes accordingly. You must call this constructor
  • public boolean isLand(), this method returns true if this tile is equal to Tile.LAND (aka if this.type == “L”).

CatIsland.java: This is the class you will code in and submit to autolab. You will fill in the solveIsland1() through solveIsland5() methods, each containing solutions to the corresponding islands shown in the Driver visualizer (and the descriptions below). 

Driver.java: This class is a visualizer for CatIsland world for this assignment. When you run it, you will see a menu bar containing 6 buttons. The first is a short text intro introducing you to the island. Buttons 2-6 correspond to Islands 1-5, which each have challenges you must solve in CatIsland.java. After selecting an island, you can run your solution using the Run Island button at the bottom, at your preferred speed.

SPECIAL CLASSES

In the “island” package folder, there is a sub-package titled “constants”. These contain two simple classes which we use for specific purposes.

CatInWaterException.java is an Exception class, indicated in its class declaration by “CatInWaterException extends Exception“

• Note: we will talk about Class inheritance and the extends keyword in Lab 2.
• An Exception is a java runtime error, meaning an error that is caused by the program when it runs, which can’t be predicted before it runs (like doing calculations and accidentally dividing by 0, or accessing an array with a too large index).
  • Programs throw exceptions, which normally means the program will stop running because of the error. But you can use a try-catch statement to wrap code, and handle errors if they occur.
• In this lab, the Cat.java class will “throw” a CatInWaterException if your cat falls in the water. This then gets “caught” by the Driver using a try-catch statement, which stops the simulation. No other Exceptions will get caught by the Driver, as these mean there’s a problem with your code.

Color.java is an Enum class, indicated by its class declaration “public enum Color”

• An Enum is a simple object which represents constant values. In this case, the enum contains 5 values representing 5 different cat colors (orange, white, brown, black, grey). You will use these values to choose the color of your cats in solveIsland4()
• These values are static, meaning they are accessible through the class itself.
• i.e. Color.WHITE, Color.BROWN, Color.ORANGE…

Directions

• DO NOT add new import statements.
• DO NOT add any new class attributes
• DO NOT change any of the method’s signatures.
• DO NOT modify the given constructor.

Note about Coordinates:

To complete this Lab, you will fill in CatIsland.java with the solutions for solveIsland1() through solveIsland5(). These will require working with Cat objects to traverse islands, as well as working with the island object itself.

To Run: run the following 3 commands from the innermost CatIsland directory, containing the src and bin folders.

1. javac -d bin src/island/constants/*.java
2. javac -cp bin -d bin src/island/*.java
3. java -cp bin island.Driver

OR: Run through VSCode, ensuring you open the correct innermost CatIsland directory,

solveIsland1()

Island 1 is a 4×4 island, which consists of a 2×2 of land tiles in the center, surrounded by water tiles. The island contains two pieces of yarn.

You are given a Cat via the method parameters, which will spawn at (row 1, column 1). Make the cat collect both yarn on the island then return to (row 1, column 1).

The cat you’re given is already instantiated, so you can simply call cat.moveLeft(), cat.moveUp(), cat.moveRight(), and cat.moveDown() to move the cat around on the island. The cat will automatically collect yarn when it steps on one.

To solve this island, simply traverse all land tiles (aka moving the cat right, down, left, and up OR down, right, up, and left) by using the corresponding cat move methods.

How to test: run the driver (see the How to open + run section below), then select “Island 1”. Run the island, then see the steps the cat takes and if it meets the expected goals.

solveIsland2()

Island 3 is a 7×7 island, which consists of a 3×5 of land tiles in the center, surrounded by water tiles. The island contains NO pieces of yarn.

Same as solveIsland1(), you are given a Cat via the method parameters which you will control. This cat will spawn at (row 3, col 2). Your goal is to make the cat step on every land tile exactly once. You can take any route to do so.

Note: Since the Cat starts on (3,2), ensure that you do not step on this tile again.

solveIsland3()

Island 3 is a 7×7 island, which consists of a bowtie shape of land tiles in the center, surrounded by water tiles. The island contains 4 pieces of yarn.

Same as solveIsland1(), you are given a Cat via the method parameters which you will control. This cat will spawn at (row 3, col 3). Your goal is to make the cat collect all the yarn on the island. You can take any route to do so. Remember, to collect yarn, simply make the cat step onto that tile.

solveIsland4()

Island 4 is a 5×5 island, which consists of two masses land tiles, seperated from each other by water tiles. Each landmass has a cat on it, and the island contains no pieces of yarn. Your goal is to modify this island, by adding land, yarn, and a cat.

In solveIsland4(), you are not given either cats as method parameters. Instead, are given the Island object itself. Your goal is to modify this island object to change the island.

To modify the island, you must modify its tiles. The Tiles for an island are stored in a 2D array of tiles, which you can get with island.getTiles(). You can then access any index as a 2D array.

i.e. Tile[][] tiles = island4.getTiles();      THEN       tiles[0][0].hasYarn = false;         // Note: Just a random example

To modify a tile type, set its .type attribute to either Tile.LAND or Tile.WATER (which are both static variables in the Tile class).

To add yarn to a LAND tile, you can set the hasYarn attribute to true for that tile.

To add a cat, you simply call the Cat constructor, and pass in the island and desired row/col coordinates. The cat will place itself onto the island object, you don’t have to.

Note: you’ll need to fill out all parameters when you use the Cat constructor. The cat’s name doesn’t matter. And colors must match those declared in Color.java — scroll to the “Special Classes” section above for more info.

solveIsland5Recursive()

Island 5 is different from the rest, as it will be randomly selected from 5 possible choices every time it is chosen. Every possible choice is a 9×9 island, which contains a singular path from (0,0) to (0,8). The cat will always spawn at (0,0).

You are given solveIsland5() for this task, but you must fill out the method it calls, solveIsland5Recursive(). You will write a simple algorithm which can walk a single wide path from start to finish. 

To do this, first get the row and the col from the cat c. Then, using if statements, check all four directions (down aka (row+1, col), up aka (row-1,col), right aka (row, col+1), and left aka (row, col-1)).

If that direction is 1) in bounds (>=0 and < its row width or its column height) 2) a LAND tile and 3) not equal (!=) to the previous tile (given in the “prev” parameter), then move in that direction. After moving, simply re-call this recursive method and update the prev parameter accordingly. 

Hint: Start with only one case, moving right (since all given islands start that way).