CSCI H343 Data Structures Fall 2023

Project 1: Flood It! 🌊

[Note] This is a group project. Students work in groups of 3 ~ 4 people. After completion, Every group member submits their solutions on Autograder individually.

Table of Contents

  1. The Game
  2. Support Code and Submission
  3. Specifications of flood()
  4. Problem Set

The Game

“Flood It” is a tile coloring game played on a square board of colored tiles.

At each move, the player selects a color by clicking on one of the tiles. The tile in the upper left corner, as well as all connected neighboring tiles of the same color, are changed to the selected color. The objective of the game is end up with all the tiles on the board being the same color while minimizing the number of moves.

If you haven’t played “Flood It” before, please spend some time playing the game so that you can develop an intuition for how it works and formulate strategies for game play before trying to implement anything. There is an online version.

Support Code and Submission

Don’t worry! We have written most of the game here. The project has the following file structure:

.
├── FloodIt.iml
├── README
├── out
├── src
│   ├── Board.java
│   ├── Constants.java
│   ├── Coord.java
│   ├── Flood.java  (your code goes here)
│   ├── GUI.java
│   ├── Game.java
│   ├── Tile.java
│   ├── TimingGraph.java
│   └── WaterColor.java
├── test
│   └── FloodTest.java  (your tests goes here)
└── test_suite.yaml

Download (“Code (green button) -> Download ZIP”) or clone the repository and open it as an IntelliJ project. Run the main() function in src/Game.java (use the green “Play” button next to that function or run the configuration “FloodIt - Interactive”) and you will see an interactive game window:

The game is not working properly at this moment, because the flooded region does not expand when you click on a tile. We need your help! Your task is to implement the flood() function in src/Flood.java. Like prior labs, test your implementation locally by adding test cases in test/FloodTest.java.

After completion, submit three files to Autograder:

⚠️Do NOT submit your tests. Autograder will test the correctness of your implementation using its own test suite.

Specifications of flood()

We would like you to write the flood() function in Flood class.

Input of flood():

The flood() function takes four parameters:

Output of flood():

The flood() function modifies flooded_list by adding the newly flooded tiles. Please note that you are not responsible for changing the color of any tiles.

[Definition 1] We say that a tile neighbors another tile if it is directly above, below, left, or right, that is, sharing a side with the other one.

The Coord class contains some helpful functions:

[Definition 2] An X-colored region is a set of tiles defined as follows:

Given a flooded_list and a player selected color X (parameter color in input), the flood() function should add every X-colored region to the flooded_list, provided that the region contains a tile that neighbors a tile in the flooded_list.

Problem Set

Problem 1: Implementing, Testing and Debugging flood()

Play the game online and observe the behavior of flooding. Program flood() according to the specifications.

Before submitting to Autograder, test your code locally by writing test cases in src/FloodTest.java. We have included a simple test case in that file to get you started.

[Development note] You may submit just Flood.java on Autograder to test the correctness of flood().

Problem 2: Plotting Execution Time and Analyzing Time Complexity

After ensuring the correctness of flood(), we consider its time efficiency.

Run the game in batch timing mode by adding "timing" to the program arguments in the “Run: FloodIt - Interactive” configuration window:

This will display a graph of the execution time (along the y-axis) versus the number of tiles on the board (along the x-axis) and it will save the graph to PNG file named result.png.

[Development note] If flood1() is empty, you may temporarily change the limit for loop variable k in Game.batchTest() to k != 1, so that only flood() is used for plotting. Remember to change k back in Problem 3.

[Development note] If your code is so slow that no graph is produced when running in batch mode, try temporarily reducing the value of MAX_BOARD_SIZE_FOR_AUTOPLAY in src/Constants.java. For each board size, the game is repeated 5 times to reduce the effect of noise. Turning down the NUM_GAMES_TO_AUTOPLAY parameter may save you time during development.

Look at the graph. Answer the following questions in your project write-up:

Problem 3: Comparing Time Complexity Between Implementations

Try to improve the time complexity of your flood function.

Write a new flood functions flood1(), whose execution time does not grow so quickly as the number of tiles increases. When you run flood1() in batch mode, the timing for the alternate implementation will show up as a gray line.

Swap the names so that your most time efficient implementation is named flood(), so that it will be the version used interactively. Re-run with "timing" and produce a graph, in which the line of the most efficient version is in red.

Last Step: Checking Your Submission

Make sure all three files were submitted: Flood.java (both flood() and flood1()), result.png and README.md.