2
\$\begingroup\$

What is Spellathon?

The rules of Spellathon are as follows:

  • Create words that have 4 to 7 letters.
  • Include the center letter in every word.
  • Form at least one 7-letter word.
  • Plurals are acceptable.
  • The dictionary used is in English.

Here is a similar implementation.

The dictionary (word list) I'm using is this.

public class Spellathon {

    private static final Set<String> permutations = new HashSet<>();

    private static void permutation(String str) {
        permutation(str.charAt(0), "", str);
    }

    private static void permutation(char idx, String prefix, String str) {
        int n = str.length();

        if (n != 0) {
            for (int i = 0; i < n; i++) {
                permutation(idx, prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
            }
        }

        if(prefix.length() > 3 && prefix.indexOf(idx) >= 0) {
            permutations.add(prefix);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String letters;

        System.out.print("Input: ");
        letters = sc.nextLine();

        permutation(letters);

        try {
            for(String x: permutations) {
                Scanner scFile = new Scanner(new File("words.txt"));

                while(scFile.hasNextLine()) {
                    String cur = scFile.nextLine();
                    if(cur.equalsIgnoreCase(x)) {
                        System.out.println("Found: " + cur);
                    }
                }
            }
        } catch (FileNotFoundException ex) {
            System.out.println("Word list file Not Found.");
        }
    }
}

Input: Pass the given letters as a String with the central letter as the first letter. The other letters can be in any order.

Output:

Input: elolh
Found: Hell
Found: hell
Found: Lole
Found: hello
Found: Holle
Found: Hole
Found: hole

I don't mind the redundant occurrences. My issue is that the code takes a lot of time to execute (that is why, I used 5 letters as an example).

Any comments/answers that can help reduce the execution time will be appreciated. Also, if anyone review the overall correctness of the program, it will be helpful.

\$\endgroup\$
6
\$\begingroup\$

The explanation for slowness is simple: you're doing a slow operation (reading a file) many many times (due to combinatorial explosion).

How many permutations of "hello" are there? For 5 items, there are 5!, or 120 permutations. However, two of the letters are indistinguishable, so it's actually \$\frac{5!}{2!}\$, or 60. Add the 12 permutations of "hell", 24 permutations of "helo", and 12 permutations of "hllo", and we have about a hundred.

Of those, I would expect only maybe a dozen to be valid English words.

Then, for each permutation, you are opening the file and reading every line to see if the candidate is a word. File IO involves the operating system and the disk — both very expensive.


Generating all permutations of something is costly. In contrast, checking whether two given words are permutations of each other is a simple matter of counting.

A smarter approach, therefore, would be to go through the dictionary once, and check whether each word meets the acceptance criteria.

\$\endgroup\$
  • 1
    \$\begingroup\$ "[T]he 12 permutations of 'hell'" sounds like the title of book. \$\endgroup\$ – Dair Sep 29 '16 at 22:45
3
\$\begingroup\$

Don't read the file multiple times

        try {
            for(String x: permutations) {
                Scanner scFile = new Scanner(new File("words.txt"));

                while(scFile.hasNextLine()) {
                    String cur = scFile.nextLine();
                    if(cur.equalsIgnoreCase(x)) {
                        System.out.println("Found: " + cur);
                    }
                }
            }

You don't need to create a new Scanner on every iteration of a loop. Consider

        try (Scanner scFile = new Scanner(new File("words.txt"))) {
            while (scFile.hasNextLine()) {
                String word = scFile.nextLine().toLowerCase();
                if (permutations.contains(word)) {
                    System.out.println("Found: " + word);
                }
            }

The try-with-resources form will automatically close the Scanner for you when finished. Even if an exception is thrown.

Then you just need to change

        permutation(letters);

to

        permutation(letters.toLowerCase());

and you can take advantage of the quick access time of HashSet.

Note that you could also use a custom type with case insensitive equals and hashCode methods instead of taking toLowerCase on letters and the words in the file.

Separate logic and display

Rather than printing the string, consider saving it instead:

                if (permutations.contains(word)) {
                    words.add(word);
                }

And declare

        List<String> words = new ArrayList<>();

Don't mix delegation and logic

You delegate to permutations and then you check them in main. Delegate the checking.

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            System.out.print("Input: ");
            String letters = sc.nextLine().toLowerCase();

            permutation(letters);

            for (String word : findWordsInPermutations()) {
                System.out.println("Found: " + word);
            }
        }
    }

This way main only handles standard input and output.

Note that permutation and findWordsInPermutations would be more flexible if they were static and returned permutations and took permutations as a parameter respectively.

You can do better

Rather than generating permutations, test each word in the dictionary against the input.

Change

                if (permutations.contains(word)) {

to

                if (isPermutation(word, letters)) {

Then just define isPermutation such that it returns true if and only if word can be made from letters.

Then you don't need the permutation method at all.

\$\endgroup\$
0
\$\begingroup\$

As suggested in other answers, the best way to improve the performance is to read the dictionary only once. For a decent sized dictionary, the difference in performance will be huge.

This is an alternative approach reading each word in the dictionary and checking if it is a permutation of the given letters:

public class Spellathon {

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            System.out.print("Input: ");
            String letters = sc.nextLine();
            permutationsOf(letters, "words.txt").forEach(System.out::println);
        } catch(IOException e) {
            System.out.println("Unable to open the file");
        }
    }

    public static List<String> permutationsOf(String letters, String file) throws IOException{
        List<Character> letterList = new ArrayList<>(letters.length());
        for (char c : letters.toLowerCase().toCharArray()) {
            letterList.add(c);
        }
        try (Stream<String> words = Files.lines(Paths.get(file));) {
            return words.filter(word->word.length() <= letters.length())
                        .filter(word->isPermutation(word, letterList))
                        .collect(Collectors.toList());
        } 
    }

    public static boolean isPermutation(String word, List<Character> letterList) {
        List<Character> remainingLetters = new ArrayList<Character>(letterList);
        for (char letter : word.toLowerCase().toCharArray()) {
            if (!remainingLetters.remove(Character.valueOf(letter))) {
                return false;
            }
        }
        return true;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.