The Cemers

// Copyright (c) 2005 Ronald B. Cemer
// All rights reserved worldwide.
	
import java.io.*;
import java.util.*;
	
public class WSGen
    implements WSWordOrientation {
    public static final int MIN_WIDTH_HEIGHT = 8;
    public static final int MIN_WORD_LENGTH = 3;
	
    private int gridWidthChars, gridHeightChars;
    private char[][] grid;        // [y][x]
    private Random rand = new Random(System.currentTimeMillis());
	
    public WSGen(int gridWidthChars, int gridHeightChars) {
        if ( (gridWidthChars < MIN_WIDTH_HEIGHT) || (gridHeightChars < MIN_WIDTH_HEIGHT) ) {
            throw new Error("Width and height must each be at least "+MIN_WIDTH_HEIGHT+".");
        }
        this.gridWidthChars = gridWidthChars;
        this.gridHeightChars = gridHeightChars;
        grid = new char[gridHeightChars][gridWidthChars];
        for (int y = 0; y < gridHeightChars; y++) {
            for (int x = 0; x < gridWidthChars; x++) {
                grid[y][x] = ‘ ‘;
            }
        }
    }
	
    public void process(File wordFile, File outFile)
        throws IOException {
	
        process(wordFile, outFile, true);
    }
	
    public void process(File wordFile, File outFile, boolean fillUnusedCellsWithRandomCharacters)
        throws IOException {
	
        List sourceWordList = readWordList(wordFile);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(new FileOutputStream(outFile)));
        try {
            out.print("grid:");
            out.print(gridWidthChars);
            out.print(",");
            out.println(gridHeightChars);
	
            int failuresInARow = 0;
            while ( (sourceWordList.size() > 0) && (failuresInARow < 100) ) {
                int wordIdx = (rand.nextInt()&0×7fffffff)%sourceWordList.size();
                String testWord = (String)sourceWordList.get(wordIdx);
                if (fitWord(out, testWord)) {
                    failuresInARow = 0;
                } else {
                    failuresInARow++;
                }
                sourceWordList.remove(wordIdx);
            }
///
///printGrid();
///System.out.println();
            if (fillUnusedCellsWithRandomCharacters) {
                fillUnusedCellsWithRandomCharacters(out);
///
///printGrid();
///System.out.println();
            }
            out.flush();
            out.close();
            out = null;            // Setting out to null indicates successful completion.
        } finally {
            if (out != null) {
                // Not successful because out != null.
                try { out.close(); } catch(Exception ex) {}
                outFile.delete();
            }
        }
    }
	
    public void fillUnusedCellsWithRandomCharacters(PrintWriter out)
        throws IOException {
	
        out.print("fillchars:");
        for (int y = 0; y < gridHeightChars; y++) {
            for (int x = 0; x < gridWidthChars; x++) {
                if (grid[y][x] == ‘ ‘) {
                    char c = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".charAt((rand.nextInt()&0×7fffffff)%26);
                    grid[y][x] = c;
                    out.print(c);
                }
            }
        }
        out.println();
    }
	
    private List readWordList(File wordFile)
        throws IOException {
	
        BufferedReader in =
            new BufferedReader(new InputStreamReader(new FileInputStream(wordFile)));
        List wordList = new ArrayList();
        try {
            String s;
            int maxWordLength = Math.max(gridWidthChars, gridHeightChars);
            while ((s = in.readLine()) != null) {
                s = s.trim().toUpperCase();
                int len = s.length();
                if (len == 0) continue;                    // Empty line
                if (s.startsWith("#")) continue;    // Comment
                if (len < MIN_WORD_LENGTH) {
                    System.err.println(
                        "Tossing word “"+s+"” because it is too short (must be at least "+
                        MIN_WORD_LENGTH+" characters).");
                    continue;
                }
                if (len > maxWordLength) {
                    System.err.println(
                        "Tossing word “"+s+
                        "” because it is longer than the grid’s width and height.");
                    continue;
                }
                boolean hasNonLetters = false;
                for (int i = 0; i < len; i++) {
                    if (!Character.isLetter(s.charAt(i))) {
                        hasNonLetters = true;
                        break;
                    }
                }
                if (hasNonLetters) {
                    System.err.println(
                        "Tossing word “"+s+
                        "” because it contains one or more non-letter characters.");
                    continue;
                }
                if (wordList.indexOf(s) >= 0) {
                    System.err.println("Tossing duplicate word “"+s);
                    continue;
                }
                wordList.add(s);
            }
            return wordList;
        } finally {
            in.close();
        }
    }
	
    private boolean fitWord(PrintWriter out, String testWord)
        throws IOException {
	
        // Pick a random starting point and orientation.
        int x = (rand.nextInt()&0×7fffffff)%gridWidthChars;
        int y = (rand.nextInt()&0×7fffffff)%gridHeightChars;
        int orientation = (rand.nextInt()&0×7fffffff)%8;
        // Try to fit the word in every spot in the grid, starting at the random x, y position.
        // Each fit attempt must try all eight orientations.
        for (int yy = 0; yy < gridHeightChars; yy++, y = (y+1)%gridHeightChars) {
            for (int xx = 0; xx < gridWidthChars; xx++, x = (x+1)%gridWidthChars) {
                for (int oo = 0; oo < 8; oo++, orientation = (orientation+1)%8) {
                    if (fitWord(out, testWord, x, y, orientation)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
	
    private boolean fitWord(PrintWriter out, String testWord, int x, int y, int orientation)
        throws IOException {
	
        // Try to fit the word into the grid at the starting x,y position with the specified
        // orientation (0=up, 1=up/right, 2=right, 3=down/right, 4=down, 5=down/left, 6=left,
        // 7=up/left
        int xo = ORIENTATION_XY[orientation][0];
        int yo = ORIENTATION_XY[orientation][1];
        int len = testWord.length();
        // The fit attempt must fail if the word would run off of any edge of the grid.
        int xEnd = x+((len-1)*xo);
        int yEnd = y+((len-1)*yo);
        if ( (xEnd < 0) || (xEnd >= gridWidthChars) || (yEnd < 0) || (yEnd >= gridHeightChars) ) {
            return false;
        }
        // The fit attempt must fail if any character that exists in the grid is not a space and
        // does not match the character at that position in the word.
        // The fit attempt must fail if the entire word matches characters already in the grid
        // (no spaces encountered in the grid while placing the word).
        boolean allMatch = true;
        for (int i = 0, xx = x, yy = y; i < len; i++, xx += xo, yy += yo) {
            char wc = testWord.charAt(i);
            char gc = grid[yy][xx];
            if (gc != wc) {
                allMatch = false;
                if (gc != ‘ ‘) {
                    return false;
                }
            }
        }
        if (allMatch) {
            return false;
        }
        for (int i = 0, xx = x, yy = y; i < len; i++, xx += xo, yy += yo) {
            grid[yy][xx] = testWord.charAt(i);
        }
        out.print("word:");
        out.print(x);
        out.print(‘,’);
        out.print(y);
        out.print(‘,’);
        out.print(orientation);
        out.print(‘,’);
        out.println(testWord);
        return true;                // success
    }
	
    private void printGrid() {
        for (int y = 0; y < gridHeightChars; y++) {
            for (int x = 0; x < gridWidthChars; x++) {
                if (x > 0) System.out.print(‘ ‘);
                System.out.print(grid[y][x]);
            }
            System.out.println();
        }
    }
	
    public static void usage() {
        System.err.println
            ("Usage:");
        System.err.println
            ("java "+WSGen.class.getName()+" <width> <height> <wordListFile> <outFile>");
    }
	
    public static int process(String[] args) {
        if (args.length != 4) {
            usage();
            return 1;
        }
        try {
            int gridWidthChars = Integer.parseInt(args[0].trim());
            int gridHeightChars = Integer.parseInt(args[1].trim());
            if ( (gridWidthChars < MIN_WIDTH_HEIGHT) || (gridHeightChars < MIN_WIDTH_HEIGHT) ) {
                System.err.println("Width and height must each be at least "+MIN_WIDTH_HEIGHT+".");
                usage();
                return 1;
            }
            File wordFile = new File(args[2]);
            File outFile = new File(args[3]);
            new WSGen(gridWidthChars, gridHeightChars).process(wordFile, outFile);
        } catch(Exception ex) {
            ex.printStackTrace();
            return 99;
        }
        return 0;
    }
	
    public static void main(String[] args) {
        System.exit(process(args));
    }
}
	

// Copyright (c) 2005 Ronald B. Cemer
// All rights reserved worldwide.
	
public interface WSWordOrientation {
    public static final int[][] ORIENTATION_XY = {
        {  0, -1 },      // up
        {  1, -1 },      // up/right
        {  1,  0 },      // right
        {  1,  1 },      // down/right
        {  0,  1 },      // down
        { -1,  1 },      // down/left
        { -1,  0 },      // left
        { -1, -1 }      // up/left
    };
}