Problems

1. (16 points) John Conway designed the “Game of Life,” which is a cellular automaton. In essence, the game is a grid of cells, where each cell is either “alive” or “dead.” The neighbors of a cell are the (up to eight) cells that surround a cell. Rules advance/guide the “game” from one state to the next. These rules are as follows:

   1. If a cell \(c\) is alive and has between two and three alive neighbors, then it remains alive.

   2. If a cell \(c\) is alive and has less than two alive neighbors, then it dies.

   3. If a cell \(c\) is alive and has more than three alive neighbors, then it dies.

   4. If a cell \(c\) is dead and has three alive neighbors, then it becomes alive.

   Design the boolean[][] gameOfLife(boolean[][] B) method that, when given an initial board configuration \(B\), returns the next state of the game after applying the preceding list of rules. Each element in \(B\) is a boolean value, where true means the cell at \(i, j\) is alive and false means the cell at \(i, j\) is dead. The gameOfLife method should not update the given board. Instead, return a new board with the updated values. It may be helpful to design the following auxiliary methods:

   • int[][] getAdjacentCells(boolean[][] B, int i, int j)

   • int[][] getAliveNeighbors(boolean[][] B, int i, int j)

   • int[][] getDeadNeighbors(boolean[][] B, int i, int j)

   Files to Submit: Problem1.java, Problem1Test.java

2. (34 points) Minesweeper is a simple strategy game where the objective is to uncover all spaces on a board without running into mines. If you are not familiar with the mechanics, we encourage you to find a version online and play it for a bit to understand its gameplay. In this exercise you will implement the minesweeper game as a series of methods. Note: you only need to officially test play, but it may help you to test other methods.

   1. First, design the boolean isValidMove(char[][] board, int row, int col) method that receives a board and a move position at row \(\mathit{row}\) and column \(\mathit{col}\), and determines whether the move is valid. A move is valid if it is located within the bounds of the board.

   2. Design the List<int[]> getValidNeighbors(char[][] board, int row, int col) method that receives a board and a move position, and returns a list of all the immediate neighbors to the cell (row, col). Each element of the list is a two-element integer array containing the row and column pairs of the neighbors. Consider the diagram below, where (0, 0) is the move position, and the surrounding cells are its neighbors, represented as offsets. Note that getValidNeighbors should only return neighbors that are in bounds.

      Hint: Use isValidMove.

   3. Design the List<int[]> getNonMineNeighbors(char[][] board, int row, int col) method that receives a board and a move position, and returns a list of all the neighbors to the cell \((\mathit{row}, \mathit{col})\) that are not mines. A non-mine neighbor is denoted by the character literal '-'.

      Warning: You must use getValidNeighbors in your definition.

   4. Design the List<int[]> getMineNeighbors(char[][] board, int row, int col) method that receives a board and a move position, and returns a list of all the neighbors to the cell \((\mathit{row}, \mathit{col})\) that are mines. Mines are denoted by the character literal 'B'.

      Warning: You must use getValidNeighbors in your definition.

   5. Design the int countAdjacentMines(char[][] board, int row, int col) method that receives a board and a move position, and returns the number of mines that are adjacent to the given position. This method should be one line long and contain a call to getMineNeighbors.

   6. With the helper methods complete, we now need a method that searches through a position and reveals all non-mine adjacent positions. In general, this is a traversal algorithm called depth-first search. The idea is to recursively extend out the path until we hit a mine, at which point we unwind the recursive calls to extend another path.

      Design the void reveal(char[][] board, int row, int col) method that receives a board and a move position, and extends the path from the given position using the following rules:

      1. If the given move position is invalid, then return.

      2. If the character at board[row][col] is not a dash, '-', then return.

      3. Otherwise, determine the number of adjacent mines to the move position. If the number of adjacent mines is non-zero, assign to board[row][col] the number of mines at that move position.

      4. If the number of adjacent mines is zero, then we can extend out the path to all non-mine neighbors. First, assign to board[row][col] the character literal '0', then loop over all non-mine neighbors to the move position. In the loop body, call reveal on each neighbor.

   7. Minesweeper board generation is an algorithmic problem in and of itself, and as such our implementation will be simple. Design the char[][] makeBoard(int N, int M, int B) method that receives a board size of \(N\) rows, \(M\) columns, and \(B\) mines to place. To randomly place mines, create a List<int[]> of all the possible cells on the board, shuffle the list, retrieve the first \(B\) cells, and assign the character literal 'B' to them. Assign the character literal '-' to all other cells.

      Hint: You can either shuffle the list yourself or use Collections.shuffle.

   8. Finally, design the char[][] play(char[][] board, int row, int col) method that receives a board and a move position, and attempts to play the given move position on the board. If, at that position on the board, there is a mine, return null. Otherwise, call reveal on the board and position, then return board. In essence, play receives one game state and transitions it to the next state. You do not need to consider invalid moves for this method, so you can assume that the move position is always valid.

   Files to Submit: Problem2.java, Problem2Test.java

3. (8 points) Design the List<Integer> exptIntermediates(int n, int m) method that, when given two integers \(n > 0\) and \(m \geq 0\), returns a List<Integer> of the intermediate values of \(n^m\). The first element of the resulting list is \(n^m\), and the second element is \(n^{0}\), the third is \(n^1\), the fourth is \(n^2\), and so forth. For example, exptIntermediates(3, 4) returns [81, 1, 3, 9, 27].

   Files to Submit: Problem3.java, Problem3Test.java

4. (8 points) Design the List<Boolean> areValidNames(List<String> names) method that, when given a list of names \(L\), returns a list of booleans where the \(i^\text{th}\) boolean denotes whether the \(i^\text{th}\) name in \(L\) is valid. A name is valid if it is all upper-cased and contains only letters or dashes. (This means that a name can contain letters and dashes.)

   Files to Submit: Problem4.java, Problem4Test.java

5. (12 points) Design the int[] minDistancePoint(List<int[]> L, int x, int y) method that, when given a non-empty list of two-element integer arrays \(L\) and a coordinate pair \((x, y)\), returns the coordinate pair in \(L\) that is the closest to \((x, y)\).

   The input list, as described, contains two-element arrays, where index \(0\) is its \(x\)-coordinate and index \(1\) is its \(y\)-coordinate.

   For example, if \(L = [[1, 2], [-2, 3], [2, 0]]\) and \((x, y) = (0, 0)\), the returned pair is \([2, 0]\) because its distance of \(2\) to the point \((0, 0)\) is the smallest out of all three points.

   Note: If there are multiple points that are equidistant to \((x, y)\), return the first one in the list.

   Files to Submit: Problem5.java, Problem5Test.java

6. (22 points) The prime factorization problem is about finding prime numbers that multiply to some positive integer. That is, given a positive integer \(n\), we want to find its prime factors. It is an open mathematics and computer science question whether it is possible to find the prime factorization of a positive integer in polynomial time. The naive algorithm is to iterate over the primes from \(2, 3, \dots, n\), find the lowest prime \(p\) that divides \(n\), divide \(n\) by \(p\), then repeat until \(n\) is prime.

   We can visualize this algorithm via a prime factor tree. For example, let's find the prime factorization of \(330\). The smallest prime starting from \(2\) that divides \(330\) is \(2\). So, the root of the tree is \(330\), the left branch leads to a prime factor, and the right is a smaller sub-problem, that being \(330 / 2 = 165\). The smallest prime that divides \(165\) is \(3\), so we get \(3\) in the left branch and \(55\) in the right branch. Repeat once more to get \(5\) and \(11\), and we stop because \(11\) is prime.

   1. Design the List<Integer> primeFactors(int n) method that, when given a positive integer \(n \geq 2\), returns a list of the prime factors of \(n\). To test a positive integer for primality, use the method that we provide as an example in Chapter \(2\), or design your own version.

   2. Design the List<Integer> primeFactorsTree(int n) method that creates a “factor tree” as a list. That is, consider once again the prime factorization of \(330\). The returned list should be \([330, 2, 165, 3, 55, 5, 11]\), because the left branch of \(330\) leads to \(2\), and the right branch leads to factoring \(165\). The primeFactorsTree method must call primeFactors.

      Files to Submit: Problem6.java, Problem6Test.java