9. Validator

Validator는 지금까지 고생하면서 만든 input 파일이 올바른 양식(이는 whitespace도 포함합니다)을 지니고 있는지, 또 문제 input 조건을 어기는 test가 invalid한지 등을 판별하는 프로그램입니다. 이런 프로그램이 따로 있는 것은 기본적으로는 test가 말 그대로 valid한지 판별하는 목적도 있겠지만, Codeforces의 Hack 등을 걸러내는 것에도 목적이 있습니다.

Validator 역시 testlib.h를 사용하여 만드는 것이 강력하게 권장됩니다. 우선 Polygon의 Validator 탭에 들어가 봅시다.

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

• Select: Files 탭에서 'Source Files'에 업로드된 파일들을 선택할 수 있습니다. 기본적으로는 저렇게 'No validator'라고 나와 있습니다.
  
  
• Or upload: 아니면 사용자의 컴퓨터에서 업로드할 수 있습니다. 확인해보지는 않았지만, 이 떄 올리는 파일의 이름 역시 4. Statement의 그림 파일 올릴 때처럼 다음 조건을 만족해야 할 겁니다.
  
  

• 알파벳 소문자 및 대문자

• 숫자

• .(Period, 0x2E)

• _(Underscore, 0x5F)

• -(Hyphen, 0x2D)

• Language: validator의 언어입니다. 일반적으로 Autodetect(자동 감지)를 사용해도 전혀 무리가 없으며, 아니면 testlib.h 자체의 특성상 대부분 gcc.c++로 할 테지만, 그 외에도 다양한 언어로 짤 수는 있습니다. 하지만 다른 언어로 옮기면서 예상치 못한 버그가 나타날 수도 있으니, 그냥 c++로 짜는 것을 추천드립니다.

아무튼 validator를 올리는 과정 자체는 간단합니다. 이제 validator를 만드는 과정이 남아 있을 뿐입니다. 그다지 어렵지는 않으므로, 걱정하진 마세요.

validator를 만드면서 꼭 필요할 함수들을 소개하겠습니다. registerValidation 함수만 제외하면, inf.xxx의 형태로 사용이 가능합니다. 이 inf는 testlib.h 에 선언되있는 class 중 하나인 InStream이 전역 변수의 형태로 선언되어 있는 것이며, generator가 생성한 값이 여기에 저장됩니다.

• void registerValidation(int argc, char* argv[]):
  validator 선두에 무조건적으로 호출해야 하는 함수입니다. 이 함수의 역할은 argv로 받은 인자들이 올바른지 판별하는 역할을 합니다. 참고로 validator 실행파일에 주어지는 인자는 Polygon이 알아서 잘 집어넣어 줍니다.
  
  
• void skipBlanks():
  whitespace가 아닌 문자를 만날 때까지, 아니면 EoF(End of File, 파일의 끝)를 만날 때까지 포인터를 이동합니다. 이 포인터는 그냥 input을 저장하는 배열값을 가리키는 포인터라고 생각하면 되겠습니다.
  
  
• char readChar():
  문자를 하나 읽으면서 포인터를 다음 문자로 넘깁니다. return값은 읽은 문자값입니다.
  
  
• char readChar(char c):
  문자를 하나 읽으면서, 포인터를 다음 문자로 넘깁니다. return값은 읽은 문자값입니다. readchar()과의 차이점은 읽은 문자가 c와 같지 않을 경우 'Unexpected character 'x', but 'y' expected'의 형식으로 stderr로 출력합니다.
  
  
• char readSpace():
  readChar(' ')과 동일합니다. ' '(SPACE)를 읽으며 포인터를 다음 문자로 넘기되, SPACE가 아니면 stderr로 해당 사실을 출력합니다.
  
  
• void unreadChar(char c):
  포인터를 한 칸 앞으로 옮기면서, input 배열에(실제로는 std::string입니다만)그 자리에 c를 집어넣습니다. 당연한 소리지만, 포인터가 맨 앞에 있는데 이 함수를 호출하면 에러가 납니다.
  
  
• std::string readToken(), std::string readWord():
  한 단어, 즉 whitespace 또는 EoF를 만나기 전까지의 모든 글자들을 std::string 형식으로 읽으며, 이를 return합니다. 이 경우 포인터는 그 whitespace 또는 EoF를 가리키게 됩니다.
  
  
• std::string readToken(const std::string& ptrn, const std::string& variableName = ""): 구조적으로는 위의 함수와 똑같지만, 2가지 차이점이 있습니다. 첫째는 읽은 문자열이 ptrn로 주어진 Regex 형태와 일치해야 하며, 둘째로는 이 문자열의 '이름'을 variableName을 통해 명명할 수 있다는 것입니다. '이름'을 붙이는 이유는, Regex 형태와 일치하지 않을 때 다음과 같이 stderr로 출력되기 때문입니다. 예를 들면 'Token parameter [name=str] equals to "abc", doesn't correspond to pattern "[ab]+"'의 형식으로 말이죠. 이 경우 입력받은 문자열은 abc, ptrn에는 [ab]+, variableName에는 str이 들어가 있는 것입니다. 이렇게 하면 어떤 변수가 조건을 부합하지 않는지 알 수 있습니다. readWord도 똑같이 오버로딩되어 있습니다.
  
  
• long long readLong():
  long long 타입의 정수를 하나 읽습니다. 작동 원리는 readWord()를 부른 다음에 읽은 string이 long long 타입의 정수인지 판별하고(판별 과정은 생략하겠습니다), 그 값을 long long 으로 return하는 형식입니다. 이하 다른 readxxx함수도 마찬가지 방식으로 작동합니다.
  
  
• int readInteger(), int readInt():
  int 타입의 정수를 하나 읽습니다.
  
  
• double readReal(), double readDouble():
  double 타입의 실수를 하나 읽습니다.
  
  
• long long readLong(long long minv, long long maxv, const std::string& variableName = ""): 구조적으로는 readLong()과 동일하지만, 이 경우 읽은 값이 minv 이상 maxv 이하여야 합니다. 그렇지 않을 경우 variableName에 들어가는 변수 명을 이용하여 'Integer parameter [name=n] equals to 132039, violates the range [1,100000]' 등으로 에러 메시지를 냅니다. 사실 이쪽을 사용하는 것이 권장됩니다. 
  
  
• int readInt(int minv, int maxv, const std::string& variableName = ""):
  구조적으로는 readInt()와 동일하지만, 이 경우 읽은 값이 minv 이상 maxv 이하여야 합니다. variableName은 에러 메시지에 출력할 변수명입니다. readInteger 함수도 해당 버전이 있습니다.
  
  
• double readDouble(double minv, double maxv, const std::string& variableName = ""):
  구조적으로는 readDouble()와 동일하지만, 이 경우 읽은 값이 minv 이상 maxv 이하여야 합니다. variableName은 에러 메시지에 출력할 변수명입니다. readReal 함수도 해당 버전이 있습니다.
  
  
• double readStrictDouble(double minv, double maxv, int minAfterPointDigitCount, int maxAfterPointDigitCount, const std::string& variableName = ""):
  구조적으로는 readDouble(minv, max, variableName)과 동일하지만, 소수점의 자릿수가 minAfterPointDigitCount 이상 maxAfterPointDigitCount 이하이어야 합니다. readStrictReal 함수도 해당 버전이 있습니다.
  
  
• std::string readString(), std::string readLine(): EOF나 EOLN(End of Line, 즉 줄바꿈을 의미하는 글자입니다)을 만날 때까지 입력된 값을 읽어나가, 그 읽은 값은 std::string의 형태로 반환합니다.
  
  
• std::string readString(const std::string& ptrn, const std::string& variableName = ""):
  readString()과 동일하나, 읽은 값이 ptrn로 주어진 Regex 패턴을 만족해야 하며, 아닐 경우 variableName에 주어진 변수명을 토대로 에러를 띄웁니다.
  
  
• void readEoln():
  줄바꿈 문자('\n')를 읽습니다. 줄바꿈 문자가 아닐 경우, 'Expected EOLN'이라면서 에러를 띄웁니다. 이 함수는 Windows에서는 0x0D와 0x0A를 읽으며(CR LF), OS X(버전 10 이상)와 *nix에서는 0x0A를 읽습니다(LF).
  
  
• void readEof():
  파일의 끝을 읽습니다. 파일의 끝이 아닐 경우, 'Expected EOF'라며 에러를 띄웁니다.
  
  
• inline void ensuref(bool cond, const char* format, ...):
  cond에 입력된 조건이 만족되지 않을 경우, format을 stderr로 출력합니다. printf처럼 가변형 인자를 가진 함수입니다. 이 함수는 주로 변수를 입력받은 다음에, 변수의 범위로만은 따질 수 없는 성질을 확인하고자 할 때 사용합니다. 

7. Tests (1 - Generator with testlib.h)에서 선보였던 generator가 기억나십니까?

#include "testlib.h"
#include <iostream>
 
int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);
    
    int query=atoi(argv[1]);
    int max_int=atoi(argv[2]);
    
    cout << query << endl;
    
    for(int i=0;i<query;i++)
    {
        int n=rnd.next(0, max_int);
        int r=rnd.next(0, n);
        std::cout << n << " " << r << endl;    
    }
    return 0;
}
 

query와 max_int의 최댓값이 80000이라고 문제에 명시가 되어 있다면, 이 generator에 해당하는 validator의 한 예시는 다음과 같습니다.

#include "testlib.h"
 
int main()
{
    registerValidation();
 
    int q = inf.readInt(1, 80000, "q");
    inf.readEoln();
 
    for (int i = 0; i < q; i++)
    {
        int n = inf.readInt(0, 80000, "n");
        inf.readSpace();
        int r = inf.readInt(0, 80000, "r");
        ensuref(r <= n, "'r' must not  exceed 'r'");
        inf.readEoln();
        
    }
    inf.readEof();
    return 0;
}
 

q를 읽은 다음에 줄바꿈 문자을 읽고, 'n을 읽는다 ->  공백을 읽는다 -> r을 읽는다 -> r <= n인지 확인한다 -> 줄바꿈 문자를 읽는다'를 q번 반복합니다. 그 다음에는 EOF을 읽으며 끝납니다. Polygon의 Well-formed policy는 이런 whitespace을 각 문제별로 규격화하기 우해서 있는 것이지요. space가 난잡하게 어떤 곳은 1개, 어떤 곳은 3개 이렇게 있으면 validator가 작동하기 힘들기 때문입니다.

하나 더 예시를 들어보겠습니다. 이 코드는 다음 문제의 validator로 작동합니다.

#include "testlib.h"
char status[1000001];
int main()
{
    registerValidation();
 
    int n=inf.readInt(1, 100, "n");
    inf.readEoln();
 
    for(int i=0;i<n;i++)
    {
        char ch=inf.readChar();
        ensuref(ch=='+'||ch=='-', "Invalid operation %c, + or - expected", ch);
        inf.readSpace();
        int x=inf.readInt(1, 1000000, "x");
        if(status[x]==ch)
        {
            ensuref(ch!='+', "Invalid operation %c %d, %d is already in the library", ch, x, x);
            ensuref(ch!='-', "Invalid operation %c %d, %d is not in the library", ch, x, x);
        }
        status[x]=ch;
        inf.readEoln();
    }
    inf.readEof();
    return 0;
}
 

입력 데이터가 복잡해질수록 validator도 복잡해지지만, validator는 모든 invalid input을 잡아야 하기에, 신중히 코딩할 필요가 있습니다. 그래서 Polygon은 validator를 시험해볼 기회를 줍니다. Set validator 밑을 보면 다음과 같습니다.

Test를 하나 만들고 설명하겠습니다. Add test를 누르면 다음과 같은 화면이 나타납니다.

각 항목을 설명하자면 다음과 같습니다.Validator test #: test의 번호입니다. 여기서도 마찬가지로, test의 개수는 1000개를 넘을 수 없습니다(1~1000).

• Multiple tests: 저 체크박스가 활성화되어 있으면 ===을 경계로 여러 개의 test를 한꺼번에 만들 수 있습니다. 특히 Validator test는 Archive로 한꺼번에 올릴 수도 없고, Create를 누르면 Tests의 경우처럼 다시 이 창으로 이동하는게 아니라 Validator 탭으로 다시 이동하기 때문에, 여러 개를 한꺼번에 만드는 것을 추천합니다.
  
  
• Input(s): test data를 여기에 적으면 됩니다. 공백이나 줄바꿈에 유의하면서 입력하시기 바랍니다. 참고로 Multiple Test를 만들 때 구분을 ===로 한다고 했는데, 사용 예시는 다음과 같습니다.
  
  

  1

  2 1

  ===

  0
  

  
  

  ===를 사용할 때는, ===를 치고 바로 줄바꿈을 해야 합니다. 즉 === 직전까지(2 1 이후의 줄바꿈까지)가 1번째 test이고, === 다음 줄부터 2번째 test로 인식되는 것입니다.
  
  
• Verdict(s): test가 올바른지 아닌지를 적는 칸입니다. 올바르면 1 또는 VALID를, 올바르지 않으면 0 또는 INVALID를 입력하면 됩니다. 영단어로 표기할 경우 대소문자 구별은 하지 않으며, test가 여러 개일 때는 각 줄마다 올바른지 아닌지를 해당 양식으로 적으시면 됩니다(즉, 공백으로 구분지을 수 없습니다).

이런 식으로 만든 다음에 Create를 누르면 Validator 탭에 해당 test가 추가된 것을 볼 수 있습니다. 비록 지금은 Main Solution이 없어서 이를 지금 당장 확인할 수는 없지만, 다 만든 문제(위에 있었던 generator가 쓰이는 문제)에서는 다음과 같이 나옵니다.

31번과 32번 test를 보면, INVALID한 이유가 상세히 나옵니다. 다만 예상했던 결과와 다르게 나오면 그 열의 배경색깔이 빨간색이 됩니다. 다음과 같이 말입니다.

43번부터 45번까지는 VALID라 설정했지만 validator가 INVALID라 판별하였기에 빨간색이 되었습니다. 반대로 INVALID라 설정한 것이 VALID일 경우도 저렇게 됩니다. 그런 경우가 있다면, validator를 고쳐야겠지요!

validator를 만들면서 주의해야 할 점은 특히 input의 범위나 양식은 올바른데 실제로는 올바르지 않은 경우(중복되었다든지, 추가적인 제약조건이 있다든지)도 고려해야 한다는 점입니다. 참고로 testlib.h 폴더 있는 validator 중에서도 bipartite graph validator 등이 있으니 참고하셔도 좋을 듯 합니다.

그 외에 testlib.h zip 파일에 있는 'validate-using-testset-and-group.cpp' 파일을 보면 testset과 group에 따라 validator가 다르게 작동하는 것의 예시도 나와 있습니다. 이를 사용하면 group 또는 testset에 따른 sub-task와 그것의 제약조건을 고려한 validator를 만들 수 있습니다. sub-task에 주어진 제약조건을 어기는 test가 있으면 곤란하기 때문입니다(ex. N<=15, K<=100이라고 했는데 N=1, K=1000인 경우가 있을 때). 

PS. 43번 test가 INVALID한 이유가 '0이 [1,80000] 범위에 있지 않아서'가 아니라 '정수가 아니어서'인 이유는, 복붙 과정에서 BOM이라는 문자가 끼어들어갔기 때문입니다. 하지만 직접 타이핑하면서 생길 문자는 아니므로, 특이한 케이스라고 보시면 되겠습니다.