Skip to main content
deleted 34 characters in body
Source Link
Stef
  • 397
  • 1
  • 8

The result is a 0.58% +- 0.27% probability that no word can be formed.

$ python3 get_proba.py 1000 50
loading dictionary
total words in dictionary is 279497
words 7 letters or shorter is 77459
Running for 50 experiments of 1000 draws...
Ran for 50 experiments of 1000 draws.
Successes: [996, 996, 996, 995, 992, 996, 998, 993, 994, 993, 992, 993, 998, 994, 994, 986, 994, 996, 990, 994, 997, 998, 994, 993, 993, 991, 999, 991, 997, 996, 993, 989, 995, 996, 998, 996, 995, 996, 992, 992, 998, 994, 993, 989, 993, 991, 991, 999, 995, 995]
Proba of failure = 0.00582000000000005 +- 0.0027472895733795517

The result is a 0.58% +- 0.27% probability that no word can be formed.

$ python3 get_proba.py 1000 50
loading dictionary
total words in dictionary is 279497
words 7 letters or shorter is 77459
Running for 50 experiments of 1000 draws...
Ran for 50 experiments of 1000 draws.
Successes: [996, 996, 996, 995, 992, 996, 998, 993, 994, 993, 992, 993, 998, 994, 994, 986, 994, 996, 990, 994, 997, 998, 994, 993, 993, 991, 999, 991, 997, 996, 993, 989, 995, 996, 998, 996, 995, 996, 992, 992, 998, 994, 993, 989, 993, 991, 991, 999, 995, 995]
Proba of failure = 0.00582000000000005 +- 0.0027472895733795517

The result is a 0.58% probability that no word can be formed.

$ python3 get_proba.py 1000 50
loading dictionary
total words in dictionary is 279497
words 7 letters or shorter is 77459
Running for 50 experiments of 1000 draws...
Ran for 50 experiments of 1000 draws.
Successes: [996, 996, 996, 995, 992, 996, 998, 993, 994, 993, 992, 993, 998, 994, 994, 986, 994, 996, 990, 994, 997, 998, 994, 993, 993, 991, 999, 991, 997, 996, 993, 989, 995, 996, 998, 996, 995, 996, 992, 992, 998, 994, 993, 989, 993, 991, 991, 999, 995, 995]
Proba of failure = 0.00582000000000005
added 687 characters in body
Source Link
Stef
  • 397
  • 1
  • 8

Rendering unto Caesar:

  • The code in build_dict() is from @DenisS's answer;
  • The rest of the code is from me;
  • The file dictionary.txt is the 2019 Collins Scrabble Words file linked in this answer to a related question;
  • The justification that a hand with a blank tile can always score is in @DenisS's answer (if '*' in letters: return True in my code);
  • The basic idea of the algorithm is to use a Monte-Carlo method, because browsing the dictionary is acceptable but trying out all possible hand combinations is unreasonable.

Rendering unto Caesar:

  • The code in build_dict() is from @DenisS's answer;
  • The rest of the code is from me;
  • The file dictionary.txt is the 2019 Collins Scrabble Words file linked in this answer to a related question;
  • The justification that a hand with a blank tile can always score is in @DenisS's answer (if '*' in letters: return True in my code);
  • The basic idea of the algorithm is to use a Monte-Carlo method, because browsing the dictionary is acceptable but trying out all possible hand combinations is unreasonable.
Source Link
Stef
  • 397
  • 1
  • 8

I used the beginning of the program in @DenisS's answer to build the Scrabble dictionary, then I used it to write a small monte-carlo program to estimate the probability that no word can be formed with seven random tiles.

The result is a 0.58% +- 0.27% probability that no word can be formed.

Output

$ python3 get_proba.py 1000 50
loading dictionary
total words in dictionary is 279497
words 7 letters or shorter is 77459
Running for 50 experiments of 1000 draws...
Ran for 50 experiments of 1000 draws.
Successes: [996, 996, 996, 995, 992, 996, 998, 993, 994, 993, 992, 993, 998, 994, 994, 986, 994, 996, 990, 994, 997, 998, 994, 993, 993, 991, 999, 991, 997, 996, 993, 989, 995, 996, 998, 996, 995, 996, 992, 992, 998, 994, 993, 989, 993, 991, 991, 999, 995, 995]
Proba of failure = 0.00582000000000005 +- 0.0027472895733795517

Code

def build_dict():
    words = []
    words_in_dictionary = 0
    words_short_enough = 0
    print("loading dictionary")
    with open("dictionary.txt", "r") as dictfile:
        for line in dictfile:
            base_word = line.strip()
            if len(base_word) > 0:
                words_in_dictionary = words_in_dictionary + 1
                if len(base_word) <= 7:
                    words_short_enough = words_short_enough + 1
                    word = {"base": base_word, "sorted": sorted(base_word)}
                    words.append(word)
    print("total words in dictionary is " + str(words_in_dictionary))
    print("words 7 letters or shorter is " + str(words_short_enough))
    ok_combinations = [''.join(word["sorted"]) for word in words]
    return(ok_combinations)

def flatten(ll):
    return [x for l in ll for x in l]

def build_letter_bag():
    return flatten([['A']*9, ['B']*2, ['C']*2, ['D']*4, ['E']*12, ['F']*2, ['G']*3, ['H']*2, ['I']*9, ['J']*1, ['K']*1, ['L']*4, ['M']*2, ['N']*6, ['O']*8, ['P']*2, ['Q']*1, ['R']*6, ['S']*4, ['T']*6, ['U']*4, ['V']*2, ['W']*2, ['X']*1, ['Y']*2, ['Z']*1, ['*']*2])

dico = build_dict()
letter_bag=build_letter_bag()

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def can_make_word(letters):
    if '*' in letters:
        return True
    return any((''.join(subset) in dico) for subset in powerset(sorted(letters)))

import random

def montecarlo(n):
    nb_ok = 0
    for i in range(n):
        letters = random.sample(letter_bag, 7)
        nb_ok += (1 if can_make_word(letters) else 0)
    return nb_ok

import statistics

def run_experiments(nb_draws, nb_experiments):
    nb_ok_list = [montecarlo(nb_draws) for i in range(nb_experiments)]
    average = statistics.fmean(nb_ok_list)
    stdev = statistics.pstdev(nb_ok_list, mu=average)
    return average, stdev, nb_ok_list

def get_args(argv):
    nb_draws, nb_exp = 1000, 1
    if len(argv) > 1:
        nb_draws = int(argv[1])
        if len(argv) > 2:
            nb_exp = int(argv[2])
    return nb_draws, nb_exp

def main(argv):
    random.seed()
    nb_draws, nb_experiments = get_args(argv)
    print('Running for {} experiments of {} draws...'.format(nb_experiments, nb_draws))
    average, stdev, l = run_experiments(nb_draws, nb_experiments)
    print('Ran for {} experiments of {} draws.'.format(nb_experiments, nb_draws))
    print('Successes:', l)
    print('Proba of failure = {} +- {}'.format((nb_draws - average)/nb_draws, stdev/nb_draws))

import sys
if __name__=='__main__':
    main(sys.argv)