Homework 4

Playable 2048

Please download the following zip file: hw04-template. The next step is to finish a playable version of 2048! Before you read the specification and the set of methods, please think through how you would design this program given what you've implemented so far.

Summary: This assignment will break the problem of providing a 2048 playable environment up into a few pieces:

- We need to be able to collapse in each direction. We do this not by providing a method for each direction, but by instead implementing a method for rotating the board 90 degrees. If we want to collapse in a specific direction (e.g. right), we could rotate 90 degrees twice, then combineLeft, then rotate the result twice to get the original orientation back. You can use and extend your combineLeft from last homework. The next image shows an example of the high-level steps to perform the "down" action (3 rotations, a combine, and a last rotation).

We need to randomly add a 2 or 4 each time we move. We need to add that new value in a random square that has a zero in it. We come up with a method for determining randomly which of the zero squares to use for the new value (see randCoord).
We will use a few provided functions for generating 1) a 2 or a 4 randomly (you'll see we've hard-coded it to 2 for now), and 2) a method to generate a random number between 0 and some upper value. We'll use this to figure out which of the zero squares to populate with the new value.

You'll implement the missing methods of the TwoDimensional2048 class in a comparably named file. You are required to implement the methods defined in the interface named TwoDimensional.java. It will include the following methods:

public boolean validateBoard(int[][] b)
I strongly recommend that you make this method invoke your validateRow method in your last assignment. You can do this using the following syntax. Your OneDimensional2048.java file must be in the current directory.
```
OneDimensional2048 oneDimension = new OneDimensional2048();
// for each row of b (row = b[i]) then:
boolean result = oneDimension.validateRow(row); 
```
Additionally, this method checks that each row is of the same length. Note that it does allow boards that are not square.
public int[][] blankBoard(int x, int y)
Return a board with the specified dimensions, i.e. with x number of rows, and y number of columns. All values should be initialized to zero.
public boolean identicalBoard(int[][] a, int[][] b)
Check if the two boards that are passed in have identical values in all of their squares. Return true or false accordingly.
public int numUnoccupied(int[][] b)
Return the number of 0 cells on the board. This is quite useful when finding a bound on the random number you'll need to generate (see next section) to determine here a new item needs to be placed.
public int[] randCoord(int[][] b, int offset)
Given an offset (the index of an available space, currently occupied by a 0), return the x,y coordinate (as an array of length 2) in the board where a new random value should be placed.
In the picture below, we have three examples. Notice that the board size is 3 rows by 5 columns or 15 spaces but the available spaces are only 9. We could index each of these available spaces as if they were on an array by themselves. We call that index the offset.
For an offset of 0, we want to find the 0th available position on the board and return its board coordinates. The red circle highlights that location. The coordinates of the 0th empty square are row = 0 and column = 1. This method would, therefore, return the array [0,1] for an offset of 0.
In the second example, the offset is 4, which means we want the zero that is in the fifth available position (offset 4 spaces from the first available position). The method would return the array [1,3], which is the position in the board for that 4-offset zero (highlighted in green).
In the third example, the offset is 8 (the maximum possible). The method would return the array [2,4], which is the position in the board for that 8-offset zero (highlighted in blue).

This method is one of the more challenging ones of this assignment.
public boolean addNewValue(int[][] b)
This method is supposed to perform the function in 2048 of adding a new random value into the board. We will do so in a very controlled manner. First, you must figure out where to put the new value. Of course it can only be in one of the spots with a zero. This method will
1. Invoke Rnd2048.randValue() to get the value to be inserted (a 2 or a 4).
2. Invoke offset = Rnd2048.randNum(numUnoccupied(b)) to figure out in which of the zeros (i.e. the offset of the zero square) to place the value we just generated.
3. Invoke randCoord(b, offset) to get the [x,y] coordinates in the board we'll insert the value into. This takes the randomly generated offset into the zeros from the previous step.
4. Add the new value at the corresponding coordinates.
This method is straight-forward, but it is important as it connects many other functionalities.
public int[][] combineLeft(int[][] b)
Returns a copy of the board where rows have been combined left.
It is important that you first copy the input board (using the copyBoard method) and then apply combineLeft on each row of the copied board. This is because we wish to keep the original board unchanged for the case when we want to compare before and after board states (this will be used later).
You can use your previous solution to combineLeft that only works on a 1D array. If you call this for each row in your copy of board b, it should have the desired effect.
You can call the combineLeft method in your previous OneDimensional2048 implementation as such:
```
// let's say that you've copied board b into a new board n
// and that row is the ith row of the copy-board n (row = n[i])
// If you create a OneDimensional2048 object like this:
OneDimensional2048 oneDimension = new OneDimensional2048();

// Assuming row is the 1D array of the ith row of the copied board
// then you combine left in-place by doing:
oneDimension.combineLeft(row);
```
Notice that OneDimensional2048's combineLeft method modifies the row "in-place". That means that the actual location gets modified, not a copy. That's why we want to pass in the row of the copied board instead if that of the original one. Otherwise, we would lose the original board b.
Your previous implementation has to be in the same directory/folder as your current implementation. Though you don't have to use your previous implementation, I strongly recommend it. You already did the hard work for combine; you might as well use it! The alternative is to code the combineLeft method from scratch in this class.
public int[][] rotateLeft(int[][] b)
Take a board as input, and return a new board that is the same contents, but rotated 90 degrees to the left (counter-clockwise). This method, and combineLeft will be used together to implement up, down, and right. For instance, to move the squares to the right, we can rotate left twice, then combineLeft, then rotate left twice. This means that we only need to implement the logic of combine once!
public int[][] left(int[][] b)
public int[][] right(int[][] b)
public int[][] up(int[][] b)
public int[][] down(int[][] b)
Each of these move all blocks, and combine them, in the direction specified. They will just use a combination of rotateLeft and combineLeft, and they should be pretty short (e.g. 5 lines each).

The following are methods that I found useful, but that you do not have to implement if you choose not to. Consider them when designing your program.

public int numMax(int[][] b)
Return the maximum number of cells in the board.
public int numOccupied(int[][] b)
Return the maximum number of cells that are non-zero in the board.
public boolean addValue(int[][] b, int x, int y,int val)
Try and set the zero-valued cell in a board at coordinate x, y to val. Return false if the coordinate is outside of the bounds of b, or if that coordinate is non-zero.
public int[][] copyBoard(int[][] b)
Create a new board, and copy an existing (argument) board into it.
public void printBoard(int[][] b)
Print out a board (with tabs between values). Used for debugging.

Other classes and provided files: We are providing the template for the TwoDimensional2048.java class with assertions and some methods for testing, and the Rnd2048.java class to help produce random numbers. You should base your implementation off of these. To get the assertions to work, you'll have to implement many of the methods above.

You will have to use methods from another class we provide to get both random values (e.g. 2 or 4) to insert into the 2048 board, and to give us an offset into the blank (empty) spaces into the board to insert a new value.

  int value  = Rnd2048.randValue();
  int offset = Rnd2048.randNum(numUnoccupied(b))

Note that it is very important for this assignment that we don't actually use random numbers. It would be difficult to test such a solution. Thus we provide the Rnd2048 class for your use. It is required to get the provided assertions to work. Please note that the assertions assume that you only call each of these random methods when required. If you call them additional times, then they might start giving values that will make the assertions fail. Think of both of these methods as returning a value that is at an offset into an array that increases by one every time you call it.

Suggested implementation strategy: You should try and, as much as possible, implement the methods one at a time, and comment out all of the assertions for methods you haven't finished. I've included the mandatory methods in an order that I believe will enable you to iteratively develop your solution. Please write and test each method separately, and try and resist writing code for latter methods until your former ones are in good shape. You will require a means to visualize your program, so I suggest writing the printBoard method ASAP.

Notes and grading: Your implementations must compile to get any credit. You must include all of the required methods, and they must compile, even if they don't work. Please develop these in small chunks. Don't program everything, and hope it will work. Write each method separately, and test it separately. Your implementation will get credit proportional to how many assertions they pass. Make sure to submit your .java files, and that TwoDimensional2048.java has the correct class name. Your main method will not be invoked, so do not assume that it executes.

If you simply implement your methods in such a way that they are customized to the specific test cases we provide (i.e. by returning the desired string, but not having any of the logic required by the assignment), you'll receive no credit.

Submission: Please submit your .java files (if you use your code for the previous assignment, please submit it as well) via blackboard.