How to resolve the algorithm Word search step by step in the Java programming language
How to resolve the algorithm Word search step by step in the Java programming language
Table of Contents
Problem Statement
A word search puzzle typically consists of a grid of letters in which words are hidden. There are many varieties of word search puzzles. For the task at hand we will use a rectangular grid in which the words may be placed horizontally, vertically, or diagonally. The words may also be spelled backwards. The words may overlap but are not allowed to zigzag, or wrap around.
Create a 10 by 10 word search and fill it using words from the unixdict. Use only words that are longer than 2, and contain no non-alphabetic characters. The cells not used by the hidden words should contain the message: Rosetta Code, read from left to right, top to bottom. These letters should be somewhat evenly distributed over the grid, not clumped together. The message should be in upper case, the hidden words in lower case. All cells should either contain letters from the hidden words or from the message. Pack a minimum of 25 words into the grid. Print the resulting grid and the solutions.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Word search step by step in the Java programming language
The provided code is written in Java and implements a word search game. The WordSearch class contains a nested Grid class that represents the game board and stores the grid of characters, a list of solutions (words found on the board), and the number of attempts it took to generate a valid grid.
The main method generates a word search grid and prints it to the console. It starts by reading a list of words from a file and then uses the createWordSearch method to generate a valid grid. The createWordSearch method starts by randomly shuffling the list of words, then it initializes a new Grid object and places a secret message on it using the placeMessage method. It then tries to place the words on the grid using the tryPlaceWord method. If the tryPlaceWord method is successful, it adds the word to the list of solutions and increments the number of cells filled.
The tryPlaceWord method starts by selecting a random direction and location on the grid. It then checks if the word can be placed in that location, taking into account the bounds of the grid and the existing characters on the board. If the word can be placed, it updates the grid with the new characters and adds the word to the list of solutions.
The printResult method prints the grid to the console, along with the number of attempts it took to generate the grid and the number of words found. It prints the grid in a table format, with the rows and columns labeled. It also prints the list of solutions, grouped into pairs when possible.
Here are some key concepts and algorithms used in the code:
- Grid: The game board is represented as a grid of characters. Each cell in the grid can contain a letter or a blank space.
- Word placement: The
tryPlaceWordmethod uses a greedy algorithm to try to place words on the grid. It starts by selecting a random direction and location, then checks if the word can be placed in that location. If the word can be placed, it updates the grid with the new characters and adds the word to the list of solutions. - Solution checking: The
tryLocationmethod checks if a word can be placed in a given location on the grid. It checks the bounds of the grid and the existing characters on the board. - Random generation: The
createWordSearchmethod uses a random number generator to shuffle the list of words and select a random direction and location for each word. This helps to ensure that the grid is not always the same.
Source code in the java programming language
import java.io.*;
import static java.lang.String.format;
import java.util.*;
public class WordSearch {
static class Grid {
int numAttempts;
char[][] cells = new char[nRows][nCols];
List<String> solutions = new ArrayList<>();
}
final static int[][] dirs = {{1, 0}, {0, 1}, {1, 1}, {1, -1}, {-1, 0},
{0, -1}, {-1, -1}, {-1, 1}};
final static int nRows = 10;
final static int nCols = 10;
final static int gridSize = nRows * nCols;
final static int minWords = 25;
final static Random rand = new Random();
public static void main(String[] args) {
printResult(createWordSearch(readWords("unixdict.txt")));
}
static List<String> readWords(String filename) {
int maxLen = Math.max(nRows, nCols);
List<String> words = new ArrayList<>();
try (Scanner sc = new Scanner(new FileReader(filename))) {
while (sc.hasNext()) {
String s = sc.next().trim().toLowerCase();
if (s.matches("^[a-z]{3," + maxLen + "}$"))
words.add(s);
}
} catch (FileNotFoundException e) {
System.out.println(e);
}
return words;
}
static Grid createWordSearch(List<String> words) {
Grid grid = null;
int numAttempts = 0;
outer:
while (++numAttempts < 100) {
Collections.shuffle(words);
grid = new Grid();
int messageLen = placeMessage(grid, "Rosetta Code");
int target = gridSize - messageLen;
int cellsFilled = 0;
for (String word : words) {
cellsFilled += tryPlaceWord(grid, word);
if (cellsFilled == target) {
if (grid.solutions.size() >= minWords) {
grid.numAttempts = numAttempts;
break outer;
} else break; // grid is full but we didn't pack enough words, start over
}
}
}
return grid;
}
static int placeMessage(Grid grid, String msg) {
msg = msg.toUpperCase().replaceAll("[^A-Z]", "");
int messageLen = msg.length();
if (messageLen > 0 && messageLen < gridSize) {
int gapSize = gridSize / messageLen;
for (int i = 0; i < messageLen; i++) {
int pos = i * gapSize + rand.nextInt(gapSize);
grid.cells[pos / nCols][pos % nCols] = msg.charAt(i);
}
return messageLen;
}
return 0;
}
static int tryPlaceWord(Grid grid, String word) {
int randDir = rand.nextInt(dirs.length);
int randPos = rand.nextInt(gridSize);
for (int dir = 0; dir < dirs.length; dir++) {
dir = (dir + randDir) % dirs.length;
for (int pos = 0; pos < gridSize; pos++) {
pos = (pos + randPos) % gridSize;
int lettersPlaced = tryLocation(grid, word, dir, pos);
if (lettersPlaced > 0)
return lettersPlaced;
}
}
return 0;
}
static int tryLocation(Grid grid, String word, int dir, int pos) {
int r = pos / nCols;
int c = pos % nCols;
int len = word.length();
// check bounds
if ((dirs[dir][0] == 1 && (len + c) > nCols)
|| (dirs[dir][0] == -1 && (len - 1) > c)
|| (dirs[dir][1] == 1 && (len + r) > nRows)
|| (dirs[dir][1] == -1 && (len - 1) > r))
return 0;
int rr, cc, i, overlaps = 0;
// check cells
for (i = 0, rr = r, cc = c; i < len; i++) {
if (grid.cells[rr][cc] != 0 && grid.cells[rr][cc] != word.charAt(i))
return 0;
cc += dirs[dir][0];
rr += dirs[dir][1];
}
// place
for (i = 0, rr = r, cc = c; i < len; i++) {
if (grid.cells[rr][cc] == word.charAt(i))
overlaps++;
else
grid.cells[rr][cc] = word.charAt(i);
if (i < len - 1) {
cc += dirs[dir][0];
rr += dirs[dir][1];
}
}
int lettersPlaced = len - overlaps;
if (lettersPlaced > 0) {
grid.solutions.add(format("%-10s (%d,%d)(%d,%d)", word, c, r, cc, rr));
}
return lettersPlaced;
}
static void printResult(Grid grid) {
if (grid == null || grid.numAttempts == 0) {
System.out.println("No grid to display");
return;
}
int size = grid.solutions.size();
System.out.println("Attempts: " + grid.numAttempts);
System.out.println("Number of words: " + size);
System.out.println("\n 0 1 2 3 4 5 6 7 8 9");
for (int r = 0; r < nRows; r++) {
System.out.printf("%n%d ", r);
for (int c = 0; c < nCols; c++)
System.out.printf(" %c ", grid.cells[r][c]);
}
System.out.println("\n");
for (int i = 0; i < size - 1; i += 2) {
System.out.printf("%s %s%n", grid.solutions.get(i),
grid.solutions.get(i + 1));
}
if (size % 2 == 1)
System.out.println(grid.solutions.get(size - 1));
}
}
You may also check:How to resolve the algorithm Loops/Continue step by step in the C# programming language
You may also check:How to resolve the algorithm Nested function step by step in the Mathematica/Wolfram Language programming language
You may also check:How to resolve the algorithm Box the compass step by step in the Ruby programming language
You may also check:How to resolve the algorithm Compare length of two strings step by step in the Haskell programming language
You may also check:How to resolve the algorithm Numerical integration step by step in the Pascal programming language