-
Notifications
You must be signed in to change notification settings - Fork 81
[EN] 4. Package with an output verificator
There are many problems which output can be not deterministic. By now, the methods discussed in this guide do not allow you to deal with such situations well. Example: Write at most 10 numbers, the sum of which is n. It is not possible to verify the answer by comparing with the model answer because there are many correct solutions to the given problem. A verification program will help us with this problem. We can write it and attach to the package.
This time we'll prepare a package for the problem Puzzle (short name puz). The user will be given a single natural number n denoting length of the rectangle. The rectangle in this task will be 3 x n and user will want to cover it entirely with small rectangles 1 x 2 by placing them vertically or horizontally. Small rectangles cannot overlap or extend beyond the large rectangle. If the field cannot be covered, user should write the sentence Can't do that.
If the number n is not divisible by 2, then the task cannot be solved. This is due to the different parity of the rectangle field and the single block (puzzle). In that case we will print the phrase Can't do that. If n is an even number, we can definitely cover the field using exactly 3n / 2 block. One of the simplest covers is covering the entire rectangle by placing block horizontally next to each other, going from left to right. However, it can be seen that this is not the only possible solution.
To deal with this problem we will write a program puzchk.cpp. You can use it to tell the system which answers should be considered correct and which should be incorrect, and how many points to award.
Input processing can be very tedious. If we want to verify the file correctly, we should not use standard reading methods (scanf, cin, input). In order to facilitate work (not forgetting about security), a dedicated library was created. You can find it here. It provides many functions for reading the input. Of course, you can use any other method, but you must remember that participants can try different methods of deceiving your checker! In the rest of the guide we will use the oi.h library, and the verification program puzchk.cpp will be written in C++. First, we must discuss other tools to facilitate the work on the package.
A convenient tool for local work on the package is the make program. It works under Linux, which we recommend to work on packages that are more difficult than those in the first two guides. Make is a system shell program that aims to automate the process of compiling programs, which consist of many dependent files. The program reads the rules saved in the Makefile and determines which files require compilation. There are three Makefile files in the standard package. The first, general purpose Makefile, The second, used to compile LaTeX files doc/Makefile, and the third in prog/Makefile used for compiling solutions. Exact specification is not required to use the facilities provided by the make program, so we won't discuss it in detail. In the list below you can find few common commands:
-
make ingen– generate input files (requires puzingen) -
make inwer– check the correctness of the input files (requires puzinwer) -
make outgen– run the model solution (puz) on all tests from the in directory and save the results to the out directory -
make run– run the main model solution and display the result on the screen -
make run_3– run the third model solution and display the result on the screen (in this case puz3.py) -
make run_b1– run the first incorrect solution (file puzb1) -
make run_s1– run the first slow solution (file puzs1) -
make oirun– run the benchmark solution, but will use sio2jail to estimate execution time (requires path to oiejq.sh in makefile.in) -
make report > report.html– generate an HTML report by running all solutions and save the result to the report.html file -
make oireport > oireport.html– same as above, but sio2jail will be used to run
One way to automate the task description creation process is to use TeX. It is widely used in the creation of scientific texts, because it allows you to build complex expressions, including complicated mathematical formulas. It also has many ready-made packages that solve standard problems associated with creating publications, e.g. numbering of equations, automatic creation of tables, lists, abbreviations, inserting illustrations. We will use a template to prepare the task sinol.cls. We will not explain what is happening in it, we will only explain how to use it. The easiest way to explain how it works, and how useful it is, is by showing an example. The TeX file from which we generated the task description is located here. We can set different values for the title, id, date, competition name and many more. By default, a main section is created in which the problem is described, followed by an input section, which is the exact input specification, then the output section that contains the output specifications. Then there should be examples and a section with grading, specifying sub-tasks. The finished file should be named puzzad.tex. If we want to create files in several language versions (e.g. in English), we will create a second file puzzad-en.tex. We should begin our document with this line.
\documentclass[en]{spiral}To compile them, use the make command in the puz/doc directory. You can also use the make clean command to delete unnecessary files created during compilation.
Finally we can move on to the program that verifies the output. Program is getting three arguments:
- argv[1] – input file
- argv[2] – user's output file
- argv[3] – model output file
Firstly we will be reading the input file, to find out the test case it covers. We will do so using fstream library. Note, that we don't have to do security checks, we are the creators of those files, so we can be sure of their formats.
int n;
{
std::ifstream input(argv[1]);
input >> n;
}That way we can read number n, which denotes the length of the side. The task is simple enough to find out the solution at this stage, which will be easier than reading additional data from the input file and then calculating the correct answer. In more complex tasks we would want to get measurable information about the correct solution from our model solution. In this case, it might feel enforced, but we will use the first line of the model output file (for educational reasons) to determine, whether solving the riddle is possible.
int modelK;
bool cantDoIt = false;
{
std::ifstream output(argv[3]);
char first;
output >> first;
if (first == 'C') {
cantDoIt = true;
} else {
output.putback(first);
output >> modelK;
}
}We check the first character from our model output, so we can find out if the riddle has the solution. Now we get to the hardest part - reading the user's output file. Firstly, we create a scanner from oi.h library.
oi::Scanner scanner(argv[2], endf, oi::PL);After that, we use previously defined variable canDoIt, to see if we should expect a word or a number. If variable equals true, we should get one line Can't do that. Because of that, we will read one line (which means - all of the characters until white delimiting character) with the following command.
int readLen = scanner.readLine(result, resultLen);Now readLen variable stores number of chars that have been read into the result. It is important because although we gave an upper limit for line length (resultLen), the user still could not write anything to output. We should remember, we should not punish the user for leaving whitespace characters at the end of the line (and file). We will load all of the whitespace characters until the end of the file.
scanner.skipWhitespaces();Now, if everything went according to the plan, we should encounter the end of file character.
if (resultLen == readLen) {
scanner.readEof();
}We can now see, how useful is saving the number of characters read to variable readLen. If the maximum length has been read, we still haven't reached the end of the file. However, if the value is smaller, it means that we are at the end of the file or line. Now we can check, if the line is valid, using the strcmp function known from C.
if (strcmp(cantStr, result) == 0) {
std::cout << "OK" << std::endl;
} else {
std::cout << "WRONG" << std::endl;
std::cout << cantStr << " expected!" << std::endl;
}If the answer is the same as our model answer, we will write one line to standard output, containing OK. This will inform SIO2 that test has been passed, and we can award it with a positive number of points. If we want to attach any comment to the solution, that will be visible to the participant, we should do so in the second line. The third line is used to assign points. Leaving this line blank will result with the participant receiving the maximum score available.
If the lines are not identical, we will write WRONG in the first line, and a custom comment in the next. Remember that regardless of the result, ending the program with a code other than 0 will result with an error on SIO2. We want to avoid this result at all costs, because in the same way the system communicates all internal irregularities. If cantDoIt is set to false, then the first line should be a number.
int k = scanner.readInt();
if (k != modelK) {
std::cout << "WRONG" << std::endl;
std::cout << "Wrong number of puzzles!" << std::endl;
exit(0);
}
scanner.skipWhitespacesUntilEOLN();
scanner.readEoln();The scheme is very similar as before. We read one integer. If it does not match our reference number, we will stop checking. Now we read 3 user numbers. This is the most risky part of our program. We read three numbers and then mark in the table which squares have been covered. If the user gives a number outside the range of our array, and we do not check it, we can start writing in memory we don't have access to. So, in a loop, we read numbers like this.
int x = scanner.readInt(0, n - 1);
scanner.skipWhitespacesUntilEOLN();
int y = scanner.readInt(0, 2);
scanner.skipWhitespacesUntilEOLN();
int z = scanner.readInt(0, 1);
if (i < k - 1) {
scanner.skipWhitespacesUntilEOLN();
scanner.readEoln();
} else {
scanner.skipWhitespaces();
scanner.readEof();
}It is worth paying attention to the above condition. If we are not on the last line, we should skip the whitespace at the end of the line and load the newline character. However, if we are on the last line then we should skip any whitespace and then load the end of the file. This will allow us to separate solutions that leave some sort of rubbish right after the correct output. Now we can check if any block is coming out of the board.
bool checkXY = (grid[x][y] == 0);
if (z == 0) {
if (x == n - 1) {
puzzleOutOfBoard();
}
if (!checkXY || grid[x + 1][y] != 0) {
puzzlesIntesect();
}
} else {
if (y == 2) {
puzzleOutOfBoard();
}
if (!checkXY || grid[x][y + 1] != 0) {
puzzlesIntesect();
}
}If everything works and our program didn't end in a result of calling any of the above functions, all that remains is checking, if all of the fields have been covered. If k is the same as the number in the correct output, we know that we will give at least half of the points. We then write OK in the first line. If we want to give the test less than 100% points, in the third line of the standard output we should have an integer, which will be the percentage of the points assigned. If any of the fields will be left uncovered, we will write an appropriate message and give the user only 50 points. The finished program can be found in the file puz/prog/puzchk.cpp. We can run the make run command and see if the model solution is interpreted correctly by the checker. The good habit is to write many model solutions and many bugged ones, that write output in a different form. It will allow us to find out, whether the checker recognizes output correctly.