Problems

1. (10 points) Joe the mountain climber has come across a large mountain range. He wants to climb only the tallest mountains in the range. Design the int[] peakFinder(int[] H) method that returns an array \(H'\) of all the peaks in an int[] of mountain heights \(H\). A peak \(p\) is defined as an element of \(h\) at index \(i\) such that \(p[i - 1] < p[i]\) and \(p[i] > p[i + 1]\). If \(i = 0\) or \(i = |H| - 1\), Joe will not climb \(p[i]\). Joe doesn't want to climb a mountain of the same height more than once, so you should not add any peaks that have already been added to \(H'\). We present some test cases below.

   peakFinder({9, 13, 7, 2, 8})                        => {13}
   peakFinder({8, 7, 8, 7, 8, 7, 8, 7})                => {8}
   peakFinder({111, 27, 84, 31, 5, 9, 4, 3, 2, 1, 64}) => {84, 9}
   peakFinder({})                                      => {}
   peakFinder({1})                                     => {}
   peakFinder({1, 2})                                  => {}
   peakFinder({1, 2, 1})                               => {2}
   peakFinder({1, 2, 3, 2, 1})                         => {3}
     

   Warning: For this problem you are not allowed to use an ArrayList or any helper methods, e.g., .contains, or methods from the Arrays class. You may (and should) use a Set<Integer> to keep track of previously-seen peaks.

   Files to Submit: Problem1.java, Problem1Test.java

2. (16 points) Design the List<String> tokenize(String s, char d) method that, when given a string \(s\) and a char delimiter \(d\), returns an ArrayList of tokens split at the delimiter.

   You may assume that delimiters are not side-by-side, that there is at least one delimiter in the string, and it is neither at the beginning nor the end of the string.

   Warning 1: For this problem, you must parse the input by hand; you cannot call any String methods (except .length and .charAt).

   Warning 2: You also cannot use methods that do the "heavy lifting" for you, e.g., String.split, StringTokenizer, or regular expressions.

   Note: Because of the above criteria, we guarantee that the length of the input string is at least 3.

   Files to Submit: Problem2.java, Problem2Test.java

3. (16 points) Design the Map<String, Integer> wordCount(String s) method that, when given a string \(s\), counts the number of words in the list, then stores the resulting frequencies in a HashMap<String, Integer>.

   Assume that \(s\) is not cleaned. That is, you should first remove all of the following punctuation: periods, commas, exclamation points, question marks, semi-colons, dashes, hashes, ampersands, asterisks, and parentheses, from \(s\), producing a new string \(s'\). Then, split the string based on spaces, and produce a map of the words to their respective counts.

   Do not factor case into your total; e.g., "fAcToR" and "factor" count as the same word. The ordering of the returned map is not significant.

   String s = "Hello world, the world is healthy, is 
               it not? I certainly agree that the world 
               is #1 and healthy."
   wordCount(s) => [<"hello" : 1>, <"world" : 3>, <"the" : 2>
                    <"is" : 3>, <"healthy" : 2>, <"it" : 1>,
                    <"i" : 1>, <"certainly" : 1> <"agree" : 1>
                    <"that" : 1>, <"1" : 1>, <"and" : 1>, <"not" : 1>]
     

   Warning: Like in Problem 2, you are not allowed to use built-in mechanisms for splitting your string.

   Note: Only the punctuation listed above should be filtered out. Do not use a blanket ``punctuation'' filter.

   Hint: You are allowed to use the tokenize method that you designed in Problem 2 to help you with this problem. If you do use it, either copy and paste it into the Problem3 file or call it directly.

   Files to Submit: Problem3.java, Problem3Test.java

4. (16 points) Design the double postfixEvaluator(List<String> l) method that, when given a list of binary operators and numeric operands represents as strings, returns the result of evaluating the postfix-notation expression. We provide a few examples below.

   postfixEvaluator({"5", "2", "*", "5", "+", "2", "+"}) => 17
   postfixEvaluator({"1", "2", "3", "4", "+", "+", "+"}) => 10
   postfixEvaluator({"12", "3", "/"})                    => 4
   postfixEvaluator({"2.5", "3", "*", "1", "-"})         => 6.5
   postfixEvaluator({"3", "4", "-"})                     => -1
     

   Hint 1: You will need to write a few helper methods to solve this problem, and it is best to break it down into steps. First, write a method that determines if a given string is one of the four binary operators: "+", "-", "*", or "/". You may assume that any inputs that are not binary operators are operands, i.e., numbers. Then, write a method that applies a given binary operator to a list of operands, i.e., an ArrayList<Double>.

   Hint 2: What particular data structure would be helpful in solving this problem?

   Files to Submit: Problem4.java, Problem4Test.java

5. (12 points) The substitution cipher is a text cipher that encodes an alphabet string \(A\) (also called the plain-text alphabet) with a key string \(K\) (also called the cipher-text alphabet). The \(A\) string is defined as "ABCDEFGHIJKLMNOPQRSTUVWXYZ", and \(K\) is any permutation of \(A\). We can encode a string \(s\) using \(K\) as a mapping from \(A\). For example, if \(K\) is the string "ZEBRASCDFGHIJKLMNOPQTUVWXY" and \(s\) is "WE MIGHT AS WELL SURRENDER!", the result of encoding \(s\) produces "VA JFCDQ ZP VAII PTOOAKRAO!".

   Design the String substitutionCipher(String A, String K, String s) method, which receives a plain-text alphabet string \(A\), a cipher-text string \(K\), and a string \(s\) to encode. substitutionCipher should return a string \(s'\) using the aforementioned substitution cipher algorithm. If a character from \(s\) does not have a pairing letter in the cipher-text string, use the character itself in the encoded string \(s\). You may assume that there is exactly one pairing per letter in each alphabet.

   Files to Submit: Problem5.java, Problem5Test.java

6. (16 points) Design the List<List<String>> lex(String e) method that, when given an expression written in prefix fashion, returns a list of tokens and their identifiers.

   The lex method returns a list of two-element lists. The first is the “tag” of the token, and the second is the token itself. Tokens in this language are "L_PAREN", "R_PAREN", "NUMBER", and "SYMBOL". Left and right parentheses are straightforward, as are numbers (you may assume that all numbers are positive integers). Anything else should be regarded as a symbol. Note that symbols are to be considered space-separated, e.g., "HELLO" is one "SYMBOL"; not five.

   For example, consider the input (+ (- 43 5) 42). The lex method therefore returns:

   [
    ["L_PAREN", "("],
    ["SYMBOL", "+"],
    ["L_PAREN", "("],
    ["SYMBOL", "-"],
    ["NUMBER", "43"],
    ["NUMBER", "5"],
    ["R_PAREN", ")"],
    ["NUMBER", "42"]
    ["R_PAREN", ")"]
   ]
     

   Warning: Like in Problems 2 and 3, you are not allowed to use built-in mechanisms for splitting your string.

   Note: In some contexts, this method could also be called “tokenize,” but that method name has a particular meaning with respect to the problem set.

   Hint 1: You are allowed to use the tokenize method that you designed in Problem 2 to help you with this problem. If you do use it, either copy and paste it into the Problem6 file or call it directly.

   Hint 2: It might be a good idea to write a helper method that receives the input string and adds exactly one space between each of the "tokens," and then tokenize that string.

   Files to Submit: Problem6.java, Problem6Test.java

7. (14 points) Design the Set<List<Integer>> selectPairs(int[] A, int t) method that, when given an array of integers \(A\) and a target \(t\), returns all possible pairs of numbers in \(A\) that sum to \(t\). For example, if \(A=\{2, 2, 4, 10, 6, -2\}\) and \(t=4\), we return a set containing two two-element lists: \(\{2, 2\}\) and \(\{6, -2\}\). Do not add a pair that already exists in the set or a pair that, by reversing the pair, we get a pair in the existing set. E.g., \(\{-2, 6\}\) should not be added to the set.

   There is a simple brute-force algorithm to solve this problem via two loops, but by incorporating a second set for lookups, we can do much better: for every number \(n\) in \(A\), add \(n\) to a set \(S\), and if \(t-n=m\) for some \(m\in S\), then we know that \(m+n\) must equal \(t\), therefore we add \(\{n, m\}\) to the resulting set of integer arrays. Walking through this with the example from before, we get the following sequence of actions:

   • Initialize \(S=\{\}\) and \(L=\{\}\). We know that \(t=4\).

   • We add \(2\) to \(S\). \(S=\{2\}\).

   • Because \(4-2\in S\), the two-element array \(\{2, 2\}\) is added to \(L\). \(2\) is not re-added to \(S\).

   • Because \(4-4\not\in S\), we only add \(4\) to \(S\). \(S=\{2, 4\}\).

   • Because \(4-10\not\in S\), we only add \(10\) to \(S\). \(S=\{2, 4, 10\}\).

   • Because \(4-6\not\in S\), we only add \(6\) to \(S\). \(S=\{2, 4, 10, 6\}\).

   • Because \(4-(-2)\in S\), the two-element array \(\{6, -2\}\) is added to \(L\). We add \(-2\) to \(S\). \(S=\{2, 4, 10, 6, -2\}\).

   Files to Submit: Problem7.java, Problem7Test.java

8. Extra Credit (10 points) You are designing a system with querying functionality similar to a database language such as SQL. In particular, we have a 2D array of strings whose first row contains column headers to a database. Examples of such columns may be "ID", "Name", "Age", "Salary", and so forth.

   Design the List<String> query(String[][] db, String cmd) method that, when given a “database” and a “Command”, returns the data from the rows that satisfy the criteria enforced by the command.

   A Command is "SELECT <count> <header> WHERE <predicate>"
     

   The SELECT command receives a <count>, which is a number between \(1\) and \(n\), or the asterisk to indicate everyone in the database. The WHERE clause receives a “Predicate”. The SELECT command receives a <count> and a <header> to designate that the command should return <count> rows with data from the <header> column. An asterisk can be used to select all rows in the database. Your implementation should be flexible enough to work with any arbitrary column over the database. (You may assume that the input <header> is a valid column in the database, but it cannot be hard-coded to fit only a particular set of database columns, e.g., "ID", "Name", and so forth.)

   A Predicate is "<header> <comparator> <value>"
     

   Headers are one of the column headers of the database, and comparators are either =, !=, <, <=, >, or >=, or LIKE. Values are either numbers, floats, or strings, and are alwaysenclosed by single quotes.

   Parsing a LIKE command is more complicated. There are four possible types of values:

   'S'
   '%S'
   'S%'
   '%S%'
     

   The first matches an exact string, namely S. The second matches any string that ends with S. The third matches any string that begins with S. The fourth matches any string that contains S.

   You may assume all commands are well-formed. However, it is possible that a command returns no results, e.g., SELECT * Name WHERE Salary >= '10000000'

9. Extra Credit (10 points) Reversi is a “pebble-based,” grid-style, turn-based, two-player game where the goal is to have as many pebbles of your color on the board as possible. If you're unfamiliar with the game, play it here until you understand how it works.

   There are a few rules to placing pebbles on the board:

   1. For a player to place a pebble of color P at position (r, c), it must make a valid move. A move is valid if and only if there is at least one pebble of the opposite color Q in between (r, c) and some other pebble of color P.
   2. When making a move at position (r, c) by pebble of color P, we flip all Q-colored pebbles in between (r, c) and other P-colored pebbles along the grid.

   For example, consider the following board configuration, where one pebble is colored R (red) and the other is colored B (black).

   If it is R's move, then they must make a move that flips at least one B, according to rule (1). So, we can place a pebble colored R at the following positions (denoted by “(row, column)”): (3, 5), (5, 3), (2, 4), and (4, 2). If we choose to place a R-colored pebble at position (3, 5), we flip the B-colored pebble at position (3, 4) because a line forms between (3, 3) and (3, 5), according to rule (2):

   From here, it is B's turn, and they can move to positions (2, 3), (4, 5), and (2, 5). In this exercise you will implement Reversi as a series of piecemeal-designed methods.

   1. Design the boolean isBlankCell(char[][] B, int r, int c) method that, when given a Reversi board B and a position at row r and column c, returns whether that position is blank. A cell is blank if it is denoted by the '.' character.

   2. Design the boolean isValidMove(char[][] B, int r, int c) method that returns whether the position (r, c) is in the bounds of the array.

   3. Design the Set<List<Integer>> getValidMovesForPebble(char[][] B, int r, int c) method that returns all valid moves from the pebble located at (r, c). Follow the rules from above.

      Hint: It may be helpful to have an array of the eight directional offsets (similar to the Minesweeper presentation), and expand outward.

   4. Design the Set<List<Integer>> getPebblePositions(char[][] B, char P) method that returns all positions where there is a pebble colored as P.

   5. Design the Set<List<Integer>> getValidMoves(char[][] B, char P) method that returns all valid moves from all positions with a pebble colored as P.

      Warning: You must use getPebblePositions and getValidMovesForPebble in your definition of this method.

   6. Design the Set<List<Integer>> getFlippablePebbles(char[][] B, char P, int r, int c) method that returns a set of all the positions that will be flipped by placing a pebble P at position (r, c).

      Warning: Do not assume that position (r, c) starts off as valid.

   7. Design the char[][] flipPositions(char[][] B, char P, char Q, int r, int c) method that returns a new board after flipping all of the pebbles of color Q that, if we start from position (r, c) with a pebble colored P, we expand out until we hit another pebble that is also colored P.

      Warning: Don't forget to place a P-colored pebble at position (r, c)!

   Important Warning: This is a pretty difficult problem that you should only attempt after doing the rest of the problems and you want a challenge. We reserve the right to question the validity of your solution to this problem, and we will only give you credit if we are convinced that you wrote your own solution. (Therefore, don't ChatGPT the solution and expect to get away with it!)