Took quite a lot time to on this project, however I even spent more time on playing the finished game!

Introduction

The intent of this project is to give you a chance to get familiar with Java and the various tools used in the course like the IntelliJ IDE and JUnit for writing and running unit tests. Though you’ll find many files and lots of code in the proj0 folder, your task only resides in Model.java and is constrained to just four methods.

In this project, you’ll be building the core logic of this game. That is, we’ve already put together all the GUI code, handle key-presses, and a ton of other scaffolding. Your job will be to do the most important and interesting part.

Specifically, you will fill out 4 methods in the Model.java file which governs what happens after certain key-presses from the user.

The game itself is quite simple. It’s played on a 4*4 grid of squares, each of which can either be empty or contain a tile bearing an integer–a power of 2 greater than or equal to 2. Before the first move, the application adds a tile containing either 2 or 4 to a random square on the initially empty board. The choice of 2 or 4 is random, with a 75% chance of choosing 2 and a 25% chance of choosing 4.

The player then chooses a direction via their arrow keys to tilt the board: north, south, east, or west. All tiles slide in that direction until there is no empty space left in the direction of motion (there might not be any to start with). A tile can possibly merge with another tile which earns the player points.

public static boolean emptySpaceExists(Board b)

This method should return true if any of the tiles in the given board are null. You should NOT modify the Board.java file in any way for this project. For this method, you’ll want to use the tile(int col, int row) and size() methods of the Board class. No other methods are necessary.

Note: We’ve designed the Board class using a special keyword private that disallows you from using the instance variables of Board directly. For example, if you try to access b.values[0][0], this will not work. This is a good thing! It forces you to learn to use the tile method, which you’ll use throughout the rest of the project.

Try opening the TestEmptySpace.java folder. Run the tests. You should see that 6 of the tests fail and 2 of them pass. After you’ve correctly written the emptySpaceExists method, all 8 tests in TestEmptySpace should pass.

Considerations:

1. The variable of the function is board b, use Board’s public method “tile”, return Tile and check if it is null;
2. Double for loops to check every tile of the Board b;
3. Imagine emptyspaceexists is False at start, if any tile is null, then it change to True;
4. Once emptyspaceexists became true, break the two for loops.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static boolean emptySpaceExists(Board b) {
    // TODO: Fill in this function. DONE!
    boolean emptyspaceexists = false;
    for (int i = 0; i < 4 ; i++) {
        if (emptyspaceexists == true) {
            break;
        }
        for (int j = 0; j < 4; j++) {
            //b.tile(i,j) returns a Tile.
            if (b.tile(i,j) == null) {
                emptyspaceexists = true;
                break;
            }
        }
    }
    return emptyspaceexists;
}

public static boolean maxTileExists(Board b)

This method should return true if any of the tiles in the board are equal to the winning tile value 2048.

Note that rather than hard coding the constant 2048 into your code, you should use MAX_PIECE, which is a constant that is part of the Model class. In other words, you shouldn’t do if (x == 2048) but rather if (x == MAX_PIECE).

Leaving in hard coded numbers like 2048 is a bad programming practice sometimes referred to as a “magic number”. The danger of such magic numbers is that if you change them in one part of your code but not another, you might get unexpected results. By using a variable like MAX_PIECE you can ensure they all get changed together.

After you’ve written the method, the tests in TestMaxTileExists.java should pass.

Considerations:

1. Should be similar to for loop each tile like the previous emptySpaceExists(Board b);
2. Only tile is not null can we get the value, need to exclude null tile.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public static boolean maxTileExists(Board b) {
    // TODO: Fill in this function. DONE!
    boolean maxtileexist = false;
    for (int i = 0; i < 4; i++) {
        if (maxtileexist == true) {
            break;
        }
        for (int j = 0; j < 4; j++) {
            //b.tile(i,j) returns a Tile.
            Tile t = b.tile(i, j);
            //value() is a public method for Tile.
            if (t != null && t.value() == MAX_PIECE) {
                maxtileexist = true;
                break;
            }
        }
    }
    return maxtileexist;
}

public static boolean atLeastOneMoveExists(Board b)

This method is more challenging. It should return true if there are any valid moves. By a “valid move”, we mean that if there is a button (UP, DOWN, LEFT, or RIGHT) that a user can press while playing 2048 that causes at least one tile to move, then such a keypress is considered a valid move.

There are two ways that there can be valid moves:

1.There is at least one empty space on the board.
2.There are two adjacent tiles with the same value.

Considerations:

1. Two nested for loops to check tiles on board b;
2. Set atleastonemoveexists False at start;
3. The first way of valid moves: If emptyspaceexists and not maxtileexist, atleastonemoveexists is True;
4. The second way of valid moves:
   Should be complicated to check if two adjacent tiles with the same value;
   (1)exclude the first way of valid moves;
   (2)compare tile(i,j) and tile(i+1,j), if they have same value, atleastonemoveexists is True;
   (3)compare tile(i,j) and tile(i,j+1), if they have same value, atleastonemoveexists is True.
5. Once atleastonemoveexists became true, break loops.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public static boolean atLeastOneMoveExists(Board b) {
    // TODO: Fill in this function. DONE!
    boolean emptyspaceexists = emptySpaceExists(b);
    boolean maxtileexist = maxTileExists(b);
    boolean atleastonemoveexists = false;
    for (int i = 0; i < 4; i++) {
        if (atleastonemoveexists == true) {
            break;
        }
        for (int j = 0; j < 4; j++) {
            Tile t = b.tile(i, j);
            if (emptyspaceexists == true && maxtileexist == false) {
                atleastonemoveexists = true;
                break;
            } else {
                if (i < 3) {
                    Tile tipj = b.tile(i + 1, j);
                    if (t.value() == tipj.value()) {
                        atleastonemoveexists = true;
                        break;
                    }
                }
                if (j < 3) {
                    Tile tijp = b.tile(i, j + 1);
                    if (t.value() == tijp.value()) {
                        atleastonemoveexists = true;
                        break;
                    }
                }
            }
        }
    }
    return atleastonemoveexists;
}

Main Task: Building the Game Logic

public boolean tilt(Side side)

The above three methods are quite easy, the hardest part is to build the main game logic.

The tilt method does the work of actually moving all the tiles around.

In addition to modifying the board, two other things must happen:

1.The score instance variable must be updated to reflect the total value of all tile merges (if any). We merged two 4s into an 8, and two 2s into a 4, so the score should be incremented by 8 + 4 = 12.
2.If anything about the board changes, we must set the changed local variable to true. That’s because at the end of the skeleton code for tilt, you can see we call a setChanged() method: this informs the GUI that there is something to draw. You will not make any calls to setChanged yourself: only modifying the changed local variable.

All movements of tiles on the board must be completed using the move method provided by the Board class. All tiles of the board must be accessed using the tile method provided by the Board class.

Due to some details in the GUI implementation, you should only call move on a given tile once per call to tilt.

Starting by thinking only about the up direction.

Considerations:

1. Write the tilt method for up direction, the skeleton gives a very cleaver way to make the other directions act according to given sides by board.setViewingPerspective(side), but reset viewing perspective to north after each move;

   1 2	board.setViewingPerspective(side); board.setViewingPerspective(Side.NORTH);

2. Seperate into two steps;
   First step:
   (1) When pressing up, from the top row 3 to bottom row 0 order, use nested for loops to check each non-null tile;
   (2) If there are any null space above this tile, move the tile to null tile in the highest row which the tile can reach.
   Second step:
   (1) After first step, check if there is additional move to merge the joint tile in same column with same value, nested for loops from the top row 3 to bottom row 0 order;
   (2) Should notice that after merge, null tile between non-null tiles could be created, need to repeat the first step to fill that null space created by merge;
   (3) If the upper row have merged, no further merge in this column will happen, so when we find null tile between tiles in (2), no further merge;
   (4) Merge moving process: For each non-null tiles in a column, check if any previous merge, if yes, just use similar way as first step to fill null tile. if no, check if there are any joint same values;
   (5) score plus 2 times of the merged tile value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

public boolean tilt(Side side) {
    boolean changed;
    changed = false;

    //act as if Side side is north.
    board.setViewingPerspective(side);

    // TODO: Modify this.board (and perhaps this.score) to account Done!
    // for the tilt to the Side SIDE. If the board changed, set the
    // changed local variable to true.

    //Step 1:Find row number joint to non-null tile when moving up.
    // [x, 2, 2, x] -> [2, 2, x, x]
    // skip merging this step.
    for (int c = 0; c < board.size(); c ++) {
        for (int r = board.size() - 1; r >= 0; r --) {
            Tile t = board.tile(c, r);
            if (t != null) {
                int rd = r;
                while (rd < board.size() - 1 && board.tile(c, rd + 1) == null) {
                    rd ++;
                }
                board.move(c, rd, t);
                changed = true;
            }
        }
    }

    //Step 2:merge tiles with same value.
    // [2, 2, 2, x] -> [4, 2, x, x]
    for (int c = 0; c < board.size(); c ++) {
        for (int r = board.size() - 2; r >= 0; r --) {
            Tile t = board.tile(c, r);
            //after merge of above tiles, should check the null tiles.
            //check_merge to find out whether tup is a merge tile.
            //if null tiles exist, tup is a merge tile, no more merge for following tile t.
            if (t != null) {
                int rd = r;
                boolean check_merge = false;

                while (rd < board.size() - 1 && board.tile(c, rd + 1) == null) {
                    rd ++;
                    check_merge = true;
                }
                Tile tup = board.tile(c, rd + 1);

                while (rd < board.size() - 1 && board.tile(c, rd + 1).value() == t.value() && check_merge == false) {
                    rd++;
                    score += 2 * t.value();
                }

                board.move(c, rd, t);
                changed = true;
            }
        }
    }

    //Reset game original perspective NORTH.
    board.setViewingPerspective(Side.NORTH);

    checkGameOver();
    if (changed) {
        setChanged();
    }
    return changed;
}

Enjoy the game!

Happy to see the game running and pass all tests, enjoy the game!

The discussion part is skiped and this note is mainly for the record of two ways of forming Fibonacci number.

The First Fibonacci

Implement fib which takes in an integer n and returns the nth Fibonacci number.

The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, . . .. The first two numbers in the sequence are 0 and 1, and every number thereafter it is the sum of the two numbers in the sequence before it.

Considerations:
1.Recursive in the first thought;
2.Fibonacci pattern, fib(n) = fib(n - 1) + fib(n - 2);
3.Special consideration to fib(0) and fib(1), since they do not have something like fib(n - 2).

1
2
3
4
5
6
7

public static int fib(int n) {
    if (n > 1) {
        return fib(n - 1) + fib(n - 2);
    } else {
        return n;
    }
}

Another Fibonacci

Extra: Implement a more efficient version of fib in 5 lines or fewer. Here, efficiency might mean making less recursive calls or doing less overall computation. You don’t have to make use of the parameter k in your solution.

start with :

1
2

public static int fib2(int n, int k, int f0, int f1) {
}

Considerations:
1.Recursive, but unlike the previous ocassion, we start from the smaller number;
2.We want nth Fibonacci number, k start from 0 and we recursivly find kth Fibonacci number, until k=n;
3.f0 represents the value of kth number, f1 represents (k+1)th number.
4.The recursive should be like:
fib2(n,0,0,1)
fib2(n,1,1,1)
fib2(n,2,1,2)
fib2(n,3,2,3)
fib2(n,4,3,5)
…

1
2
3
4
5
6
7

public static int fib2(int n, int k, int f0, int f1) {
    if (n == k) {
        return f0;
    } else {
        return fib2(int n, int k + 1, int f1, int f0 + f1);
    }
}

Creative Exercise 1a: Drawing a Triangle

Your goal is to create a program that prints the following figure. Your code should use loops (i.e. shouldn’t just be five print statements, that’s no fun).

1
2
3
4
5

*
**
***
****
*****

Considerations:

1 * in row 1,
2 * in row 2,
…
5 * in row 5.

i is row number.
j is number of * in a row.
First while loop to limit row number in to 5.
while j (number of *) is less than i (row number), print *.
when i,j are equal, print the last *, i + 1 and move to the next row, the j roll back to 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class DrawingaTriangle {
	public static void main(String[] args) {
		int i=1;
		int j=1;
		
		//limit row number into 5
		while (i<=5) {
			//draw i-1 "*" in each row
			while (j <= i) {
				if (j < i) {
					System.out.print("*");
				//statment for i=j condition
				} else {
					System.out.println("*");						
				}
				j++;
			}								
			i++;
			j = 1;				
		}
	}		
}

Creative Exercise 1b: DrawTriangle

Name this new method drawTriangle and give it a return type of void (this means that it doesn’t return anything at all).

The drawTriangle method should take one parameter named N, and it should print out a triangle exactly like your triangle from exercise 1a, but N asterisks tall instead of 5.

After writing DrawTriangle, modify the main function so that it calls DrawTriangle with N = 10.

Considerations:

This is similar to the previous Exercise 1a code, but need to change 5 into a variable n in the function drawTriangle(int n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class DrawTriangle {
	public static void drawTriangle(int n) {
		int i=1;
		int j=1;
		//limit row number into n
		while (i<=n) {
			//draw i-1 "*" in each row
			while (j <= i) {
				if (j < i) {
					System.out.print("*");
				//statment for i=j condition
				} else {
					System.out.println("*");					
				}
				j ++;
			}						
			i ++;
			j = 1;				 
		}		
	}
	
	public static void main(String[] args) {
    	drawTriangle(10);
	}
}

Exercise 2

Using everything you’ve learned so far on this homework, you’ll now create a function with the signature public static int max(int[] m) that returns the maximum value of an int array. You may assume that all of the numbers are greater than or equal to zero.

Modify the code below (also found here) so that max works as described. Furthermore, modify main so that the max method is called on the given array and its max printed out (in this case, it should print 22).

1
2
3
4
5
6
7
8
9

public class ClassNameHere {
    /** Returns the maximum value from m. */
    public static int max(int[] m) {
        return 0;
    }
    public static void main(String[] args) {
       int[] numbers = new int[]{9, 2, 15, 2, 22, 10, 6};      
    }
}

Considerations:

Set first interger as the initial max value, use While loop to compare max with other intergers in the array, any other one bigger than max will instead it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class MaxValue {

    public static int max(int[] m) {
        int n = m.length;
        int max = m[0];
        int i = 1;
        while (i < n) {
            if (m[i] > max) {
                max = m[i];
            }
            i ++;
        }
        return max;
    }

    public static void main(String[] args) {
        int[] m = new int[]{9, 2, 15, 2, 22, 10, 6};
        System.out.println(max(m));
    }
}

Exercise 3

Rewrite your solution to Exercise 2 so that it uses a for loop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class MaxValue_for {
    /** Returns the maximum value from m using a for loop. */
    public static int forMax(int[] m) {
        int mv = m[0];
        for (int i = 1; i < m.length; i += 1) {
            if (m[i] > mv) {
                mv = m[i];
            }
        }
        return mv;
    }
    public static void main(String[] args) {
       int[] numbers = new int[]{9, 2, 15, 2, 22, 10, 6};
       System.out.println(forMax(numbers));      
    }
}

Exercise 4

This is a particularly challenging exercise, but strongly recommended.

Write a function windowPosSum(int[] a, int n) that replaces each element a[i] with the sum of a[i] through a[i + n], but only if a[i] is positive valued. If there are not enough values because we reach the end of the array, we sum only as many values as we have.

For example, suppose we call windowPosSum with the array a = {1, 2, -3, 4, 5, 4}, and n = 3. In this case, we’d:

Replace a[0] with a[0] + a[1] + a[2] + a[3].
Replace a[1] with a[1] + a[2] + a[3] + a[4].
Not do anything to a[2] because it’s negative.
Replace a[3] with a[3] + a[4] + a[5].
Replace a[4] with a[4] + a[5].
Not do anything with a[5] because there are no values after a[5].
Thus, the result after calling windowPosSum would be {4, 8, -3, 13, 9, 4}.

As another example, if we called windowPosSum with the array a = {1, -1, -1, 10, 5, -1}, and n = 2, we’d get {-1, -1, -1, 14, 4, -1}.

Hint 1: Use two for loops.
Hint 2: Use continue to skip negative values.
Hint 3: Use break to avoid going over the end of the array.

Considerations:

1. For loop each element;
2. For each element, if it is positive, use sum of this element and all elements behind instead itself;
3. The sum can be calculated by another for loop, each loop need to check if it is over the array, if so, break;
4. For each element, if it is negative, use continue to skip.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class BreakContinue {

	public static void windowPosSum(int[] a, int n) {
	  for (int i = 0; i < a.length; i += 1) {
		if (a[i] >= 0) {
		  for (int j = 1; j <= n; j += 1) {        
			if (i + j > a.length-1) {
			  break;
			}
			a[i] = a[i] + a[i + j];     
		  }
		} else {
		  continue;
		}
	  }
	}
  
	public static void main(String[] args) {
	  int[] a = {1, 2, -3, 4, 5, 4};
	  int n = 3;
	  windowPosSum(a, n);
  
	  // Should print 4, 8, -3, 13, 9, 4
	  System.out.println(java.util.Arrays.toString(a));
	}
}