Goal: I will practice using vectors and Git. I will also learn to follow good programming style.

Instructions: Create a new project: student/04/carpet.

Your task is to implement a mystery carpet, which applies pattern matching as shown in the figure below.

The program receives a carpet and a pattern as its input. As its output it tells, in which positions the pattern was found and the number of pattern instances. However, the program only has a textual user interface (not a graphical one), so the input and output uses only ASCII characters.

Important

Before starting to write code, read carefully the whole assignment. Note especially the points Implementing the program in parts (required commits), Special requirements, and Evaluation. Note also that to get any points, your project must pass all automated tests.

Note

This project can be done either in pairs or independently. If you do the project in pairs, choose Form a group from the menu on the left to register your group. In addition, the submission box at the very end of the current page shows two choices: Submit alone / Submit with. You should be careful when selecting the choice, because you cannot change it afterwards. Enter only the address of the Git repository owned by either of you (not both) in the submit box. The code files must contain (in comments) the personal data of both of you.

You can look for a group via Kooditorios Discord link (see Timetable & links).

Header comment and feedback language

The Evaluation point in this section requires a header comment in the code file. It means something like below:

/* Mystery carpet * * Desc: * This program implements a mystery carpet applying pattern matching. * The carpet consists of squares of different colors, which also holds * true for the pattern, but the size of the pattern is always 2 x 2, i.e. * it has four colored squares. The program searches for pattern * occurrences from the carpet. * At first, the program asks for the size of the carpet (width and heigth). * The user is also asked for if the carpet (grid) will be filled with * randomly drawn colors, or with user-given ones. In the first option, * a seed value for the random number generator will be asked next. * In the latter option, the user is asked to input as many colors as the * there are squares in the carpet, whereupon the user lists the first * letters of the colors as one long string. * On each round, the user is asked for a pattern to be searched for * (a string consisting of four letters/colors). The program prints, how * many occurrences was found and from which coordinates they were found. * The program checks if the user-given colors are among accepted ones. * The program terminates when the user gives a quitting command ('q' or 'Q'). * * Program author ( Fill with your own info ) * Name: Teemu Teekkari * Student number: 123456 * UserID: teekkart ( Necessary due to gitlab folder naming. ) * E-Mail: teemu.teekkari@tuni.fi * * Notes about the program and it's implementation (if any): * * */ 

Add above kind of comment at the very beginning of the file main.cpp. This assignment has only one code file. If there are more of them (as in the later projects), information must be in all of them. The description part is not necessary to repeat in every file, it is enough to put it in the main program file.

You can write the above comment also in Finnish (see Finnish assignment), but write all comments in the same language. Remember to replace parts of the above text with your personal data.

If you are working in pairs, add personal data of both of you.

The feedback language will be chosen in the submission box (at the very end of this page). By default, the feedback language is Finnish, but you can change it, if you want to have the feedback, given by an assistant, in English. We will use the language you have given in the submission box of the final submission.

Mystery carpet vs waterdrop game

The materials of this round include a description of waterdrop game that uses a vector, the elements of which are vectors. Further the elements of the inner vector are squares (Square objects). This project has a similar structure in a sense that a carpet (as well as a pattern) consists of color squares. This kind of structure can be described as a vector, the elements of which are vectors. However, the elements of the inner vector are color codes (enum type, see Assignment), so they are simpler than the squares in the waterdrop game, and thus, there is no need to describe them as a class.

In the waterdrop game, each square has a pointer to the game board, since each square must know its adjacent squares. In the project, this is not needed, nor pointers at all.

Assignment

Your task is to implement a mystery carpet applying pattern matching in a way described below.

The program uses five colors: R (red), G (green), B (blue), Y (yellow), and W (white). The user can give a pattern consisting of four colors e.g. in a form as BRYG, or bryg, or Bryg. (So upper and lower case letters can be used equally and mixed.) The colors of the carpet can be given in the same way, but as a longer string.

For declaring colors, you must use an enum type, for example, like this:

enum Color {RED, GREEN, BLUE, YELLOW, WHITE, NUMBER_OF_COLORS}; 

The program starts by asking for the width and height of the carpet:

Enter carpet's width and height: 10 5 

It should be asked by giving two numbers separated by an empty space. Width (the input number given first) is a horizontal measurement, and height (the latter one) is a vertical one, which can be seen unlogical in the case of a carpet. (To save space, it is better to draw a carpet horizontally, and typically a horizontal measurement is called width, and a vertical one is called height. Moreover, instead of a carpet, we could use a more general term as grid or rectangle.) Anyway, the carpet in the figure shown at the beginning has 7 as its width and 3 as its height.

Since the size of the pattern is 2 x 2, the size of the carpet cannot be smaller than that. If one of the given numbers is smaller than two, the program prints the following error message and terminates with the return value EXIT_FAILURE:

Enter carpet's width and height: 4 1 Error: Carpet cannot be smaller than pattern. 

If the user gave an acceptable size for the carpet, the program continues by asking a starting way (drawing color squares randomly or reading them from the user input):

Enter carpet's width and height: 10 5 Select start (R for random, I for input): x Select start (R for random, I for input): yyy Select start (R for random, I for input): r Enter a seed value: 1 R R Y B B G R Y Y W G B W R R B Y R G R B Y B W W B R Y B Y W Y G R Y G Y Y W G G W Y Y Y R Y W G B Enter 4 colors, or q to quit: 

The question is repeated until the user gives either string R or I. Note that both upper-case and lower-case letters are accepted equally.

If the user selects a way, where the carpet is created with randomly drawn colors, the program asks next a seed value for the random number generator. After giving a seed value the program prints the carpet of desired size, filled with random colors in a way shown above. (Each color, also the first in line, is preceded by an empty space.)

If the user choses a non-random creation way, the program asks for the colors of the carpet and checks if the correct amount of acceptable colors was given:

Enter carpet's width and height: 10 5 Select start (R for random, I for input): i Input: GGGYGGYYRWGBWWRRRRYBBGBWRGBYBYWBWWRRBWWRWYYWWGBRB Error: Wrong amount of colors. Select start (R for random, I for input): i Input: GGGYGGYYRWGBWWRRRRYBBGBWRGBYBYWBWWRRBWWRWYYWWGBRBX Error: Unknown color. Select start (R for random, I for input): i Input: XYZ Error: Wrong amount of colors. Select start (R for random, I for input): i Input: GGGYGGYYRWGBWWRRRRYBBGBWRGBYBYWBWWRRBWWRWYYWWGBRBY G G G Y G G Y Y R W G B W W R R R R Y B B G B W R G B Y B Y W B W W R R B W W R W Y Y W W G B R B Y Enter 4 colors, or q to quit: 

If the user gave an incorrect number of colors, the program prints the error message shown above: Error: Wrong amount of colors. If one of the colors the user gave is not a code for an acceptable color, the program prints the error message shown above: Error: Unknown color.

If the user input is incorrect in two ways: it has an incorrect number of colors and it contains an unknown color, the program informs only of the first mentioned error, as can be seen in the example above (input XYZ).

The example above shows also that after an erroneuos input, the user has the possibility to choose the starting way again.

After giving an acceptable input, the program prints the carpet in the same way as in the starting way with random colors: as many colors are taken from the input as is the width of the carpet, and these colors are printed in the first line, then the same amount of colors are taken and printed in the second line and so on.

Now, the program proceeding does not depend on the creation way any more.

Next the program asks for a pattern consisting of four colors. If the input is something else than a color series consisting of four acceptable colors, the program prints the same error messages as before:

Enter 4 colors, or q to quit: GGG Error: Wrong amount of colors. Enter 4 colors, or q to quit: GGGYY Error: Wrong amount of colors. Enter 4 colors, or q to quit: GGGX Error: Unknown color. Enter 4 colors, or q to quit: XYZ Error: Wrong amount of colors. Enter 4 colors, or q to quit: 

Besides the acceptable color series, the user can always give the quitting command "Q" or "q", which makes the program terminate without any prints with the return value EXIT_SUCCESS.

Let us next consider the actual going of the game:

Enter carpet's width and height: 10 5 Select start (R for random, I for input): i Input: RRYBBGRYYWWYWRRRYRGRWYBWWWRYBYWYGRYGYYWGGWYYYRYWGB R R Y B B G R Y Y W W Y W R R R Y R G R W Y B W W W R Y B Y W Y G R Y G Y Y W G G W Y Y Y R Y W G B Enter 4 colors, or q to quit: wrwb = Matches found: 0 Enter 4 colors, or q to quit: rywr - Found at (6, 2) = Matches found: 1 Enter 4 colors, or q to quit: ryyy - Found at (7, 3) - Found at (4, 4) = Matches found: 2 Enter 4 colors, or q to quit: wywy - Found at (1, 2) - Found at (1, 3) = Matches found: 2 Enter 4 colors, or q to quit: rrww - Found at (4, 2) - Found at (5, 2) = Matches found: 2 Enter 4 colors, or q to quit: 

The program prints first the coordinates, where the pattern was found (the left upper corner of the pattern), and after that the amount of occurrences. Occurrences can be overlapping, as wywy and rrww above.

When searching for a pattern, the carpet is gone through line by line, whereupon the program prints first the occurrence, the line number or y-coordinate of which is the smallest (see the input ryyy). If there are several occurrences in the same line (the same y-coordinate), the program program prints first the occurrence, the column number or x-coordinate of which is the smallest (see the input rrww).

The shape of the pattern is 2 x 2, but a pattern is given by listing four consecutive colors. For example, the input BRYG means the pattern:

B R Y G 

i.e. the first two characters are the colors of the upper line, and the latter two characters are the colors of the lower line of the pattern. The same thing is shown in the figure below, where the pattern can be seen on the left, and the corresponding input can be seen on the right.

Implementing the program in parts

Use version control in your project such that there can be found at least five commits as follows:

The program asks for initial data from the user and fills the carpet according to the users choice (R/I).

The program prints the carpet.

The user can give patterns to be searched for, and after that the program tells their locations and amount.

In addition, you must have at least two more commits (before, between, or after the aforementioned ones).

You must also mention the steps described above clearly enough in the commit messages to enable course assistant to find them easily when evaluating your project. However, you can section above commits into several ones.

Tips for completing the assignment

It is enough to use vector container from STL, but also other containers from STL are allowed.

From the waterdrop game, you can learn how define a vector, the elements of which are vectors (square., line 12). Moreover, you can look at how to fill a game board with random elements (main.cpp, function initBoard). Otherwise, the example is not so important.

Special requirements

You must an enum type for declaring colors, for example, a type like this:

enum Color {RED, GREEN, BLUE, YELLOW, WHITE, NUMBER_OF_COLORS}; 

The above type can be used as an element of a vector.