CODEWITHSUNDEEP
javaalgorithmperformance
Jacob
Jacob

Reputation: 333

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:

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?

Upvotes: 0

Views: 295

Answers (1)

Robin
Robin

Reputation: 36611

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.

Upvotes: 3

Related Questions