Project 0 | CS 61B Fall 2021 Main Course Info Staff Beacon Resources Piazza Navigation Due: Friday, 17 September 2021 Navigation Introduction The Puzzle Play Time Program Design Getting Started Detailed Overview of the Skeleton Place Model _cells _active _marks, _readOnlyMarks _history Methods of Model solved colorsPresent forNeighbors findRegion numMoves roundOver setActiveRegionColor adjacentCells copy constructor (i.e., Model(Model model)). PuzzleGenerator getPuzzle Solver movesNeeded chooser Instrumentation and Testing Running Integration Tests in IntelliJ Submission and Version Control Grading Details Project 0: Flood 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 and BoardWidget 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 FIXMEs 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, ArrayLists, ArrayDeques, and LinkedLists (among others). Where Python has dictionaries, Java has HashMaps and TreeMaps. Where Python has sets, Java has HashSets, TreeSets, and BitSets. 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
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 FIXMEs in the order specified here. Some FIXMEs will depend on how you handle the other FIXMEs, 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 Places 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 FIXMEs, 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 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: , one instead can write (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/ where 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 # 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.
