Due: Friday, 17 September 2021
Navigation
- Introduction
- The Puzzle
- Play Time
- Program Design
- Instrumentation and Testing
- Discussion
- Submission and Version Control
Introduction
This initial programming assignment is intended to give you a chance to get familiar with Java and the various tools used in the course. This project is smaller in scale compared to the other three projects you will complete this semester. However, you may still find it challenging and we encourage you to start as early as possible. You should have completed Lab 1 and Lab 2 before starting this assignment as they contain import setup steps.
We will be grading solely on whether you manage to get your program
to work (according to our tests, which are provided to you in the
skeleton) and to hand in the assigned pieces. There is a slight
stylistic component: the submission and grading machinery require that
your program pass a mechanized style check (style61b
), which mainly
checks for formatting and the presence of comments in the proper
places. See the style61b guide for a description of the style it
enforces and how to run it yourself.
First, make sure that everything in your repository is properly updated and checked in. Before you start, the command
cd ~/repo
git status
should report that the directory is clean and that there are no untracked files that should be added and committed. Never start a new assignment without doing this.
To obtain the skeleton files (and set up an initial entry for your project in the repository), you can use the command sequence
git fetch shared
git merge shared/proj0 -m "Get proj0 skeleton"
git push
from your repo directory. Should we update the skeleton, you can use the
same sequence (with an appropriate change in the -m
parameter) to update your
project with the same changes.
The Puzzle
The puzzle game Flood is one of Simon Tatham's
collection of GUI games (available on a variety of operating-system
configurations, including Ubuntu.) He in turn got the idea from a now-defunct
web site: http://floodit.appspot.com
. In this
project, you are given an incomplete Java program that creates these
puzzles and allows its user to solve them, and you must supply the
missing parts to complete the implementation.
The puzzle itself is quite simple. It is played on a $W\times H$ rectangular grid of square cells. Every square is colored from a set of available colors. We'll use the term active region to refer to the set of grid cells having the same color as the upper-left cell and orthogonally reachable from that square. A cell is orthogonally reachable from a square S having color C if it can be reached by moving one square at a time up, down, left, or right starting from S and moving only to squares of color C.
Each time the player clicks on a square with a color different from that of the active region, all the cells currently in the active region take on that color. So if there are cells of this color adjacent to the active region, they get added to the active region.
The player's goal is to make all cells the same color by clicking a series of cells. The program sets an upper limit on the number of moves, depending on its own determination of how many moves are needed.
As an example, consider starting from the board labeled 0/7 below. The subsequent numbered boards that follow result from clicking on cells whose colors are, respectively, green, yellow, red, green, yellow, blue, and red. This results in an all-red board in 7 moves.
Here is an optional conceptual quiz to check some of your understanding about the game.
Play Time
The first step in tackling the project is to play the game. That is, you should familiarize yourself with what the final product should look like. You can do so by playing the game on an instructional machine using the staff solution program.
On the instructional machines (only), you can run the staff version of this program with the following command:
staff-flood
It takes the same options as your project (see Instrumentation and Testing).
If you are working on your local computer you will have to SSH into your instructional machine to run the staff solution. To allow the GUI of the program to appear via SSH you will have to follow the instructions here: Staff GUIs over SSH. Section C of the linked guide will show you how to SSH to your instructional machine with X11 forwarding enabled (which allows to view the staff solution's GUI on your local computer over an SSH connection).
Once you are on an instructional machine, run the following command:
staff-flood --log
This command starts the flood program (specifically, the one
implemented by the course staff). The --log
option will output
information about the program's execution. Every time the program is
invoked, it creates a flood puzzle board with some randomly
selected colors. In your terminal you will see an output very
similar to the following:
PUZZLE
6 6 4
0 2 2 2 3 1
1 2 3 0 3 2
0 2 1 1 0 2
3 0 0 1 1 1
1 2 3 0 0 1
0 3 3 3 2 2
7
ENDPUZZLE
This is a log of the program's execution, describing its operations. The first line, PUZZLE, indicates that a puzzle follows. The second line indicates that it is a $6\times 6$ flood puzzle with 4 colors (numbered 0 to 3). The next 6 lines define the solution of this puzzle, which happens to be the one illustrated in the The Puzzle section. The colors are denoted by small integers. How these map to actual colors when viewed is largely irrelevant to the logic of the program. In fact, the GUI (Graphical User Interface) is the only component of the project that has this information, using it to convert the numbers you see to colors. In our version of the project the colors are red for 0, yellow for 1, green for 2, dark blue for 3, orange for 4, purple for 5, brown for 6, light blue for 7, pink for 8, and light green for 9. The next line indicates that there is a limit of 7 moves to solve the puzzle. Finally, ENDPUZZLE indicates that this board is done initializing.
If you want to always get the same board, you can use the seed option as in the following example:
staff-flood --seed=42 --log
The same seed number produces the same random sequence, which will make the puzzle generated deterministic (you will get the same starting board each time). This way bugs and other behavior can be reproduced.
Now that the puzzle has been generated by the program, it's time to play the game. If we click on, say, the leftmost green (color 2) cell in the bottom row, the program would output the following log message
SET 5 4
meaning "turn all cells in the current active region the same color as the cell in row 5, column 4." This has the effect of expanding the current active region to include adjacent green cells.
Program Design
The skeleton exhibits a design pattern in common use: the Model-View-Controller Pattern (MVC).
The MVC pattern divides our problem into three parts:
- The model represents the subject matter being represented and acted
upon—in this case incorporating the state of a board and the rules by
which it may be modified. Our model resides in the
Model
class. - A view of the model, which displays the puzzle state to the user.
Our view resides in the
GUI
andBoardWidget
classes. - A controller for the puzzle, which translates user actions into
operations on the model. In our case, it also notifies the view when the
model has been modified. Our controller
resides mainly in the
Controller
class, although it also uses the GUI class to read mouse clicks.
Your job for this project is to modify and complete the Model
,
PuzzleGenerator
, and BoardWidget
classes. We've marked places
that need attention with comments containing "FIXME
" (the style
checker will point these out to you should you forget to fix one).
Don't let that stop you from looking at all the other code in these
classes. That's actually part of the point of giving you the
skeleton. You can learn a great deal about programming by reading
other people's programs. It is unlikely that you will be able to
complete the "FIXME
"s successfully without understanding the
majority of the provided code in the aforementioned classes.
Initially, the skeleton contains some dummy code. Running the
skeleton program actually won't result in anything (it will error),
so you will have to address some of the FIXME
s before actually
getting to play your own version of the game.
Getting Started
This project is largely an exercise in reading someone else's program and understanding its intent, which is actually a common activity in "real-world" programming as well.
You'll see numerous uses of parts of the Java library we haven't
talked about. However, you have seen all these data structures in
Python. Where Python has lists, Java has arrays, ArrayList
s,
ArrayDeque
s, and LinkedLists
(among others). Where Python has
dictionaries, Java has HashMap
s and TreeMap
s. Where Python has
sets, Java has HashSet
s, TreeSet
s, and BitSet
s. These and many
more library classes are all defined in the online Java library
documentation, which should constitute much of your bedtime reading
for this semester. This said, you won't fully understand these Java data structures only by reading about them, but by using the documentation along with writing code to use them.
Say, for example, that we wanted to create a list to hold integers.
You could investigate the ArrayList Documentation, and find that
in order to create an empty ArrayList
called newList
, you would
write a line of code such as
ArrayList<Integer> newList = new ArrayList<>();
If you wanted to add the numbers 1 through 4 to newList
, and print out whether 4 is in newList
you could write:
newList.add(1);
newList.add(2);
newList.add(3);
newList.add(4);
if (newList.contains(4)) {
System.out.println("4 in newList");
} else {
System.out.println("4 not in newList");
}
We've gone to some pains to provide comments that actually indicate what things do (in sharp contrast, I fear, to standard practice these days). We'd like you to get into the habit of doing the same.
Reading and trying to understand these files and comments before beginning programming will be well worth the time. Spending up-front time before writing code can feel a bit counterintuitive at first. If you begin writing code before making an attempt to understand the preexisting code, you will likely struggle more. You need not understand every line of the given code, but you should strive to understand the different objects, their instance variables, what their instance methods do, and how the methods relate to one another. The comments in line with the methods and instance methods are a great way to begin learning about the code.
Before you start working on a particular class, you must read the
comment above the class to understand the object at hand. Then,
continue to the bottom of the class to read about its instance
variables. Finally, read the comments of the methods that were
provided for you. Only after this exercise you will be truly prepared
to tackle the first "FIXME
".
A note on style: you will see that all instance and static variable names are preceded by an underscore. The underscore gives these variables no special powers. It is merely a visual signal to the programmer that a variable is an instance or static variable of a class.
This project makes considerable use of abstraction; the simpler functions you write will be instrumental in helping you accomplish more complex goals. Be sure to respect the abstraction barriers to minimize the impact of bugs or logical errors in your code. Further, if you find yourself bogged down by the details of a particular method, consider pausing to break it down into "helper" functions, each performing some coherent piece of the original function (only, as a stylistic matter, do give these new functions descriptive names, generally avoiding the word "helper" in the name.)
Detailed Overview of the Skeleton
We recommend that you complete the FIXME
s in the order specified here.
Some FIXME
s will depend on how you handle the other FIXME
s, so you might
need to go out of this recommended order, or go back to a FIXME
that
you previously handled.
Place
You need not do anything to the class Place
(full name
flood.Place
). It exists simply as a sometimes convenient way to
refer a (row, column) position on a puzzle board as a single quantity.
So, a Place
in variable pl
denotes the position (pl.row,
pl.col)
. The programmer can convert a row and column into a Place
using the method pl
(an example of what is called a factory
method).
Later in the course, we'll get into what other methods in the class are
there for.
The method equals
compares two Place
s for equality.
An interesting fact: thanks to our use of the pl
method to create Places
,
it turns out that equals
happens to return the same value as the ==
operator, something that is not generally true for objects in Java. Again,
there will be more about such subtleties later in the course.
Model
The Model
class (full name flood.Model
) contains the current state
of the puzzle board. That is, it tells what squares it has, what
color each square currently has. It also has some useful additional
information: how many moves there have been, how many moves are
allowed for solving the puzzle, what squares are marked (when you play
the staff version, you will see that using the "Solve" menu item marks
suggested squares to click on), whether the puzzle has been solved, and what
the previous positions have been. All this information is presented to
users (or "clients") of the Model
class in the forms of methods that can be
called (using the myBoard.methodName(...)
syntax familiar from Python, C++,
and other object-oriented languages).
Our problem is to figure out how to
represent this information so as to make it possible to implement these
methods. We represent the information with instance variables (generally
marked as private
in the skeleton; we'll discuss access modifiers such as
public
and private
later in the course.) A convention used in this course
is to give these instance variables names beginning with underscores to
distinguish them from classes, methods, local variables, and non-private
variables (mostly symbolic constants in our case).
For this project, we've already provided the necessary representation variables, which you should try to understand before implementing things. Of particular importance:
_cells
A two-dimensional array of non-negative integers all of which are less than
the value of _ncolors
, representing the colors of the squares.
In Java, a 2D array is an array of arrays (like a list of lists in Python).
We've set things up so that the integer representing the color of the square at
row R
and column C
is contained in _cells[R][C]
. The correspondence
between integers and colors is arbitrary; the classes representing the
graphical user interface (GUI), especially BoardWidget
, basically decide how
to display these integers as colors.
_active
A set containing the Places
contained in the active region.
This information is redundant, since the rules of the puzzle tell you what the
active region must be given the colors of the squares. We keep it for
convenience. Sets in Java are represented by a number of types, all described
in the Java library documentation. This particular set is a HashSet
, which
is implemented similarly to sets in Python.
_marks
, _readOnlyMarks
The programmer can "mark" certain cells in the Puzzle (used in this
program to indicate squares that would or could be added to the active region).
Both of these instance variables refer to exactly the same data, but
readOnlyMarks
can't be changed, and therefore can be safely returned to
clients of Model
without allowing them to fiddle with it on the side.
_history
A list of puzzle contents leading up to the current position. This is useful
for implementing the undo
function. The elements of the list are
GameStates
, a class whose use is restricted to Model
and which represents
a combination of 2D array and active region.
Methods of Model
When starting the project, it will be helpful to use the unit tests in
the skeleton as sanity tests to make sure you are writing correct
code. If you run the tests in ModelTests.java
on the skeleton code,
11 tests will fail, and 5 tests will pass. As you complete FIXME
s,
more of these test should start to pass, and all tests should pass
upon completion of the project. We suggest that you implement the
incomplete methods of Model
as follows:
solved
What tells you that a puzzle is solved? You could check that all squares are the same color, but is there a faster way, given the instance variables available to you?
colorsPresent
Indicates which of the available colors (numbered from 0, inclusive, to
_ncolors
, exclusive) are actually present in the current state of the puzzle.
colorsPresentTest
in ModelTests.java
should pass after
you complete this method.
forNeighbors
We've included this one to illustrate how Java handles higher-order functions
(those that take functions as arguments or returns them as values). Java
in fact does not have such functional values, unlike Python or C++.
Instead, it uses its object-oriented features: instead of a function, f
that one calls with syntax like f(3)
, it represents f
as an object
whose class implements a method with some specified name
(in our case, .accept
) so that one can instead get the desired effect as
f.accept(3)
. Then, as is the case with Python, one can pass in different
objects with different implementations of accept
to get the effect of
passing in different functions. The type Consumer<Place>
is a library
class with an accept
method that takes a single argument of type
Place
and returns nothing. Java has a special syntax for defining objects
of type Consumer<...>
that is essentially a lambda expression (as in Python).
Thus, instead of writing lambda pl: <do something with pl>
, one instead
can write (pl) -> <do something with pl>
. There are examples of the syntax
in the class GUI
(see the constructor, GUI(String title)
).
You can also see how the forNeighbors
method is used in checkNeighbors
in ModelTests.java
.
We'll go into this in lecture as well.
The method call someModel.forNeighbors(pl, doSomething)
,
calls doSomething.accept
on each neighbor (above,
below, to the left, and to the right) of pl
that is present in someModel
.
After completing this method successfully, forNeighborsTest
in
ModelTests.java
should pass.
findRegion
This method finds orthogonally reachable cells starting at a given
Place
(start
) and having a given color, and adds them to a given
set (result
). The comment mentions that the method does not use cells that
are already in result
at the beginning of the method. You might want to
think first about how this provision might be useful
(hint: there is a recursive approach, but we have to prevent infinite recursion
somehow).
As the internal comment suggests, you can use forNeighbors
to good effect
here. You don't have to, but it's a good idea to figure out how you would
use it.
numMoves
The number of moves from the start (adjusted for any undo
and redo
operations). This is included mostly to see if you
understand the representation.
roundOver
This simply tells you whether the puzzle has been solved or the player has run out of moves.
setActiveRegionColor
This is the method that actually does the work of responding to a move on the part of the user. Implementation is pretty simple once you understand the representation. Try and make use of the other methods that you have already implemented to make this task less difficult.
adjacentCells
This method finds the set of squares that would be added to the active
region if the current active region was the passed color. The comment
indicates that you are free to use markedCells
(and therefore the
_marks
variable) if you want to implement it. Just how you do this
is entirely up to you, and you needn't
use it at all.
copy constructor (i.e., Model(Model model)).
The things that look like methods except that they don't have return types and
have the same name as the class are constructors, like the __init__
method in Python. That is, they initialize the contents of a newly created
object. You might first want to look at the other constructor (with
parameters initial
and ncolors
), which should, among other things, help you
understand the representation of Model
. A copy constructor is one that
initializes an object from an already existing one. The one in the skeleton
is missing some things (i.e., fails to initialize some of the instance
variables properly). You should determine what these are and remedy the
situation.
Be careful to observe the sentence about not "sharing structure" between the
argument being initialized and the model
argument. For example, if you were
to initialize _cells
with a statement
_cells = model._cells;
You could easily get into difficulty, since any changes to the contents of the
model
argument would also happen to the newly initialized Model
, and
vice-versa.
PuzzleGenerator
This class contains the logic for creating new puzzles at random. Its
representation contains a pseudo-random number generator, an object
(_random
) with
methods that return numbers that have many of the statistical characteristics
of sequences of integers selected by random natural processes. In fact,
however, they are only pseudo-random, in that they actual come out in
a deterministic and reproducible sequence (good for debugging). Be sure to
find and read the documentation on the library class java.util.Random
to
see what is available. HW 1 may also be
helpful when it comes to getPuzzle
.
getPuzzle
This method creates a Model
using the first Model
constructor (the
one you didn't have to implement). The problem is to come up with its
arguments, and then use any other methods needed to provide a puzzle
Model
that meets the requirements given in the comments in
PuzzleSource.getPuzzle
. Why look at that particular comment?
Because PuzzleGenerator
overrides that method, and therefore (to
conform to proper object-oriented practice, a subject we will be
considering later). The intended use of the argument extra
is to indicate
how many moves should be allowed for solving the puzzle, which should be
extra
moves more than your Solver
's guess as to how many moves are needed.
Thus when extra
is 0, you are requiring that the user solve the puzzle in
no more than the number of moves your Solver
algorithm estimates are needed.
Solver
The class encompasses the logic for solving puzzles that you generate.
You use this to determine what the move limit should be for the
puzzles generated in PuzzleGenerator
!
movesNeeded
This method estimates how many moves will be needed to solve the puzzle. The
estimate may (in fact, probably will) be higher than the actual minimal number,
but that's fine. It may seem strange to implement this
first (before chooser
), but if you rely on the chooseBestMove
's comment
(and abstract away what actually happens when you call chooseBestMove
),
you should be able to figure out how to use it to implement movesNeeded
.
chooser
This method does the actual solving.
It returns a two-element array, containing the suggested color (one that
is on the board and expands the current active region), plus some measure of
the "goodness" of this move (larger being better).
In order to meet the bare requirements of
this assignment, you needn't actually use the depth
argument at all.
It's basically
there as a suggestion for those of you who'd like to be more ambitious (something
you should consider only after finishing everything else, I advise). The
idea is to provide a maximum number of moves to look ahead when searching for
the best move (i.e., color) to choose for a given puzzle state.
Likewise, the returned goodness value is of no
importance if you are simply looking for any acceptable move, but you
might find a use for it if you choose to make a "smarter" solver. To pass
the tests, chooser
just needs to return a move that increases the size
of the active region.
Instrumentation and Testing
Check out this video for a detailed overview of the testing features!
To facilitate automated testing of your work, there are a few features that you can use to record sessions and to play back moves for testing or debugging purposes. The skeleton is set up so that when you start your program with
java -ea flood.Main --log
you'll get a record on the standard output of all of the edges clicked, all the randomly created puzzles, and all the menu commands entered. The -ea option stands for "enable assertions". Typically logs would be printed to the terminal, but one might want to save them to a file which can be done by capturing a log through redirection. You can capture logs using redirection, like this:
java -ea flood.Main --log > testing/myscript1.in
The --seed
option will allow you to prime the random number generation so that
you can get the same set of random numbers (the same initial puzzle generated)
each time:
java -ea flood.Main --seed=42
The same seed produces the same random sequence, which will make the puzzle deterministic. This way bugs and other behavior can be reproduced.
The --testing
option reads in a script produced by --log
and uses it (in
place of user clicks and random numbers) to supply the results of getPuzzle
and getCommand
. It also prints out a textual display of the initial
board and after each command, which Tester.py
can use to test the
program. For example, to read back the file myscript1
, use
java -ea flood.Main --testing testing/myscript1.in
This will print out what tester.py sees, which it compares to
testing/myscript1.out
. Using --log
and --testing
, you can thus create
your own .in
and .out
testing files to augment the ones we've provided in
testing
.
We have set up the Makefiles in the proj0
directory and in the flood
subdirectory to have targets check
and unit
. In order to use make, you'll
need to install it. Follow the instructions here to do so.
You may have already done so in HW 1.
Once installed, the command
make unit
will run all the unit tests on Model.java
, PuzzleGenerator.java
and
Solver.java
. If you try this on
the skeleton, you'll see that, unsurprisingly, it fails all these tests, giving
you an indication of what needs to be changed.
The command make integration
in the proj0
directory will run
integration tests, which run the program and check its outputs
against expected output using the scripts tester.py
and testing.py
in the testing
subdirectory. Integration tests test all the
program's components together.
Usually, you will probably want to use the command make check
for testing,
which runs both the unit and integration tests.
By the time you finish the project
make check
should report no errors. If your
python command is python
rather than python3
you will need to use
make PYTHON=python check
to run the integration tests.
Running Integration Tests in IntelliJ
Integration tests used in make check
are stored under the
proj0/testing
folder. If you would like to run an integration test
in IntelliJ so that you can use the debugger, use the following steps:
- Navigate to the Main class in IntelliJ and open it.
- Click on Run > Edit Configurations...
- In the left sidebar of the pop-up window, under "Application", select Main.
- For "Program arguments", put in
--testing testing/<test_file>
where<test_file>
is the name of the file of the integration test you would like to run.
For example, if you would like to run integration test 1, you should have
--testing testing/01-fullgame1.in
as your program arguments.
- Now you can click Run > Run 'Main' or Run > Debug 'Main' to run and use the debugger on the integration tests. Remember to set a breakpoint if you're debugging!
Submission and Version Control
It is important that you commit work to your repository at frequent intervals. Version control is a powerful tool for saving yourself when you mess something up or your dog eats your project, but you must use it regularly if it is to be of any use. Feel free to commit every 15 minutes; Git only saves what has changed, even though it acts as if it takes a snapshot of your entire project.
The command git status
will tell you what you have modified, removed, or
added since the last commit. It will also tell you what you have
not yet sent to your central repository. You needn't just assume that things
are as you expect; git status
will tell you whether you've committed and
pushed everything.
If you are switching between using a clone of your central repository on the instructional computers and another at home (or on your laptop), be careful to synchronize your work. When you are done working on one system, be sure to push your work to the central repository:
git status # To see what needs to be added or committed.
git add <filepath> # To add, or stage, any new files.
git commit -a -m "Commit message" # To commit changes.
git push
If you start working on the other system, you then do
git status # To make sure you didn't accidentally leave
# stuff uncommitted or untracked (if you did, commit
# it before doing the next step.)
git pull --rebase # Get changes from your central repo.
Submit your project by committing and tagging it:
git tag proj0-0 # Or proj0-1, etc.
git push
git push --tags
Be sure to respond to all prompts and to make sure the messages you get indicate that the submission was successful. Don't just "say the magic words" and assume that everything's OK.
Grading Details
For Project 0: Flood, style will be worth 2 points, passing the unit tests will be worth 6 points, and passing the integration tests will be worth 8 points.
Checking in your code (adding, committing and pushing) and pushing tags will submit your code to the autograder on Gradescope. You can see your score and details about your submission there. There will not be hidden test on this project, though there well may be in future projects, so please practice writing your own tests!
In order to encourage testing your own code without relying on the autograder, you will be able to submit once per hour. Starting the day the assignment is due (9/17), you will be able to submit four times per hour. From 12PM (Noon) PT on the day the assignment is due until the deadline, you will be able to submit as many times as you want. It will likely be very difficult to get full credit on this assignment if you wait until the last minute, so please use the limited submissions you have wisely. The unit and integration tests that you have are the same as the tests the autograder runs, so you shouldn't need to submit to gradescope too often, only when you want an idea for your final score.
The idea behind this policy is that we want you to get out of the habit of using the autograder to test and debug your program. Ideally, you would have already thoroughly tested your code before submitting it and would need only a few submissions. However, we understand that this can be difficult for beginning programmers, so we'll be pretty loose on submissions.