CODEWITHSUNDEEP
pythonalgorithmpermutationscrabble
George Cheng
George Cheng

Reputation: 61

Generating Optimal Word Combinations from Letters to Maximize Scrabble Score (Based on length of words)

My Goal:

Scoring Rules:

Sorry I am new to Python or other coding language. I have no idea how to list out all possible combination of words without generating a 36! Permutations - If I do so (silly of course), I can simply continue by splitting the string from the first letter to the last letter to form all possible words (Show in next sections)

My Current Thoughts (Seems extremely inefficient):

Focus on constrained search space of 4-10 letter words and using a dictionary to prune invalid combinations.

  1. Generate all possible letter combinations of lengths 4-10 letters
  2. Filter combinations to valid dictionary words
  3. Calculate score for each valid word
  4. Find the combination of valid words that maximizes total score
    • Max score is 120 points using 4 words of length 9

Implementation:

But I ask this question because I seriously want to avoid this inefficient methods: Imagine I create a 36! Permutations, for each permutation I split the string in a loop to generate all possible combinations of words (tuples), then I compare the score of all tuples to identity the highest possible score a player can generate in any given 36 letters. It seems ridiculous for me to solve a simple (to some extent) game using brutal computation force.

Trying to Avoid with your Suggestions:

Upvotes: 4

Views: 294

Answers (1)

sjking
sjking

Reputation: 1290

Instead of considering every permutation of the 36 letters, another approach to solve this problem is to generate the valid words, and then enumerate all the combinations of valid words. What are valid words? I will explain.

Given a dictionary, and a list of 36 letters, the valid words are all the words in the dictionary that can be constructed by using the 36 letters. After finding the valid words, a backtracking algorithm can be used to enumerate all possible combinations (with repetition) of the valid words that can be combined together by using the 36 letters.

The time complexity of this algorithm is polynomial in the size of the set of valid words. Since at most nine four-letter words can be used as matches for the 36 letters, it means the algorithm has an O(n^9) runtime, where n is the size of the set of valid words.

Here is the implementation in Python (note that I am using the Linux dictionary file, so you can change the dictionary file if you are on a different platform). After the algorithm finishes, the last set of words printed will be one of the optimal solutions. If you only want to check if there is a solution with 120 points, that should run quickly, since the valid words count will be low, and it only needs to check for combinations of up to four words. You can play with the MAX_WORD_SIZE and MIN_WORD_SIZE variables to see what gives the best results. You can also set the LETTERS to whatever you want. I just initialized it randomly from ASCII characters.

import random
import string
from typing import List, Dict
from collections import Counter

DICT_FILE = "/usr/share/dict/words"
MIN_WORD_SIZE = 4
MAX_WORD_SIZE = 10
LETTERS = "".join(random.choice(string.ascii_lowercase) for _ in range(36))

def is_valid(word: str, letter_counts: Dict[str, int]):
    for c in word:
        if letter_counts[c] == 0:
            return False
        letter_counts[c] -= 1
    return True


def valid_words(letters: str) -> List[str]:
    valid = []
    letter_counts = Counter(letters)
    with open(DICT_FILE) as f:
        for line in f:
            word = line.strip()
            if (
                "'" in word or 
                len(word) < MIN_WORD_SIZE or
                len(word) > MAX_WORD_SIZE
            ):
                continue
            if is_valid(word, letter_counts.copy()):
                valid.append(word)
    return valid


def remove_letters(word: str, counts: Dict[str, int]):
    for c in word:
        counts[c] -= 1

def add_letters(word: str, counts: Dict[str, int]):
    for c in word:
        counts[c] += 1

def find_optimal(valid_words: List[str], letters: str):
    curr_words = []
    counts = Counter(letters)
    n = len(valid_words)

    def find_words(i: int, num_letters: int):
        if i == n or num_letters < 4:
            return
        for j, word in enumerate(valid_words[i:], i):
            if is_valid(word, counts.copy()):
                remove_letters(word, counts)
                curr_words.append(word)
                yield from find_words(j, num_letters - len(word))
                yield curr_words.copy()
                curr_words.pop()
                add_letters(word, counts)

    yield from find_words(0, len(letters))


def score(word_combos: List[str]):
    return sum(
        min(
            (len(word) - 3) * 5, 
            30,
        ) for word in word_combos
    )


if __name__ == "__main__":
    valid = valid_words(LETTERS)
    latest_highest_score = 0
    latest_best_words = []
    for word_combos in find_optimal(valid, LETTERS):
        curr_score = score(word_combos)
        if curr_score >= latest_highest_score:
            latest_highest_score = curr_score
            latest_best_words = word_combos
            print(word_combos, latest_highest_score)

Upvotes: 0

Related Questions