Task 2: Boggle Buddy
The game of Boggle is normally played on a 4x4 grid. 16 dice, each die printed with six characters from the letters A to Z, are placed in a closed container and the container is shaken. The dice land in the 4x4 grid and the letter on the top face is the letter for that grid square. A three-minute timer is typically started and players try and make as many words from the letters on the grid as they can before time runs out. These words have to follow certain rules - for this task we will assume the rules followed are:
Each letter (except for the first letter) must be adjacent (horizontally, vertically or diagonally) to its preceding letter.
A grid square's letter can only be used once (if there are two copies of the same letter appearing in different grid squares - both can be used).
The word must be one of the allowed words.
Though there are additional rules when played as a group of players, but points are assigned for the total number of letters in all valid words made.
Part A (Code)
A regular board-game playing group have invited some tourists to play and brought Boggle. The tourists wanted to try playing but were not confident in their foreign language skills and were worried the words they'd make might not be valid for play. The group asked online if anyone would be willing to put together a system to quickly retrieve all valid words so that the tourists can quickly check the list to see that they did not make a mistake.
Part B (Code)
Hooked on the board game, the tourists purchased a copy and brought it home as a souvenir. Their children wanted to play the game with their parents, but because they are still practicing the language, they sometimes get stuck trying to find a word. Seeing a good opportunity for their children to practice a foreign language, the parents reached out again to see if anyone could put together a tool that gives a hint for the next letter that can be played to make a word.
Part C (Written)
The parents notice the program often takes time to think of solutions, but only on boggle games where the same letter appears lots of times. Given the sand timer for thinking of words gives such a short time, they ask if there's a way to speed it up, for example, if each letter can only be used once in each word (even if it appears more than once on the board). How might their rule modification change the worst case complexity of finding all words?
Part D (Code)
Hearing that the improvement might be promising, they ask you to put together the tool giving all valid words with the added rule.
Task 2: Prefix Tries and Boggle Graphs
Background - Prefix Tries
For Task 2, you will need to build a prefix trie. This is a data structure where, rather than containing a full key in each node, each edge in the trie represents a particular letter. Since each edge is associated with a character, both checking whether a given string is in the tree and finding all strings that match a given prefix are efficient operations.
For example, to store the strings "ham", "hat", "hi" and "who", our prefix tree might look like:
For simplicity, the tree will:
Contain a pointer for each possible following character - even if that character is unlikely to appear.
Also store the \0 character used as the delimiter when storing the string in the tree.
This means every node will contain 256 pointers - the majority of most of which are typically set to NULL. This also means each leaf of the tree will correspond to the completion of an inserted string - with completion of strings occurring nowhere else in the tree.
Background - Boggle Graphs
For a given set of dice, a graph can be constructed showing the connections.
This graph can then be used to work out what are valid words to play. For example, the word "open" could be played, starting from O:
Part A (Code)
To support checking you will search simultaneously through the prefix tree and the boggle graph. Returning the list of all words starting from each position. You must use the prefix tree to limit the available locations to travel to next. You will likely find it useful to temporarily mark seen words as you travel through the prefix tree (and then unmark these at the end of the search).
Part A will take two filenames at the command line:
The first filename is the name of the dictionary of words which are allowed for that game.
The second filename is the name of the board used for boggle.
The format of the file with the first given filename will be similar to this example:
10 cleaner clean lean opera open pants panel pager speak team
Where all files follow the format:
The first line specifies the number of words in the dictionary (10 in this example)
All following lines specify words in the dictionary.
The format of the file with the second given file name will be similar to this example:
O E E T S P A G J N E L V E R C
Where the board this file represents matches the example board above. The format of the file will always be 16 capital letters, arranged in a 4-by-4 grid. When determining whether letters on the board can be used to make words, you must ignore capitalisation.
The output must be the list of words (alphabetically ordered (breaking ties by length)) that can be made on the board which follow the boggle rules stated earlier. For the given example this would be:
clean cleaner lean open pager panel
Part B (Code)
In Part B, the file inputs are the same, but an additional input is given on the command line through stdin. This is the word constructed so far - you must output the list of letters following the given input that can follow on the boggle board as a hint.
For example, for the same input filenames as in Part A, if the input pa were given through stdin, the output printed to stdout must be:
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
