If you attended K–12 schools in the U.S., there’s a good chance you were given word search worksheets to fill out. I know I
certainly spent many an afternoon rushing to finish these so I wouldn’t have to actually bring home any homework.
You shall write a Python 3 program (compatible up to Python 3.9) that reads a word-search grid from standard input, and
prints all valid words in the grid to standard output. Specifically:
1. Use cse30_word_search as the name the module intended to be run as __main__.
2. The grid will consist of any number of lines of text on standard input, containing uppercase English letters.
I. You may assume that the length of each line is also the total number of lines, i.e. that the grid is square.
3. The program shall expect two command-line arguments, which together dictate the characteristics of a valid word:
I. Argument 1 shall be a positive integer indicating the minimum length of a valid word.
II. Argument 2 shall be a path to a spell-checking dictionary file.
a. You may assume that the dictionary file contains one word per line, though there are no guarantees
on case or contents otherwise.
4. The output shall consist of all unique valid words in the grid, one per line, in alphabetical order.
I. Words may be oriented in any horizontal, vertical, or diagonal direction from the initial letter (i.e., 8
Make sure that you choose an approach with appropriate data types and algorithms so that the time complexity of your solution is:
1. Good enough as a baseline to terminate within 5 seconds given 20×20 grids and dictionary sizes up to 1 million words.
2. O(n) or better where n is the total size of the grid
3. O(log n) or better where n is the total size of the dictionary
4. O(n) or better where is the difference between the dimension of the grid and the minimum length of a valid word (e.g. 8 for
a 10×10 grid with a minimum length of 2)
Testing and Demos
Two sample executables are available on the server:
1. cse30_word_search_gen creates grids compatible with your program.
It expects three command-line arguments:
I. n: The dimension of the grid (i.e. output will consist n lines, each of which has length n)
II. min_length: The minimum length of a valid word
III. dict_file: A path to the same kind of dictionary file your program expects.
It produces two distinct outputs:
I. The grid is emitted on standard output.
II. The dictionary words are emitted on standard error, one per line, sorted alphabetically.
2. cse30_word_search demonstrates the expected behavior of your program.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx