8. Tests (2 - Generator with Freemarker)

일러두기 : 제가 정작 generator를 만드는 것 자체를 간단히 넘어간 면이 없지 않아 있지만 우선 이는 문제에 따라서 그 양상이 너무나도 다르고(input이 자연수 한 개뿐인 문제도 있는 반면, 그래프 상태를 입력을 받고 추가적으로 쿼리까지 받는 복잡한 문제들도 존재하기 때문입니다), 거기에 여러 커팅등을 방지하는 corner case를 만드는 것까지 고려하면 이건 문제를 만드는 사람이 해결해나가야 하는 일입니다. Codeforces Round에서도 '이거 정해는 O(n^2*m)인데 왜 O(n^3)이 통과되나요' 등의 일이 자주 발생하기 때문입니다. 그래서 problem setter가 여러 분들의 도움을 받는다는 것을 알 수 있습니다. 이와 별개로, 가끔씩은 test case를 만드는 것 자체가 하나의 문제가 되는 경우도 많습니다(ex. 점 n개가 주어질 때 세 점을 지나는 직선이 존재하는지의 여부). 사실 이쪽이 문제를 만드는 데 많은 시간을 투자하게 되는 부분이기도 합니다.

아무튼 testlib.h로 test case를 만드는 Generator를 작성하셨다면(참고로 testlib.h에는 bipartite graph generator라든지, tree generator라든지 만들기 힘든 generator도 있습니다), Polygon에 test를 zip 파일로 올리는 수도 가능하겠지만, 가장 좋은 방법은 만든 generator를 Polygon에서도 작동하게 만드는 것 아닐까요?

5. Files에서 이미 나왔던 내용이지만 이런 종류의 file은 Files - Source Files에 업로드를 할 수 있습니다. 업로드를 합시다.

업로드를 한 후에 Tests로 이동하여 Script로 이동해 봅시다. Script의 모습은 다음과 같습니다.

이 창은 특수한 구문을 이용하여 자동으로 test를 추가해 줍니다. Generator의 이름이 randomGen(확장자는 무시하고 씁니다)이라고 하고, 기본적으로 인자를 2개 받는다고 합시다. 그러면 generator를 부를 때는 'randomGen 인자1 인자2' 형태로 쓰시되, '인자1'과 '인자2'에는 실제 프로그램에 전달할 인수의 값을 집어넣으시면 됩니다. randomGen 10 10 처럼 말입니다.

하지만 이것만 적으면 안 됩니다. 이렇게 만들 test가 몇 번째 test인지 알려주어야 합니다. 알리는 방식은 크게 3가지가 있습니다.

• randomGen 10 10 > 1 : 말 그대로 1번째 test를 randomGen 10 10을 실행했을 때 만들어지는 값으로 설정한다는 뜻이며, 이 경우 표준 입출력을 사용합니다. 뒤에 붙이는 숫자는 이전에 언급했듯이 1에서 1000까지만 있을 수 있으며(test 최대 개수가 1000개입니다)다만 Manual하게 만든 해당 번호의 test가 이미 있을 경우에는 사용할 수 없습니다. 또한 Script에 같은 test 번호를 가리키는 구문이 있을 수 없습니다.
  
  
• randomGen 10 10 > {1} : 이 경우, 1번째 test를 randomGen 10 10을 실행했을 때 나오는 test로 설정한다는 뜻이나, 파일 입출력의 형식으로 지정됩니다. 일반적인 숫자 사용법과는 다르게, 범위를 지정할 수 있습니다. {1-3,7}의 경우 1,2,3,7에 randomGen 10 10이 들어가게 됩니다.
  다만 저 경우 각 test가 모두 같게 되는지, 아니면 Polygon에서 자체적으로 이 뒤에 parameter를 더 추가해 seed를 바꾸어 다른 test가 되는지는 잘 모르겠습니다.
  
  
• randomGen 10 10 > $ : 이 경우, 해당하는 test는 Script에서 저렇게 test 번호가 명시적으로 나타난 경우를 모두 처리한 다음, 가능한 제일 작은 번호 값을 가지게 됩니다. $는 파일 입출력을 의미하는 {} 안에 넣어 사용할 수 없습니다.

실제로 파일 입출력과 표준 입출력을 섞어서 쓰는 경우는 거의 없고, 또 testlib.h에서도 표준 입출력을 사용하도록 장려하고 있기 때문에 {}는 무시하면 됩니다만......{}처럼 범위 지정을 못한다는 것이 문제입니다.

일단 그 문제는 잠시 제쳐두고, 그렇게 생성된 test를 한 번 봅시다. 다음과 같은 script를 시험삼아 한 번 돌려보았습니다.

randomGen 10 10 1 > 1

randomGen 10 10 2 > 3

randomGen 10 10 3 > {4}

randomGen 10 10 4 > $

randomGen 10 10 5 > $

parmeter는 2개만 전달하는 것 아니었나요라고 질문할 수 있습니다. 추가적으로 3번째 인자를 전달하는 것의 의미는 다음과 같습니다.

• 저런 식으로 표시하지 않으면 test가 중복(coincide)된다고 에러를 띄웁니다.
  
  
• 또, 저렇게 추가적인 인자를 보내면 generator 내의 함수 registerGen에서 seed값을 다르게 가지게 되어, 실제 test data도 다르게 됩니다.

아무튼 저렇게 script를 만들고, Save Script를 누르면 script에 따른 test case가 생깁니다. 한번 볼까요?

Manual하게 만든 test와는 달리, Content에 test data가 아닌 script가 들어가 있습니다. 단, 중괄호는 사라져 있습니다. 또, $를 사용한 test들의 위치가 번호에 맞게 들어간 것을 알 수 있습니다(참고로 이 때 밑에 적었던 script 자체의 순서도 이에 따라 변경됩니다). 이 때 Preview Tests를 누르면 실제 test data를 볼 수 있습니다. 물론, 아직은 validator, checker, main solution 등이 없어서 무용지물입니다.

이 때 edit을 누르면, 7. Tests (1 - Generator with testlib.h)에서 생략하고 넘어간 Script Type의 test를 볼 수 있게 됩니다.

주목할 점은 Script Line과 옆에 있는 체크박스입니다. Script Line에는 Script 창에 써넣은 구문이 각 test에 대해서 들어가 있습니다. 이를 수정하면 전체적인 script 역시 수정되며, 옆에 있는 체크박스 (Check it if generator produces test as file (doesn't use stdout)) 역시 수정시 그대로 script가 수정됩니다. 해당 체크박스는 파일 입출력을 사용 유무를 나타냅니다.

그럼 다시 그 문제로 돌아와서......표준 입출력을 사용할 때 저렇게 대량의 test를 어떻게 양산해낼까요? 물론 모든 script를 출력하는 프로그램을 만들어서 (이 정도 코딩은 정말 간단하니까요) Ctrl CV하는 수도 있습니다. 하지만 그것보다 훨씬 더 효율적인 방법이 존재합니다. 바로 Freemarker Template을 이용하는 것입니다.

저도 Freemarker Template은 잘 모르지만, Polygon Tests에서 Script를 만들 때 필요한 지식은 얼마 되지 않습니다. 다음은 그 내용입니다.

• 변수 선언 및 간단한 연산은 <#assign i = 2/>, <#assign i = i + j /> 등의 식으로 #assign을 이용하여 할 수 있습니다.
  
  
• for문의 경우, <#list 1..5 as i> ... </#list> 등의 식으로 할 수 있는데, i라는 변수를 1에서 5까지 1씩 증가시키면서 <#list 1..5 as i> 와 </#list> 사이에 있는 구문을 반복해서 실행한다는 의미입니다. #list는 중첩이 가능합니다.
  
  
• 변수를 사용할 때는 ${변수명}으로 사용합니다. i를 사용하고 싶으면 ${i}, num을 사용하고 싶으면 ${num}......
  
  
• Freemarker Template을 사용할 경우 generator 구문 맨 끝에 번호를 나타내는 인자에는 무조건 $가 와야 합니다. 숫자나 중괄호는 올 수 없습니다.
  
  
• Freemarker Template으로는 random을 지원하지 않습니다. 대부분의 경우 Freemarker Template으로 random을 돌릴 이유가 없기도 하지만 말이죠.
  
  
• Freemarker Template은 SPACE나 TAB으로 들여쓰는 것이 의무가 아닙니다.

그러면 다음과 같은 간단한 구문으로 test를 만들 수 있습니다.

<#assign i = 1/>

<#list 1..100 as i>

    randomGen 50000 50000 ${i} > $

</#list>

여러 개의 generator를 이용해서 이렇게 만드는 수도 있습니다.

<#assign num = 1/>

<#assign i = 1/>

<#list 1..100 as i>

    <#assign j = 1/>

    <#list 1..7 as j>

        randomGen ${i*i*8} ${i*i*8} ${num} > $

        <#assign num = num + 1/>

    </#list>

    CenterGen ${i*i*8} ${i*i*8} > $

    <#assign num = num + 1/>

    xStackGen ${i*i*8} ${i*i*8} > $

    <#assign num = num + 1/>

    yStackGen ${i*i*8} ${i*i*8} > $

    <#assign num = num + 1/>

</#list>

이런 방식으로, test를 만들 수 있습니다. 하지만 test를 만드는 것이 문제를 만드는 것에서 가장 중요한 부분 중 하나라는 것을 명심하시길 바랍니다. 일례로 바로 위의 코드도 CenterGen 등의 다른 generator를 사용한 이유 역시 커팅 등을 사용한 풀이를 TLE 내기 위해서이니까요 (참고로 CenterGen 등의 generator는 random generator가 아님을 밝힙니다). 물론 실제 test set에 test를 저렇게 1000개를 넣고 돌리지는 않을 겁니다. 저건 어디까지나 시험용일 뿐입니다. 실제 test set은 많아야 100개 남짓 되는 test가 들어가고, 이를 어떻게 구성할 지는 여러분의 몫이기 때문입니다.