CS 310 HW 1: 2048 Last Updated: 2016-06-16 Thu 15:06 CS 310 HW 1: 2048 → shiftRight() → Courtesy of the 2048 Web Site Deadlines Milestone Deadline: 11:59pm Tuesday 6/14/2016 Final Deadline: 11:59pm Tuesday 6/21/2016 Submit to Blackboard Approximately 8.75% of total grade Code for this assignment is here: distrib-hw1.zip Freshest Set of Test Cases HW1MilestoneTests.java TwoNTileTests.java DenseBoardTests.java (Updated: Thu Jun 16 15:03:50 EDT 2016 ) Game2048Tests.java junit-cs310.jar (Copy of JUnit library) CHANGELOG: Thu Jun 16 15:03:55 EDT 2016 Minor update to DenseBoardTests.java which may affect your pass/fail on the test copy2(). The original version used the assert() function which seems to misbehave in some environments. Update your copy of those tests. Fri Jun 10 11:31:43 EDT 2016 Minor update to the manual inspection criteria in include a section on abstraction boundaries. Table of Contents 1. Overview 2. Grading 2.1. Milestone Automated Tests (5%) 2.2. Final Automated Tests (45%) 2.3. Final Manual Inspection (50%) 2.4. Late Final Submissions 3. Project Files 4. Class Architecture 4.1. TwoNTile 4.2. DenseBoard 4.3. Game2048 4.4. PlayText2048 5. Shifting Mechanics 5.1. Shifts without Merges 5.2. Shifts with Merges 5.3. Resolving Merges 5.4. Shifts that Do and Do Not Change the Board 5.5. Scoring of Shifts 6. Random Tile Placement 6.1. Constructors for Game2048 6.2. Provided Methods in Game2048 6.3. Placing the Random Tile on the Board 6.4. Adding Tiles to a Board at a Free Space 7. Game Over Conditions 8. PlayText2048 8.1. Usage Message: No arguments 8.2. Play the Original 4 by 4 game 8.3. Fat Board: 2 by 8 8.4. Play a Large 10 by 12 game 9. PlayGUI2048.java 10. Manual Inspection 10.1. Code Readability (5%) 10.2. Use of Additional Methods (5%) 10.3. Adherence to Abstraction Boundaries (5%) 10.4. Board Shift Methods: Code Clarity/Elegance (10%) 10.5. Board Shift Methods: Complexity (10%) 10.6. Target Complexities of Other Methods (10%) 10.7. Additional Analysis (5%) 11. Notes on Test Cases 11.1. Methods that should throw Exceptions 12. Setup Submission 12.1. HW Distribution 12.2. HW Directory 12.3. ID.txt 12.4. Penalties 12.5. Milestone and Final Submission to Blackboard 1 Overview 2048 is a simple, open-ended, addictive puzzle game which involves shifting tiles around a grid in an attempt to merge simlar tiles to score points. The game especially resonates with computer science folk as the scoring system is based on powers of 2. You will build the underlying classes to implement a slightly expanded version of 2048 in this assignment and analyze the complexity of some of the operations required for the game. To get an intuitive sense of what you are to implement play the game for a few minutes but know that many HW submissions have been made late by dropping to much time into the game. To make our implementation of the game more interesting, you will implement an arbitrary rectangular board of tiles. The original 2048 game was played only on a 4 by 4 board, but our version will allow for 3 by 5, 10 by 2, 1 by 300, or any other size board. 2 Grading Grading for this HW will be divided into three distinct parts: Part of your grade will be based on passing some automated test cases by an early "milestone" deadline. See the top of the HW specification for Part of your grade will be based on passing all automated test cases by the final deadline Part of your grad will be based on a manual inspection of your code and analysis documents by the teaching staff to determine quality and efficiency. 2.1 Milestone Automated Tests (5%) Prior to the final HW deadline, some credit will be garnered by submitting portions of the HW and passing some automated test cases associated with that portion The file HW1MilestoneTests.java contains tests which will be used for the HW milestone. These tests are duplicates of tests in some other testing files. This early deadline is to encourage you to begin your work early on the project and make consistent incremental steps towards its completion. For details of automated tests, see the next section No manual inspection is done at the HW milestone, only automated tests. Milestone tests will not be used for the final grading. No late submissions are accepted for milestones and the submission link be unavailable shortly after the Milestone deadline. 2.2 Final Automated Tests (45%) JUnit test cases will be provided to detect errors in your code. These will be run by a grader on submitted HW after the final deadline. Tests may not be available on initial release of the HW but will be posted at a later time. Tests may be expanded as the HW deadline approaches. It is your responsibility to get and use the freshest set of tests available. Tests will be provided in source form so that you will know what tests are doing and where you are failing. It is up to you to run the tests to determine whether you are passing or not. If your code fails to compile against the tests, little credit will be garnered for this section Most of the credit will be divide evenly among the tests; e.g. 50% / 25 tests = 2% per test. However, the teaching staff reserves the right to adjust the weight of test cases after the fact if deemed necessary. Test cases are typically run from the command line using the following invocation which you should verify works as expected on your own code. UNIX Command line instructions
Compile
> javac -cp .:junit-cs310.jar *.java
Run tests
> java -cp .:junit-cs310.jar SomeTests
WINDOWS Command line instructions: replace colon with semicolon
Compile
> javac -cp .;junit-cs310.jar *.java
Run tests
> java -cp .;junit-cs310.jar SomeTests
2.3 Final Manual Inspection (50%) Graders will manually inspect your code and analysis documents looking for a specific set of features after the final deadline. Most of the time the requirements for credit will be posted along with the assignment though these may be revised as the the HW deadline approaches. Credit will be awarded for good coding style which includes Good indentation and curly brace placement Comments describing private internal fields Comments describing a complex section of code and invariants which must be maintained for classes Use of internal private methods to decompose the problem beyond what is required in the spec Some credit will be awarded for clearly adhering to the target complexity bounds specified in certain methods. If the specification lists the target complexity of a method as O(N) but your implementation is actually O(N log N), credit will be deducted. If the implementation complexity is too difficult to determine due to poor coding style, credit will likely be deducted. All TARGET COMPLEXITIES are worst-case run-times. Some credit will be awarded for turning in any analysis documents that are required by the HW specification. These typically involve analyzing how fast a method should run or how much memory a method requires and are reported in a text document submitted with your code. 2.4 Late Final Submissions For the Milestone submission, late submissions will be accepted. For the Final Deadline, HW may be submitted up to 2 days late with penalties. Day-late tokens are automatically used by graders to nullify penalties for late submission if HW is submitted after the final deadline. No submissions are accepted 48 hours after the final deadline. Late submission and token policies are outlined in the course syllabus; refer there for more details. 3 Project Files The following files are relevant to the HW. Some are provided and require modification (Provided), while others must be edited (Edit) or must be created (Create) from scratch. File State Notes Tile.java Provided Abstract base class for tiles TwoNTile.java Create Tiles with powers of 2 Board.java Provided Abstract base class for tile boards DenseBoard.java Create Dense board of tiles Game2048.java Create Game logic/state to run a game of 2048 PlayText2048.java Provided Main loop to play 2048 on the console PlayGUI2048.java Provided Main loop to play 2048 graphically TwoNTileTests.java Testing Tests for various classes. No modifications DenseBoardTests.java Testing are required. Game2048Tests.java Testing HW1MilestoneTests.java Testing junit-cs310.jar Testing JUnit testing library for CS 310. ANALYSIS.txt Edit Answer questions contained within ID.txt Edit Identifying information 4 Class Architecture You are required to implement 2048 using the following architecture. It divides the responsibilities of game elements into several pieces, the most significant being Board. Tile Abstract class which has the concrete implementation TwoNTile. This class tracks a game piece which is moved around a board. If a moving tile collides with another tile, they may merge. In the case of TwoNTile, merging happens if two colliding tiles have the same value: two 2-tiles would merge, two 4-tiles would merge, but a 2-tile and a 4-tile would not merge. Tiles provide methods to determine if they merge and to produce Board Abstract class with the concrete implementation DenseBoard. This class is responsible for keeping track of a grid of tiles of arbitrary rectangular dimensions. The main operation of the Board is to perform a shift to the left, right, up, or down which moves tiles in the specified direction as far as they will go. If two tiles collide they may merge depending on their properties. The board allows tiles to be added and retrieved according to certain semantics that enable random tiles to be placed. The concrete implementation of this homework, DenseBoard, will keep track of tiles using a 2D array or ArrayList. Since 2048 boards never grow or shrink, there is not much difference between using standard arrays or ArrayList in this case so long as there is one memory slot available for every possible tile position. DenseBoard will be contrasted with alternative Board implementations in later assignments. Game2048 Concrete class. Provides a high level interface to a complete game of 2048 with methods to manipulate a board, report the score, and detect the Game Over Conditions. User Inteface classes will interact with this class. A number of the methods of Game2048 simply call corresponding methods of the game's internal Board. PlayText2048 and PlayGUI2048 Concrete class, provided, do not modify. Implement a simple text-based and GUI user interface to play 2048 through its main() function. This decomposition is required because we will continue to use pieces of it in future HWs. HW 2 will require implementation of an alternative Board with the same methods but different unerlying data. New kinds of tiles to create 2048 variants. Since you will be modifying, updating, and re-using your own code base, it is in your own best interest to code well. Use simple techniques that are easy to understand after several weeks of neglect. Everyone knows that debugging is twice as hard as writing a program in the first place. So if you're as clever as you can be when you write it, how will you ever debug it? – Brian Kernighan Write comments to explain to yourself your intentions. These are useful for graders as well. Use error checking, assertions, and exception throwing to fail early if assumptions are violated. The remaining subsections give an overview of the concrete classes you must implement. All the listed public methods are required. You are free to write own additional internal methods that have any visibility modifier (public/private/proctected/default). Doing so will likely make the implementation of the project easier. 4.1 TwoNTile
// Concrete implementation of a Tile. TwoNTiles merge with each other
// but only if they have the same value.
public class TwoNTile extends Tile {
// Create a tile with the given value of n; should be a power of 2
// though no error checking is done
public TwoNTile(int n);
// Returns true if this tile merges with the given tile. "this"
// (calling tile) is assumed to be the stationary tile while moving
// is presumed to be the moving tile. TwoNTiles only merge with
// other TwoNTiles with the same internal value.
public boolean mergesWith(Tile moving);
// Produce a new tile which is the result of merging this tile with
// the other. For TwoNTiles, the new Tile will be another TwoNTile
// and will have the sum of the two merged tiles for its value.
// Throw a runtime exception with a useful error message if this
// tile and other cannot be merged.
public Tile merge(Tile moving);
// Get the score for this tile. The score for a TwoNTile is its face
// value.
public int getScore();
// Return a string representation of the tile
public String toString();
}
4.2 DenseBoard
// Tracks the positions of an arbitrary 2D grid of Tiles. DenseBoard
// uses an internal, multi-dimensional array to store the tiles and
// thus has a O(R * C) memory footprint (rows by columns).
public class DenseBoard extends Board {
// Build a Board of the specified size that is empty of any tiles
public DenseBoard(int rows, int cols);
// Build a board that copies the 2D array of tiles provided Tiles
// are immutable so can be referenced without copying but the a
// fresh copy of the 2D array must be created for internal use by
// the Board.
public DenseBoard(Tile t[][]);
// Create a distinct copy of the board including its internal tile
// positions and any other state
public Board copy();
// Return the number of rows in the Board
public int getRows();
// Return the number of columns in the Board
public int getCols();
// Return how many tiles are present in the board (non-empty spaces)
// TARGET COMPLEXITY: O(1)
public int getTileCount();
// Return how many free spaces are in the board
// TARGET COMPLEXITY: O(1)
public int getFreeSpaceCount();
// Get the tile at a particular location. If no tile exists at the
// given location (free space) then null is returned. Throw a
// runtime exception with a useful error message if an out of bounds
// index is requested.
public Tile tileAt(int i, int j) ;
// true if the last shift operation moved any tile; false otherwise
// TARGET COMPLEXITY: O(1)
public boolean lastShiftMovedTiles();
// Return true if a shift left, right, up, or down would merge any
// tiles. If no shift would cause any tiles to merge, return false.
// The inability to merge anything is part of determining if the
// game is over.
//
// TARGET COMPLEXITY: O(R * C)
// R: number of rows
// C: number of columns
public boolean mergePossible();
// Add a the given tile to the board at the "freeL"th free space.
// Free spaces are numbered 0,1,... from left to right accross the
// columns of the zeroth row, then the first row, then the second
// and so forth. For example the board with following configuration
//
// - - - -
// - 4 - -
// 16 2 - 2
// 8 8 4 4
//
// has its 9 free spaces numbered as follows
//
// 0 1 2 3
// 4 . 5 6
// . . 7 .
// . . . .
//
// where the dots (.) represent filled tiles on the board.
//
// Calling addTileAtFreeSpace(6, new Tile(32) would leave the board in
// the following state.
//
// - - - -
// - 4 - 32
// 16 2 - 2
// 8 8 4 4
//
// Throw a runtime exception with an informative error message if a
// location that does not exist is requested.
//
// TARGET COMPLEXITY: O(T + I)
// T: the number of non-empty tiles in the board
// I: the value of parameter freeL
public void addTileAtFreeSpace(int freeL, Tile tile) ;
// Pretty-printed version of the board. Use the format "%4s " to
// print the String version of each tile in a grid.
//
// TARGET COMPLEXITY: O(R * C)
// R: number of rows
// C: number of columns
public String toString();
// Shift the tiles of Board in various directions. Any tiles that
// collide and should be merged should be changed internally in the
// board. Shifts only remove tiles, never add anything. The shift
// methods also set the state of the board internally so that a
// subsequent call to lastShiftMovedTiles() will return true if any
// Tile moved and false otherwise. The methods return the score
// that is generated from the shift which is the sum of the scores
// all tiles merged during the shift. If no tiles are merged, the
// return score is 0.
//
// TARGET COMPLEXITY: O(R * C)
// R: the number of rows of the board
// C: the number of columns of the board
public int shiftLeft();
public int shiftRight();
public int shiftUp();
public int shiftDown();
}
4.3 Game2048
// Represents the internal state of a game of 2048 and allows various
// operations of game moves as methods. Uses TwoNTiles and DenseBoard
// to implement the game.
public class Game2048{
// Create a game with a DenseBoard with the given number of rows and
// columns. Initialize the game's internal random number generator
// to the given seed.
public Game2048(int rows, int cols, int seed) ;
// Create a game with a DenseBoard which has the given arrangement
// of tiles. Initialize the game's internal random number generator
// to the given seed.
public Game2048(Tile tiles[][], int seed) ;
// Return the number of rows in the Game
public int getRows();
// Return the number of columns in the Game
public int getCols();
// Return the current score of the game.
public int getScore();
// Return a string representation of the board; useful for text UIs
// like PlayText2048
public String boardString();
// Return the tile at a given position in the grid; throws an
// exception if the request is out of bounds. Potentially useful for
// more complex UIs which want to lay out tiles individually.
public Tile tileAt(int i, int j);
// Shift tiles left and update the score
public void shiftLeft();
// Shift tiles right and update the score
public void shiftRight();
// Shift tiles up and update the score
public void shiftUp();
// Shift tiles down and update the score
public void shiftDown();
// Generate and return a random tile according to the probability
// distribution.
// 70% 2-tile
// 25% 4-tile
// 5% 8-tile
// Use the internal random number generator for the game.
public Tile getRandomTile();
// If the game board has F>0 free spaces, return a random integer
// between 0 and F-1. If there are no free spaces, throw an
// exception.
public int randomFreeLocation();
// Add a random tile to a random free position. To adhere to the
// automated tests, the order of calls to random methods MUST BE
//
// 1. Generate a random location using randomFreeLocation()
// 2. Generate a random tile using getRandomTile()
// 3. Add the tile to board using one of its methods
public void addRandomTile();
// Returns true if the game over conditions are met (no free spaces,
// no merge possible) and false otherwise
public boolean isGameOver();
// true if the last shift moved any tiles and false otherwise
public boolean lastShiftMovedTiles();
// Optional: pretty print some representation of the game. No
// specific format is required, used mainly for debugging purposes.
public String toString();
}
4.4 PlayText2048
// Class to play a single game of 2048
public class PlayText2048 {
// Play a game of 2048 of the given size
// usage: java PlayText2048 rows cols [random-seed]
public static void main(String args[]);
}
5 Shifting Mechanics class DenseBoard{
// Shift the tiles of Board in various directions.
// Return the score of the shift from merged tiles.
public int shiftLeft();
public int shiftRight();
public int shiftUp();
public int shiftDown();
}
class Game2048 {
// Shift tiles left and update the score
public void shiftLeft();
// Shift tiles right and update the score
public void shiftRight();
// Shift tiles up and update the score
public void shiftUp();
// Shift tiles down and update the score
public void shiftDown();
}
Boards must provide shift methods which move tiles according to the game mechanics. The mechanics of shifting are the same every direction: all tiles slide as far as they can in the given direction, any colliding tiles that should merge are removed and replaced with the collision result, the method returns the total score of any merged tiles, and if any tiles moved the Board will return true if lastShiftMovedTiles() is called. Game2048 wraps these methods and allows outside classes to call its versions of the methods which will manipulate the internal board and update the game's score. Specifics of shifting are described in the subsections. 5.1 Shifts without Merges When shifting tiles in a particular direction, all tiles on the board that can move do so in the direction indicated. The following examples do contain any merges of tiles. Example 1
- - - - -
- - 4 - 2
- - - 2 4
shiftUp()
- - 4 2 2
- - - - 4
- - - - -
Example 2
- - - - -
- 8 - - 2
8 32 4 2 -
shiftLeft()
- - - - -
8 2 - - -
8 32 4 2 -
Example 3
4 16 2 - -
32 8 - 2 -
4 8 4 - 2
shiftRight()
- - 4 16 2
- - 32 8 2
- 4 8 4 2
Example 4
- 2
- -
- -
2 4
shiftUp()
2 2
- 4
- -
- -
Example 5
- -
2 -
- 4
2 8
shiftLeft()
- -
2 -
4 -
2 8
5.2 Shifts with Merges During a shift, tiles are thought to be "moving" in the shift direction and colliding with one another. For TwoNTiles, collisions between two tiles with the same value causes them to merge and creates a new tile with a larger value. Merging happens even when tiles haven't actually "moved" through any empty space but moving in a direction would cause a collision with another tile of the same value. Example 1
2 - - 2 -
shiftLeft()
4 - - - -
Example 2
4 2 4 2 2
shiftRight(): Right 2-tiles merge
- 4 2 4 4
shiftRight(): Right 4-tiles merge
- - 4 2 8
Example 3
2 - -
- - 2
- - -
2 - 2
- - -
- - -
shiftDown(): Multiple merges of 2-tiles
- - -
- - -
- - -
- - -
- - -
4 - 4
shiftLeft(): merge 4-tiles
- - -
- - -
- - -
- - -
- - -
8 - -
Example 4
4 2 - -
8 2 - -
2 16 - -
32 16 8 2
shiftDown(): 2-tiles merge, 16-tiles merge, settle to bottom
4 - - -
8 - - -
2 4 - -
32 32 8 2
shiftLeft(): 32-tiles merge
4 - - -
8 - - -
2 4 - -
64 8 2 -
Example 5
8 8 4 2
16 - 8 2
- - - -
- - - -
shiftDown(): everything moves, 2-tiles merge
- - - -
- - - -
8 - 4 -
16 8 8 4
5.3 Resolving Merges Merges are resolved in the opposite direction of the shift direction. Shifting left resolves merges from left to right Shifting right resolves merges from right to left Shifting up resolves merges from up to down Shifting down resolves merges from down to up Example 1: Letters for explanation only
- - - -
2A - 2B 2C
- - - 2D
- - - -
shiftLeft(): 2B collides with 2A and merge, 2C remains distinct, 2D only moves
- - - -
4 2C - -
2D - - -
- - - -
Example 2: Letters for explanation only
2A - - -
2B - - -
2C 8 - -
16 - - -
shiftDown(): bottom 2-tiles, 2B and 2C merge, upper 2-tile remains
- - - -
2A - - -
4 - - -
16 8 - -
Example 3
- - - 4
- - 2 2
- 8A 8B 8C
64 16 4 4
shiftLeft(): 2-tiles merge, left-most 8-tiles merge (8A and 8B), 4-tiles merge
4 - - -
4 - - -
16 8C - -
64 16 8 -
Example 4
2A 2B 2C 2D 2E
shiftLeft(): 2A merges with 2B; 2C merges with 2D; 2E remains
4 4 2E - -
Example 5
2A 2B 4 2C 2D
shiftRight(): 2A merges with 2B; 2C merges with 2D
- - 4 4 4
5.4 Shifts that Do and Do Not Change the Board
public class DenseBoard{
public boolean lastShiftMovedTiles()
}
Some shifts move tiles while others do not. In the 2048 game mechanics, performing a shift that moves tiles results in another tile being added to a random free location on the board. Shifts that do not not move any tiles do not move the game forward: no tiles are added, no score is gained, and the state of the board remains the same. To facilitate this in the game, Boards must indicate when the last shift has moved tiles. During a shiftLeft(), shiftRight(), etc., the Board should track if any tiles have actually been moved. Merging tiles counts as moving. After the shift operation completes, a subsequent call to Board's lastShiftMovedTiles() method should return true if any tiles moved and false otherwise. A freshly created Board returns false if no shifts have been performed. Examples follow. Example 1
- - - 2
- - - -
- - - 2
- 2 4 8
shiftRight(): Nothing moves
- - - 2
- - - -
- - - 2
- 2 4 8
lastShiftMovedTiles(): returns false
Example 2
- - - 8
- - - -
- - - 4
4 2 4 8
shiftUp(): many tiles move but no merges
4 2 4 8
- - - 4
- - - 8
- - - -
lastShiftMovedTiles(): returns true
Example 3
- - - -
- - - -
2 - - 4
2 2 4 8
shiftDown(): leftmost 2-tiles merge
- - - -
- - - -
- - - 4
4 2 4 8
lastShiftMovedTiles(): returns true
Example 4
- - - -
- - - 8
- 2 - 4
4 4 4 8
shiftRight(): Tiles move and merge
- - - -
- - - 8
- - 2 4
- 4 8 8
lastShiftMovedTiles(): returns true
5.5 Scoring of Shifts Players score points every time a shift merges tiles. The score for merging two TwoNTiles is the sum of their values which also happens to be the value of the tile they produce. Merging two 2-tiles gives a score of 4 and produces a 4-tile Merging two 4-tiles gives a score of 8 and produces an 8-tile Merging two 8-tiles gives a score of 16 and produces an 16-tile The return value of the DenseBoard shift methods (shiftLeft(),shiftRight(), etc.) is the score for shifting which is the sum of all merges that happen. Example 1: Letters for explanation only
- - - -
2A - 2B 2C
- - - 2D
- - - -
shiftLeft(): 2B collides with 2A and merge, 2C remains distinct, 2D only moves
return score is 4
- - - -
4 2C - -
2D - - -
- - - -
Example 2: Letters for explanation only
- - - -
2 - 2 2
- 4 - 4
- - - -
shiftLeft(): Two 2-tiles merge (4 points)
Two 4-tiles merge (8 points)
return score is 12
- - - -
4 2 - -
8 - - -
- - - -
Example 3
- - - 4
- - 2 2
- 8 8 8
64 16 4 4
shiftLeft(): Two 2-tiles merge (4 points)
Two 8-tiles merge (16 points)
Two 4-tiles merge (8 points)
return score 28
4 - - -
4 - - -
16 8 - -
64 16 8 -
Example 4
4 8 4
- - -
2 - -
- - -
- - -
shiftUp(): no tiles merge
return score 0
4 8 4
2 - -
- - -
- - -
- - -
6 Random Tile Placement During game play, after tiles are shifted and actually move in a specified direction, a random tile is added at a random location on the board. This requires players to manage movements well or the board will fill up with tiles and signal the Game Over Conditions. Randomness creates problems with automated testing so make sure to follow the guidelines in this section carefully so that you will pass automated tests involving random generation. 6.1 Constructors for Game2048
public Game2048(int rows, int cols, int seed)
A required constructor for Game2048 takes as its final argument an integer seed which should be used to initialize a random number generator, specifically an instance of java.util.Random. Any calls to generate randomness should utilize this internal generator. Each instance of Game2048 should have its own random number generator. Such a field is present in the provided code for Game2048 called private Random random;
public Game2048(Tile tiles[][], int seed)
Game2048 has a second required constructor that will be used extensively in testing. The initial board is built using the given 2D array of tiles. It should initialize its random number generator identically to the previous constructor. 6.2 Provided Methods in Game2048 Two methods are provided for Game2048 involving randomness and the random field
class Game2048{
public Tile getRandomTile()
}
This method generates a random Tile, always a TwoNTile for this implementation. The distrbution of tiles is as follows. 70% of the time, a 2-tile is returned. 25% of the time, a 4-tile is returned. 5% of the time, an 8-tile is returned. It uses a call to Random.nextDouble() to generate a probability for determining the tile. to be generated. Note: The original game of 2048 does not appear to ever randomly add 8-tiles so we are taking a slight liberty here.
class Game2048{
public int randomFreeLocation()
}
Determines how many free spaces exist in the Board using appropriate method calls. Calls the count of free spaces F Use a call to Random.nextInt(int) to generate a random number between [0,F-1]; call this number L Returns L 6.3 Placing the Random Tile on the Board
class Game2048{
public void addRandomTile()
}
Determine if there are any free spaces on the board If not, return without doing anything Otherwise follow these steps in exactly the order given: Generate a random location L using randomFreeLocation() Generate a random tile T using getRandomTile() Ask the board to place T at free location L using addTileAtFreeSpace() Warning: Since we are dealing with a random number generator, it is very important that you follow the above steps in exactly the order listed. In a real setting, you could change the order but in order to test your implementation, we have assumed the above order. Deviating from it will likely cause you to fail some of the automatic test cases. 6.4 Adding Tiles to a Board at a Free Space
public class DenseBoard{
public void addTileAtFreeSpace(int freeL, Tile tile)
}
This method adds the requested tile to the location freeL which should be between 0 and the number of free spaces available on the board -1. A RuntimeException is thrown when that condition does not hold. The exact location of where tile is placed is determined by counting free spaces from left to right, top to bottom up to freeL. For example, consider the board - - - -
- 4 - -
16 2 - 2
8 8 4 4
which has its 8 free spaces numbered as follows 0 1 2 3
4 . 5 6
. . 7 .
. . . .
where the dots (.) represent filled tiles on the board. Calling addTileAtFreeSpace(6, new Tile(32) would leave the board in the following state. - - - -
- 4 - 32
16 2 - 2
8 8 4 4
7 Game Over Conditions class Game2048{
public boolean isGameOver();
}
class DenseBoard{
public int getFreeSpaceCount();
public boolean mergePossible();
}
A game of 2048 ends when two conditions are met. The board is completely filled with tiles (no free spaces remain) No shift would merge any tiles At a high level, the isGameOver() method of Game2048 returns true if both these conditions are met and false otherwise. This makes it relatively easy for higher level UI interfaces to determine whether to continue playing. Examples 2 -
4 8
isGameOver() returns false because there is at least 1 free space
2 2
4 8
isGameOver() returns false, a right/left shift will merge
4 16 8 2
4 8 2 4
4 2 16 8
isGameOver() returns false, an up/down shift will merge
2 32
4 8
isGameOver() returns true, no free spaces, no merges possible
2 4
4 8
isGameOver() returns true, no free spaces, no merges possible
4 16 8 2
2 8 2 4
4 2 16 8
isGameOver() returns true, no free spaces, no merges possible
8 PlayText2048 public class PlayText2048 {
// usage: java PlayText2048 rows cols [random-seed]
public static void main(String args[]){
}
This class is provided and does not require modification. It sets up the basic game loop by utilizing the DenseBoard and Game2048 classes that you are to implement. The interface is crude but complete: players are shown the board and their score and the prompted to enter a single letter from l r u d indicating the direction of the shift they want (or q to quit). If the shift moves any tiles, appropriate Game2048 methods are called to add a random tile. This loop continues until the game-over conditions are met. Command line arguments must be specified to indicate the desired size of the board. An optional 3rd argument can be added which is a integer that is used to seed the random number generator used by Game2048 to generate random tiles. The defaul seed is 13579 which means the same sequence of random numbers will be generated which greatly eases the task of testing. A sample session of running the game on 3 different board sizes is given below. All of the games demonstrated below are quit manually by entering q as the move. 8.1 Usage Message: No arguments lila [ckauffm2-hw1]% java PlayText2048
usage: java PlayText2048 rows cols [random-seed]
8.2 Play the Original 4 by 4 game lila [ckauffm2-hw1]% java PlayText2048 4 4
Instructions
------------
Enter moves as l r u d q for
l: shift left
r: shift right
u: shift up
l: shift down
q: quit game
Score: 0
- - - -
2 - 2 2
- - - 2
- - - -
Move: u
u
Score: 4
2 - 2 4
- - - -
- - 4 -
- - - -
Move: d
d
Score: 4
- - - -
- - - -
2 - 2 -
2 - 4 4
Move: l
l
Score: 16
- - - -
- - - -
4 - - -
2 8 2 -
Move: r
r
Score: 16
- - - 2
- - - -
- - - 4
- 2 8 2
Move: d
d
Score: 16
- - - -
- 2 - 2
- - - 4
- 2 8 2
Move: l
l
Score: 20
- - - -
4 - - -
4 - 2 -
2 8 2 -
Move: q
Score: 20
- - - -
4 - - -
4 - 2 -
2 8 2 -
Game Over! Final Score: 20
8.3 Fat Board: 2 by 8 lila [ckauffm2-hw1]% java PlayText2048 2 8
Instructions
------------
Enter moves as l r u d q for
l: shift left
r: shift right
u: shift up
l: shift down
q: quit game
Score: 0
- - - - 2 - 2 2
- - - 2 - - - -
Move: r
r
Score: 4
- - - - - - 2 4
- 4 - - - - - 2
Move: d
d
Score: 4
- - - - - - - 4
- 4 2 - - - 2 2
Move: r
r
Score: 8
- - - 2 - - - 4
- - - - - 4 2 4
Move: d
d
Score: 16
- - - 2 - - - -
- - - 2 - 4 2 8
Move: d
d
Score: 20
- - - - 2 - - -
- - - 4 - 4 2 8
Move: r
r
Score: 28
2 - - - - - - 2
- - - - - 8 2 8
Move: r
r
Score: 32
- - - - - - 8 4
- - - - - 8 2 8
Move: l
l
Score: 32
8 4 - - - 2 - -
8 2 8 - - - - -
Move: d
d
Score: 48
- 4 - - - - - -
16 2 8 - - 2 2 -
Move: q
Score: 48
- 4 - - - - - -
16 2 8 - - 2 2 -
Game Over! Final Score: 48
8.4 Play a Large 10 by 12 game lila [ckauffm2-hw1]% java PlayText2048 10 12
Instructions
------------
Enter moves as l r u d q for
l: shift left
r: shift right
u: shift up
l: shift down
q: quit game
Score: 0
2 - 4 - - - - - - 2 - -
2 - - 2 - 4 - - - - 2 -
- 2 - - - 2 - - 2 2 - -
- - 2 - - 2 8 - - - - -
- - - - - 2 - 4 - - 4 -
- - - - 2 - - - - 2 - -
- - - - - - - - - - - 2
- - 4 - - - 2 - - - - -
- - 4 - 2 2 - - 2 - - 2
- - - - - - - - 2 4 2 -
Move: d
d
Score: 36
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - 2 - - - - - -
- - - - - - - - - - - -
- - 4 - - 4 - - - 2 2 -
- - 2 - - 4 8 - 2 4 4 -
4 2 8 2 4 4 2 4 4 4 2 4
Move: d
d
Score: 52
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - 4 -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - 4 - - 2 - - - - 2 -
- - 2 - - 4 8 - 2 2 4 -
4 2 8 2 4 8 2 4 4 8 2 4
Move: l
l
Score: 68
- - - - - - - - - - - -
- - - - - - - - - - - -
4 - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
4 4 - - - - - - - - - 2
2 4 8 4 4 - - - - - - -
4 2 8 2 4 8 2 8 8 2 4 -
Move: d
d
Score: 108
- - - - - - - - - - - -
- - - - - - - - - - 2 -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
8 - - - - - - - - - - -
2 8 - 4 - - - - - - - -
4 2 16 2 8 8 2 8 8 2 4 2
Move: l
l
Score: 140
2 - - - - - - - - - - -
2 - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
8 - - - - - - - - - - -
2 8 4 - - - - - - - - -
4 2 16 2 16 2 16 2 4 2 - -
Move: d
d
Score: 144
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
4 - - - - - - - - - - -
8 - - - - - - - - - - -
2 8 4 - - - - - - - 2 -
4 2 16 2 16 2 16 2 4 2 - -
Move: l
l
Score: 144
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - 2 - - -
4 - - - - - - - - - - -
8 - - - - - - - - - - -
2 8 4 2 - - - - - - - -
4 2 16 2 16 2 16 2 4 2 - -
Move: l
l
Score: 144
- - - - - - 2 - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
2 - - - - - - - - - - -
4 - - - - - - - - - - -
8 - - - - - - - - - - -
2 8 4 2 - - - - - - - -
4 2 16 2 16 2 16 2 4 2 - -
Move: l
l
Score: 144
2 - - - - - - - - - - -
- - - 2 - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
2 - - - - - - - - - - -
4 - - - - - - - - - - -
8 - - - - - - - - - - -
2 8 4 2 - - - - - - - -
4 2 16 2 16 2 16 2 4 2 - -
Move: d
d
Score: 152
- - - - - - - - - - - 2
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
4 - - - - - - - - - - -
4 - - - - - - - - - - -
8 - - - - - - - - - - -
2 8 4 2 - - - - - - - -
4 2 16 4 16 2 16 2 4 2 - -
Move: q
Score: 152
- - - - - - - - - - - 2
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - - - - -
4 - - - - - - - - - - -
4 - - - - - - - - - - -
8 - - - - - - - - - - -
2 8 4 2 - - - - - - - -
4 2 16 4 16 2 16 2 4 2 - -
Game Over! Final Score: 152
lila [ckauffm2-hw1]%
9 PlayGUI2048.java A graphical interface is provided which relies on Game2048 to function. This class does not require modification and should work after It allows the arrow keys to be used to speed play. The board size can be set on starting a new game by entering appropriate information. → press right arrow (shiftRight()) → 10 Manual Inspection The following features will be evaluated during manual inspection of your code and analysis documents. 10.1 Code Readability (5%) Good indentation and curly brace placement is used. Comments are present describing private internal class fields. Comments describing a complex section of code and invariants which must be maintained for classes 10.2 Use of Additional Methods (5%) Complex methods were broken into manageable pieces which stitched together other (possibly private methods). Boundaries were checked on accesses to ensure that if IndexOutOfBoundsExceptions would have happened, more information is produced for debugging purposes. 10.3 Adherence to Abstraction Boundaries (5%) No runtime casting is employed to convert an abstract class to a concrete class such as Tile to TwoNTile or Board to DenseBoard Instead, available methods from the abstract parent classes are utilized so that new child classes of abstract parents may be incorporated seamlessly. 10.4 Board Shift Methods: Code Clarity/Elegance (10%) Shifting is a very tricky operation as it involves movement of tiles, merging and replacement, and resolution of merges Each of the shifts has a very similar pattern to it with only slight differences. Full credit will be awarded here if the 4 shift methods, shiftLeft(), shiftRight(), shiftUp(), shiftDown() are able to share some code, perhaps an internal method in order to reduce copy/paste of similar code. Hint: Consider implementing some internal iterator-type objects which move through the board in different directions. Use the iterators to implement a single shift(iterator) method and implement each of the left/right/up/down shifts by passing in a different iterator. 10.5 Board Shift Methods: Complexity (10%) As tricky as the shift methods are to get correct, they should also run fast Full credit will be awarded here if the implementations of shift clearly adhere to the target complexity of \(O(R \times C)\) which is linear in the size of the board. Hint: Resolving merge conflicts and moving tiles is difficult if you iterate in the direction of the shift. Instead, consider iterating in the opposite direction of the shift: on a left shift, iterate from left to right. Hint: you should be able to structure the code of the shifts as a single pass through the board which using two nested loops. This will guarantee you adhere to the target complexity. 10.6 Target Complexities of Other Methods (10%) The following methods of DenseBoard have target complexities. It should be clear from the code that your implementation adheres to the complexity to receive full credit. // TARGET COMPLEXITY: O(1)
public int getTileCount();
// Return how many free spaces are in the board
// TARGET COMPLEXITY: O(1)
public int getFreeSpaceCount();
// Get the tile at a particular location
// TARGET COMPLEXITY: O(1)
public boolean lastShiftMovedTiles();
// TARGET COMPLEXITY: O(R * C)
// R: number of rows
// C: number of columns
public boolean mergePossible();
// TARGET COMPLEXITY: O(T + I)
// T: the number of non-empty tiles in the board
// I: the value of parameter freeL
public void addTileAtFreeSpace(int freeL, Tile tile);
// TARGET COMPLEXITY: O(R * C)
// R: number of rows
// C: number of columns
public String toString();
// TARGET COMPLEXITY: O(R * C)
// R: the number of rows of the board
// C: the number of columns of the board
public int shiftLeft();
10.7 Additional Analysis (5%) Report your answer to the following question(s) in the text file ANALYSIS.txt which should be submitted with your project. BACKGROUND:
Note the complexity of the operation DenseBoard.addTileAtFreeSpace():
// TARGET COMPLEXITY: O(T + L)
// T: the number of non-empty tiles in the board
// L: the value of parameter freeL
public void addTileAtFreeSpace(int freeL, Tile tile);
This approach may seem a little strange. It works in conjunction with
methods of Game2048 to generate a random location and tile then set
the random location to the provided tile using the method
above. Below is the approach you must implement.
REQUIRED IMPLEMENTATION
- The Game asks the Board how many free spaces F it has left
- The Game generates a random number called L from 0 to F-1 for the
location of a new tile
- The Game generates a random tile called X
- The Game uses the method addTileAtFreeSpace(L,X) to place the new
tile on the board
An ALTERNATIVE APPROACH would be the following
- The Game asks the Board to generate a list of its free spaces as 2D
coordinates, such as [(0,1), (1,1), (2,3), (4,1)]
- The Game picks a random coordinate (I,J) from the list
- The Game generates a random tile called X
- The Game uses a new method of Board to set the tile at position
(I,J) to be X
QUESTIONS:
Use the following notation in your answer.
- R, C: the number of rows and columns of the Board
- I, J: the position where the new tile should be placed
- L: same as above, the linear location of among free spaces for the
new tile
GIVE A BIG-O ESTIMATE OF THE RUNTIME COMPLEXITY OF THE ALTERNATIVE
APPROACH IN YOUR ANSWER.
IS THIS ALTERNATIVE APPROACH FASTER, SLOWER, OR THE SAME IN TERMS OF
BIG-O COMPLEXITY THAN THE REQUIRED IMPLEMENTATION?
IS THIS ALTERNATIVE APPROACH FASTER, SLOWER, OR THE SAME IN TERMS OF
PRACTICAL PERFORMANCE THAN THE REQUIRED IMPLEMENTATION?
YOUR ANSWER HERE:
11 Notes on Test Cases 11.1 Methods that should throw Exceptions Several tests examine whether or not an exception is thrown and what kind of exception it might be. When two tiles that shouldn't be merged are asked to merge in TwoNTile.merge() When an out of bounds access is made in DenseBoard.tileAt() When a board is asked to place a tile at a free space that doesn't exist in DenseBoard.addTileAtFreeSpace(). In all of these cases, it is desirable to receive an exception more informative than IndexOutOfBounds so you are required to detect such cases and throw a different exception. The type signature of the methods does not say anything about throwing any checked exceptions and you are not allowed to change the type signature of the parent classes. The way around this is throw an unchecked exception, the most common type being java.lang.RuntimeException. The reference implementation uses RuntimeExceptions in the above situations to push out an exception that doesn't require any declaration of throws this or that. The use of checked versus unchecked exceptions is somewhat controversial and is discussed in several places for those that want to know more. Official Java Position, containing the "bottom line guideline: If a client can reasonably be expected to recover from an exception, make it a checked exception. If a client cannot do anything to recover from the exception, make it an unchecked exception." Discussion of the intention of the two types of exceptions. Top Post on StackOveflow discussing the issue. One notable fact conveyed in the discussion is that Java is one of the very few programming languages which have checked exceptions. Most other modern languages feature only some form of unchecked exception. 12 Setup Submission 12.1 HW Distribution Most programming assignments will have some code that is provided and should be used to complete the assignment. Download it and extract all its contents; by default it will create a directory (folder) named distrib-hwX where X is the HW number. 12.2 HW Directory Rename the distrib-hwX directory to masonid-hwX where masonid is your mason ID. My mason ID is ckauffm2 so I would rename HW 1 to ckauffm2-hw1. This is your HW directory. Everything concerning your assignment will go in this directory. 12.3 ID.txt Create a text file in your HW directory called ID.txt which has identifying information in it. My ID.txt looks like. Chris Kauffman
ckauffm2
G001234567
It contains my full name, my mason ID, and G# in it. The presence of a correct ID.txt helps immensely when grading lots of assignments. 12.4 Penalties Make sure to Set up your HW directory correctly Include an ID.txt Indent your code and make comments Failure to do so may be penalized by a 5% deduction. 12.5 Milestone and Final Submission to Blackboard Do not e-mail the professor or TAs your code. Create a zip file of your HW directory and submit it to the course blackboard page. On Blackboard Click on the Assignments section Click on either HW 1 Milestone for the early deadline HW 1 Final for the final deadline Scroll down to "Attach a File" Click "Browse My Computer" Select you Zip file You can resubmit to blackboard as many times as you like up to the deadline. Author: Chris Kauffman (kauffman@cs.gmu.edu) Date: 2016-06-16 Thu 15:06
