CMPUT 201 Practical Programming Methodology - Assignment 2: Rabin-Karp algorithm
Problem Description
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.
Algorithm Description
You may wonder, why use hash functions at all? Why don't we just use brute-force search? We certainly could do that, but it would be highly inefficient. If you don't know anything algorithm complexity, and symbols like O(n), O(logn) or O(1) sound foreign to you, review this article: Complexity of Algorithms. So, as you can imagine, using a special algorithm for string matching makes the process much, much faster.
bash tests/github_actions/github_actions.sh
Let's assume that we're searching for a word "dog" in a string "gadogado". We need to compare "dog" with any substring of "gadogado" that has the same length ("gad", "ado", "dog", "oga", "gad", "ado"). So, in a sense, you are "rolling" the word "dog" over the string "gadogado". To compare the word with the substrings, instead of comparing them character by character (which would be very time consuming!), wouldn't it be nice if we had some fixed value that represents each substring? Then, we can just quickly compare these values! Here comes the idea of a hash function.
What is a hash function? It's a function that can be used to map data of arbitrary size to fixed-size values. For example, a hash function can map strings to integers. Probably, one of the simplest hash functions would be the sum of ASCII codes of the characters of the string:
s = "gadogado"
H(s[0..3]) = H("gad") = 103 + 97 + 100 = 300 H(s[1..4]) = H("ado") = 97 + 100 + 111 = 311 H(s[2..5]) = H("dog") = 100 + 111 + 103 = 314
However, it's not the best hash function because it allows many collisions when different strings have equal hash values. For example:
So we need to have a better hash function, that can take into account the order and position of letters. Here is how it works in the Rabin-Karp algorithm.
Study this resource to understand the algorithm.
Let's see an example of how to find the word dog in the string gadogado using the Rabin-Karp algorithm.
- We need to know the size of our alphabet -- D. We use ASCII codes, so D = 256.
- Also, we need to choose a large enough prime number. The higher it is, the less collisions we will see. As a rule of thumb, it should be larger than the alphabet size. For this example, we'll use P = 577 (in your assignment, you'll use a different value, see below).
- Let's calculate the value of h. It's a rehashing coefficient, and we'll need it later, on Step 7. h = D^(len- 1) % P (len is the length of the word we're searching ("dog"), so len=3) In this example, h = 335.
4. Now, let's calculate the hash of the word "dog", letter by letter, using this step-by-step formula:
H("dog") = 100 + 111 + 103 = 314 H("axa") = 97 + 120 + 97 = 314 H("esb") = 101 + 115 + 98 = 314
hash = (D * <previous_hash> + <current letter>) % P;
- Let's now loop through the string "gadogado", calculating "rolling" hashes of all three-letter substrings of it: "gad", "ado", ... .
- First, let's calculate the hash of the substring "gad". Applying the same formula as above, we get the result: hash of "gad" is 6.
- Now, we start "rolling" through the string "gadogado", or "rehashing" -- basically, moving to the right. Moving from "gad" to "ado" means that we need to "subtract" the letter "g" and "add" the letter "o". In the modular arithmetic of the Rabin-Karp algorithm, it's done the following way:
Thus, hash of "ado" is 506 (if the result if negative, just subtract it from P). Rolling one more step to the right, we can get from "ado" to "dog". Applying the same formula, we get the hash of "dog": 280!
- We see that we have found the hash we were looking for. So, with some probability, we have found the word we're looking for. But beware of collisions! Even with large enough P, collisions can happen. So, the final step.
- To be certain that we found the right substring, we need to compare the word with the found substring character by character.
IMPORTANT: For the purposes of this assignment, you must fix P (the prime number) to 7079, and D (alphabet size) to 256.
Task
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 (↑)
hash = (D * (<previous_hash> - <letter to subtract> * h) + <letter to add>) % 577
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 (↙)
How to run your program Your program runs as follows:
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 word_length is a required argument. It is preceded by the -l flag. It is a number in the range [1, n] that represents the fixed length of the words the program will search for.
wordlist_file is a required argument. It is preceded by the -w flag. It is a text input file that contains the list of words to look for. Each word will be provided on a separate line and will have exactly word_length characters; otherwise, the wordlist file is invalid. The wordlist file can contain any ASCII character with values [32, 126], not necessarily English letters only.
If the input word is not found in the puzzle, the output would be word;(0,0);0. Note that the top left corner of the puzzle corresponds to coordinate (0,0), but since the direction is 0, this indicates that the word is not found. Note that you must output the solution of each input word in the same order they were provided in the wordlist_file.
You must account for any edge cases for command-line arguments. We may run with too many arguments, not enough arguments, invalid arguments, etc. Also, note that, similar to assignment 1, the order of the arguments is not fixed. For example, ./wordSearch2D -w wordList.txt -p puzzleFile.txt -l 20 is valid.
Error Checking
./wordSearch2D -p <puzzle_file> -l <word_length> -w <wordlist_file> [-o <solution_file>]
Your program must report and print an error to stderr and quit in the following cases. Note the return code that needs to be returned in each case. The return code is the integer that your program returns upon exit (e.g., return 0; in main or exit(2) from anywhere in the program). The error message should be the exact error message provided:
If the input puzzle_file is not found (angle brackets are placeholders here, replace with appropriate file name)
Assumptions
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
Error: Puzzle file <name-of-input-file> does not exist
Error: Wordlist file <name-of-input-file> does not exist
Usage: ./wordSearch2D -p <puzzle_file> -l <word_length> -w <wordlist_file> [-o <solution_file>]
Example with Expected Output Here is a full example.
Given the following 5*5 puzzle file, puzzle.txt:
batlw
hello
gblfk
cikkl
jdgod
then running the program with
would write the following to a file called mysolution.com.png:
./wordSearch2D -l 3 -w wordlist.txt -p puzzle.txt -o mysolution.com.png
wok;(0,4);3
dog;(4,4);2
bat;(0,0);1
elk;(1,1);5
xxx;(0,0);0
Note that the directions correspond to the enumerated list provided above.
Program Organization
Your program must have the following files
Only your main function and any helper methods for reading arguments should be in a file called
src/wordSearch2D.c
All functionality related to solving the word puzzle should be in file src/puzzle2D.c and its corresponding header file src/puzzle2D.h. You must divide the logic of solving the word puzzle into multiple functions.
Feel free to add additional files and functions to further divide the functionality in your program.
You must not use any global variables! You can define macros for predefined constants such as the maximum puzzle size or the prime number, but you cannot use any global variables.
All .c and .h files must be in ./src. Your Makefile must be at the project root and the binary it produces (wordSearch2D) is also at the root.
Refer to the repository-layout to know how your repository should look (though you can always add MORE files). Use the following command on our lab machines to see what your repository structure: