June Newsletter Puzzle

Whis puzzle should be appearing in the June Newsletter:
WordSearch
==========
Given any N X N grid of letters (where N > 0, N <= 100), and any set of words which may be found in the grid, write a program to find and display the starting and ending grid coordinates for each word. The top left corner of the grid is [0,0] (row 0, col 0), and the bottom right corner of the grid is [N-1,N-1].
You may input the grid of letters and the words in the manner of your own choosing. Words in the grid may be found oriented in any direction within the grid (vertical, horizontal, reverse-horizontal, reverse-diagonal-up, diagonal down, etc...).
Use the following grid and list of words to test your code.

[ May 31, 2003: Message edited by: Jason Menard ]
[ June 05, 2003: Message edited by: Jason Menard ]

are we supposed to write the program, or just idea? my idea is as followed:
for example, in the case of "java",
1) search for "j";
2) search for "a" in adjacent 8 positions;
3) in the same direction, search for "v" in the next position, if no "v" exists, then no "java" exists;
4) search for "a" in next position in same direction, if no "a" exists, then no "java" exists;
5) then you find set(s) of starting and ending positions for each "java" appearance.
[ May 31, 2003: Message edited by: Don Liu ]

Originally posted by Don Liu:
are we supposed to write the program, or just idea?

Given any N X N grid of letters (where N > 0, N <= 100), and any set of words which may be found in the grid, write a program to find and display the starting and ending grid coordinates for each word.

My solution. I think it outperforms the obvious solution (at least asymptotically) of visiting every square for each word and checking every direction, but I'm too lazy to do the analysis at the moment (it is, after all, 3:30am). I figure the O(1) HashMap lookups plus the fact that words are generally short add up. I also sort the word characters by frequency in the grid first, so I expect that'd speed stuff up too. There's an O(n^2) insertion sort in the middle, but that may actually be faster than an O(n log n) sort since n is word.length(), which is expected to be rather small (in the 2-20 range).
Location.java

GridSolver.java:

(These damn smilies appear every time you want to write an Iterator loop! I'll show them...)
[ June 01, 2003: Message edited by: David Weitzman ]

You may input the grid of letters and the words in the manner of your own choosing.
My method if choosing is to set it in the source and recompile .

My solution is more a "visit every letter" solution, but it eliminates the grid, working only with a String.
(This was my second solution; my first one died after a little bit of work because I liked this one better....)

(Edited to remove the CFile class and replace it with standard Java I/O)
[ June 03, 2003: Message edited by: Joel McNary ]

This puzzle reminds me of a project that another professor gave a class in college. The year I took Object-Oriented Programming, it was based on C++. The following year it was based on Java, and that professor gave his class the assignment of reproduction the work of Michael Drozin's The Bible Code, in which Drozin uses the whole of the Bible as the text from which to work and looks for "hidden messages" in the Bible.
(No, not everyone at the college was involved in both CS and Religion; it's just that it seemed that way at times ; there were actually 5 of us who were both Religion and CS major and/or minors).
Of course, the class didn't have to use the Bible as their text base. A friend of mine found hidden messages in the script for Star Wars...
The project

import com.coolskill.foundation.io.CFile;

Joel, you just reminded me of something I meant to add to the guidelines: "Don't use third party APIs"! Ok, it was just for reading the file so you're forgiven this time.

Oops! My fault. CFile is something I wrote, so I use it all the time without thinking about it. I'll edit the code to use regular Java I/O.

Here's my solution, at a glance it looks like it may be closer to David's than Joel's. Only iterates through the grid once, in order to set up a HashMap of HashSets (ChracterGrid class). The map has a Character for a key, with a Set value. Each Set contains the grid coordinates (GridReference) that the key letter may be found at.
There are three classes: WordFinder (the driver), CharacterGrid (the grid of letters), and GridReference (basically a [row,col] location in a grid). I'd be interested in taking I/O out of the chain and benchmarking it against the other two solutions, but haven't gotten around to it yet.
NOTE: wordsearch.txt contains the grid of letters followed by a blank line followed by each word to find on its own line.
WordFinder.java

CharacterGrid.java

GridReference.java

(updated GridReference.java)
[ June 09, 2003: Message edited by: Jason Menard ]

Here's mine. I take the approach of rotating the puzzle, rather than rotating my searches. It's longish.
Wordsearch.java

Char1d.java

Char2d.java

Direction.java

WordList.java

XY.java

XYChar.java

Just realized I didn't post my output, so others can see if they have the same thing.
javaranch: [13,9],[5,1]
moose: [2,11],[6,11]
bartender: [7,8],[7,0]
sheriff: [2,2],[2,8]
drivel: [14,14],[9,14]
reviews: [13,5],[7,11]
uml: [13,0],[13,2]
threads: [3,14],[9,8]
jdbc: [0,5],[0,2]
roundup: [4,6],[10,0]

Yup, I match... My solution reversed the rows and columns, though :roll:

My results:

I timed the search after Input was performed, but included the print statements.
BTW, the instructions are unclear -- is the upper left corner 0,0 and lower right N-1, N-1, or is upper left 1,1 and lower right N,N?

Originally posted by Joel McNary:
BTW, the instructions are unclear -- is the upper left corner 0,0 and lower right N-1, N-1, or is upper left 1,1 and lower right N,N?

ou're the first one to catch that! The upper left corner is [0,0].
I tried running your code with the following files (which seems to be the format you require:
grid.txt

word.txt

I received the following output:
javaranch runs from (9,13) to (1,5) [WIDTH: 15]
moose could not be found.
bartender runs from (8,7) to (0,7) [WIDTH: 15]
sheriff could not be found.
drivel runs from (14,14) to (14,9) [WIDTH: 15]
reviews could not be found.
uml could not be found.
threads could not be found.
jdbc runs from (5,0) to (2,0) [WIDTH: 15]
roundup could not be found.
What am I doing wrong?

And btw, your coordinates are inverted.

No clue what you're doing wrong I can't find any common thread among those that it cannot find.
[DELIBERATE MIS-INTERPRETATION]
And, yes, my positions are inverted. They should be (9, -13) because the origin is in the upper left corner, meaning that this is in the fourth quadrant. But I make the y-coordinate positive to clarify things. Othen than that, they are in standard (x,y) positioning.
[/DELIBERATE MIS-INTERPRETATION]

Originally posted by Joel McNary:
No clue what you're doing wrong I can't find any common thread among those that it cannot find.

The code that is posted is the same you are using to get your results? Am I running your program with the text files in the correct format?

Yes, that's the version (without the time...)
I just copied-and-pasted it, (relpacing < etc), compiled, and ran it. The format of the files are each row/word on its own line. I tested and there should not be any issues with having to have a newline after the last row (it should work either way...)
Perhaps someone else can test?

Got it.
You replaced & lt and & gt with '<'. This meant that you could only find words that ran backwards! Copy, paste, replace things correctly, and try again.
[ June 05, 2003: Message edited by: Joel McNary ]

Originally posted by Joel McNary:
Got it.
You replaced & lt and & gt with '<'. This meant that you could only find words that ran backwards! Copy, paste, replace things correctly, and try again.
[ June 05, 2003: Message edited by: Joel McNary ]

Yep, that was it, thanks!
I gotta give it to you, your solution is generally more performant than mine, even with IO figured in. I wonder if it's simply the algorithm, or if it's due to the fact that I am instantiating more objects. I'd also be interested to see how the performance curve goes as N increases to much larger sizes. Any comments?
I also haven't tried any of the other solutions yet so maybe I'll also get around to that if somebody else doesn't first.

I'd think that as N increases, your code will eventually outpace mine because of the better lookup performance; I assume that String's .indexOf() function is iterative.
I could iterate through the text at the start and create a Map of Lists mapping letters to their indices in the String; that way, I can look up the letters in the Map and get thier locations in the string without having to interate through the text for every word. Then I think my solution would better compete with yours at larger Ns. Mayhaps I'll give that a try....

I probably went way overboard on this, but here's my solution: I thought it would be cool to look at the problem as a set of polar-coordinate searches, so this code translates the seearrch angle (increments of 45 degrees) into an X/Y increment. I also used a HashMap to invert the locations of the first letters of each search word.

Slightly improved performance, eliminating the need to iterate through the character string for every word to be found.

We were talking about performance as grid size increased... On my machine, my algorithm takes around ten seconds to find the same word list in a 1000x1000 grid.
What about yours, Joel (or anyone else really)?
To save some time, here is a class I wrote to make the Word Search grids. You will need the GridReference class from my previous post in order to run this.
WordSearchMaker.java

First post here (hope this is the right way to do it)
This is my attempt at the word puzzle

[edited by me to add UBB [ code] tags for easier reading -Jason]
[ June 09, 2003: Message edited by: Jason Menard ]

I added an IO routine to my solution and ran both it and Jason's on a generated 1000x1000. From start to finish (including IO) mine took about 12 seconds and Jason's 15, although I have an idea for an enhancement I'd like to add to mine before I do any serious testing without IO included and such. I may want to test out the relative merits of heapsort, quicksort, and using a TreeMap and see which is the best option (or perhaps it will turn out that insertion sort is still the winner in this context).
Actually I'm probably directing my efforts in the wrong direction, now that I think about it. Judging roughly by output, 10.5 of those seconds were spent in IO and setting up the HashSets. The individual word searches were quite fast. I'll think about that.

Originally posted by David Weitzman:
Actually I'm probably directing my efforts in the wrong direction, now that I think about it. Judging roughly by output, 10.5 of those seconds were spent in IO and setting up the HashSets. The individual word searches were quite fast. I'll think about that.

You're correct. I just ran it on a 1000x1000 grid, and the actual word search only took about 1.2 seconds or so. It seems 90% of the running time is in setting up the HashMap of HashSets. Specifically, in my CharacterGrid.init() method, the following line is eating up my performance:
set.add(new GridReference(i,j));
More specifically, the vast percentage of that performance hit is due to creating the GridReference objects. The moral of the story is that I have to sacrafice performance for convenience. The act of me instantiating a GridReference object for every cell of the grid takes 80%-90% of the running time if IO is factored out of the equation.

Michael Dunn,
I tried to benchmark yours with a 1000x1000 grid, but it seems that whenever I try to paste one in the app hangs. Although to be fair, the specs for the puzzle stated that N should have a max of 100. It looks good though, and works with the puzzle grid.

Here's my results:

The Grid initialization time include both reading the grid from the text file and indexing all the letters therein. The Word initialization time is how long it took to read the list of words from the text file, the Search time how long it took to perform the search, and Results display the time to display the results to the user.
So, for 10 words in a 15x15 grid, the total time was .02 seconds, half of which was initializing the grid and half of which was searching for the words. For the same 10 words in a 1000x1000 grid, the total time was roughly 3.5 seconds, 2.9 seconds of which were spent intializing the grid and .6 seconds spent performing the search.
Word reading time and results display time were insignificant. These results were obtained on a Pentium 4 machine with 256 MB of memory running at 2.4 GHz.
BTW: Running Jason's code on my machine takes 4.4 seconds at 1000x1000 and 20 milliseconds at 15x15
[ June 10, 2003: Message edited by: Joel McNary ]

Interestingly, my original code runs faster by about an entire second at N=1000. (2.5 seconds as opposed to 3.5 seconds.) The time needed to read the grid decreased by a second and there is no noticable increase in the time needed to find the words.
This means that String's .indexOf(char) must be indexed and my attempts to index the string myself just detracted from the overall performance of the process.

Jason,
So that others don't do what I did, why don't you change the first message from
"where N > 0, N <= 100"
to
"where N >= 0, N < 100"
I got the right answers, but my indicies are off.

Originally posted by Sonny Pondrom:
Jason,
So that others don't do what I did, why don't you change the first message from
"where N > 0, N <= 100"
to
"where N >= 0, N < 100"
I got the right answers, but my indicies are off.

Actually that's correct as written, although I will admit that my upper boundry for N was arbitrary (letting N = 1000 for example is decent for testing performance). Remember N as used in that context doesn't refer to indices, but the size of the grid. If N = 1 for example, you would have a one cell grid (NxN = 1x1) with coordinates [0,0]. If N = 100, your lower right cell would be [99,99]. But as I said the upper bound of N is arbitrary and may just as easily be done away with.

I made some modifications and it now runs about five times faster. Joel, your machine is apparently faster than mine so I'd be interested in your results as well.
I did away with the HashMap of HashSets and instead used my own data structure, which I lamely called a LetterMap. It operates on the same principle as a HashMap but uses chars as keys (their int value actually, and is only works with lower case letters) with a dynamic array of ints as the corresponding value for each key.
I represent the [row,col] coordinates as a single integer. The low sixteen bits represent the column and the high sixteen bits represent the row. The 16th bit of each component (ie bits 16 and 32) are a sign bit. CharacterGrid2 contains the methods for dealing with these packed grid references.
The rest of my algorithm is otherwise the same. I had to modify CharacterGrid to deal with the new data structure, as well as a couple of very small changes to WordFinder. The new classes are CharacterGrid2 and WordFinder2.
Benchmarks are from start to finish including display on a random 1000x1000 grid using the same set of words as the puzzle. Disk IO is ommitted because the grid is randomly generated.
Original Code:
======================
Map setup: 8673 milliseconds
Found and displayed all words in 2604 milliseconds
Total running time: 11287 milliseconds
New Code:
======================
Map setup: 340 milliseconds
Found and displayed all words in 1933 milliseconds
Total running time: 2373 milliseconds
LetterMap.java

CharacterGrid2.java

WordFinder2.java

Joel, you might be interested in looking at the source for String.indexOf from the most recent JDK. It's not indexed, but it's pretty well optimized.

Jason:
I just now had the time to test your code on my machine for comparison's sake. Congratulations, yours now runs faster than mine 1.281 seconds to find the words in the 1000-sized grid.
Map setup: 150 milliseconds
Found all words in 1091 milliseconds
Total running time: 1281 milliseconds

This forum is fun! And this particular question was really tempting to be solved!

I followed these steps:
1. Read input - original matrix and original words list
2. Create another array that contains all the input words reversed - reversed word list
3. Create three more matrices
a) transposed
b) loweredLeft - one that has number of rows == N*2+1 and with zeroth column lowered N-2 times.
c) loweredright - one that has number of rows == N*2+1 and with last column lowered N-2 times.
4. Then search all the matrices one by one for each of the words in the original word list and reversed words list
based on where an substring is found, just adjust the row and column values.
E.g.
Input matrix
123
456
789
Transposed
147
258
369
LoweredLeft
--3
-26
159
48-
7--
LoweredRight
1--
42-
753
-86
--9
if input word is 123, it will be caught in the original matrix.
if input word is 321, it will be caught in the original matrix using reversed word list
if input word is 147, it will be caught in the transposed matrix.
if input word is 741, it will be caught in the transposed matrix using reversed word list
if input word is 159, it will be caught in the loweredLeft matrix
if input word is 591, it will be caught in the loweredLeft matrix using reversed word list
..and so forth
Currently, it works only with square matrices, M X N, where M == N, but can be modified to handle M!=N.
Tested with the input provided by Jason, but haven't tried the performance part with N = 1000.

Thank you for an interesting challenge on this puzzle. My solution is straighforward, without hash tables and other exotic tricks.
I used 4 search functions and each one is used with the word forward and again, when the word is spelled backwards.
Here's my code:
/** Search Puzzle Program
* @author Jeff Goldstein
* %G%
*/
import java.awt.Point;
public class Puzzle
{
public static final int NUM = 15;
static char[][] chMat = new char[NUM][NUM];
static Point[] beginEnd = new Point[2];
//testing the following strings within the puzzle
static String[] target = {"javaranch", "moose", "bartender", "sheriff",
"drivel", "reviews", "uml", "threads", "jdbc",
"roundup"};
static String[] descrip = {"Across L to R ", "Across R to L ", "Vert. Down ",
"Vert. Up ","Down Diag. L to R ","Up Diag. R to L ",
"Down Diag. R to L ", "Up Diag. L to R "};

/**
* Loading the Array by assigning each row to a String[].
*
* @param none
* @return matrix of chars
*/
public static char[][] loadArray()
{
String[] s = new String[NUM];
s[0] = "xbcbdjwgpmpcfsh";
s[1] = "avijureeroltfha";
s[2] = "bdsheriffnamnev";
s[3] = "lsuraibvoikoist";
s[4] = "iakpffrsngtoshr";
s[5] = "zhdanosourzsrea";
s[6] = "eicnuludnexerwn";
s[7] = "rednetrabvasbec";
s[8] = "mldoarahcdwyvrh";
s[9] = "auyjvroosendetl";
s[10] = "pkypuiaciornede";
s[11] = "sitemapvitralsv";
s[12] = "rafnopekaminiui";
s[13] = "umlksreyejmlpir";
s[14] = "pgetwdmpevitood";
for(int i = 0; i < NUM; i++)
for(int j = 0; j < NUM; j++)
chMat[i][j] = s[i].charAt(j); // assign the char at j to chMat[][]
return chMat; // return the matrix of chars
}
/**
* Searching for tWord in all directions:
*horizontal, vertical, diagonal right to left, diagonal left to right
*
* @param tWord the target string to be searched.
* @param row the row to begin the search.
*/
public static void searchAllDirections(String tWord, int row)
{
// horizontal search forward and backwards
String back = reverse(tWord);
beginEnd = searchForward(tWord, row);
if(isFound(tWord, beginEnd))
System.out.println(descrip[0] + beginEnd[0] + beginEnd[1]);
beginEnd = searchForward(back, row);
if(isFound(tWord, beginEnd))
System.out.println(descrip[1] + beginEnd[1] + beginEnd[0]);
// vertical search up and down
beginEnd = searchDown(tWord, row);
if(isFound(tWord, beginEnd))
System.out.println(descrip[2] + beginEnd[0] + beginEnd[1]);
beginEnd = searchDown(back, row);
if(isFound(tWord, beginEnd))
System.out.println(descrip[3] + beginEnd[1] + beginEnd[0]);
// diagonal search down Left to Right
beginEnd = searchDownDiagLR(tWord, row);
if(isFound(tWord, beginEnd))
System.out.println(descrip[4] + beginEnd[0] + beginEnd[1]);
beginEnd = searchDownDiagLR(back, row);
if(isFound(tWord, beginEnd))
System.out.println(descrip[5] + beginEnd[1] + beginEnd[0]);
// diagonal search down Right to Left
beginEnd = searchDownDiagRL(tWord, row);
if(isFound(tWord, beginEnd))
System.out.println(descrip[6] + beginEnd[0] + beginEnd[1]);
beginEnd = searchDownDiagRL(back, row);
if(isFound(tWord, beginEnd))
System.out.println(descrip[7] + beginEnd[1] + beginEnd[0]);
}
/**
* a Boolean function to determine if the target string was actually found
* inside the character matrix.
* @return true - if the length of the target is same as coord. distance.
* @return false - if coord. distance is not the same as the target length.
*/
public static boolean isFound(String target, Point[] pt)
{
return (Math.abs(pt[1].x - pt[0].x) == target.length() - 1) ||
(Math.abs(pt[1].y - pt[0].y) == target.length() - 1);
}
/** Reverses the string (for example: "cat" becomes "tac").
*
* @param String s is the input string.
* @return String result is the string in reversed order.
*/
public static String reverse(String s)
{
int len = s.length();
String result = new String();
for(int i = len - 1; i >= 0; i--)
result += s.charAt(i);
return result;

}

/**
* Searches Down Diagonally (Left to Right: 10:00 to 4:00 position)
* @param s - input string as target for the search.
*
* @param row - current row to start searching from.
* @return array of Points containing the end coordinates.
*/
public static Point[] searchDownDiagLR(String s, int row)
{
int i, j, col;
int index;
int slen = s.length();
Point p0 = new Point();
Point p1 = new Point();
Point[] result = new Point[2];
String target;
char ch[] = new char[NUM];
char ltr;
for(i = 0; i < slen; i++)
ch[i] = s.charAt(i);// put each char into array
for(col = 0; col < NUM && col<slen; col++)// start searching for 1st char
{
target = "";
index = 1;
ltr = chMat[row][col];
if(ltr == ch[0])// find the first letter 1st
{
target += ltr;// prepend the first letter
// now we must search down and right
for(j = 1 + row, i = 1; j < slen + row && j < NUM; j++, i++)
{
ltr = chMat[j][col+i];
if(ltr != ch[index])
{
break;
}
target += ltr;
index++;
}

if(s.equals(target))
{
i--;
j--;
p0.setLocation(col, row);// set begin coord of point p0
p1.setLocation(col+i, j);// set ending coord of point p1
break;
}
}
}
result[0] = p0;
result[1] = p1;
return result;
}

/**
* Searches Down Diagonally (Right to Left: 2:00 to 8:00 position)
* @param s - input string as target for the search.
*
* @param row - current row to start searching from.
* @return array of Points containing the end coordinates.
*/
public static Point[] searchDownDiagRL(String s, int row)
{
int i, j, col;
int index;
int slen = s.length();
Point p0 = new Point();
Point p1 = new Point();
Point[] result = new Point[2];
String target;
char ch[] = new char[NUM];
char ltr;
for(i = 0; i < slen; i++)
ch[i] = s.charAt(i);// put each char into array
for(col = 0; col < NUM; col++)// start searching for 1st char
{
target = "";
index = 1;
ltr = chMat[row][col];
if(ltr == ch[0])// find the first letter 1st
{
target += ltr;// prepend the first letter
// now we must search down and left 2 to 8
for(j = 1 + row, i = 1; j < (slen + row) && j < NUM; j++, i++)
{
if(col - i < 0)
break;
ltr = chMat[j][col-i];
if(ltr != ch[index])
{
break;
}
target += ltr;
index++;
}

if(s.equals(target))
{
i--;
j--;
p0.setLocation(col, row);// set begin coord of point p0
p1.setLocation(col-i, j);// set ending coord of point p1
break;
}
}
}
result[0] = p0;
result[1] = p1;
return result;
}

/**
* Searches Down Vertically (12:00 to 6:00 position)
* @param s - input string as target for the search.
*
* @param row - current row to start searching from.
* @return array of Points containing the end coordinates.
*/
public static Point[] searchDown(String s, int row)
{
int i, j, col;
int index;
int slen = s.length();
Point p0 = new Point();
Point p1 = new Point();
Point[] result = new Point[2];
String target;
char ch[] = new char[NUM];
char ltr;
for(i = 0; i < slen; i++)
ch[i] = s.charAt(i);// put each char into array
for(col = 0; col < NUM; col++)// start searching for 1st char
{
target = "";
index = 1;
ltr = chMat[row][col];
if(ltr == ch[0])// find the first letter 1st
{
target += ltr;// prepend the first letter
// now we must search straight down
for(j = 1 + row; j < slen + row && j < NUM; j++)
{
ltr = chMat[j][col];
if(ltr != ch[index])// get out if letter is not found
{
break;
}
target += ltr;
index++;
}
if(s.equals(target))
{
j--;
p0.setLocation(col, row);// set begin coord of point p0
p1.setLocation(col, j);// set ending coord of point p1
}
}
}
result[0] = p0;
result[1] = p1;
return result;
}


/**
* Searches Forward Horizontally (9:00 to 3:00 position)
* @param s - input string as target for the search.
*
* @param row - current row to start searching from.
* @return array of Points containing the end coordinates.
*/
public static Point[] searchForward(String s, int row)
{
int i, j, col;
int index;
int slen = s.length();
Point p0 = new Point();
Point p1 = new Point();
Point[] result = new Point[2];
String target;
char ch[] = new char[NUM];
for(i = 0; i < slen; i++)
ch[i] = s.charAt(i);// put each char into array
for(col = 0; col < NUM; col++)// start searching for 1st char
{
target = "";
index = 1;
if(chMat[row][col] == ch[0])// find the first letter 1st
{
target += ch[0];
for(j = col + 1; j < col + slen && j < NUM; j++)
{
if(chMat[row][j] != ch[index])
{
break;
}
target += ch[index];// append the letter to target
index++;
}

if(s.equals(target))
{
j--;
p0.setLocation(col, row);
p1.setLocation(j, row);
break;
}
}
}
result[0] = p0;
result[1] = p1;
return result;
}
/**
* Main method to test this class
*/
public static void main(String[] args)
{
chMat = loadArray();// load char matrix (puzzle)
for(int i = 0; i < target.length; i++)// loop through each word
{
String tWord = target[i];
System.out.println("\n" + tWord);
for(int row = 0; row < NUM; row++)
{
searchAllDirections(tWord, row);// search each direction
}
}
}
}

I just finished this old programming diversion.
It was a lot of fun!

I think most people went for a far to large object orient design where a recursive method would be a lot simpler. Well that is my 2 cents

I'm not payed per line:

[ November 02, 2005: Message edited by: Stefan Wagner ]