Description
Problem 1: (C++) Pokémon in Order Write a C++ program which reads in some Pokémon names from user input and outputs them in a way as described below. Input: • Each line contains a single word which is the name of a Pokémon. • Last line is always “???” indicating end of input. • You may assume the number of input names are no more than 30. Output: • Names of the input Pokémon, one on each line, in the following order: ◦ In descending order of length of Pokémon name. ◦ If two Pokémon names are of the same length, then the two names will be printed in lexicographical order (case insensitive). Requirement: • Your program MUST implement the selection sort algorithm you learned in Module 6. You will need to adapt the sorting algorithm to satisfy the output requirement. In other words, you are not allowed to use external libraries to handle the sorting. • You can ONLY use the data types char , bool , int , double , strings and arrays. • You are NOT allowed to use data structures from other external libraries such as STL containers (e.g., vectors), etc. Sample Test Cases User inputs are shown in blue. 1_1 Azelf Lurantis Drapion Sudowoodo Fletchinder ??? Fletchinder Sudowoodo Lurantis Drapion Azelf 1_2 chinchou Tirtouga Venusaur Cobalion Ribombee cacturne Vaporeon ??? cacturne chinchou Cobalion Ribombee Tirtouga Vaporeon Venusaur 1_3 Liepard rhyperior Lairon petilil Pignite druddigon Aron ??? druddigon rhyperior Liepard petilil Pignite Lairon Aron Problem 2: Sudoku Sudoku is a puzzle game whose goal is to enter the digits 1 to 9 into a game board with 9 x 9 cells, such that: • Each digit appears exactly once in each row • Each digit appears exactly once in each column • Each digit appears exactly once in each of the nine 3 x 3 sub-grid. An example game solution is shown below. Given an incomplete game board, we may determine the allowed digits for an empty cell, which are the digits that can be entered into the cell without violating the above rules for the game board. For example, in the following game board, the allowed digits for cell at position (6, 2) are 3, 5, 6 and 7. A very basic Sudoku solving technique, named Naked Single, is to determine the allowed digits of an empty cell and if the empty cell has only one allowed digits, we fill the empty cell with this allowed digit. In the above game board, the cell at position (4, 5) can be filled with the digit 5. We may then apply the Naked Single technique to the empty cells to solve a Sudoku game as much as possible. Note that • Once an empty cell is filled, the allowed digits for other empty cells may change so we will need to redetermine them. • We can apply the Naked Single technique to the empty cells repeatedly, until we find that no empty cells can be filled after visiting all empty cells once. • For some very simple Sudoku game board, all empty cells can be solved eventually by using the Naked Single technique alone, but in general we may still end up with an incomplete board. Write a C++ program that uses the Naked Single technique alone to solve a Sudoku game as much as possible as described above. You are provided with a template program 2.cpp . Input: • Nine lines, each containing nine digits from 0 to 9, representing a Sudoku game board. • A digit 0 represents an empty cell, while any digit from 1 to 9 represent a filled cell. • You may assume that the input board is always consistent, which means that there must be at least one allowed digit for an empty cell at any time during the solving process. Output: • Your program should first display the given game board in the format as specified in the sample test cases, in which an empty cell is printed as x , and we have grid lines to better visualize the sub-grids. • Your program should then display the final game board (which may be complete or incomplete) obtained by repeatedly applying the Naked Single technique ONLY until no more empty cells can be filled. Requirement: • You should start working from the 2.cpp provided. • The main() function has been written for you. A 2D array is also defined in main() for storing the game board. You do not need to change anything in the main() function. • Complete the following functions in 2.cpp . Read the code in the template carefully to see what have been provided for you. You will find details of the function prototypes in the in-code comments too. ◦ ReadBoard() which reads a Sudoku board from input ◦ PrintBoard() which displays a given Sudoku board to screen ◦ SolveBoard() which solves a given Sudoku board as much as possible using the Naked Single technique only. • You can ONLY use the simple data types char , bool , int , double , strings and arrays. In other words, you are not allowed to use other data types or data structures STL containers (e.g., vectors), etc. • You may add your own functions wherever appropriate for better program modularity. Sample Test Cases User inputs are shown in blue. 2_1: 3 9 0 7 8 0 0 0 0 0 0 4 9 0 6 8 0 7 0 0 0 0 0 3 0 6 0 0 0 8 2 4 0 0 0 0 7 3 1 0 0 0 6 2 4 0 0 0 0 6 7 9 0 0 0 1 0 4 0 0 0 0 0 2 0 9 6 0 8 3 0 0 0 0 0 0 1 9 0 4 8 Input Sudoku board: 3 9 x | 7 8 x | x x x x x 4 | 9 x 6 | 8 x 7 x x x | x x 3 | x 6 x ——+——-+——- x x 8 | 2 4 x | x x x 7 3 1 | x x x | 6 2 4 x x x | x 6 7 | 9 x x ——+——-+——- x 1 x | 4 x x | x x x 2 x 9 | 6 x 8 | 3 x x x x x | x 1 9 | x 4 8 Final Sudoku board: 3 9 6 | 7 8 4 | 1 5 2 1 2 4 | 9 5 6 | 8 3 7 5 8 7 | 1 2 3 | 4 6 9 ——+——-+——- 9 6 8 | 2 4 1 | 5 7 3 7 3 1 | 8 9 5 | 6 2 4 4 5 2 | 3 6 7 | 9 8 1 ——+——-+——- 8 1 5 | 4 3 2 | 7 9 6 2 4 9 | 6 7 8 | 3 1 5 6 7 3 | 5 1 9 | 2 4 8 2_2: 4 0 9 0 0 0 0 0 0 0 2 0 4 0 0 0 0 6 6 0 0 2 3 0 1 0 0 5 9 0 3 0 0 0 7 0 0 0 0 0 4 0 0 5 0 0 8 0 0 0 2 0 9 1 0 0 1 0 2 4 0 0 8 7 0 0 0 0 8 0 4 0 0 0 0 0 0 0 7 0 5 Input Sudoku board: 4 x 9 | x x x | x x x x 2 x | 4 x x | x x 6 6 x x | 2 3 x | 1 x x ——+——-+——- 5 9 x | 3 x x | x 7 x x x x | x 4 x | x 5 x x 8 x | x x 2 | x 9 1 ——+——-+——- x x 1 | x 2 4 | x x 8 7 x x | x x 8 | x 4 x x x x | x x x | 7 x 5 Final Sudoku board: 4 3 9 | x x x | 5 2 7 1 2 8 | 4 x x | 9 3 6 6 7 5 | 2 3 9 | 1 8 4 ——+——-+——- 5 9 x | 3 x x | x 7 2 2 1 x | x 4 x | x 5 3 3 8 x | x x 2 | x 9 1 ——+——-+——- 9 5 1 | 7 2 4 | 3 6 8 7 6 3 | x x 8 | 2 4 9 8 4 2 | x x x | 7 1 5 2_3: 7 0 9 0 0 0 3 0 6 0 8 0 0 3 0 0 5 0 0 0 0 0 0 2 0 0 0 5 0 0 0 0 0 8 0 0 0 2 0 0 6 0 0 3 0 0 0 1 0 0 0 0 0 7 0 0 0 4 0 0 0 0 0 0 5 0 0 1 0 0 6 0 9 0 7 0 0 0 4 0 5 Input Sudoku board: 7 x 9 | x x x | 3 x 6 x 8 x | x 3 x | x 5 x x x x | x x 2 | x x x ——+——-+——- 5 x x | x x x | 8 x x x 2 x | x 6 x | x 3 x x x 1 | x x x | x x 7 ——+——-+——- x x x | 4 x x | x x x x 5 x | x 1 x | x 6 x 9 x 7 | x x x | 4 x 5 Final Sudoku board: 7 x 9 | x x x | 3 x 6 x 8 x | x 3 x | x 5 x x x x | x x 2 | x x x ——+——-+——- 5 x x | x x x | 8 x x x 2 x | x 6 x | x 3 x x x 1 | x x x | x x 7 ——+——-+——- x x x | 4 x x | x x x x 5 x | x 1 x | x 6 x 9 x 7 | x x x | 4 x 5 Problem 3: (C++) Morse Code Decoder Morse code is a method used in telecommunication that encodes text characters with dot and dash . The following figure shows the encodings of the characters supported by our program. E.g., A ‘s morse code is one dot and one dash, 0 ‘s morse code is five dashes, etc. In this problem, you are asked to write a C++ program that takes in a sequence of morse code and decodes it to text characters. The input morse code in this problem follows the rules: • A dot is represented using . . • A dash is represented using _ . • The space between letters is represented using | . • The space between words is represented using || . For example, given the input morse code: …|___|… The decoder should output: SOS Given the input morse code: ….|.|._..|._..|___||.__|___|._.|._..|_.. The decoder should output: HELLO WORLD You are provided with a template program 3.cpp . Input: • The program accepts morse code from a file. The command line of the program is given by: < filename E.g., if your program is named decoder , and the morse code is stored in a file named “message.txt”; then, the following command at the command prompt ./decoder < message.txt will decode the morse code in “message.txt” and print out the text. Output: • Your program will print out the decoded text in one line. Requirements: • You should start working from the 3.cpp provided. • Complete the function string morseCodeToText(string s) which ◦ takes the morse code as input. ◦ returns the decoded text. Note: • The main() function has been completed for you, and you do not need to make any change to it. • You may add your own functions wherever appropriate for better program modularity. Sample Test Cases User inputs are shown in blue. 3_1 ./decoder < input3_1.txt RUN 3_2 ./decoder < input3_2.txt THIS IS THE WAY 3_3 ./decoder < input3_3.txt SHANTARAM 3_4 ./decoder < input3_4.txt PEOPLE IN THEIR RIGHT MINDS NEVER TAKE PRIDE IN THEIR TALENTS Problem 4: (C) Luhn algorithm The Luhn algorithm, also known as the “modulus 10” algorithm, is a simple checksum method to prevent simple transcription errors for a sequence of digits. It is commonly used in distinguishing valid credit card numbers. Given an input code as a string of digits, the algorithm works as follows: 1. Reverse the input string. 2. Sum the odd digits (i.e., first, third,… digits) in the reversed string to obtain a partial sum s1. 3. For every even digits (i.e., second, fourth, … digits) in the reversed string, multiply the digit by 2 4. Obtain a partial sum s2 of the products in (3) with this rule: If a product in (3) is less than 10, just add the product to s2; otherwise, add the sum of two digits in the product to s2. 5. If s1 + s2 is divisible by 10, then the input string of digits is a valid code. Let’s work out an example. Suppose the input string is 5255638118968609: 1. we first obtain the reversed string 9068698118365525 2. summing the odd digits, we have s1 = 9+6+6+8+1+3+5+2=40 3. the multiples of the even digits are 0, 16, 18, 2, 16, 12, 10, 10 4. summing the multiples of the even digits, we have s2 = 0 + (1+6) + (1+8) + 2 + (1+6) + (1+2) + (1+0) + (1+0) = 30 5. since s1 + s2 = 70 which is divisible by 10, the input string is a valid code. Write a C program to determine if an input string of digits is a valid code. Input: • An input string of digits. • You may assume that the length of the input string is no more than 30 digits. Output: • the first line displays the reversed string in step 1. • the second line displays the values s1 and s2, separated by a space. • the third line displays the string “valid” if the input is a valid string, or “invalid” if otherwise. Requirement: • Use the command gcc -pedantic-errors -std=c11 4.c -o 4 to compile your program. (Or specify -pedantic-errors -std=c11 as the compiler flags in the Atom editor.) Sample Test Cases User inputs are shown in blue. 4_1 5255638118968609 9068698118365525 40 30 valid 4_2 5255638118968608 8068698118365525 39 30 invalid
