Professor Neil enjoys playing word search puzzles when on airplanes. The objecti
ID: 3703351 • Letter: P
Question
Professor Neil enjoys playing word search puzzles when on airplanes. The objective is to locate words hidden in a table of letters. The word might be written in a horizontal or vertical orientation. It might be written from bottom to top (upside down) or left to right (backwards). A particularly fun version of a word search puzzle is one where the words can be written with changes in direction. A word that starts out being written from top to bottom might take a turn in the middle and continue left to right.
For example, if you are searching for the word “helifex”, it might be written like this:
h
e
l
i f e x
If you are looking for “yellow“, it might appear like this:
w
o l
l
e y
In this problem you will write a program to read a word search grid from a file and then ask the user what word they would like to search for.
The user will enter the word from the keyboard.
When you locate the word in the grid, display the location of each letter in the word by displaying its cell location in the table.
Here is an example of a word search grid.
Suppose you want to find the word "eskimo".
It can be found beginning at location Row 2, Column 2 and the path is expressed like this:
e:2,2 s:2,3 k:2,4 i:3,4 m:4,4 o:5,4
Words will always be contiguous in the grid, and the turns must be 90 degrees. Using the sample grid above, the word “salty” is:
s:1,5 a:2,5 l:3,5 t:4,5 y:5,5
You must also handle the case where a word the user enters doesn’t exist in the gird.
Using the sample grid above, the word "pizza" could not be found. In that case, display the word (pizza) and “cannot be found” as shown in the sample output below.
All letters will be lower case as will the words to be searched for. The same letter may appear more than once but correct combinations of letters will only appear once. For example, if the hidden word is “eskimo” the letters e and s may appear many times individually but will only appear “together” once.
The input will consist of a text file named wordpuzzle.txt. The first two pieces of data on the file will be the number of rows and the number of columns in the word search puzzle. This will be followed by the correct number of letters to fill up the word search puzzle. All the data will be on a single line in the file. Each piece of data will be separated by a single space.
Prompt the user to enter the word to search for as shown in the table below. You can execute (run) your application multiple times testing one word with each execution.
s o f t s w e s k a o l z i l k l q m t r e y o yExplanation / Answer
===================================================================================
Modified the program to read input string with spaces between every letter.
Added Program sample output. Tested with example provided in question.
==================================================================================
WordMatrix.java file
-----------------------------------
import java.io.*;
import java.util.LinkedList;
import java.util.Scanner;
public class WordMatrix {
public int[][] solution;
int path = 1;
LinkedList<String> solution2 = new LinkedList<String>();
// initialize the solution matrix in constructor.
public WordMatrix(int N, int C) {
solution = new int[N][C];
for (int i = 0; i < N; i++) {
for (int j = 0; j < C; j++) {
solution[i][j] = 0;
}
}
}
public boolean searchWord(char[][] matrix, String word) {
int N = matrix.length;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (search(matrix, word, i, j, 0, N)) {
return true;
}
}
}
return false;
}
public boolean search(char[][] matrix, String word, int row, int col,
int index, int N) {
// check if current cell not already used or character in it is not not
if (solution[row][col] != 0 || word.charAt(index) != matrix[row][col]) {
return false;
}
if (index == word.length() - 1) {
// word is found, return true
solution[row][col] = path++;
solution2.add(word.charAt(index) + " : (" + (row+1) + "," + (col+1) + ")");
return true;
}
// mark the current cell as 1
solution[row][col] = path++;
solution2.add(word.charAt(index) + " : (" + (row+1) + "," + (col+1) + ")");
// check if cell is already used
if (row + 1 < N && search(matrix, word, row + 1, col, index + 1, N)) { // go
// down
return true;
}
if (row - 1 >= 0 && search(matrix, word, row - 1, col, index + 1, N)) { // go
// up
return true;
}
if (col + 1 < N && search(matrix, word, row, col + 1, index + 1, N)) { // go
// right
return true;
}
if (col - 1 >= 0 && search(matrix, word, row, col - 1, index + 1, N)) { // go
// left
return true;
}
// if none of the option works out, BACKTRACK and return false
solution[row][col] = 0;
solution2.removeLast();
path--;
return false;
}
public void print() {
System.out.println();
System.out.println("Solution: " + solution2);
}
public static void main(String[] args) throws IOException {
//FileInputStream in = null;
File file = new File("wordpuzzle.txt"); //change file path accordingly
Scanner input = new Scanner(file);
//read number of rows and columns
int rows = input.nextInt();
int columns = input.nextInt();
String str = input.nextLine().replaceAll(" ", "");; // Read the remaining text to string
//System.out.println(str);
char[][] words = new char[rows][];
// Splitting the string into multiple words and store in a 2D array.
for (int i=0, pos=0; i < rows; i++, pos=pos+columns) {
// getting word with column (word length) number of chars.
words[i] = str.substring(pos, pos+columns).toCharArray();
}
//class object
WordMatrix w = new WordMatrix(rows, columns);
Scanner in = new Scanner(System.in);
String a;
System.out.println("Enter word to Search:");
a = in.nextLine();
if (w.searchWord(words, a)) {
w.print();
} else {
System.out.println(a + " was not found.");
}
in.close();
input.close();
}
}
=========================================================
wordpuzzle.txt
----------------------
5 5 s o f t s w e s k a n m z i l k c q m t r u f o y
==============================================================
Sample Output:
Enter word to Search:
soft
Solution: [s : (1,1), o : (1,2), f : (1,3), t : (1,4)]
Enter word to Search:
eskimo
Solution: [e : (2,2), s : (2,3), k : (2,4), i : (3,4), m : (4,4), o : (5,4)]
Enter word to Search:
salty
Solution: [s : (1,5), a : (2,5), l : (3,5), t : (4,5), y : (5,5)]
Enter word to Search:
yellow
yellow was not found. //Note: the word yellow is not present in puzzle. mistake in the exmple given in question.
Enter word to Search:
pizza
pizza was not found.
===========================================================================
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.