Solve the following coding problems. ### 1. Find the missing number from a concatenated range You are given an integer `n` and a string `s`. The string was formed by taking every integer from `1` to `n`, removing exactly one number, converting the remaining numbers to decimal strings, and concatenating them together with no separators. Return the missing number. There are two versions: - **Part 1:** the numbers were concatenated in increasing numeric order. - Example: `n = 5`, `s = "1234"` → return `5`. - **Part 2:** the numbers may appear in any order before concatenation, still with no separators. - Example: for `n = 13`, a valid string could represent a shuffled sequence such as `13, 10, 9, 2, 3, ...` with one number missing. Assume the input is valid and exactly one number from `1..n` is missing. ### 2. Determine the status of a square board game Implement a function that takes: - a board size `size`, where the board is `size x size` and `3 <= size <= 9` - a list of action strings `moves` Return one of: - `"in progress"` - `"player 1 is the winner"` - `"player 2 is the winner"` Assume every action is valid and well-formed. #### Board rules Each square may be empty or owned by one player, and it stores a number of pieces. #### Turn structure Players alternate turns. A turn consists of: 1. **Place** exactly once. 2. **Topple** zero or more times. The input is a flat list of actions, not a list of turns. The first place action belongs to player 1. After each place action, subsequent topple actions belong to that same player until the next place action, which starts the other player's turn. #### Action encoding - `"pRC"` means place one piece at row `R`, column `C`. - `"tRCd"` means topple the square at row `R`, column `C` in direction `d`, where `d` is one of: - `u` = up - `r` = right - `d` = down - `l` = left #### Place action A player may place a piece on: - an empty square, or - a square already owned by that player If the square is empty, the player claims it and places one piece there. If the square already belongs to that player, increment its piece count by one. #### Topple action A player may topple a square they own that contains at least 2 pieces. - Pick up all pieces from that square. - Move in the chosen direction, placing one piece per square on consecutive cells. - Pieces that move beyond the board are lost. - If a placed piece lands on an opponent-owned square, that square is captured: ownership changes to the current player, and all pieces on that square now belong to the current player. #### Game end The game ends as soon as one player has no pieces remaining anywhere on the board. Examples: - `moves = ["p10", "p12", "p10", "t10r"]` → `"player 1 is the winner"` - `moves = ["p00", "p22", "p02", "p22", "t22u", "t02l"]` → `"player 2 is the winner"` ### 3. Generate word sequences for T9 input A phone keypad uses this mapping: - `2 -> abc` - `3 -> def` - `4 -> ghi` - `5 -> jkl` - `6 -> mno` - `7 -> pqrs` - `8 -> tuv` - `9 -> wxyz` Implement a function with inputs: - `input_digits`: an array of digits, each from `2` to `9`, length up to `25` - `valid_words`: an array of up to `50` lowercase English words Return a 2D array containing **all** word sequences whose T9 encodings concatenate exactly to `input_digits`. Each inner array represents one valid translation. - Example: `input_digits = [2,2,8]`, `valid_words = ["act", "bat", "cat", "acd", "test"]` → `[["act"], ["bat"], ["cat"]]` - Example: `input_digits = [7,6,6,3,8,4,6,3]`, `valid_words = ["some", "time", "rome", "sometime", "so", "me"]` → valid outputs include `[["rome", "time"], ["so", "me", "time"], ["some", "time"], ["sometime"]]` Any output order is acceptable unless otherwise specified.