/**
* See https://en.wikipedia.org/wiki/Word_search
*
* Enhance the program shown below.
*
* 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.
*
* 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 + "]";
}
}
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);
}
abstract class AbstractWordSearcher implements WordSearcher {
protected final char[][] grid;
protected final int numRows, numCols;
protected AbstractWordSearcher(final char[][] grid) {
this.grid = grid;
this.numRows = grid.length;
this.numCols = grid[0].length;
}
public final String toString() {
final StringBuilder sb = new StringBuilder();
for (int i = 0; i < numRows; i = i + 1) {
for (int j = 0; j < numCols; j = j + 1) {
sb.append(grid[i][j]);
}
sb.append('\n');
}
return sb.toString();
}
}
final class LinearWordSearcher extends AbstractWordSearcher {
public LinearWordSearcher(final char[][] grid) {
super(grid);
}
public 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));
}
}
}
}
public class WordSearch {
public static void main(final String[] args) {
final int maxPrintable = 10000;
final int numArgs = args == null ? 0 : args.length;
if (numArgs < 2) {
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 " + maxPrintable + ". ");
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]);
}
final WordSearcher ws = new LinearWordSearcher(grid);
System.out.println("Word Search\n");
for (String word : words) {
System.out.print(word + ": ");
System.out.println(ws.occurrencesOf(word).size());
}
if (numRows * numCols <= maxPrintable) {
System.out.println("\n" + ws);
}
}
}