Newsletter Inverse

[Joel McNary]

OK, thinking about the June newletter / wordfind problem got me thinking about the inverse. What algortihm can be used to hide words in a grid?
a). Write a program to hide a list of words in a grid. The program should take a list of words and a grid size (through any input means you want), and produce as output a grid with those words hidden in it. Exceptions can be handled any way you see fit (you can't hide "redneck" in a 2x2 grid...). non-used spaces in the grid should be filled with random characters.
b). This is the same as (a), except that instead of a grid size and random-characters, the program uses a string of characters to fill in the empty spaces (usually a quote with spaces removed), thereby producing a "true" word seek puzzle. (Good word seek solvers always look at the left over letters to see what they spell.)

(Ulterior motive: I want to test the newsletter soltutions with different word grids, but I'm too lazy to come up with my own grid... )

[Jason Menard]

I didn't even see this post before I posted in the other thread! Here's my solution to part a. Part b is not accounted for though I'm afraid.
Start with an empty char[][].
Sort the word list by length, with the longer words first in the list, the idea being that it's easier to insert the longer words in as empty a grid as possible.
For each word {
Obtain a random empty grid space.
Obtain a random direction.
If the word will not fit (that is each letter must either fall across an empty space or a space containing the same letter) in that direction, try all the other directions until a fit is found.
If the word will not fit in any orientation in this grid space, get the next empty grid space and repeat the process.
}
Fill all remaining empty spaces with a random character.
Here's my code, including the GridReference class I used for WordFinder.
WordSearchMaker.java

package jr.wordfind;
import java.util.ArrayList;
import java.util.Random;
public class WordSearchMaker {
private char[][] grid;
private int columns;
private int rows;
private String[] words;
private ArrayList solution = new ArrayList();
private ArrayList failed = new ArrayList();
private Random rand = new Random(System.currentTimeMillis());
private static final GridReference[] directions = {GridReference.EAST,
GridReference.NE,
GridReference.NORTH,
GridReference.NW,
GridReference.SE,
GridReference.SOUTH,
GridReference.SW,
GridReference.WEST};
public WordSearchMaker(int n) {
this(n,n);
}
public WordSearchMaker(int rows, int columns) {
this.rows = rows;
this.columns = columns;
grid = new char[rows][columns];
}
public char[][] makeGrid(String[] words) {
this.words = sortByLength(words);
insert();
fill();
return grid;
}
public String toString() {
StringBuffer sb = new StringBuffer();
String newline = System.getProperty("line.separator");
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
sb.append(grid[i][j]);
}
sb.append(newline);
}
sb.append(newline);
for (int i = 0; i < solution.size(); i++) {
String s = (String)solution.get(i);
sb.append(s + newline);
}
return sb.toString();
}
private boolean canFitWord(char[] word,
GridReference start,
GridReference direction) {
if (!inBounds(start)) {
return false;
}
if (!inBounds(start.move(direction, word.length - 1))) {
return false;
}
for (int i = word.length - 1; i >= 0; i--) {
char c = get(start.move(direction, i));
if (c != 0 && c!= word[i]) {
return false;
}
}
return true;
}
private void fill() {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (grid[i][j] == 0) {
grid[i][j] = getRandomChar();
}
}
}
}
private GridReference[] findInsertPoint(char[] word) {
GridReference[] gra = null;
GridReference startRef = getRandomGridReference();
GridReference startDir = getRandomDirection();
GridReference nextRef = new GridReference(startRef);
GridReference nextDir = new GridReference(startDir);
while (gra == null && nextRef != null) {
nextRef = getNextEmptyGridReference(nextRef);
if (nextRef == null) {
continue;
}
int i = 0;
while(i < directions.length && gra == null) {
if (canFitWord(word, nextRef, nextDir)) {
gra = new GridReference[2];
gra[0] = nextRef;
gra[1] = nextDir;
return gra;
}
nextDir = getNextDirection(nextDir);
i++;
}
nextRef = nextRef.move(GridReference.EAST,1);
}
return null;
}
private char get(GridReference gridRef) {
return grid[gridRef.getRow()][gridRef.getColumn()];
}
private GridReference getNextEmptyGridReference(GridReference start) {
if (get(start) == 0) {
return start;
}
int startRow = start.getRow();
int startCol = start.getColumn();
int i = startRow;
int j = startCol + 1;
while (i != startRow && j != startCol) {
if (j >= columns) {
j = 0;
i++;
}
if (i >= rows) {
i = 0;
continue;
}
if (grid[i][j] == 0) {
return new GridReference(i,j);
}
j++;
}
return null;
}
private GridReference getNextDirection(GridReference direction) {
int n = 0;
for (int i = 0; i < directions.length; i++) {
if (directions[i].equals(direction)) {
n = i;
}
}
n++;
if (n >= directions.length) {
n = 0;
}
return directions[n];
}
private char getRandomChar() {
return (char)(rand.nextInt(26) + 97);
}
private GridReference getRandomDirection() {
int n = rand.nextInt(directions.length);
return directions[n];
}
private GridReference getRandomGridReference() {
int row = rand.nextInt(rows);
int col = rand.nextInt(columns);
return new GridReference(row, col);
}
private boolean inBounds(GridReference gridRef) {
int row = gridRef.getRow();
int col = gridRef.getColumn();
if (row < 0 || col < 0) {
return false;
}
if (row >= grid.length || col >= grid[0].length) {
return false;
}
return true;
}
private void insert() {
for (int i = 0; i < words.length; i++) {
insert(words[i]);
}
}
private void insert(char[] word,
GridReference gridRef,
GridReference direction) {
for (int i = 0; i < word.length; i++) {
set(word[i], gridRef);
gridRef = gridRef.move(direction, 1);
}
}
private void insert(String s) {
char[] word = s.toCharArray();
GridReference[] gra = findInsertPoint(word);
if (gra != null) {
insert(word, gra[0], gra[1]);
String sol = new String(word) + " " + gra[0].toString() +
"->" + gra[0].move(gra[1], word.length - 1).toString();
solution.add(sol);
}
else {
failed.add(s);
}
}
private void set(char c, GridReference gridRef) {
grid[gridRef.getRow()][gridRef.getColumn()] = c;
}
private String[] sortByLength(String[] s) {
for (int j = 1; j < s.length; j++) {
String a = s[j];
int i = j - 1;
while (i >= 0 && s[i].length() < a.length()) {
s[i + 1] = s[i];
i = i - 1;
}
s[i + 1] = a;
}
return s;
}
public static void main(String[] args) {
String[] s = {"javaranch",
"moose",
"bartender",
"sheriff",
"drivel",
"reviews",
"uml",
"threads",
"jdbc",
"roundup"};
WordSearchMaker wsm = new WordSearchMaker(1000);
char[][] grid = wsm.makeGrid(s);
System.out.println(wsm);
}
}

GridReference.java

package jr.wordfind;
public final class GridReference {
public static final GridReference EAST = new GridReference(0,1);
public static final GridReference NORTH = new GridReference(-1,0);
public static final GridReference SOUTH = new GridReference(1,0);
public static final GridReference WEST = new GridReference(0,-1);
public static final GridReference NE = new GridReference(-1,1);
public static final GridReference NW = new GridReference(-1,-1);
public static final GridReference SE = new GridReference(1,1);
public static final GridReference SW = new GridReference(1,-1);
private final int column;
private final int row;
public GridReference(GridReference gridRef) {
this.row = gridRef.row;
this.column = gridRef.column;
}
public GridReference(int row, int column) {
this.row = row;
this.column = column;
}
public int getColumn() {
return column;
}
public int getRow() {
return row;
}
/**
* <p>Obtain a new GridReference by moving this GridReference in a given
* direction a given number of times.</p>
* <p>For example, if this GridReference is [0,0],
* <code>move(GridReference.EAST, 5)</code> returns a
* GridReference of [0,5].</p>
* @param direction a GridReference containing the direction to move
* @param n the number of times to move in the given direction
* @return a new GridReference [this.row + (direction.row * n),
* this.column + (direction.column * n)].
*/
public GridReference move(GridReference direction, int n) {
int r = direction.row * n;
int c = direction.column * n;
return new GridReference(row + r, column + c);
}
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof GridReference)) {
return false;
}
GridReference gr = (GridReference)o;
if (column == gr.column && row == gr.row) {
return true;
}
return false;
}
public int hashCode() {
int hc = 17;
hc = 37 * hc + row;
hc = 37 * hc + column;
return hc;
}
public String toString() {
return "[" + row + "," + column + "]";
}
}