Skip to content
Advertisement

How to generate unique combinations of the alphabet up to length 6?

I am creating a simple program to see which combination of letters generates the most possible words for the NY Times Spelling Bee puzzle. What I have so far is a text file containing 80,000+ words and the below code which naively selects a required char and then generates a random combination of 6 characters. I then compile my pattern and test against the collection of known words. This solution needs to be optimized because there are 26^7 combinations to test.

This solution can be optimized in a few ways:

  • Do no regenerate optional character arrays that are similar or contain duplicate letters. “abcdef” would have the same results as “fedcba”. Likewise, “aaabcd” wont have as many solutions as “abcdef” because all letters can be reused.
  • Do no generate optional character arrays that contain the required character. The spot in the optional character array is best used to introduce a new character into the solution.
  • Something else i cant think of?
int numMaxSolutions = 0;
char[] alphabet = "abcdefghijklmnopqrstuvwxyz".toCharArray();
for (char keyChar : alphabet) {
  for (char a : alphabet) {
  for (char b : alphabet) {
  for (char c : alphabet) {
  for (char d : alphabet) {
  for (char e : alphabet) {
  for (char f : alphabet) {
    char[] optionalChars = new char[]{a,b,c,d,e,f};
    Pattern pattern = this.constructPattern(keyChar, optionalChars);
    List<String> results = new ArrayList<String>();
    for (String word : words) {
      if (word.length() >= this.minLength && pattern.matcher(word).matches()) {
        results.add(word);
      }
    }
    if (results.size() > numMaxSolutions) {
      numMaxSolutions = results.size();
      System.out.println(String.format("Max: %c-%s (%d)", keyChar, String.valueOf(optionalChars), numMaxSolutions));
    }
  }
  }
  }
  }
  }
  }
}

How can i acheive the first two?

Advertisement

Answer

I would go the other way around for this and loop over the list of known words instead.

E.g. in pseudocode:

Map<String,Integer> combination2Count = new HashMap<>();
for (word in list){
  String sortedCharacters = sortCharactersAlphabetically(word);
  combination2Count.put(sortedCharacters, current count + 1);
}

and now you search for the entry with the highest count. That gives you the combination of characters with the most valid words.

If you also need the words, you can adjust the map to a Map<String,List<String>> where the List<String> contains the words for that combination of characters.

Advertisement