-
November 18th, 2010, 09:03 AM
#1
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)
-
November 18th, 2010, 10:03 AM
#2
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)
-
November 18th, 2010, 11:06 AM
#3
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.
-
November 18th, 2010, 02:07 PM
#4
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.
-
December 1st, 2010, 08:27 AM
#5
Re: Help with Crossword Solver application
Originally Posted by ProgramThis
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()
-
December 1st, 2010, 02:25 PM
#6
Re: Help with Crossword Solver application
You're welcome, glad you got it worked out.
-
November 23rd, 2015, 11:52 AM
#7
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|