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 pro gramming 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.
Problem 1 Grade C: Solve a Word Search
Example of a word search puzzle
https:technology.amis.nl wpcontentuploadsimages wordSearch1Solution.jpg
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. its 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 22 and the maximum size of the grid will be 10001000. 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
3 AFC DEF GDI 3
FED IE
IF
Sample Input
3 AFC DEF GDI 1
HI
Sample Output
2 FED 1IE 1IF
Sample Output
0HI
2
CSCI2110 Sample Input
3
A B C D E F GHI 3
FED HI GET
Winter 2020 Sample Output
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. The first line contains an integer, M, denoting the width and height of the first grid. 2. The next M lines contain M letters each. The letters are separated by spaces.
3. The next line contains an integer, N, denoting the width and height of the second grid. 4. The next N lines contain N letters each. The letters are separated by spaces.
5. The next line contains an integer, W , denoting the size of the word list. 6. The next W lines each contain a single word
Processing
Same processing rules as Problem 1.
An easy definition of nonequivalence 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
3
ABC DEF GHI
4 XCBA YFED ZIHG WVUT 3
FED
HI
GET
Sample Input
3
ABC DEF GHI
4 XTBA YFED ZIHG WVUI 3
FED
HI
GET
Sample Output
Grids are equivalent.
Sample Output
HI GET
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 isGridChainedL:
C empty list
w L.removeFirst
C.addw
while L is not empty:
w findIntersectionC, L
if w ! null:
L.removew
C.addw
else:
return false
return true
def findIntersectionC, L:
for each w in L:
for each c in C:
if c intersects w:
return w
return null
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 Examples
Sample Input
3 ABC DEF GHI 5
AB
BE
HI
HE
IF
Sample Input
3 ABC DEF GHI 5
AB
BE
HI HEN IF
Winter 2020
Sample Output
Grid is chained.
Assignment 1
Hints and Suggestions
Sample Output
HI IF
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 auto
mated 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 t tests, you will receive T
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 format
ted, 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 nonfunctional and of extremely poor quality, meaning you will receive 0 for the solution.
Marks
Problem 1: Word Search Functionality
Quality of Solution
25 25
Problem 2: Word Equivalence Functionality
Quality of Solution
5 5
Problem 3: Word Chains Functionality
Quality of Solution
10 10
Code Clarity
20
Total
100
7