The assignment is attached.WordPuzzle_description CMPUT 201 - Winter 2019 Assignment 2 Dr. Sarah...

Question

The assignment is attached.WordPuzzle_description CMPUT 201 - Winter 2019 Assignment 2 Dr. Sarah Nadi -- University of Alberta Arrays Inputs/Outputs Expressions Functions Selection statements and loops Strings and string library Pointers Program organization and variable scope The GitHub clasroom invitation link for the assignment is https://classroom.github.com/a/Xh-s-mwL By now, you should have already associated your GitHub account with your CCID when you used the invitation link for the Labs repo Once you click on the above link, GitHub will automatically create your private repository for this assignment. It will be at https://gihub.com/cmput201- w19/assignment2-. Please read the RepoStructure.md  to understand the files provided in the repo and how to find and interpret the Travis CI build status Please update the LICENSE.md  file with your name where it says  Make sure to continuously commit and push to your repository as you are developing your assignment and not simply when you are done. This serves two purposes: (1) you always have a backup of your code and can navigate through history to see your changes or revert back to an old version of the code that worked better and (2) showing your progress through the assignment and having the ability to explain the changes you were doing is of great help to you if you are suspected of plagiarism. Additionally, note that being able to use a version control system such as git is an essential skill you need to learn for any real software development job. Bob and Alice are competitive word-search puzzle solvers. However, even to the best of Bob's abilities, he was never able to find words in the puzzles faster than Alice. As Bob's friend and amazing programmer, you have decided to help him out by creating a solver for word-search puzzles. A word-search puzzle is solved when, given a grid of random letters and a set of words, the program finds the location of the input words in the grid (if they exist). The orientation of the words can be horizontal, vertical, left diagonal, or right diagonal. The words can be read left to right, right to left, top to bottom (whether vertically or diagonally), and bottom to up (whether vertically or diagonally). Note that a diagonal can start at any index, not necessarily on a central diagonal. You have decided to approach the problem using the Rabin-Karp algorithm. The Rabin-Karp algorithm uses what is called a hash function to find a substring of size x in a string of size y >= x. The hash function is applied as follows: Decide on a prime number p. For a substring of size x, the hash function multiplies the ASCII value of the first letter by p^(x-1), adds it to the ASCII value of the second letter multiplied by p^(x-2), and so on until the ASCII code of the last letter is multiplied by p^(0). For example, hash("hello") = 80976  with p=5 . This is calculated as hash("hello") = h*(5^4) + e*(5^3) + l*(5^2) + l*(5^1) + o*(5^0) = 104*625 + 101*125 + 108*25 + 108*5 + 111*1 = 80976 The Rabin-Karp algorithm applies this hash function to all substrings of a specific size in a given string, storing the calculated hash value for each applicable Concepts Covered GitHub Instructions Problem Description https://classroom.github.com/a/Xh-s-mwL https://gihub.com/cmput201-w19/assignment2-%3Cyour%20github%20id index of the given string. The hash value is stored at the index corresponding to the start of the substring being hashed. The number of stored hashes depends on the length of the given string and the length of the substring being searched for. If the algorithm cannot make a hash value with the specified length of the word, it counts those positions as 0 . For example, assume the algorithm is searching for the word oworl  in the string helloworld . Since the input word is of length 5, it will calculate the hash values of all substrings of length 5. In this case, it will calculate 10 hash values: the hash value of the word hello  at index 0, the hash value for the word ellow  at index 1, the hash value for the word llowo  at index 2, the hash value for the word lowor at index 3, the hash value of the word oworl  at index 4, the hash value of the word world  at index 5, and the value 0 in indices 6-9. While searching for a word, if any of the values match the hash value of the given word, the algorithm has found the position of the start of the word. The nice thing about Rabin-Karp is that it constructs consecutive hashes in O(1) time. This is done by taking the previous hash value, subtracting from it the hash value of the first letter of the previous hash, multiplying by the prime p, and adding the value of the new letter. For example, the hash value for the word hello  with a prime p=5 is 80976. To get the hash value for the next substring of length x  (x=5 in this case) ellow , we can simply remove the ASCII value for h (104) multiplied by p^(x-1), then multiply by p, then add the ASCII value of w (119). So the hash( ellow ) = ( 80976 - 104 * 5^(4) ) * 5 + 119 = 79999 For the purposes of this assignment, you must fix p to 101. Write a program that uses the Rabin-Karp algorithm to find the location of individual words in a given word-search grid and outputs their starting position and direction, if they exist. Enumerate the directions as follows: 1. horizontal right (→) 2. horizontal left (←) 3. vertical down (↓) 4. vertical up (↑) 5. top left to bottom right diagonal (↘) 6. bottom right backwards to top left diagonal (↖) 7. bottom left to top right (↗) 8. top right backwards to bottom left (↙) Your program runs as follows: ./wordSearch2D -p  -l  -w  [-o ] where: puzzle_file  is a required argument. It is preceded by the -p  flag. It is a text input file that contains the puzzle grid. The provided puzzle file will have n lines of single strings of length n, providing an n by n square grid of letters. Each line in the file represents a row, and each line will be of same size n. The positions go from 0 to n - 1 on each axis, with indices read from left to right and top to bottom. Note that 0  does not exist" Return Code 4 If the input wordlist_file  is not found (angle brackets are placeholders here, replace with appropriate file name): Error Message: "Error: Wordlist file  does not exist" Return Code 5 For any other incorrect program usage (e.g., forgetting a mandatory argument), your program should report (angle brackets need to appear as is here since they indicate the placeholders needed for correct usage): Error Message: "Usage: ./wordSearch2D -p  -l  -w  [-o ]" Return Code: 6 Unless explicitly stated in the assignment description or in the assumptions below, there are no simplifying assumptions in this assignment. You should handle all corner cases you can think of. If there is a case of incorrect input that prevents the program from proceeding correctly, your program should report: Error message: "Encountered error" Return code: 7 Only characters with ASCII values between 32 and 126 will appear in the puzzle and word files a  is not the same as A . This is already the case, given their ASCII codes The input word file can have any number of words, but each line will contain a single word. Each word will have a maximum size of 100 characters A word exists at most once in the puzzle Here is a full example. Given the following 5*5 puzzle file, puzzle.txt : ahelw hello gblfk cikml jdgod and the following word list, wordlist.txt : Error Checking Assumptions Example with Expected Output wok dog bat elk then running the program with ./wordSearch2D -l 3 -w wordlist.txt -p puzzle.txt -o soln.txt  would write

WordPuzzle_description CMPUT 201 - Winter 2019 Assignment 2 Dr. Sarah Nadi -- University of Alberta Arrays Inputs/Outputs Expressions Functions Selection statements and loops Strings and string...

Get Answer To This Question

Related Questions & Answers

Submit New Assignment