A word search puzzle gives the player a rectangular grid of letters g and a a wo

Question

A word search puzzle gives the player a rectangular grid of letters g and a a word w to find in the grid. g s w o w a l h e w a w a w a g g e w a l e C s w a k b s s e h k s d e e e i l o v e w c s s y n d o n a The goal is to find out whether w occurs anywhere in g. For our purposes we will recognise w if it occurs in g either left to right, or downwards, or e left to right and downwards, i e. diagonally down and across g. Thus the word wales occurs exactly three times in the above grid. Write a method public boolean word search String W char 00 g) that returns true if and only if the word w is found in the grid g according to the above rules. You may assume that g is rectangular. You will benefit from writing one or more private helper methods to decompose the problem.

Explanation / Answer

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class WordSearch
{
    public WordSearch( ) throws IOException
    {
        puzzleStream = openFile( "Enter puzzle file" );
        wordStream   = openFile( "Enter dictionary name" );
        System.out.println( "Reading files..." );
        readPuzzle( );
        readWords( );
    }

    public int solvePuzzle( )
    {
        int matches = 0;

        for( int r = 0; r < rows; r++ )
            for( int c = 0; c < columns; c++ )
                for( int rd = -1; rd <= 1; rd++ )
                    for( int cd = -1; cd <= 1; cd++ )
                        if( rd != 0 || cd != 0 )
                            matches += solveDirection( r, c, rd, cd );

        return matches;
    }

    private int solveDirection( int baseRow, int baseCol, int rowDelta, int colDelta )
    {
        String charSequence = "";
        int numMatches = 0;
        int searchResult;

        charSequence += theBoard[ baseRow ][ baseCol ];

        for( int i = baseRow + rowDelta, j = baseCol + colDelta;
                 i >= 0 && j >= 0 && i < rows && j < columns;
                 i += rowDelta, j += colDelta )
        {
            charSequence += theBoard[ i ][ j ];
            searchResult = prefixSearch( theWords, charSequence );

            if( searchResult == theWords.length )
                break;
            if( !((String)theWords[ searchResult ]).startsWith( charSequence ) )
                break;

            if( theWords[ searchResult ].equals( charSequence ) )
            {
                numMatches++;
                System.out.println( "Found " + charSequence + " at " +
                                    baseRow + " " + baseCol + " to " +
                                    i + " " + j );
            }
        }

        return numMatches;
    }

    private static int prefixSearch( Object [ ] a, String x )
    {
        int idx = Arrays.binarySearch( a, x );
      
        if( idx < 0 )
            return -idx - 1;
        else
            return idx;
    }

    private BufferedReader openFile( String message )
    {
        String fileName = "";
        FileReader theFile;
        BufferedReader fileIn = null;

        do
        {
            System.out.println( message + ": " );

            try
            {
                fileName = in.readLine( );
                if( fileName == null )
                     System.exit( 0 );
                theFile = new FileReader( fileName );
                fileIn = new BufferedReader( theFile );
            }
            catch( IOException e )
              { System.err.println( "Cannot open " + fileName ); }
        } while( fileIn == null );

        System.out.println( "Opened " + fileName );
        return fileIn;
    }
      
    private void readPuzzle( ) throws IOException
    {
        String oneLine;
        List puzzleLines = new ArrayList( );

        if( ( ) ) == null )
            throw new IOException( "No lines in puzzle file" );

        columns = oneLine.length( );
        puzzleLines.add( oneLine );

        while( ( ) ) != null )
        {
            if( oneLine.length( ) != columns )
                System.err.println( "Puzzle is not rectangular; skipping row" );
            else
                puzzleLines.add( oneLine );
        }
      
        rows = puzzleLines.size( );
        theBoard = new char[ rows ][ columns ];
        Iterator itr = puzzleLines.iterator( );
        for( int r = 0; r < rows; r++ )
        {
            String theLine = (String) itr.next( );
            theBoard[ r ] = theLine.toCharArray( );
        }
    }

    private void readWords( ) throws IOException
    {
        List words = new ArrayList( );

        String lastWord = null;
        String thisWord;
      
        while( ( thisWord = wordStream.readLine( ) ) != null )
        {
            if( lastWord != null && thisWord.compareTo( lastWord ) < 0 )
            {
                System.err.println( "Dictionary is not sorted... skipping" );
                continue;
            }
            words.add( thisWord );
            lastWord = thisWord;
        }
      
        theWords = words.toArray( );
    }

    public static void main( String [ ] args )
    {
        WordSearch p = null;
      
        try
        {
            p = new WordSearch( );
        }
        catch( IOException e )
        {
            System.out.println( "IO Error: " );
            e.printStackTrace( );
            return;
        }
      
        System.out.println( "Solving..." );
        p.solvePuzzle( );
    }

    private int rows;
    private int columns;
    private char [ ][ ] theBoard;
    private Object [ ] theWords;
    private BufferedReader puzzleStream;
    private BufferedReader wordStream;
    private BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.