KeiruaProd

I help my clients acquire new users and make more money with their web businesses. I have ten years of experience with SaaS projects. If that’s something you need help with, we should get in touch!
< Back to article list

Solving dadagram

Dadagram came up a few days ago.

This is like a 1-dimensional, 1-step Scrabble : you only have to find the best word given 7 letters and a board layout, where each letter has a score than can be increased by the multiplier on the cell it lays on.

This is of course very easy to brute force. It’s also very fast.

Yes, it kills the game, but I don’t care. It’s much more fun for me to play Dadagram like this, by solving it once and for all.

Here is my code. It’s not clever, but I think it’s interesting anyway since:

# Solve Dadagram
# python solve.py --letters "FNISDEE" --multipliers "3131112" --nb_solutions 3

from wordlist import wordlist, scores
from collections import defaultdict
from typing import List, Set, Dict
from itertools import combinations
import pprint as pp
import click

def score(word: List[str], multipliers: List[int]) -> int:
    """
    Computs the score of a word on a board with multipliers
    """
    # POINTS = {'V': 4,'R': 1,'B': 3,'U': 1,'E': 1,'O': 1,'T': 1,…}
    return sum([scores[l] * multipliers[i] for i, l in enumerate(list(word))])


def valid_words_and_mapping(wordlist: List[str]):
    """Sort the word list, build a mapping between the sorted letters and the
    possible words"""
    valid_words = sorted([sorted(w) for w in wordlist])
    mapping = defaultdict(list)
    for w in wordlist:
        mapping["".join(sorted(w))].append(w)
    return valid_words, mapping


def search_possible_words(letters: List[str], valid_words) -> Set[str]:
    """
    Generate all 6-letter words given the input letters,
    return those that exist in the dictionnary
    """
    possible_solutions = set()
    curr_length = len(letters)

    while curr_length >= 1:
        for w6 in combinations(letters, curr_length):
            w6 = sorted(w6)
            if w6 in valid_words:
                possible_solutions.add("".join(w6))
        curr_length -= 1
    return possible_solutions


def score_possible_solutions(
    possible_solutions: Set[str], mapping, multipliers
) -> Dict[str, int]:
    words_and_points = {}
    for p in possible_solutions:
        for word in mapping[p]:
            words_and_points[word] = score(word, multipliers)
    return words_and_points


from collections import OrderedDict


def get_top_words(words_and_points, n=10):
    """
    Get top n words by score.

    Returns a dictionary or an `OrderedDict` if `order` is true.
    from https://stackoverflow.com/a/38218745
    """
    top = sorted(words_and_points.items(), key=lambda x: x[1], reverse=True)[:n]
    return OrderedDict(top)


def tabulate(data):
    widths = [[len(w), len(str(score))] for w, score in data.items()]

    max_width_w = 2 + max([word_w for (word_w, score_w) in widths])
    max_width_s = 2 + max([score_w for (word_w, score_w) in widths])

    for index, (word, score) in enumerate(data.items()):
        score = str(score)
        lw = word.ljust(max_width_w)
        cs = score.center(max_width_s)
        print(f"{lw}|{cs}")



@click.command()
@click.option('--letters', default="VRBUEOT", help='The letters you want to want words with.')
@click.option('--multipliers', default="1311213")
@click.option('--nb_solutions', default=15)
def main(letters, multipliers, nb_solutions=15):
    multipliers = list(map(int, list(multipliers)))
    valid_words, mapping = valid_words_and_mapping(wordlist)
    possible_solutions = search_possible_words(sorted(letters), valid_words)
    words_and_points = score_possible_solutions(
        possible_solutions, mapping, multipliers
    )

    best_word = max(words_and_points, key=words_and_points.get)
    print("Best solution:")
    print(best_word, words_and_points[best_word])

    print(f"\nTop {nb_solutions} solutions:")
    best_words = get_top_words(words_and_points, nb_solutions)
    # simple alternative: pp.pprint(best_words)
    tabulate(best_words)


if __name__ == "__main__":
    # python solve.py --letters "VRBUEOT" --multipliers "1311213"
    # python solve.py --letters "FNISDEE" --multipliers "3131112" --nb_solutions 3
    # Best solution:
    # DEFINES 24
    # 
    # Top 3 solutions:
    # DEFINES  | 24 
    # DEFIES   | 22 
    # INFEEDS  | 22 
    main()

You’ll also need wordlist.py for some external data:

# from view-source:https://dadagrams.com/practice
boards = ["1111123", "1111223", "1111332"]
scores = {'A': 1,'B': 3,'C': 3,'D': 2,'E': 1,'F': 4,'G': 2,'H': 4,'I': 1,'J': 8,'K': 5,'L': 1,'M': 3,'N': 1,'O': 1,'P': 3,'Q': 8,'R': 1,'S': 1,'T': 1,'U': 1,'V': 4,'W': 4,'X': 8,'Y': 4,'Z': 8};

# from https://dadagrams.com/wordlist.js
wordlist = [
     "AA",
     "AAH",
     "AAHED",
     "AAHING",
     "AAHS",
     
]

and requirements.txt:

click==8.1.3

Then, you can install the dependencies in a virtual environment:

python3 -m venv .env
source .env/bin/activate
pip install -r requirements.txt

and run the code:

python solve.py --letters "FNISDEE" --multipliers "3131112" --nb_solutions 3