CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    Nov 2010
    Posts
    3

    Help with Crossword Solver application

    This is my first post so apologies if I've done anything wrong.

    I'm working on a crossword solver that take user input e.g. h**s*. A text file (dictionary.txt) which contains a list of about 250,000 words is read and matching words are returned i.e. horse, house, etc.

    The program kind of works sometimes but mostly i keep getting a StringIndexOutOfBoundsException. Here is my code so far:

    import java.util.ArrayList;
    import java.util.Collection;

    public class MatchingWithWildcards {

    public static Collection<String> getMatches(String t, String p) {
    Collection<String> result = new ArrayList<String>();
    for (int i = 0; i < t.length(); i++) {
    int j = 0;
    int h = i;
    int n = p.length();

    while(true){
    int L = SimpleLongestCommonExtension.longestCommonExtension(p, j, t, h);

    if (j + 1 + L == n + 1) {
    result.add(t.substring(i, i + n));
    break;
    }

    if (((j + L) < p.length() && p.charAt(j + L) == '*')
    || ((h + L) < t.length() && t.charAt(h + L) == '*')) {
    j = j + L + 1;
    h = h + L + 1;
    } else
    break;
    }

    }
    return result;
    }
    }





    public class SimpleLongestCommonExtension {

    public static int longestCommonExtension(String t1, int i1, String t2, int i2) {
    int res = 0;
    for (int i = i1; i < t1.length() && i2 < t2.length(); i++, i2++) {
    if (t1.charAt(i) == t2.charAt(i2))
    res++;
    else
    return res;
    }
    return res;
    }
    }





    import java.io.BufferedReader;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.Collection;

    public class Test {

    public static void main(String[] args) {

    try {
    BufferedReader in = new BufferedReader(new FileReader("dictionary.txt"));
    String str;
    String input = "aa******";

    while ((str = in.readLine()) != null) {

    if(str.length() == input.length()){
    MatchingWithWildcards wild = new MatchingWithWildcards();
    //System.out.println(wild.getMatches("bingbongbang", "b***"));

    Collection<String> results = wild.getMatches(str, input);
    if(!results.isEmpty()){
    System.out.println(results);
    }
    }
    }
    in.close();
    }
    catch (IOException e) {
    System.out.println(e.toString());
    }
    }
    }



    OUTPUT

    [aardvark]
    [aardwolf]
    Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 9
    at java.lang.String.substring(String.java:1934)
    at gmit.MatchingWithWildcards.getMatches(MatchingWithWildcards.java:20)
    at gmit.Test.main(Test.java:23)

  2. #2
    Join Date
    Nov 2010
    Posts
    3

    Re: Help with Crossword Solver application

    Here is the code correctly formatted. I hope

    Code:
     
    import java.util.ArrayList;
    import java.util.Collection;
    
    public class MatchingWithWildcards {
    
    	public static Collection<String> getMatches(String t, String p) {
    		Collection<String> result = new ArrayList<String>();
    		for (int i = 0; i < t.length(); i++) {
    			int j = 0;
    			int h = i;
    			int n = p.length();
    			
    			while(true){
    				int L = SimpleLongestCommonExtension.longestCommonExtension(p, j, t, h);
    				
    				if (j + 1 + L == n + 1) {
    				    result.add(t.substring(i, i + n));
    				    break;
    				}
    				
    				if (((j + L) < p.length() && p.charAt(j + L) == '*')
    				        || ((h + L) < t.length() && t.charAt(h + L) == '*')) {
    				    j = j + L + 1;
    				    h = h + L + 1;
    				} else
    				    break;
    			}
    			
    		}
    		return result;
    	}
    }
    
    
    
    
    
    public class SimpleLongestCommonExtension {
    
    	public static int longestCommonExtension(String t1, int i1, String t2, int i2) {
    	    int res = 0;
    	    for (int i = i1; i < t1.length() && i2 < t2.length(); i++, i2++) {
    	        if (t1.charAt(i) == t2.charAt(i2))
    	            res++;
    	        else
    	            return res;
    	    }
    	    return res;
    	}
    }
    
    
    
    
    
    import java.io.BufferedReader;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.Collection;
    
    public class Test {
    	
    	public static void main(String[] args) {
    		
    		try {
    		    BufferedReader in = new BufferedReader(new FileReader("dictionary.txt"));
    		    String str;
    		    String input = "aa******";
    		    
    		    while ((str = in.readLine()) != null) {
    		    	
    		    	if(str.length() == input.length()){
    		    		MatchingWithWildcards wild = new MatchingWithWildcards();
    				    
    				    Collection<String> results = wild.getMatches(str, input);
    			    	if(!results.isEmpty()){
    			    		System.out.println(results);
    			    	}
    		    	}
    		    }
    		    in.close();
    		} 
    		catch (IOException e) {
    			System.out.println(e.toString());
    		}
    	}
    }

    OUTPUT

    [aardvark]
    [aardwolf]
    Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 9
    at java.lang.String.substring(String.java:1934)
    at gmit.MatchingWithWildcards.getMatches(MatchingWithWildcards.java:20)
    at gmit.Test.main(Test.java:23)

  3. #3
    Join Date
    May 2006
    Location
    UK
    Posts
    4,473

    Re: Help with Crossword Solver application

    You need to put some print statements in file MatchingWithWildcards.java, in the while loop just before line 20 and print out all the variable values. Run the program and look at how the variable values change, find which one is causing the exception and then look at how you calculate its value.
    Posting code? Use code tags like this: [code]...Your code here...[/code]
    Click here for examples of Java Code

  4. #4
    Join Date
    Feb 2008
    Posts
    966

    Re: Help with Crossword Solver application

    Another note is that your for loop goes until "t.length()" and your substring is from (i , i + n). So as "i" reaches the end of "t" and you add "n" to it, you are going to go out of bounds.

    Maybe you need the for loop to terminate at "t.length() - n", not sure without looking more into it though.

  5. #5
    Join Date
    Nov 2010
    Posts
    3

    Re: Help with Crossword Solver application

    Quote Originally Posted by ProgramThis View Post
    Another note is that your for loop goes until "t.length()" and your substring is from (i , i + n). So as "i" reaches the end of "t" and you add "n" to it, you are going to go out of bounds.

    Maybe you need the for loop to terminate at "t.length() - n", not sure without looking more into it though.
    That worked. Thank you. I terminated the for loop at t.length() - p.length()

  6. #6
    Join Date
    Feb 2008
    Posts
    966

    Re: Help with Crossword Solver application

    You're welcome, glad you got it worked out.

  7. #7
    Join Date
    Nov 2015
    Posts
    3

    Re: Help with Crossword Solver application

    I'm sorry to bump this, but I'm having the exact same problem and don't understnad what needs to be done :x Can anyone help me?

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured