Scrabble algorithm review and performance suggestions

Question

After finishing Project Euler 24, I decided to make a scrabble type of application using /usr/lib/dict as my dictionary what I cat that into a word file. It does take a few seconds, and the dictionary selection isn't that great.

Is there any way I could make it faster, more effective, and with a better dictionary source?

public class Scrabble {
 public static ArrayList<String> numbers = new ArrayList<String>();
 public static ArrayList<String> numbers2 = new ArrayList<String>() {
 };
 public static void main(String[] args) {
 Scanner dict = null;
 try {
 dict = new Scanner(new File("words.txt"));
 } catch (FileNotFoundException ex) {
 }
 while (dict.hasNextLine()) {
 numbers.add(dict.nextLine());
 }
 String n = "gojy";//random text here
 rearrange("", n);
 LinkedHashSet<String> listToSet = new LinkedHashSet<String>(numbers2);
 ArrayList<String> listWithoutDuplicates = new ArrayList<String>(listToSet);
 for (int i = 0; i < listWithoutDuplicates.size(); i++) {
 if (numbers.contains(listWithoutDuplicates.get(i))) {
 System.out.println(listWithoutDuplicates.get(i));
 }
 }
 }
 public static void rearrange(
 String q, String w) {
 if (w.length() <= 1) {
 String k = q + w;
 numbers2.add(k);//full word
 numbers2.add(q);//smaller combination to get words with less letters. doesn't work too well
 } else {
 for (int i = 0; i < w.length(); i++) {
 String c = w.substring(0, i)
 + w.substring(i + 1);
 rearrange(q
 + w.charAt(i), c);
 }
 }
 }
}

Answer 1

If what you are trying to do is store a huge list of valid words in such a way that you can test whether a given string is a valid word, a Trie works well. See this Stack Overflow question.

Load the wordlist into the Trie when your server starts, and use the same Trie for all games (assuming this is a client server game). It's trickier than the linked thread if you need to include more than the standard 26 letters of the alphabet, but I've done a Unicode Trie for a chat filter before and I could help if you need that.

I don't understand what you are trying to do with the rearrange method. Can you explain?

• c0rruptbytes: The rearrange method is basically like if I have "abc", it'll do "a","b","c","ab","bc","ac","cb","ca","ba", etc.. Also, thanks. I will look into Tries

Answer 2

@Teresa has already provided some good hints on how to improve the performance by using a better data structure so I'll concentrate on general things:

1. Your code has a bug such as that it will crash with a NullPointerException if the file cannot be found.

   • You initialize dict to null
   • You catch the FileNotFoundException when trying to create dict
   • If the exception got caught the dict will still be null and it will throw when you try to access it.

   So the whole try-catch around the Scanner instantiation is pretty much useless as it will crash anyway. Even worse: Instead of getting a FileNotFoundException which pretty much tells you what is wrong you get a fairly meaningless NullPointerException.

2. You have two static arrays numbers and numbers2. These names are useless as they do in no way give you any idea whatsoever what they are being used for. The name of a variable, method, class, parameter, etc. is effectively the advertising sign for its purpose. A good concise name goes a long way of

   • Making your code more readable and understandable
   • Reducing bugs by misunderstanding the purpose of your own variables

   In this case there is not much code and it's not terribly complicated but you should get into the habit of choosing good names.

3. dict is not a good name for the Scanner as it doesn't represent a dictionary in itself - it's a reader which reads lines from a file.

4. All your code is in the main method. You should get into the habit of building reusable pieces of code - in the case of Java this means creating reusable classes. So I'd suggest your create a dedicated class which holds your lookup structure and provide as well defined interface for adding valid words and looking up a word. Something like this:

   public class WordLookup
   {
    public WordLookup()
    {
    ...
    }
    public void addValidWord(string word)
    {
    ...
    }
    public bool isValidWord(string word)
    {
    ...
    }
   }
   

   Now main can be rewritten as:

   public static void main(String[] args) {
    Scanner reader = new Scanner(new File("words.txt"));
    WordLookup lookup = new WordLookup();
    while (reader.hasNextLine()) {
    lookup.addValidWord(reader.nextLine());
    }
    String n = "gojy";//random text here
    rearrange("", n);
    LinkedHashSet<String> listToSet = new LinkedHashSet<String>(numbers2);
    ArrayList<String> listWithoutDuplicates = new ArrayList<String>(listToSet);
    for (int i = 0; i < listWithoutDuplicates.size(); i++) {
    string currentWord = listWithoutDuplicates.get(i);
    if (lookup.isValidWord(currentWord)) {
    System.out.println(currentWord);
    }
    }
   }
   

   What do you gain from it: You can now fiddle with the implementation of WordLookup without having to touch the main method.

I came across a saying a while ago, don't remember where, which I quite like:

Train like you fight because you will fight like you train

So train yourself to write well structured encapsulated code even for seemingly simple things because it will form a habit. Even if you don't want to develop software professionally in the long run you will find it more rewarding when you do it right.

• 200_success: I would move even more code out of main(). How about WordLookup lookup = WordLookup.load(new File("words.txt"))?
• ChrisWue: Hm, don't know about putting the responsibility about loading the list from a file into the class. Ideally you make the ctor take an Iterable<string>. Then you can use something like this: stackoverflow.com/a/4677481/220986 to pipe in the words without having to read the entire file into memory first and WordLookup doesn't need to know where it's coming from.

Answer 3

I found the code rather hard to follow due to some unconventional naming:

• numbers and numbers2 are actually lists of Strings, not numbers.
• dict is a Scanner, not a dictionary.
• n is a String, not an integer.

---

The numbers2 assignment has inexplicable trailing braces. That creates an anonymous inner class that extends ArrayList, but not overriding or defining any additional members!

---

You swallowed FileNotFoundException, which just makes debugging more difficult. In general, if you don't know what to do about an exception, just let it propagate. In this case,

public static void main(String[] args) throws FileNotFoundException

will take care of it.

---

To iterate through all elements of a list...

for (String s : listWithoutDuplicates) {
 ...
}