11. Checker

Polygon 2015. 8. 17. 16:19

Checker는 어떤 주어진 test에 대해(input), 제출한 답안이 출력한 답과 모범 답안이 출력한 답을 비교해서, verdict를 내는 프로그램입니다. 기본적으로 input data와 output data(모범 답안이든, 타인의 답안이든)을 제공받습니다. 이는 Validator에서 inf라는 Instream 타입 전역 변수를 이용하여 readInt 같은 함수로 입력을 받았던 것처럼, 제출한 답안(즉 participant's solution)이 낸 답은 ouf을 통해서, 모범 답안(즉 jury's solution)이 낸 답은 ans를 통해서 받을 수 있습니다.

Checker는 기본적으로 inf를 통해서 답의 양식이 어떻게 될 것이다라는 것을 파악한 다음에, 이를 토대로 ouf와 ans에서 값을 불러내 비교하는 것이 그 역할이지만, 이 때 readSpace(), readEoln() 등의 함수는 일반적으로 사용하지 않습니다.


다음 함수들은 Checker에서 유용하게 사용할 수 있습니다.

  • void registerTestlibCmd(int argc, char* argv[]):
    이 프로그램이 Checker라는 것을 알리는 함수입니다. main 함수의 인자인 argc,argv를 그대로 인수로 전달해야 합니다.

  • void quit(TResult verdict, string message): void quit(TResult verdict, const char* message): void quitf(TResult verdict, const char* message, ...):
    Checker가 내린 결론을 verdict에, 관련된 멘트(ex. ok 4 numbers 1 4 2 3)를 message의 형태로 적어서 알린 다음, 프로그램을 종료합니다.

  • void quitif(bool condition, TResult verdict, const char* message, ...):
    bool형 조건인 condition을 만족할 경우, quitf(verdict, message......)를 호출합니다.

  • void setName(const char* format, ...): Checker에 내부적으로 이름을 주는 함수입니다.
  • 이 외에도 디버깅 용으로 ensuref를 사용할 수 있습니다.
저 TResult verdict로 나타나 있는 인자에는 다음과 같은 값을 집어넣을 수 있습니다.
  • _ok
    Verdict는 OK. 즉 맞았다는 뜻입니다. 문제에 따라서는 최적의 해이다라는 뜻일 수도 있습니다(답이 하나가 아닌 Special Judge인 경우).

  • _wa
    Verdict는 Wrong answer. 답이 틀렸거나, 최적해가 아니라는 뜻입니다.

  • _pe
    Verdict는 Presentation error. 직접적으로 사용하기 보다는, testlib.h에서 내부적으로 이 매크로를 많이 사용합니다. 예를 들면 readInt()를 했는데 읽은 값이 숫자가 아닐 때 이는 _pe로 처리되지만 실제 verdict는 wrong answer로 대체됩니다.

  • _pc(score)
    Verdict는 Partially correct. score에 점수를 넣어 사용합니다. 주로 Sub-task를 구현한 문제일 때 사용하면 좋겠으나 흔하진 않습니다. Codeforces Rounds부터 sub-task를 사용하지 않으니 말입니다.

  • _fail
    Verdict는 Fail. 역시 testlib.h에서 프로그램에 내부적으로 문제가 있을 때 많이 사용하는 매크로이지만(ex. readInt(1,5)를 했는데 return값이 0일 때), 때로는 최적해를 구하는 문제에서 모범 답안보다 더 훌륭한 답을 구했을 때 사용되기도 합니다. 이런 경우에 Wrong answer를 줄 수는 없으니까요. 실제로 이런 상황이 일어나면 문제 출제자가 Main solution을 재검할 필요가 있습니다.

이것과 Validator에서 사용한 함수들을 그대로 이용하면 Checker를 작성할 수 있습니다. 이번에는 testlib.h에 있는 checker 폴더의 ncmp.cpp 파일을 예로 들겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include "testlib.h"
#include <sstream>
 
using namespace std;
 
int main(int argc, char * argv[])
{
    setName("compare ordered sequences of signed int%ld numbers"* sizeof(long long));
 
    registerTestlibCmd(argc, argv);
 
    int n = 0;
    string firstElems;
 
    while (!ans.seekEof() && !ouf.seekEof())
    {
        n++;
        long long j = ans.readLong();
        long long p = ouf.readLong();
        if (j != p)
            quitf(_wa, "%d%s numbers differ - expected: '%s', found: '%s'", n, englishEnding(n).c_str(), vtos(j).c_str(), vtos(p).c_str());
        else
            if (n <= 5)
            {
                if (firstElems.length() > 0)
                    firstElems += " ";
                firstElems += vtos(j);
            }
    }
 
    int extraInAnsCount = 0;
 
    while (!ans.seekEof())
    {
        ans.readLong();
        extraInAnsCount++;
    }
    
    int extraInOufCount = 0;
 
    while (!ouf.seekEof())
    {
        ouf.readLong();
        extraInOufCount++;
    }
 
    if (extraInAnsCount > 0)
        quitf(_wa, "Answer contains longer sequence [length = %d], but output contains %d elements", n + extraInAnsCount, n);
    
    if (extraInOufCount > 0)
        quitf(_wa, "Output contains longer sequence [length = %d], but answer contains %d elements", n + extraInOufCount, n);
    
    if (n <= 5)
        quitf(_ok, "%d number(s): \"%s\"", n, compress(firstElems).c_str());
    else
        quitf(_ok, "%d numbers", n);
}
 
cs


파일을 분석하자면 다음과 같습니다.


  • setName으로 Checker의 이름을 내부적으로 설정합니다.

  • registerTestlibCmd로 이 프로그램이 Checker라는 것을 알립니다.

  • while (!ans.seekEof() && !ouf.seekEof())로, ans(jury's solution) 또는 ouf(participant's solution)가 끝날 때까지 읽어들입니다. 이상적인 결과는 둘 다 동시에 EOF를 만나는 경우이겠지만, 그러지 않는 코드를 제출하는 사람들이 존재합니다(괜히 pretest 1에서 틀리는 사람들이 있는 게 아닙니다).

  • 참고로 ans에서 나오는 답과 ouf에서 나오는 답을 각각 vector에 집어넣은 다음에 하나씩 비교해나가는 방법도 있습니다. checker 폴더의 uncmp.cpp 파일을 참조하세요.

  • n은 inf로 직접 코드에서 받을 수도 있으나, 본 코드에서처럼 while문 안에서 내부적으로 계산하는 수도 있습니다. 후자의 경우 본 케이스가 몇 번째인지 알 수 있습니다. 물론 inf에서 받아서 for문을 돌려도 마찬가지입니다.

  • j와 p를 각각 ans.readLong(), ouf.readLong();으로 받았습니다. 이 때 j와 p가 같지 않을 때 quitf를 사용하는데, 이때 사용하는 함수들을 분석하면 다음과 같습니다.

    • englishEnding(n). 1st, 2nd, 3rd, 4th......등에 오는 2글자짜리 영어 서수를 std::string으로 return하는 함수입니다. testlib.h에 전역으로 정의되어 있는 함수입니다.

    • c_str(). <string>에 선언되어 있습니다. 역할은 해당 std::string에 대해 string이 저장하고 있는 값을 가리키는 char* 포인터를 return합니다. 이 경우 %s로 바로 출력할 수 있습니다(이 경우는 quitf를 통한 stderr로 말입니다).

    • vtos(n). n를 std::string으로 바꾸어 return합니다. n의 타입은 일반적인 연산자 <<(std::ostream::operator<<)로 받아들일 수 있는 타입에 한합니다.

  • 이런식으로 한 쪽이 EOF를 맞이한 경우, 나머지도 EOF를 만날 때까지 계속 빼냅니다. 이 때 extraInAnsCount, extraInOufCount로 추가적인 원소의 개수를 계산합니다.

  • extraInAnsCount이나 extraInOufCount이 양수일 경우 어느 쪽이 길이가 얼마이며 더 길다는 것을 quitf를 통해 알립니다.

  • 그렇지 않을 경우, 올바른 답을 출력했다는 뜻이므로, quitf(_ok, "%d numbers", n);를 부릅니다. 다만 n이 5 이하일 때는 모든 element를 firstElems라는 std::string에 담아 보관하고 있다가 같이 출력합니다. 이 때 사용되는 compress 함수의 역할은 다음과 같습니다.

    • compress(str): testlib.h에 전역으로 선언되어있는 함수입니다. 역할은 str의 길이가 64 이하일 경우 그대로 str를 return하고, 그보다 길 경우 처음 30글자와 마지막 31글자만 남기고 사이에 "..."를 삽입하여 return합니다. 함수명대로 압축하는 함수입니다.

간단해 보이지만, 실제로는 Checker 역시 상당히 조심스럽게 만들어야 합니다. 왜냐하면 그 어떤 output(쓰레기값이 나오는 코드라든지, 일부러 이상한 값을 출력하는 코드라든지)에도 제대로 작동해야 하기 때문입니다. 그래서 일반적으로는 값을 읽을 때도 주어진 범위가 있다면 그에 따른 범위를 주어야 합니다.


또 '읽어내는 역할'을 수행하는 readAns 함수를 만드는 것 역시 추천합니다. 그 이유는 간단한 output이라면 모르겠지만, output이 복잡하면 ans 따로, ouf 따로 출력하는 것이 비효율적이기 때문입니다. 더 자세한 것은 이 링크를 참조하시기 바랍니다.


이렇게 만든 Checker를 Polygon에 올리는 방법은 Validator와 흡사합니다. 한번 볼까요?



Select하는 부분은 Validator와 동일하므로 넘어가겠습니다.


Checker test를 만드는 방법을 설명하자면, 기본적으로 Add test를 눌러서 문제를 만드는 창으로 이동할 수 있습니다.



각 항목을 설명하자면 다음과 같습니다.

  • Checker test #: Checker test의 번호입니다. 항상 그렇듯이 번호는 1부터 1000까지의 자연수만 가능합니다.

  • Input: 한 test의 input입니다. 물론 Validator가 통과시킬 수 있는 test를 작성해야겠지요.

  • Output: 이 output은 밑에 적혀있는 것처럼, 'participant'의 답안입니다.

  • Answer: 이 항목은 밑의 Generate Answer를 누르면, Main solution이 출력한 답을 창에 생성해줍니다. 물론 직접 입력할 수도 있습니다.

  • Verdict: 채점 결과입니다. 4가지 결과 중 하나를 선택할 수 있으며, 이는 다음과 같습니다.

    • OK: Output과 Answer가 같거나, Output이 여러 최적해 중 하나일 경우 해당합니다. Correct인 셈이죠.

    • WRONG_ANSWER: Output과 Answer가 다르거나, Output이 최적해가 아닌 경우를 의미합니다.

    • PRESENTATION_ERROR: 여러 번 강조하지만, 이 결과는 (일단 Codeforces에서는) 일반적으로 사용하지 않습니다. whitespace 관련된 규격을 맞추고 싶으시다면 뭐 어쩔 수 없지만 말입니다. 다만 testlib.h 함수를 호출했는데 값이 범위나 형식이 맞지 않으면 이 verdict가 내부적으로 호출되는 경우도 있습니다.

    • FAILED: 이 경우 프로그램 내부적으로 무언가 틀린 경우를 의미하는데, 위에서 TResult verdict 관련해서 설명했던 경우 중 'Output이 Answer보다 더 최적인 경우'가 해당됩니다. 물론 이런 경우가 있으면 해당 부분에 대한 수정이 필요합니다.
이 경우 Create를 누르면 Validator처럼 다시 원래 탭으로 이동하는 것이 아니라, 다음 test를 만드는 창으로 저절로 이동하게 됩니다.

만들 수 있는 test의 종류를 몇 개 추천하자면 다음과 같습니다.
  • Correct한 답안을 판별하는 경우. 이 경우는 특히 답안이 여러 개가 나올 수 있는 Special Judge의 경우 더욱 더 부각됩니다.

  • Wrong answer를 걸러내는 경우. 그 어떠한 output이 들어와도 Checker는 Runtime Error 등의 오류를 내면 안 됩니다.

  • Checker 등에 있는 ensuref, quitf 등의 작동. 형식이 틀렸으면 왜 틀렸는지(ex. 같은 수가 두 번 나온다든지, 그래프가 트리가 아니라든지)
Checker는 결국 직접적으로 participant와 소통하는 프로그램이라는 사실을 명심하시길 바랍니다.


'Polygon' 카테고리의 다른 글

13. Invocation  (0) 2015.09.18
12. Stress  (0) 2015.08.18
10. Solution Files  (0) 2015.08.12
9. Validator  (1) 2015.08.11
8. Tests (2 - Generator with Freemarker)  (0) 2015.08.09
Posted by Evenharder
,