/**
* See https://en.wikipedia.org/wiki/Word_search
*
* The program shown below implements the following enhancements
* to the Word Search program posted at:
*
* https://apcsafreeresponsequestions.blogspot.com/2019/02/word-search.html
*
* 1. Create a class called Snake that implements WordLocations.
* A Snake object should represent the location of a word that
* may snake around in a word search grid.
*
* 2. Create a class called SerpentineWordSearcher that extends
* LinearWordSearcher and has a method that overrides search.
*
* 3. Expand the main method of the program shown below so that it
* searches the same randomly generated word search grid using both
* LinearWordSearcher and SerpentineWordSearcher objects. Enhance
* the output of the program accordingly.
*
* The following enhancements need to be implemented:
*
* 4. Add the following methods to the WordLocation interface:
*
* int wordLength();
* Cell getCell(final int i);
*
* Update Segment and Snake.
*
* 5. Add the following method to AbstractWordSearcher:
*
* String showWords(final List<WordLocation> locations);
*
* The method should return a string corresponding to the word
* search grid associated with the searcher; the letters of the
* words identified by parameter locations should somehow be
* highlighted such that they are easy to spot. For example, the
* other letters could be converted to lowercase or they could be
* replace by a single character, such as a period. Update the
* main method of the program so that it somehow uses showWords.
*/
import java.util.*;
final class Cell {
public final int row;
public final int col;
public Cell(final int row, final int col) {
this.row = row;
this.col = col;
}
public String toString() {
return "(" + row + "," + col + ")";
}
}
interface WordLocation {
}
final class Segment implements WordLocation {
public final Cell first;
public final Cell last;
public Segment(final Cell first, final Cell last) {
this.first = first;
this.last = last;
}
public String toString() {
return "[" + first + "," + last + "]";
}
}
final class Snake implements WordLocation {
public final List<Cell> cells = new ArrayList<Cell>();
public Snake add(final int i, final Cell cell) {
cells.add(i, cell);
return this;
}
}
final class GridStringifier {
public static String toString(final char[][] grid) {
final int numRows = grid.length;
final StringBuilder sb = new StringBuilder();
for (int i = 0; i < numRows; i = i + 1) {
final int numCols = grid[i].length;
for (int j = 0; j < numCols; j = j + 1) {
sb.append(grid[i][j]);
}
sb.append('\n');
}
return sb.toString();
}
}
abstract class CharacterGridBuilder {
public final char[][] getGrid(final int numRows, final int numCols) {
final char[][] grid = new char[numRows][numCols];
final int n = numRows * numCols;
for (int i = 0; i < numRows; i = i + 1) {
for (int j = 0; j < numCols; j = j + 1) {
grid[i][j] = getCharacter();
}
}
return grid;
}
public abstract char getCharacter();
}
final class RandUpperGridBuilder extends CharacterGridBuilder {
public char getCharacter() {
return (char)('A' + (int)(Math.random() * 26));
}
}
final class ConstCharGridBuilder extends CharacterGridBuilder {
private final char constChar;
public ConstCharGridBuilder(final char constChar) {
this.constChar = constChar;
}
public char getCharacter() {
return constChar;
}
}
final class WordSearchBuilder {
private final RandUpperGridBuilder randUpperBuilder = new RandUpperGridBuilder();
private final ConstCharGridBuilder constCharBuilder = new ConstCharGridBuilder('.');
private final int numRows, numCols;
public WordSearchBuilder(final int numRows, final int numCols) {
this.numRows = numRows;
this.numCols = numCols;
}
public char[][] getRandomGrid() {
return randUpperBuilder.getGrid(numRows, numCols);
}
public char[][] getEmptyGrid(final int numRows, final int numCols) {
return constCharBuilder.getGrid(numRows, numCols);
}
}
interface WordSearcher {
List<WordLocation> occurrencesOf(final String word);
String stringifyGrid();
}
abstract class AbstractWordSearcher implements WordSearcher {
protected final char[][] grid;
protected final int numRows, numCols;
protected AbstractWordSearcher(final char[][] grid) {
this.grid = grid;
if (grid == null)
throw new IllegalArgumentException("word search grid is null");
numRows = grid.length;
if (numRows == 0)
throw new IllegalArgumentException("word search grid has zero rows");
numCols = grid[0].length;
for (char[] row : grid)
if (row.length != numCols)
throw new IllegalArgumentException("word search grid is jagged");
}
public final String stringifyGrid() {
return GridStringifier.toString(grid);
}
}
class LinearWordSearcher extends AbstractWordSearcher {
public LinearWordSearcher(final char[][] grid) {
super(grid);
}
public final List<WordLocation> occurrencesOf(final String word) {
List<WordLocation> locations = new LinkedList<WordLocation>();
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
search(locations, word, i, j);
}
}
return locations;
}
protected void search(final List<WordLocation> locations,
String word, final int startRow, final int startCol
) {
final int n = word.length();
// The search is simple if the length of word is 1;
if (n == 1) {
if (word.charAt(0) == grid[startRow][startCol]) {
final Cell startEnd = new Cell(startRow, startCol);
locations.add(new Segment(startEnd, startEnd));
}
return;
}
// otherwise,
final List<Cell> terminals = new LinkedList<Cell>();
int i, r, c, lastRow=-1, lastCol=-1;
// search down;
for (i=0, r=startRow, c=startCol; i < n; i++, r++) {
if (r >= numRows || word.charAt(i) != grid[r][c]) break;
lastRow = r;
lastCol = c;
}
if (i == n) terminals.add(new Cell(lastRow, lastCol));
// search up;
for (i=0, r=startRow, c=startCol; i < n; i++, r--) {
if (r < 0 || word.charAt(i) != grid[r][c]) break;
lastRow = r;
lastCol = c;
}
if (i == n) terminals.add(new Cell(lastRow, lastCol));
// search right;
for (i=0, r=startRow, c=startCol; i < n; i++, c++) {
if (c >= numCols || word.charAt(i) != grid[r][c]) break;
lastRow = r;
lastCol = c;
}
if (i == n) terminals.add(new Cell(lastRow, lastCol));
// search left;
for (i=0, r=startRow, c=startCol; i < n; i++, c--) {
if (c < 0 || word.charAt(i) != grid[r][c]) break;
lastRow = r;
lastCol = c;
}
if (i == n) terminals.add(new Cell(lastRow, lastCol));
// search down and right;
for (i=0, r=startRow, c=startCol; i < n; i++, r++, c++) {
if (r >= numRows || c >= numCols || word.charAt(i) != grid[r][c]) break;
lastRow = r;
lastCol = c;
}
if (i == n) terminals.add(new Cell(lastRow, lastCol));
// search up and right;
for (i=0, r=startRow, c=startCol; i < n; i++, r--, c++) {
if (r < 0 || c >= numCols || word.charAt(i) != grid[r][c]) break;
lastRow = r;
lastCol = c;
}
if (i == n) terminals.add(new Cell(lastRow, lastCol));
// search down and left;
for (i=0, r=startRow, c=startCol; i < n; i++, r++, c--) {
if (r >= numRows || c < 0 || word.charAt(i) != grid[r][c]) break;
lastRow = r;
lastCol = c;
}
if (i == n) terminals.add(new Cell(lastRow, lastCol));
// search up and left;
for (i=0, r=startRow, c=startCol; i < n; i++, r--, c--) {
if (r < 0 || c < 0 || word.charAt(i) != grid[r][c]) break;
lastRow = r;
lastCol = c;
}
if (i == n) terminals.add(new Cell(lastRow, lastCol));
// then compile a list of locations where the word was found.
if (terminals.size() > 0) {
final Cell begin = new Cell(startRow, startCol);
for (Cell end : terminals) {
locations.add(new Segment(begin, end));
}
}
}
}
final class SerpentineWordSearcher extends LinearWordSearcher {
public SerpentineWordSearcher(final char[][] grid) {
super(grid);
}
protected void search(final List<WordLocation> locations,
String word, final int startRow, final int startCol
) {
final int n = word.length();
final Cell head =
(n > 0 && word.charAt(0) == grid[startRow][startCol]) ?
new Cell(startRow, startCol) : null;
if (head == null) return;
// The search is simple if the length of word is 1;
if (n == 1) {
locations.add(new Snake().add(0, head));
return;
}
// otherwise,
final String beheadedWord = word.substring(1);
final List<WordLocation> tails = new LinkedList<WordLocation>();
// search down;
if (startRow + 1 < numRows)
search(tails, beheadedWord, startRow + 1, startCol);
// search down and right;
if (startRow + 1 < numRows && startCol + 1 < numCols)
search(tails, beheadedWord, startRow + 1, startCol + 1);
// search right;
if (startCol + 1 < numCols)
search(tails, beheadedWord, startRow, startCol + 1);
// search right and up;
if (startRow > 0 && startCol + 1 < numCols)
search(tails, beheadedWord, startRow - 1, startCol + 1);
// search up;
if (startRow > 0)
search(tails, beheadedWord, startRow - 1, startCol);
// search up and left;
if (startRow > 0 && startCol > 0)
search(tails, beheadedWord, startRow - 1, startCol - 1);
// search left;
if (startCol > 0)
search(tails, beheadedWord, startRow, startCol - 1);
// search down and left;
if (startRow + 1 < numRows && startCol > 0)
search(tails, beheadedWord, startRow + 1, startCol - 1);
// add head to tails and snakes to locations.
for (WordLocation tail : tails)
locations.add(((Snake)tail).add(0, head));
}
}
public class WordSearch {
private static final int maxPrintableChars = 10000;
private static void search(final List<String> words, final WordSearcher ws) {
System.out.println("Word Search\n");
for (String word : words) {
System.out.print(word + ": ");
System.out.println(ws.occurrencesOf(word).size());
}
}
private static void printHelp() {
System.out.println("Syntax: row_count column_count optional_word_list");
System.out.print("Example: ");
System.out.println("100 100 A QUICK BROWN FOX JUMPED OVER THE LAZY DOG");
System.out.println();
System.out.print("Prints the number of times each word in ");
System.out.println("optional_word_list appears in a grid.");
System.out.print("Prints the grid if column_count times row_count ");
System.out.println("is not greater than " + maxPrintableChars + ". ");
}
public static void main(final String[] args) {
final int numArgs = args == null ? 0 : args.length;
if (numArgs < 2) {
printHelp();
return;
}
final int numRows = Integer.parseInt(args[0]);
final int numCols = Integer.parseInt(args[1]);
final WordSearchBuilder wsb = new WordSearchBuilder(numRows, numCols);
final char[][] grid = wsb.getRandomGrid();
final List<String> words = new LinkedList<String>();
for (int i = 2; i < numArgs; i = i + 1)
words.add(args[i]);
System.out.print("Linear ");
search(words, new LinearWordSearcher(grid));
System.out.print("\nSerpentine ");
search(words, new SerpentineWordSearcher(grid));
if (numRows * numCols <= maxPrintableChars)
System.out.println("\n" + GridStringifier.toString(grid));
}
}