7. Tests (1 - Generator with testlib.h)

6. testlib.h에서 이미 적었듯이 Tests에서 test, 즉 문제의 input들을 만드는 것을 우선 포스팅하겠습니다. Tests 탭에 들어가면 다음과 같은 화면이 나타납니다.

순차적으로 위에서부터 설명하겠습니다.

• Tests(0): 이는 Tests라는 test set에 문제가 0개 있다는 것을 의미하여, Tests라는 test set에 이동하라는 하이퍼링크입니다. Tests는 기본적으로 생기는 test set입니다.

• Delete Current: 현재 자신이 있는 Test set를 지우는 링크입니다. 이를 만족하려면 다음과 같은 조건을 만족해야 합니다.

• Test set이 Tests가 아닐 것이며
• test가 하나도 있지 않아야 합니다. 즉 모든 test를 삭제한 상태여야 합니다.

• Create Current: 새로운 Test set를 만드는 링크이며, 누르면 새로운 이름을 입력하라고 나옵니다. 이 때 이름의 조건은 다음과 같습니다.

• 이미 존재하는 Test set과 이름이 중복되면 안 되며
• 알파벳 소문자/대문자, 숫자 그리고 underscore(_ : 0x5F)만 사용할 수 있습니다. 

탭 밑에 존재하는 3개의 항목은 다음과 같습니다.

• Testset: 이 test set의 이름을 의미합니다. test set은 한 번 만들어지면 이름을 자체적으로는 바꿀 수 없지만, 후술할 복사 기능을 이용해서 사실상의 이름 변경을 할 수 있습니다.

• Test count: 이 test set에 있는 test의 개수를 의미합니다. 한 test set에 test는 최대 1000개 들어갈 수 있습니다.

• Enable groups: test들의 그룹을 활성화하는 버튼입니다. 그룹을 지으면 한 test set에서도 이들을 묶을 수 있습니다. 이러면 나중에 Invocation에서나, Validator에서나 그룹별로 따로 작업을 수행할 수 있습니다. 이는 그룹이 활성화되어 있을 때만 적용됩니다. 다만 그룹을 만든 다음에 비활성화해도 그룹이 사라지지는 않습니다.

밑에 Tests라고 적혀 있는 곳 오른쪽을 보면 두 개의 하이퍼링크가 존재하는데, 이들의 역할은 다음과 같습니다.

• Preview Tests: Test set을 한 번 실제로 프로그램으로 돌려보아, 그 결과를 미리 봅니다. 이는 Validator, Solution, Checker 등의 모든 것들이 기본적으로 필요하기에, 지금 당장은 큰 의미가 없는 링크입니다.

• Add Tests: test를 추가할 수 있는 링크입니다. 한 번 눌러봅시다.

다음과 같은 창이 뜹니다. 역시 각 항목을 분석하면 다음과 같습니다.

• Testset: 이 test set의 이름을 의미합니다.

• Test #: 이 test가 해당 test set에서 몇 번째 test인지를 의미합니다. 같은 번호를 가지는 test가 2개 이상 존재할 수 없기 때문에, 일반적으로는 가능한 test 번호 중 최저의 숫자를 적어놓지만, 번호를 임의로 바꿀 수는 있습니다. 예를 들면 Test #1 대신 Test #23이라든지 말이죠. 그러나 일반적으로는 순차적으로 Test를 만들게 됩니다. 상식적으로 Test가 1부터 시작하지 23부터 시작할까요. 이렇게 숫자들의 순서 및 배열이 이상한 경우 어떻게 되는지는 후술하겠습니다.

• Type: test를 어떤 방식으로 추가할 것인지를 의미하는 탭이며, 두 가지 선택지가 있습니다. 'Manual'과 'Script'입니다. Manual은 직접 더한다는 뜻이고, Script는 별도의 스크립드를 이용하여 test를 더한다는 뜻인데, 우선 이 글에서는 Manual만 다루고, Script는 다음 포스팅에서 Freemarker를 다룰 때 같이 설명하겠습니다.

• Data: test 그 자체입니다. 입력해야 할 대상을 입력하시기 바랍니다. 다만 여기에 test를 입력할 때 General Info에서 'Are tests well-formed?'를 활성화시켰다면 3. General Info의 'Well-formed'에서 설명한 규칙이 적용되어야 합니다. 적용되지 않을 경우 강제로 규칙들을 적용하며, ‘Added test has been reformatted because of the problem well-formed policy’ 라는 구문이 create를 누르고 다음 창에 나타납니다. test의 규모가 클 때 어떻게 해야 하는지는 조금 있다 다루겠습니다.

참고로 이미 존재하는 test는 만들 수 없습니다. 즉, 중복한 test는 만들 수 없습니다. 하지만 후술할 버그가 존재합니다.

• Use in statements: Statement에서 만들던 pdf 파일을 기억하십니까? Statement에서는 예제를 더하는 기능이 없었습니다. 이를 여기서 시행할 수 있습니다. 누르면 다음과 같이 나타납니다.

옆에 또 하이퍼링크가 있는 것을 알 수 있습니다. 누르면 다음과 같은 입력창이 추가적으로 나타납니다.

추가적으로 나타나는 항목들은 다음과 같습니다.

• Input in statements: 입력하는 값이 너무 많아서 pdf로 옮기기에는 좀 그런 상황일 때는 statement에 사용하지 않는 것이 정상입니다. 하지만 꼭 사용해야 할 경우 저렇게 statement에 어떻게 이 test를 나타낼지를 입력하는 창이 주어집니다. 예를 들면 처음 6줄만 쓰고 말줄임표로 생략한다든지......만일 모든 input data를 사용하고 싶다면 빈칸으로 내버려두시면 됩니다.
  
  
• Output in statements: 생략당한 입력이 있으면 그 입력에 대한 출력도 생략당하겠죠. 마찬가지입니다. 기본적으로 Input in statements가 비어있지 않으면 이 입력창 역시 비어있으면 안 됩니다(역시, 비어있으면 모든 output data를 출력하겠다는 뜻입니다). 다만 input 쪽을 다 출력했는데 output은 일부 생략한다의 방식은 가능합니다.
  
  
• Verify output for statements: 이 기능은 실제 statement에 output이 제대로 문제 형식에 맞추어서 작동하는지를 판별해야 하는데, 뭐 input을 막 조작하든 output을 조작하든 잡아내질 못합니다......결론은 무쓸모.

참고로 Use in statements를 할 때 test는 다음과 같은 조건을 만족해야 합니다.

• valid한 test여야 합니다. 즉, Validator와 Checker를 거쳐 나올 수 있는 test여야 합니다.
  
  
• input이 5000바이트를 넘어갈 수 없습니다. output 쪽은 잘 모르겠습니다.
  
  
• 아주 중요한 불문율로, Statement에 나오는 test들은 test set에서 가장 앞에 있어야 합니다.

Use in statements 밑에는 단 하나의 텍스트 필드만 있습니다.

• Description: test에 대해 기타 사항을 적는 곳입니다.

다 완료되었다 생각하시면 밑의 create를 누르시면 됩니다. 그러면 자동으로 다음 test를 만드는 창으로 이동하게 됩니다.

여기까지는 Manual하게 만드는 방법이며, 다음은 zip 파일을 통해서 제출하는 방법입니다. 창 우측 상단에 'Would you like to add several tests from the archive?'라는 탭이 존재하고, 여기에 input data가 적혀 있는 txt 파일로만 이루어진 zip 파일을 제출할 수 있습니다. 그러나 Polygon이 zip 파일에서 txt 이외의 파일은 읽지 않는다 이런 식은 아닙니다. 확장자에 관계 없이 plain하게 읽어버리는 것입니다. 이와 관계없이, Polygon 서버는 놀랍게도 zip 파일 이름에는 ASCII 코드를 비롯한 유니코드 등을 쓸 수 있습니다. 그리고 이 방식으로 중복된 test를 추가할 수 있습니다만, 무슨 의미가 있습니까. 일종의 버그 내지는 취약점인 것 같습니다. 

문제들의 input이 클 경우, 즉 byte가 많을 경우 Ctrl+CV 신공이 시간이 상당히 많이 걸리며, 이 경우 저렇게 zip 파일째로 보내는 것을 추천드립니다. 그러나 txt는 한계가 있습니다. 물론 이러한 데이터들도 나름의 프로그램을 짜서 만든 것이겠지만, 그러한 프로그램들이 Polygon에서도 무리 없이 작동하게 하려면 어떻게 해야 할까요?

기본적으로 test를 만드는 코드는 Generator라고 불립니다. Generator는 문제마다 천지 차이가 납니다. 정수 하나만 input으로 가지는 수학 문제는 매우 간단하며, 복잡한 그래프 문제라면 input의 형식이 상당히 복잡해집니다. 어쨌든 Polygon에서 이를 사용하려면 testlib.h를 통한 Generator를 사용해야 합니다.

Generator를 만들어 봅시다. 그 전에, 이전에 다운받은 testlib.h zip파일에는 예제들도 들어가 있는데, 우선 몇몇 함수들의 사용법을 알아보고, 그 다음에 이가 적용된 예시를 탐구하겠습니다. 

• void registerGen(int argc, char* argv[], int randomGeneratorVersion):
  이 프로그램이 generator라고 선언하는 코드로, main 함수 첫 줄에 쓰는 것이 권장됩니다. 이 함수는 next 함수(randomizer 함수)의 seed값을 정해, next 함수가 정상적으로 사용될 수 있게 작용합니다. 다시 한 번 쓰지만, rand()나 srand()는 쓸 수 없습니다. 내부적으로 사용하면 바로 stderr로 해당사항을 출력시킵니다. 이런 방법을 쓰는 이유는 아무래도 rand() 등의 함수들이 컴파일러나 IDE에 따라 그 값이 다르기 때문이라고 생각됩니다.
  
  
  • int argc : 네. main 함수의 그 argc 맞습니다. 실제로 main 함수의 그 argc를 넘겨야 합니다.
  • char* argv[] : 네. 역시 그 argv[] 맞습니다. 마찬가지로 main 함수의 그것을 넘겨야 합니다.
  • int randomGeneratorVersion : 1로 고정입니다. 초창기 testlib.h는 0을 사용했지만 이제는 버전이 높아져서 새로운 값인 1로 사용합니다. 0과 1 이외의 값을 넘길 경우 stderr로 해당사항을 알립니다.
    
    
  argc와 argv는 내부적으로 바로 seed값을 결정하는데 사용됩니다. argc와 argv가 가지는 자체적인 의미와, argc와 argv의 사용법은 후술하겠습니다.

random과 관련된 몇몇 함수들의 역할은, type에 따라 달라질 수는 있겠지만, 기본적으로 다음과 같습니다. type은 그냥 T라고 쓰겠습니다. 참고로 밑에 서술할 모든 함수들은 testlib.h의 class random_t에 선언되어 있고 random_t rnd;라는 구문이 testlib.h에 전역으로 존재하기 때문에 rnd.next(); 등의 방식으로 호출하시면 됩니다.

• double next(): 
  parameter가 없는 유일한 next입니다. 0 이상 1 미만의 double형 실수를 return합니다.
  
  
• T next(T n): 
  0 이상 n 미만의 T형 수를 return합니다. n이 음수거나 값이 너무 크거나 하면 stderr로 해당 사항을 알립니다.
  
  
• T next(T from, T to):
  from 이상 to 이하의 T형 수를 return합니다. to가 from보다 작거나, to나 from의 값이 너무 클 경우 stderr로 해당사항을 알립니다.
  
  
• std::string next(std::string ptm):
  ptm은 Regex에 따른 std::string(내지는 char*)입니다. Regex는 string에서 해당하는 패턴을 찾고자 할 때 사용하는 입력법인데요, ptm을 그런 식으로 입력해야 합니다. 물론 testlib.h가 모든 Regex 스펙을 따르고 있지는 않습니다. 간단한 것만 구현해서 사용하고 있는데요, 어차피 랜덤한 것을 만드는데는 별 상관 없습니다. Regex에서 사용할 수 있는 구문들은 다음과 같습니다.
  
  
  • 문자들의 집합은 대괄호 안에 넣어서 사용합니다. 예를 들어 [ac]는 a와 c를, [a-z]는 a부터 z까지, [^a-z]는 a-z를 제외한 모든 문자를, [a-z][A-Z]는 알파벳 대소문자 모두를, [0-9]는 숫자 0부터 9까지를 의미합니다.
    
    
  • 문자들의 개수는 대괄호 뒤에 중괄호를 붙여서 사용합니다. 예를 들어 [a-c]{5}는 a부터 c까지의 문자, 즉 a,b,c 셋 중 하나를 무작위로 골라 길이 5의 문자열을 만들고, [a-z]{1,100}의 경우 알파벳 소문자로만 이루어진 1자리부터 100자리의 문자열을 만들어냅니다. 
    이 중괄호는 바로 앞의 집합에만 적용됩니다. [a-z][A-Z]{10}의 경우 알파벳 소문자를 무작위하게 1개, 알파벳 대문자를 무작위하게 10개를 뽑습니다.
    또, %d 등을 통해서 범위를 변수로 조정할 수도 있습니다.

  
  

  • black|white 문자열의 경우 black 또는 white입니다.
    
    
  • 문자를 선택적으로 넣고 싶을 때는 ?를 사용합니다. 그 예시로 -?[1-9]가 있습니다. 이 경우 앞의 -가 선택적으로 들어갑니다. 그 결과 -9부터 9까지의 0이 아닌 자연수를 랜덤하게 만들게 됩니다.
    
    
  • 문자를 반복적으로 선택하고 싶을 경우 * 또는 +를 사용할 수 있습니다. [0-9]*의 경우, 0부터 9까지의 수를 0개 이상으로 연속적으로 선택하며, [0-9]+의 경우 0부터 9까지의 수를 1개 이상으로 연속적으로 선택합니다.
    
    
  • 추가적으로 실험을 해보고 싶으시면 이 링크에서 한 번 해보시길 바랍니다. 다만 testlib.h에서 지원하지 않는 기능들도 지원하니 유의하세요.
  
  
• T wnext(T n, int type): 
  w는 weight을 의미합니다. 가중치가 어떻게 구현되는지는 다음과 같습니다.
  
  
• type이 양수일 경우 |type+1|개 만큼의 0 이상 n 미만의 T형 수를 뽑은 다음, 그 중 최댓값을 return합니다. 과정은 for문으로 이루어집니다.
  
  
• type이 음수일 경우 |-type+1|개 만큼의 0 이상 n 미만의 T형 수를 뽑은 다음, 그 중 최솟값을 return합니다. 과정은 for문으로 이루어집니다.
  
  
• type이 0일 경우 T형에 해당하는 next 함수와 동일한 역할을 합니다.
  
  
• void shuffle(_RandomAccessIter __first, _RandomAccessIter __last): 
  random access가 가능한 iterator를 돌려가면서 first와 last 사이의 원소들을 무작위하게 섞습니다. 주의할 점은 algorithm 헤더의 std::random_shuffle을 사용하면 안 된다는 점입니다.
  
  

• typename Container::value_type any(const Container& c): 
  container c에 있는 원소 중 하나를 랜덤하게 선택하여 리턴합니다.

이 외에도 wany, from/to/type으로 이루어진 wnext도 있으나 설명은 생략하겠습니다.

testlib.h의 예제를 일부 살펴보겠습니다. 매우 간단한 igen.cpp와 sgen.cpp를 살펴보면 다음과 같습니다.

#include "testlib.h"
#include <iostream>
 
using namespace std;
 
int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);
 
    cout << rnd.next(1, 1000000) << endl;
 
    return 0;
}

1부터 100000 중 하나의 값을 무작위하게 출력하는 Generator입니다.

#include "testlib.h"
#include <iostream>
 
using namespace std;
 
int main(int argc, char* argv[])cc
{
    registerGen(argc, argv, 1);
 
    cout << rnd.next("[a-zA-Z0-9]{1,1000}") << endl;
 
    return 0;
}

알파벳 소문자, 대문자, 숫자를 포함하는 길이 1에서 1000까지의 문자열을 출력하는 프로그램입니다.

하지만 이러면 또 의문이 생깁니다. '저 프로그램들의 길이 범위는 정해져 있는 것이 아닌가? 우리가 조절할 수 있게 할 수는 없는건가?' 결론은 '조절할 수 있다'입니다. 이를 하기 위해서는 main 함수의 인자인 argc와 argv의 의미를 파악해야 합니다.

흔히 int main()으로 생략되기도 하는 main 함수. main 함수의 형태는 비표준 확장을 제외하면 다음 2가지 중 하나를 지녀야 한다고 명시되어 있습니다.

• int main()

• int main(int argc, char* argv[])

이 중 argc와 argv의 의미는 다음과 같습니다.

• int argc: argv에 전달되는 인자의 개수입니다. argc는 0 이상의 값입니다.

• char* argv[]: 실행 환경 자체에서 주어진 인자들입니다. argc가 1 이상의 값일 경우 argv[0]은 프로그램 이름을 나타내는 char*이며, argv[1] 부터 argv[argc-1]까지는 프로그램에 전달되는 인자(parameter)입니다. argv[argc]는 null pointer를 가리킵니다.

즉, argv는 실행 환경을 매개하는 인자들을 모아놓은 것입니다. 그 인자들은 프로그램을 실행하면서 우리가 설정할 수 있는 것입니다. 간단한 예시를 들자면 다음과 같습니다.

#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를 프로그램 자체의 인자로 받아, query를 첫째 줄에 출력한 다음, max_int 개 만큼의 0 <= r <= n을 만족하는 n, r을 각 줄에 공백으로 구분지어 출력하는 generator입니다.

이런 식으로, 우리는 프로그램이 원하는 범위만큼, 원하는 개수만큼 test를 출력하게 만들 수 있습니다. 프로그램의 인자 자체를 집어넣으려면 Windows의 경우, cmd 창 등의 shell을 이용해서 프로그램 이름 옆에 공백으로 인자를 입력하면 됩니다.

주제가 약간 옆으로 샜지만, 밑에 보면 Script라고 칸이 있으며 그 옆에 약간의 설명이 나와 있습니다. 이에 관해서는 다음 글에서 포스팅하겠습니다.

-UPD 2015.08.08 원래는 testlib.h의 자세한 함수 기능 등을 서술하려 했는데, 굳이 그럴 필요가 없어 보이고, 또 testlib.h 내에 자체적으로 주석 등으로 설명이 잘 되어 있기 때문에 서술을 생략하겠습니다.

-UPD2 argc와 argv 설명을 추가했습니다. 원래 다음 포스팅에 실으려 했슨데 생각해보니 여기에 넣지 않으면 Generator를 만들 수가 없게 되어서......

-UPD3 Group 관련 설명을 추가했습니다.