Project 0 | CS 61B Fall 2021 Main Course Info Staff Beacon Resources Piazza Navigation Due: Friday, 2/11 11:59 PM PT Navigation Useful Links and Updates Introduction The Puzzle Play Time Text Language Program Design Getting Started Detailed Overview of the Skeleton Piece Model _cells _hand _score and _streakLength _history Methods of Model The Constructors get(int row, int col) placeable(Piece piece, int row, int col) and placeable(Piece piece) place(Piece piece, int row, int col) The Hand Methods: handSize(), handUsed(), piece(int k), clearHand(), and deal(Piece piece) place(int k, int row, int col) rowColumnCounts() scoreClearedLines(int nrows, int ncols) clearFilledLines() roundOver() undo() and redo() PuzzleGenerator Instrumentation and Testing Running Acceptance Tests in IntelliJ Submission and Version Control Grading Details Project 0: Blocks Due: Friday, 2/11 11:59 PM PT Navigation Useful Links Introduction The Puzzle Play Time Program Design Instrumentation and Testing Discussion Submission and Version Control Useful Links and Updates Update 2/4: The IntelliJ Style checker plugin is inconsistent with the style checker used on the autograder. To correctly check style locally, use make style. Getting Started Video Testing Tips 1: Unit Tests Testing Tips 2: Acceptance Tests Testing Tips Slides Placeable Slides 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 important 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. As usual in CS 61B, the score you receive on Gradescope will be your final score on this assignment. 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 Blocks puzzle in this project has numerous variations available on the web and in mobile apps (for example, you can play an online Blocks Puzzle). You are presented with a grid of square cells (initially empty) and a set of some number of pieces formed from configurations of square, cell-sized blocks (we'll call these pieces the hand), which you try to arrange in order to cover empty cells of the grid. After each piece is placed, any rows and columns of the grid that have become completely filled are cleared. After you place all the pieces in the hand, it is refilled with the same number of pieces as before. Play continues until none of the pieces in the hand can fit anywhere on the board. For example, consider the board on the left below. The middle piece of the hand (shown below the board) may be placed at either of the places indicated by the pink-shaded areas. If we choose to place its reference point on the square (1,0) (row 1, column 0), we get the middle board. (The reference point of a piece refers to the upper left corner of the smallest rectangle that contains the piece. Depending on the shape of the piece, it may or may not actually be filled. For example, the first (middle) piece we placed had its reference point filled; the second (leftmost) piece did not.) If we then place the leftmost piece at the pink-shaded position on that board (so that its reference point is at row 2, column 5), we will fill all of row 2, which will then be cleared to yield the board on the right. By default, the board consists of 64 cells in an 8x8 grid, and the hand contains three pieces at a time. Your program will be able to change these parameters to make boards and hands of varying sizes. Scoring: One point for each cell that gets filled by a piece One point for each cell that then gets cleared Bonus for clearing at least one row or column. The bonus is the total number of cells in all cleared rows, plus the total number of cells in all cleared columns, then multiplied by the number of consecutive moves in which at least one line or column was cleared. When using the GUI (Graphical User Interface), scores appear above the board, as shown below. For example, assume that in the board at the left above, the previous move added a piece without clearing any squares. Inserting the rightmost piece in the hand at the position indicated by the pink shading yields the middle board. The piece added contained 4 cells and caused the clearing of one row and one column, which cleared 15 cells (the cell at (0,2) is counted only once). Since row 0 and column 2 were cleared (both with 8 cells), we get a bonus of 16 (this time, square (0, 2) is counted twice). Since we assume that the previous move did not result in clearing, the number of consecutive moves in which a row or column is cleared is 1 at this point, so that placing this piece results in a score of $4+15+1\times16=35$, and the score for the round increases to 185. Now we add the indicated piece to the middle board at the pink-shaded position. This adds 3 cells and then clears 8 (one row). Since with this move, the number of consecutive moves that clear a row or column is 2, this leads to an additional $3 + 8 + 2\times8=27$ points, bringing the total for the round to 212. Play Time The first step in tackling the project is to play the puzzle. That is, you should familiarize yourself with what the final product should look like. To execute your own version of the program (after compiling it), use the command java -ea blocks.Main from within your proj0 directory, or run it in IntelliJ. To compile your program, use the command make in the proj0 or proj0/blocks directories. 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. At first, of course, this program, being incomplete, will not really work. So, you can play the game using the staff's version of the program, which is stored as an executable in the cs61b-software directory: cd $HOME/cs61b-software/bin
staff-blocks If the staff-blocks command does not work, try running ./staff-blocks instead. Additionally, if the staff-blocks binary is not in your cs61b-software/bin folder, please run git pull from your cs61b-software directory to get the most up-to-date files. It takes the same options as your project (see Instrumentation and Testing). The staff-blocks command starts our version of Blocks. The --log option will output information about the program's execution. If you want to always get the same hands, you can use the seed option as in the following example: staff-blocks --seed=42 --log The same seed number produces the same random sequence, which will make the puzzle generated deterministic (you will get the same pieces each time). This way bugs and other behavior can be reproduced. Text Language Most users will want to use interactive graphical input and output while playing this puzzle. However, in the interests of making testing easy, we've organized the program to primarly use text as the input. The GUI, in fact, actually enters commands derived from mouse clicks and dragging by translating them into these same text commands. The acceptance tester we provide also uses these commands. To get the staff program to take text input, start it with staff-blocks --no-display The available commands are as follows: new: Clear the board, reset the current score to 0, and deal the first hand. set P R C: Place piece number P from the current hand so that its reference point is at row R and column C. Pieces of a hand are numbered from 0. Piece numbers are "sticky", so that the piece that was originally the rightmost piece continues to have index 2, even when pieces 0 and 1 are removed from the hand and played to the board. board: Print a representation of the board. size NR NC NP: Clear the board and start a new round after first setting boards to have NR rows and NC columns, and setting hands to contain NP pieces. seed S: Set the random seed to S. The seed is used to prime a pseudo-random number generator that drives the selection of pieces for a hand. Specifying the same seed causes the program to produce the same hands (useful for testing and debugging purposes). undo: Go back one move. redo: Redo a previously undone move. 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, it incorporates 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, BoardWidget, and SoundEffect 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 Piece 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, ArrayList, ArrayDeque, and LinkedList (among others). Where Python has dictionaries, Java has HashMap and TreeMap. Where Python has sets, Java has HashSet, TreeSet, and BitSet. 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. Piece The Piece class contains the definition for the pieces that the player places on the grid. Each Piece is essentially a set of positions that are relative to its reference point -- the upper left corner of the smallest rectangle that can encompass all of the filled cells of the piece. If this definition is still confusing to you, take a moment now to look at some example pieces and find their reference points; remember that the reference point of a piece isn't always a filled cell! The only method in Piece.java that will be of use to you is get(int row, int col), which is also the first FIXME that you should fill in. Model The Model class contains the current state of the puzzle board. It is responsible for keeping track of what cells are currently filled on the board, the player's current hand, the current score of the game, the move history, and a few other key components of the game. 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 boolean values which all begin as false, signifying an empty board. As pieces are added to the board and cells are filled in, the corresponding entries in _cells should be set to true. We've set things up such that the state of the cell at row R and column C is given by _cells[R][C]. _hand An ArrayList that contains the "hand" of pieces that are currently available to the player. Values in this ArrayList may be null, indicating that the piece has already been used. _score and _streakLength _score represents the current score of the game based on the scoring system outlined in the "The Puzzle" section. _streakLength represents the current streak of consecutive moves in which the player has successfully cleared a row or column. For example, if the player has cleared a row or column in each of the past 4 moves, then _streakLength should have a value of 4. _history A list of grid contents leading up to the current position. This is useful for implementing the undo and redo methods. The elements of the list are GameStates, a class whose use is restricted to Model and which represents a combination of the 2D grid, the player's hand, the score, and the streak length of the game at that point in time. 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, none of the 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: The Constructors As we will learn more about later, constructors are special types of methods that allow us to create new objects. For now, think of the Model constructors (the methods named Model(int with, int height) and Model(Model model)) as places where you need to set initial values for all relevant instance variables in the class. What is missing from the constructors currently that you think should be initialized before the game can be played? get(int row, int col) This method returns true if and only if the location described by (row, col) is currently filled or is not a location on the board. placeable(Piece piece, int row, int col) and placeable(Piece piece) There are four placeable methods here, which is an example of method overloading (once again, we'll learn more about this later in the semester); however, you will only need to implement two of them. The first should return true if the given piece can be placed with its reference point at (row, col), while the second should return true if the given piece can be placed anywhere on the board at all. (Hint: For good coding practice, try to use one placeable method to implement the other.) For a helpful visual, check out this slide deck to see more about how placeable works. place(Piece piece, int row, int col) Once we've determined that the piece can be placed at the given position using placeable, it's time to actually place the piece, which is what this method does. The Hand Methods: handSize(), handUsed(), piece(int k), clearHand(), and deal(Piece piece) These methods are responsible for the functionality of the player's hand in the Blocks game. You can read each method's Javadoc comment for more information, but they will all involve working with our instance variable _hand in some way. place(int k, int row, int col) Now that you've implemented the player's hand, you can implement the other version of the place method, which takes in an index k instead of a Piece object. Besides this difference, this method is very similar in function to the other place method. rowColumnCounts() This method returns a 2D integer array result where result[0][R] gives the number of filled cells in row R of the grid, and result[1][C] gives the number of filled cells in column C of the grid. In other words, row 0 of the returned result array contains the filled cell counts for all of the rows, and row 1 of the result array contains the filled cell counts for all of the columns. scoreClearedLines(int nrows, int ncols) Given the number of filled rows and columns currently on the grid, this method calculates the score that will be added by clearing these filled lines. clearFilledLines() Once you've found all the filled lines and calculated their score, it's time to clear those lines from the grid; this method is responsible for doing so. roundOver() This method returns true if none of the Pieces in the current hand can be placed anywhere on the board. undo() and redo() These two methods will deal with the _history instance variable, among other things. Once implemented, you should be able to undo back to previous game states and redo forward to moves that you previously undid. PuzzleGenerator This class contains the logic for creating new games 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. As in Piece.java, you only have one method to complete in this class. This is the deal(Model model, int handSize), which deals a hand with handSize pieces to the given model. We mentioned the _random instance variable earlier; you'll need to use that in this method, so be sure to read up on the Random class documentation. You can find the Javadoc comment for this method above the deal(Model model, int handSize) method of the PuzzleSource class. Instrumentation and Testing See the links in Useful Links for useful testing information! 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 blocks.Main --log you'll get a record on the standard output of your hand, the moves made, 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 blocks.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 blocks.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 output produced by --log and uses it (in place of user clicks and random numbers) to supply the results of getPuzzle and getCommand. Like --log, it also echoes the commands it reads. The tester.py script uses its output to test the program. For example, to read back the file myscript1.in, use java -ea blocks.Main --no-display --testing testing/myscript1.in This will print out what tester.py sees, which it compares to testing/myscript1.std. Using --log and --testing, you can thus create your own .in and .std testing files to augment the ones we've provided in testing. We have set up the Makefiles in the proj0 directory and in the blocks 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 Piece.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. If you are using the IntelliJ debugger on the unit tests, note that there are timeouts on these tests, so your debugging session may end abruptly due to these timeouts. To get around this, feel free to comment out the timeouts at the top of the unit test files. See the end of the Unit Testing Tips video for an example of how to do this. The command make acceptance in the proj0 directory will run acceptance tests, which run the program and check its outputs against expected output using the scripts tester.py and testing.py in the testing subdirectory. Acceptance 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 acceptance 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 acceptance tests. Running Acceptance Tests in IntelliJ Acceptance tests used in make check are stored under the proj0/testing folder. If you would like to run an acceptance 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 --no-display --testing testing/ where is the name of the file of the acceptance test you would like to run. For example, if you would like to run acceptance test 1, you should have --no-display --testing testing/01-full-round1.in as your program arguments. Now you can click Run > Run 'Main' or Run > Debug 'Main' to run and use the debugger on the acceptance 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: Blocks, style will be worth 2 points, passing the unit tests will be worth 8 points, and passing the acceptance tests will be worth 6 points. The IntelliJ Style checker plugin is inconsistent with the style checker used on the autograder. To correctly check style locally, use make style. 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 every 3 hours. Starting at 6PM PT the day the assignment is due (2/11), you will be able to submit once every hour. To account for any technical difficulties, in the last hour before the deadline you will be able to submit as many times as you want. Past the assignment deadline, you can submit as often as you would like (see the project lateness policy for information on getting credit for submitting late). Furthermore, to encourage that you utilize the full test suite that is released with the assignment, you won't be able to see the output of unit or acceptance tests ran on the autograder until two days before the assignment is due (2/9). 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 acceptance 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.
