## Description

In this assignment, we will be writing the skeleton for a simplified version of the game Boggle. Boggle is

a popular party game; for more information on Boggle, visit:

ht tp s: / /www .wi k i how . c om/ P l ay -Bo g g l e

We will be building a version of Boggle starting from the Othello platform we studied in class. Our

version of Boggle will use exclusively 5-letter words from the Word Ladder problem we (also) studied in

class. You will notice that the template file for this homework is significantly less complete than those for

previous labs and homeworks. That’s because each homework assumes you will do more and more of the

work yourselves. Both the Othello code and the Word Ladder dictionary are available on ICON; feel free

to use these as models.

The rest of these instructions outline the methods that you should implement, describing their input/output

behaviors. As you work on each function, test your work on the document provided to make sure your

code functions as expected. Feel free to upload versions of your code as you go; we only grade the last

version uploaded, so this practice allows you to “lock in” working partial solutions prior to the deadline.

Finally, some general guidance.

(1) Start with the template file and immediately complete the hawkid() function so that we may

properly credit you for your work. Test hawkid() to ensure it in fact returns your own hawkid

as the only element in a single element tuple. Also be sure to add your name and section to the

comments at the top. Ignore this instruction at your own risk: some of you have become serial

offenders and I have had to manually regrade your code too many times!

(2) As with HW1 and HW2, you will be graded on both the correctness and the quality of your

code, including the quality of your comments!

(3) Be careful with iteration; always choose the most appropriate form of iteration

(comprehension, while, or for) as the function mandates. Poorly selected iterative forms may be

graded down, even if they work!

1

class Boggle()

Our version of Boggle is always played on a 5×5 board, which is populated with letters according to the

distribution implicit in the file words.dat. The __init__() method for class Boggle should create a

representation of the Boggle board, and pop up a TKinter version of the board, showing letters randomly

allocated to each of the 25 locations. Hint: the random allocation of letters should be weighted using the

random.choices() function from Python’s random module and based on the data obtained from the

readData() method described next.

Boggle.readData(self, file)

The readData() method1 will be called from the __init__() method. It should open the specified file and

read in the list of words it contains. It should construct two data structures, both variables in the class

Boggle.

The first data structure (let’s call it F, for frequency) should be a dictionary indexed by the letters in the

words read in. As in HW2, the construction of F should involve counting the number of letters of the type

specified by the key k in F[k]. Once you have read in all the words, each F[k] should be recast to represent

the probability that a letter, drawn at random from the collection of letters contained in the words of the

file you have just finished reading, is, in fact, the letter k. You will use this value to create the population

and the weights parameters for the random.choices() function.2

The second data structure (let’s call it T, for trie, the technical name for this kind of data structure), is a

deeply nested set of dictionaries, each using letters as keys. At the outermost level, the value of key k will

itself be a dictionary, also using letters as keys. At the innermost level, the key will still be a letter, but the

value will be a word from the file you just read in. An example will help make this clear.

Assume your file contains only the word ’paste’. The value for F and T would then be:

F= { ’p’ : 0.2, ’ a’ : 0.2, ’ s’ : 0.2, ’ t’: 0.2, ’ e’ : 0.2 }

T= { ’p’ : { ’ a’ : { ’ s’ : { ’ t’: { ’ e’ : ’ pa s t e ’ } }}}}

Notice howFrepresents the frequency estimates for the letters in the (lone) word from the file, while the

trie indexes each letter of the word, in order as you descend the nested dictionaries, until you get to the

original word. If the file contained instead the words ’paste’ and ’pasta’, the value of F and T would

instead look like:

F= { ’p’ : 0.2, ’ a’ : 0.3, ’ s’ : 0.2, ’ t’: 0.2, ’ e’ : 0.1 }

T= { ’p’ : { ’ a’ : { ’ s’ : { ’ t’: { ’ e’ : ’ pa s t e ’, ’ a’ : ’ pa s t a ’ } }}}}

If it also included ’pasha’, T would look like:

T= { ’p’ : { ’ a’ : { ’ s’ : { ’ t’: { ’ e’ : ’ pa s t e ’, ’ a’ : ’ pa s t a ’ } , ’ h’ : { ’ a’ : ’ pa s ha ’ }}}}}

We will use this second data structure in the second half of the assignment.3

1 The original handout omitted the self argument, which of course is necessary for every method of class Boggle().

2 You should also feel free to use cumulative counts and the cum_weights parameter instead of frequencies and

the weights parameter.

3 There was an extra curly bracket in this expression which has since been corrected.

2