The objective of this ACW is to develop two alternative data structures to represent WordSearch puzzles, and to develop two alternative data structures to represent the WordSearch dictionaries, and to investigate their efficiency. A WordSearch puzzle comprises a rectangular (normally square) grid of letters in which a number of words are hidden, and the goal of the puzzle is to find all the words present. The number of words hidden may or may not be specified, and the search may be aided by a dictionary of words to find, or it may be that the topic context is known (e.g. computer science) and the puzzler has to use their knowledge to decide what relevant words they can find. The words may be hidden within rows and/or columns of the grid, and possibly diagonally, and possibly each in either direction (see illustration). Words may also cross over, so one letter cell in the grid may contribute to several target words. If a dictionary is provided to support the searching, this may contain either the target words only, or the target words together with many other words to make the puzzle harder, or the enjoyment greater, depending on the puzzler's point of view! In this ACW, the puzzle grid can be assumed to be square, and that it is always 9x9 in size. There will also be dictionaries of words to support the search in each puzzle grid. Therefore, the objective of the work is to develop and implement relevant data structures to represent the grid and the dictionary for each puzzle, and to evaluate the performance of these data structures in operation as your program solves each puzzle. What will be the best data structures to represent the grid, and to hold the dictionary? Two alternative structures for each aspect are proposed for investigation. For each scenario, you are required to develop a C++ program to implement two structures (one for the grid, one for the dictionary), and add diagnostic code to report on the behaviour and efficiency of the data structures while grid letter sequences are being compared to dictionary contents in order to discover hidden words. Input and Output Each grid puzzle will be in a text file called wordsearch_grid.txt and you are to implement code that can populate the grid of your data structure by reading the letters contained in the file. The data file consists of n * n letters, each in the range A-Z, for example see the grid on the right, corresponding to the example grid given earlier. You can assume that all letters and words provided are in uppercase. After you have solved the puzzle, you are to output a number of findings (described later) to a file called either: results_simple_puzzle_simple_dictionary.txt or results_simple_puzzle_advanced_dictionary.txt or results_advanced_puzzle_simple_dictionary.txt or results_advanced_puzzle_advanced_dictionary.txt. These files will be in the format specified in Appendix A. 20/03/2015 5 There will be dictionary files provided, called dictionary.txt. Unseen puzzles and dictionaries will be used in the marking of this ACW and some diagnostics