Fluent Essays

A word from the list is said to be in the grid if it appears horizontally, vertically, or diagonally in the grid of letters. You may assume that all words and grid letters will be in upper case and at least 2 letter long. The minimum size of the grid is 2×2 and the maximum size of the grid will be 1000×1000. The minimum size of the word list is 1 and the maximum size of the word list is 10000. The same word may occur more than once in the grid and some words in the list may not be in the grid assn1.pdf Unformatted Attachment Preview CSCI2110 Assignment 1 Instructor: Alex Brodsky Due∗: 11:59pm, Thursday, January 23, 2020 The purpose of this assignment is to refresh your programming skills and get you programming as quickly as possible. As discussed in class and the first tutorial, for each problem you will be provided with a description of the problem and a set of tests. These tests can be run on the submission system (Mimir) or on the unix server for this course. You can also use these tests on your own computer as illustrated in the first tutorial. Your code must compile. If it does not compile, you will receive a 0 on the assignment. The assignment consists of three (3) problems, corresponding to minimum (C), expected (B), and outstanding (A) levels of difficulty. That is, solving the first problem yields a grade of C, solving the first two problems yields a grade of B, and solving all three problems yields a grade of A. Background A Word Search puzzle consists of an n × n grid of letters, and list of words that are embedded in the grid. The orientation of the words may be horizontal, vertical, or diagonal, and the word may occur in either direction, e.g., left to right or right to left. Solving a word search puzzle involves finding all the words embedded in it. For example, the figure on the right shows a word search and its solution. Example of a word search puzzle https://technology.amis.nl/ wp-content/uploads/images/ wordSearch-1Solution.jpg Problem 1 (Grade C): Solve a Word Search Write a program called GridSearch.java that reads in a grid of letters and a list of words, and prints out all the words on the list that are embedded in the grid of letters. Input Your program should read in the input using a Scanner object, which is instantiated with System.in. The input will consists of several lines of text. 1. The first line contains a single integer, N , denoting the width and height of the grid. I.e. it’s an N × N grid. ∗ Latest version generated on: January 10, 2020 1 CSCI2110 Winter 2020 Assignment 1 2. The next N lines contain N letters each. The letters are separated by spaces. 3. The next line contains a single integer, W , denoting the size of the word list. 4. The next W lines each contain a single word Hint: Use the Scanner object to easily parse the input. For this assignment you only need to use the nextInt() and next() methods. Processing A word from the list is said to be in the grid if it appears horizontally, vertically, or diagonally in the grid of letters. You may assume that all words and grid letters will be in upper case and at least 2 letter long. The minimum size of the grid is 2×2 and the maximum size of the grid will be 1000×1000. The minimum size of the word list is 1 and the maximum size of the word list is 10000. The same word may occur more than once in the grid and some words in the list may not be in the grid. Output Your program should output to the console (System.out). The output consists of W lines, one per word from the list. Each line contains the number of times the word appears in the grid, a space, and the word. The order of the words must be the same as the input. Examples Sample Input Sample Output 3 A F C D E F G D I 3 FED IE IF 2 FED 1 IE 1 IF Sample Input Sample Output 3 A F C D E F G D I 1 HI 0 HI 2 CSCI2110 Winter 2020 Sample Input Sample Output 3 A B C D E F G H I 3 FED HI GET 1 FED 1 HI 0 GET Assignment 1 Problem 2 (Grade B): Word Search Equivalence Two word search puzzles are said to be equivalent with respect to a list of words if the number of times each word appears in each of the puzzles is the same. Write a program called GridEquiv.java that reads in two letter grids and a list of words, and determines if the two letter grids are equivalent with respect to the list of words. Hint: Your solution to Problem 1 is the starting point to Problem 2. Input The input will consists of several lines of text. 1. 2. 3. 4. 5. 6. The first line contains an integer, M , denoting the width and height of the first grid. The next M lines contain M letters each. The letters are separated by spaces. The next line contains an integer, N , denoting the width and height of the second grid. The next N lines contain N letters each. The letters are separated by spaces. The next line contains an integer, W , denoting the size of the word list. The next W lines each contain a single word Processing Same processing rules as Problem 1. An easy definition of non-equivalence is: if there is a word in the list such that that number of times it appears in the first grid differs from the number of times it appears in the second grid, then the two grids are not equivalent. Note: The locations of the words does not matter. Output Your program should output to the console (System.out). If two grids are equivalent, output Grids are equivalent. 3 CSCI2110 Winter 2020 Assignment 1 Otherwise, output the list of words for which make the two grids not equivalent. These words should be printed one per line, in the order they are in the input list. Examples Sample Input Sample Output 3 A B D E G H 4 X C Y F Z I W V 3 FED HI GET Grids are equivalent. C F I B E H U A D G T Sample Input Sample Output 3 A B D E G H 4 X T Y F Z I W V 3 FED HI GET HI GET C F I B E H U A D G I Problem 3 (Grade A): Word Search Chain Two words in a word search are intersecting if they intersect at a letter. For example, in the figure on the first page, HOLLAND and TOGO are intersecting. Two words are chained if there is a chain of intersections leading from one word to the other. For example, TOGO is chained to 4 CSCI2110 Winter 2020 Assignment 1 SPAIN because TOGO intersects with HOLLAND, which intersects with SPAIN. A grid is chained if each word in the grid is chained to every other word through a series of intersections. An algorithm for determining if a grid is chained is given below. The algorithm takes a list L of “word locations”, where a word location consists of the word, the row and column where it starts in the grid, and the direction (up, down, left, right, etc). (Hint: Creating a WordLocation class may be a good idea.) def isGridChained(L): C = empty list w = L.removeFirst() C.add(w) def findIntersection(C, L): for each w in L: for each c in C: if c intersects w: return w return null while L is not empty: w = findIntersection(C, L) if w != null: L.remove(w) C.add(w) else: return false return true Write a program called GridChain.java that reads in a letter grid and a list of words, and determines if the letter grid is chained with respect to the list of words. Hint: Your solution to Problem 1 is the starting point to Problem 3. Input Same input as Problem 1. Processing Same processing rules as Problem 1. Words that are not in the grid should be ignored. Output Your program should output to the console (System.out). If the grid is chained, output Grid is chained. Otherwise, output the list of words that are not chained to the first word in the list. The list of words should be in the same order as the words in the input list. 5 CSCI2110 Winter 2020 Assignment 1 Examples Sample Input Sample Output 3 A B C D E F G H I 5 AB BE HI HE IF Grid is chained. Sample Input Sample Output 3 A B C D E F G H I 5 AB BE HI HEN IF HI IF Hints and Suggestions • Your code must compile. If it does not compile, you will receive a 0 on the assignment. • Your code must be well commented and indented. Please see the Assignments section for this course on Brightspace for Code Style Guidelines. • You may assume that all input will be correct. You do not need to handle incorrect input, for now. • The problems in this assignment are short. The solutions for problems 1, 2, and 3, are 65, 80, and 140 lines of code, and both problem 2 and 3 start with the solution to problem 1. • Be sure to test your programs using the provided tests or via Mimir. To test without Mimir, see the README.txt file in the provided tests zip file. 6 CSCI2110 Winter 2020 Assignment 1 What to Hand In Submit the source files for your program via Mimir as described in the first tutorial. A link to Mimir is available on Brightspace. At least three of the submitted files must be called GridSearch.java, GridEquiv.java,and GridChain.java, which are the main programs for the three problems. Grading The assignment will be graded based on three criteria: Functionality “Does it work according to specifications?”. This is determined in an automated fashion by running your program on a number of inputs and ensuring that the outputs match the expected outputs. The score is determined based on the number of tests that your program passes. So, if your program passes Tt tests, you will receive that proportion of the marks. Each problem will be graded separately for functionality. Quality of Solution “Is it a good solution?” This considers whether the solution is correct, efficient, covers boundary conditions, does not have any obvious bugs, etc. This is determined by visual inspection of the code. Initially full marks are given to each solution and marks are deducted based on faults found in the solution. Each problem will be graded separated for quality. Code Clarity “Is it well written?” This considers whether the solution is properly formatted, well documented, and follows coding style guidelines. A single overall mark will be assigned for clarity. If your program does not compile, it is considered non-functional and of extremely poor quality, meaning you will receive 0 for the solution. Marks Problem 1: Word Search Functionality Quality of Solution Problem 2: Word Equivalence Functionality Quality of Solution Problem 3: Word Chains Functionality Quality of Solution Code Clarity Total 25 25 5 5 10 10 20 100 7 ... Purchase answer to see full attachment