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 + "]";
    }
}