June Newsletter Puzzle

[Stan James]

Nobody tested?

package com.saxman.sandbox.wordfinder;
 
import junit.framework.TestCase;
import junit.textui.TestRunner;
 
public class WordFinderTest extends TestCase
{
    public void testOneChar()
    {
        WordFinder fig = new WordFinder();
        fig.setHaystack( new char[][] { { 'a' } } );
        assertTrue( fig.findNeedle( "a" ) );
        assertFalse( fig.findNeedle( "b" ) );
    }
 
    public void testTwoChars()
    {
        WordFinder fig = new WordFinder();
        fig.setHaystack( new char[][] { { 'a', 'b' }, { 'z', 'z' } } );
        assertTrue( fig.findNeedle( "ab" ) );
        assertFalse( fig.findNeedle( "ax" ) );
    }
 
    public void testInMiddle()
    {
        WordFinder fig = new WordFinder();
        fig.setHaystack( new char[][] { { 'a', 'b', 'c', 'd' } } );
        assertTrue( fig.findNeedle( "ab" ) );
        assertTrue( fig.findNeedle( "bc" ) );
        assertTrue( fig.findNeedle( "cd" ) );
        assertFalse( fig.findNeedle( "bd" ) );
    }
 
    public void testInMiddleRow()
    {
        WordFinder fig = new WordFinder();
        fig.setHaystack( new char[][] { { 'x', 'x', 'x', 'x' }, 
                                        { 'd', 'e', 'f', 'g' }, 
                                        { 'z', 'z', 'z', 'z' } } );
        assertTrue( fig.findNeedle( "de" ) );
        assertTrue( fig.findNeedle( "ef" ) );
        assertTrue( fig.findNeedle( "fg" ) );
        assertFalse( fig.findNeedle( "bd" ) );
    }
 
    public void testSouth()
    {
        WordFinder fig = new WordFinder();
        fig.setHaystack( new char[][] { { 'a', 'x', 'x', 'x' }, 
                                        { 'b', 'x', 'x', 'x' }, 
                                        { 'c', 'x', 'x', 'x' },
                                        { 'd', 'x', 'x', 'x' } } );
        assertTrue( fig.findNeedle( "ab" ) );
        assertTrue( fig.findNeedle( "bc" ) );
        assertTrue( fig.findNeedle( "cd" ) );
        assertFalse( fig.findNeedle( "bd" ) );
    }
 
    public void testNorthWest()
    {
        WordFinder fig = new WordFinder();
        fig.setHaystack( new char[][] { { 'd', 'x', 'x', 'x' }, 
                                        { 'x', 'c', 'x', 'x' }, 
                                        { 'x', 'x', 'b', 'x' },
                                        { 'x', 'x', 'x', 'a' } } );
        assertTrue( fig.findNeedle( "abcd" ) );
        assertFalse( fig.findNeedle( "bcde" ) );
    }
 
    public void testJavaRanch()
    {
        WordFinder fig = new WordFinder();
        char[][] grid = new char[15][0];
        grid[0] = "xbcbdjwgpmpcfsh".toCharArray();
        grid[1] = "avijureeroltfha".toCharArray();
        grid[2] = "bdsheriffnamnev".toCharArray();
        grid[3] = "lsuraibvoikoist".toCharArray();
        grid[4] = "iakpffrsngtoshr".toCharArray();
        grid[5] = "zhdanosourzsrea".toCharArray();
        grid[6] = "eicnuludnexerwn".toCharArray();
        grid[7] = "rednetrabvasbec".toCharArray();
        grid[8] = "mldoarahcdwyvrh".toCharArray();
        grid[9] = "auyjvroosendetl".toCharArray();
        grid[10] = "pkypuiaciornede".toCharArray();
        grid[11] = "sitemapvitralsv".toCharArray();
        grid[12] = "rafnopekaminiui".toCharArray();
        grid[13] = "umlksreyejmlpir".toCharArray();
        grid[14] = "pgetwdmpevitood".toCharArray();
        fig.setHaystack( grid );
        assertTrue( fig.findNeedle( "javaranch" ) );
        assertTrue( fig.findNeedle( "moose" ) );
        assertTrue( fig.findNeedle( "bartender" ) );
        assertTrue( fig.findNeedle( "sheriff" ) );
        assertTrue( fig.findNeedle( "drivel" ) );
        assertTrue( fig.findNeedle( "reviews" ) );
        assertTrue( fig.findNeedle( "uml" ) );
        assertTrue( fig.findNeedle( "threads" ) );
        assertTrue( fig.findNeedle( "jdbc" ) );
        assertTrue( fig.findNeedle( "roundup" ) );
    }
 
    public static void main( String[] args )
    {
        TestRunner.run( WordFinderTest.class );
    }
}

and

package com.saxman.sandbox.wordfinder;
 
public class WordFinder
{
    private char[][] haystack;
    private int rowCount;
    private int colCount;
    private Delta[] delta;
 
    public WordFinder()
    {
        initDeltas();
    }
 
    private void initDeltas()
    {
        delta = new Delta[8];
        delta[0] = new Delta( "E", 0, 1 );
        delta[1] = new Delta( "SE", 1, 1 );
        delta[2] = new Delta( "S", 1, 0 );
        delta[3] = new Delta( "SW", 1, -1 );
        delta[4] = new Delta( "W", 0, -1 );
        delta[5] = new Delta( "NW", -1, -1 );
        delta[6] = new Delta( "N", -1, 0 );
        delta[7] = new Delta( "NE", -1, 1 );
    }
    
    public void setHaystack(char[][] grid)
    {
        this.haystack = grid;
        rowCount = grid.length;
        colCount = grid[0].length; // Assumes rectangular grid
    }
    
    public boolean findNeedle( String string )
    {
        char[] in = string.toCharArray();
        for ( int row = 0; row < haystack.length; row++ )
            for ( int col = 0; col < haystack[row].length; col++ )
                if ( findAtRowCol( in, row, col ) )
                    return true;
        System.out.println( "Did not find " + string );
        return false;
    }
 
    private boolean findAtRowCol( char[] in, int row, int col )
    {
        for ( int i = 0; i < delta.length; i++ )
            if ( findAtRowColWithDelta( in, row, col, delta[i] ) )
                return true;
        return false;
    }
 
    private boolean findAtRowColWithDelta( char[] in, int row, int col, Delta delta )
    {
        if ( !delta.possibleLocation( row, col, in.length ) )
            return false;
        int lookRow = row;
        int lookCol = col;
        for ( int c = 0; c < in.length; c++ )
        {
            if ( haystack[lookRow][lookCol] != in[c] )
                return false;
            lookRow += delta.deltaRow;
            lookCol += delta.deltaCol;
        }
        System.out.println( "Found " + new String( in ) 
                + " at row " + row + " col " + col 
                + " going " + delta.description );
        return true;
    }
 
    class Delta
    {
        String description = "";
        int deltaRow = 0;
        int deltaCol = 0;
 
        public Delta( String description, int deltaRow, int deltaCol )
        {
            this.description = description;
            this.deltaRow = deltaRow;
            this.deltaCol = deltaCol;
        }
 
        public boolean possibleLocation( int row, int col, int wordLength )
        {
            if ( !possibleLocation( row, deltaRow, wordLength, rowCount ) )
                return false;
            if ( !possibleLocation( col, deltaCol, wordLength, colCount ) )
                return false;
            return true;
        }
 
        private boolean possibleLocation( int start, int delta, int length, int max )
        {
            int end = start + ( delta * length );
            return ( end <= max && end >= -1 );
        }
    }
}

[Stan James]

I'm impressed by some of the neat optimizations going on. The set of locations of first letters is way cool. Just to stand up for brute force ...

Generating random: 156
Overlaying: 0
Found javaranch at row 513 col 509 going NW
Found moose at row 77 col 524 going W
Found bartender at row 507 col 508 going W
Found sheriff at row 502 col 502 going E
Found drivel at row 514 col 514 going N
Found reviews at row 513 col 505 going NE
Found uml at row 2 col 177 going NW
Found threads at row 503 col 514 going SW
Found jdbc at row 64 col 507 going S
Found roundup at row 504 col 506 going SW
1078 ms

from running ...

package com.saxman.sandbox.wordfinder;
 
import java.util.Random;
 
public class BigGridTester
{
    private static final String alpha = "abcdefghijklmnopqrstuvwxyz";
 
    public static void main( String[] args )
    {
        long before = System.currentTimeMillis();
        Random rand = new Random();
        char[][] grid = new char[1000][1000];
        for ( int r = 0; r < grid.length; r++ )
            for ( int c = 0; c < grid[0].length; c++ )
                grid[r][c] = alpha.charAt( rand.nextInt( 25 ) );
        System.out.println( "Generating random: " + ( System.currentTimeMillis() - before ) );
 
        before = System.currentTimeMillis();
        char[][] grid2 = new char[15][0];
        grid2[0] = "xbcbdjwgpmpcfsh".toCharArray();
        grid2[1] = "avijureeroltfha".toCharArray();
        grid2[2] = "bdsheriffnamnev".toCharArray();
        grid2[3] = "lsuraibvoikoist".toCharArray();
        grid2[4] = "iakpffrsngtoshr".toCharArray();
        grid2[5] = "zhdanosourzsrea".toCharArray();
        grid2[6] = "eicnuludnexerwn".toCharArray();
        grid2[7] = "rednetrabvasbec".toCharArray();
        grid2[8] = "mldoarahcdwyvrh".toCharArray();
        grid2[9] = "auyjvroosendetl".toCharArray();
        grid2[10] = "pkypuiaciornede".toCharArray();
        grid2[11] = "sitemapvitralsv".toCharArray();
        grid2[12] = "rafnopekaminiui".toCharArray();
        grid2[13] = "umlksreyejmlpir".toCharArray();
        grid2[14] = "pgetwdmpevitood".toCharArray();
 
        for ( int r = 0; r < grid2.length; r++ )
            for ( int c = 0; c < grid2[0].length; c++ )
                grid[500 + r][500 + c] = grid2[r][c];
 
        System.out.println( "Overlaying: " + ( System.currentTimeMillis() - before ) );
 
        before = System.currentTimeMillis();
        WordFinder fig = new WordFinder();
        fig.setHaystack( grid );
        fig.findNeedle( "javaranch" );
        fig.findNeedle( "moose" );
        fig.findNeedle( "bartender" );
        fig.findNeedle( "sheriff" );
        fig.findNeedle( "drivel" );
        fig.findNeedle( "reviews" );
        fig.findNeedle( "uml" );
        fig.findNeedle( "threads" );
        fig.findNeedle( "jdbc" );
        fig.findNeedle( "roundup" );
        long elapsed = System.currentTimeMillis() - before;
        System.out.println( elapsed + " ms" );
    }
}

I moved the original puzzle content to offset 975 x 975 and the time was as expected twice as long. Best of four runs ...

Generating random: 157
Overlaying: 0
Found javaranch at row 998 col 994 going NW
Found moose at row 987 col 996 going S
Found bartender at row 992 col 993 going W
Found sheriff at row 987 col 987 going E
Found drivel at row 999 col 999 going N
Found reviews at row 998 col 990 going NE
Found uml at row 1 col 409 going S
Found threads at row 988 col 999 going SW
Found jdbc at row 113 col 608 going NW
Found roundup at row 989 col 991 going SW
2047

Hee hee, it found a few short words among the random stuff! Wonder if there are any Shakespeare plays in there.
[ November 06, 2005: Message edited by: Stan James ]