I attached a .pdf document detailing the overview, requirements, steps, etc. for the project. The project is due in 43 hours (10:00 PM CST on April 6th), but it would be nice to have it done by 10:00 PM CST on April 5th (in 19 hours). The purpose of this project is to write loops, use arrays and lists, and put together a working application involving several interacting Java classes.
hw3.pdf Introduction The purpose of this assignment is to give you some practice writing loops, using arrays and lists, and, most importantly, to get some experience putting together a working application involving several interacting Java classes. There are two classes for you to implement: Powers and ShiftUtil. As always, your primary responsibility is to implement these classes according to the specification and test them carefully. These two classes can be used, along with some other components, to create an implementation of our version of a game known as "2048." If you are not familiar with the game, do not worry, it is not complicated. (It is, however, highly addictive, so watch out.) The game consists of a grid of moveable tiles. Each tile contains a number that is a power of 2. We will think of the grid as a 2D array of integer values, where the value 0 means there is no tile in that cell. There are only four possible operations: to "shift" the grid up, down, left, or right. What this means is that the tiles are shifted in the indicated direction, and that neighboring tiles with the same value are merged. For example, referring to the screenshot above, after shifting the grid upwards, it might look like this: "merged" tiles new tile Note that there is also a new tile on the left side. Whenever any tiles are moved, a new tile is generated in a random empty position, having either value 2 or 4. The object of the game is to end up with a tile that has value 2048. There are many versions online you can try out to get an idea of how it works; for example, as of the moment this document is being written, there is one you can play at http://www.coolmath-games.com/0-2048. Please note that this and other versions you find may not correspond precisely to the game as specified here. The two classes you implement will provide the "backend" or core logic for the game. In the interest of having some fun with it, we will provide you with code for a GUI (graphical user interface), based on the Java Swing libraries, as well as a simple text-based user interface. More details below. The sample code includes a documented skeleton for the two classes you are to create in the package hw3. The additional code is in the packages ui and api. The ui package is the code for the GUI, described in more detail in a later section. The api package contains some relatively boring types for representing data in the game. There are a few examples of test cases for you to start with located in the default package. You should not modify the code in the api package. Specification The complete specification for this assignment includes • this pdf, • the online Javadoc, and • any "official" clarifications posted on Canvas and/or Piazza Overview of the ShiftUtil class The class ShiftUtil consists of a collection of methods that implement the basic logic of shifting a single row or column. The idea is to carefully isolate the trickiest parts of the algorithm so that it can be developed and tested independently. This is a "utility" class and it should have no instance variables. Logically all the methods could have been specified as static methods; however we have chosen not to do so in order to facilitate testing. In particular, ShiftUtil only operates on a one-dimensional array and only shifts to the left. We will later see how these simpler operations can be used easily by the Powers class to shift in any direction. What does it mean to "shift" an array in this context? We will refer to an array cell containing a zero value as "empty" and a cell with a nonzero value as "nonempty." To shift the array basically means to a) shift values to the left so that all nonempty cells are to the left of empty ones, and b) merge two neighboring nonempty cells when they have the same value, giving the resulting cell twice the old value. The details are given more precisely in the javadoc for the ShiftUtil class, which describes the required algorithm in pseudocode. It is important to note that in ShiftUtil we work only from the left: if there are three neighboring cells with the same value, only the first two are merged. Also, merges do not cascade; a new merged value cannot be merged again during the same operation. Here are some examples of performing the shiftAll operation: • for [2, 0, 0, 4, 0, 2], result is [2, 4, 2, 0, 0, 0] • for [2, 0, 2, 4, 0, 4], result is [4, 8, 0, 0, 0, 0] • for [0, 2, 2, 2, 0, 0], result is [4, 2, 0, 0, 0, 0] • for [2, 2, 2, 2, 2, 0], result is [4, 4, 2, 0, 0, 0] The shiftAll operation is further broken down into smaller steps that can be implemented and tested incrementally. The basic step is to identify a single shift or merge operation that places a new value in a given cell of the array. A shift could be a simple move of a value from one cell to another, or it could be a merge of two cells. After identifying a shift, the array has to be updated before identifying and performing additional shifts. For example, consider the array [2, 0, 0, 4, 0, 2]. 1. Start with index 0, which has a 2. What value should go there? We find the next nonempty cell to its right, which is a 4. It can't be merged with the 2, so there is nothing to do, the 2 just stays at index 0. 2. Next, go to index 1. This cell is "empty" (contains a zero). What value should go there? We find the next nonempty cell to its right, which is the 4 at index 3. However, since we started with an empty cell, it is possible that there is another 4 to the right that should be merged. So we find the next nonempty cell to the right of index 3, which is a 2 at index 5. The 2 cannot be merged with the 4. Therefore, we just move the 4 at index 3, down to index 1. We now have [2, 4, 0, 0, 0, 2]. 3. Next, go to index 2. This cell is empty. What value should go there? We find the next nonempty cell to its right, which is the 2 at index 5. Again, look for a nonempty cell to the right of index 5, to see whether they should be merged. There is no nonempty cell to the right of index 5. Therefore, we move the 2 at index 5 down to index 2. We now have [2, 4, 2, 0, 0, 0]. 4. Next, go to index 3. This cell is empty, and there is no nonempty cell to its right, so do nothing. The same happens for indices 4 and 5. (Clearly the loop could be short-circuited once we discover that there are no nonempty cells on the right.) As an example containing some merges, consider [2, 0, 2, 4, 0, 4] 1. Start with index 0, which has a 2. What value should go there? We find the next nonempty cell to its right, which is the 2 at index 2. These cells have the same value, so we merge indices 0 and 2 into index 0, obtaining [4, 0, 0, 4, 0, 4]. 2. Next, go to index 1. This cell is empty. What value should go there? We find the next nonempty cell to its right, which is the 4 at index 3. Since we are starting with an empty cell, we also find the next nonempty cell to the right of index 3, which is the 4 at index 5. These cells have the same value, so we merge indices 3 and 5 into index 1, obtaining [4, 8, 0, 0, 0, 0]. 3. Next, go to index 2. This cell is empty, and there is no nonempty cell to its right, so do nothing. The same thing happens for indices 3, 4, and 5. We describe each shift/merge with an instance of the Shift class, which contains (among other attributes) the old index of the cell to be moved, possibly an additional index for a second cell that is to be merged, and the new index (which in case of a merge, might be the same as the old index). The Shift class actually serves two purposes. The first is to enable us to separate the logic for finding a move from the logic for updating the array. The algorithm for shiftAll is thus implemented in terms of the following basic operations of ShiftUtil: public int findNextNonempty(int[] arr, int start) - returns the index of the next nonempty cell on or after start public Shift findNextPotentialShift(int[] arr, int index) - returns the shift to perform in order to obtain the correct