CROSSWORD C++

Only editing file solve.cpp

To build the program, change directory to code folder and inside of it type

make If the building process was successful, an executable solve will be created. Run it by supplying a crossword file as the program argument: ./solve ../examples/111.cross (Here we used one of the crosswords from examples folder, but you can (and should) experiment with it, use your own crosswords, as well as use other examples we provide.)

First, it loads the supplied crossword file and creates a Puzzle object, which carries the information about the crosswords and provides the game interface for you. Then it calls function solve(Puzzle&) from solve.cpp , this is the central function you will be implementing (while also adding your own functions as the need arises).

We are provided with the following interface: int puzzle.height; // number of rows in the grid int puzzle.width; // number of columns string puzzle.words[]; // array of strings containing the list of words int puzzle.numWords; // number of words And three functions: char puzzle.get(int row, int col); Returns the character at the position (row, col) , which can be a letter 'a' - 'z' , a question mark '?' , or a space ' ' for blank squares.

bool puzzle.guess(int row, int col, char ch); Attempts to guess if the character at position (row, col) is equal to ch . Returns true if guess was correct, or false otherwise. This operation is stateful: it counts the number of correct and incorrect guesses, so use it wisely, try to minimize the number of wrong guesses. (The previous function get is free to use any number of times). void puzzle.print(); Prints out the current state of the grid. (You can implement your own version of this function using function get , btw.)

TASK:

Write a better solve() function. The provided implementation is very crude, doing brute-force search for every question-marked letter without making any use of the words list. Fix that. You can edit anything you want in solve.cpp file as long as it still contains solve(Puzzle&) function.

The Score measuring the quality of your solution is the correctness ratio: (Number of Correct Guesses) / (Total Number of Guesses). The provided solution is worse than 10% in the example above, and it becomes even worse for bigger crosswords. If you get your average score above 75%, it will be a decent improvement. Getting it above 90% would be even better.

Hint

To effectively guess words, you will need to identify word locations in the crossword grid. We will call these locations patterns, because some (or all) of the letters in such patterns may be still hidden behind question marks.

The following function is searching for such a horizontal pattern in the crossword grid, starting at the square (r, c): string horizontalPattern(Puzzle &puzzle, int r, int c) { string s = ""; // if character to the left is blank, it could be a start of a pattern if (puzzle.get(r, c-1) == ' ') { // scan all characters until we find a blank square while(puzzle.get(r, c) != ' ') { s += puzzle.get(r, c); c = c + 1; } }// return the pattern (or empty string if there is no pattern starting at (r,c)) return s; } If a pattern exists, it will return it, otherwise it returns an empty string. Please feel free to use this function, and implement its variant for finding vertical patterns.

I upload the files in here: https://www.dropbox.com/s/c3n7h4k2xg09643/project2-package.zip?dl=0

Thank you.