As soon as I joined the committee, I got started working on the next competition and learned about the processes in place. We constantly worked to improve them. In this post, I will talk about old processes, why they existed, and how we attempted to improve them.

Writing Questions

Writing questions for the competition is the most important step in the competition design process. In our committee, question writing was done by a designated group of committee members. They would write a rough-draft of their question, a small sample, and potential background stories. After a few weeks, the committee gathered to review all questions and narrow them down to the 15 we would use for the competition. To do this, we gave each question a difficulty rating of easy, medium, or hard. We then eliminated questions until all that remained were the 15 we would use, where the majority of them were “medium” difficulty.

Writing Test Cases

Of course, we also needed to create a collection of test cases to test contestant’s programs against. The test cases consisted of both INPUT and OUTPUT. Creating these test cases by hand for each problem posed a problem: crafting inputs was easy, but doing the work to calculate the expected output by hand was challenging. Further, we wanted a fairly large number of inputs to catch any corner-cases that contestants may have missed.

Another challenge was test case formatting. Test cases had to be fed to contestant’s programs, whose output then had to be verified. Some of our test cases were also pretty complex (e.g Given a 2D array which represents one map, a 2D array which represents locations of hazards, find a path to the square with coordinates (X,Y)). Contestants definitely shouldn’t have to write this parsing code and instead should only focus on solving the problem in a pre-defined function stub.

Thus, the following problems had to be solved:
1. Given hand-crafted input, auto-generate output that we would use for judging contestants.
2. Provide the contestants with programs that already contained input-parsing and output-formatting logic. Contestants would simply complete a function stub.

Behold: “Template Writers” and “Solution Writers”

We solved the problem by having committee members be “solution writers”, who would act just as the contestants. For each problem, a “template writer” would write a template program that parsed input/output. Solution writers would then use the template and implement the function stub. As long as there were 3-or-so solution writers for each problem, this went very well. After everyone was finished, input could be added into a single file and provided to the solution writer’s programs. If all their outputs agreed, this input/output combination would be considered a new “test case”.

Eventually, we settled on a standard input format (separate test cases were delineated with newlines, components of each test case were determined by the template writer) and a sort-of standard template pattern.

Below is a Java template and case input for a problem in Fall 2014:

import java.util.*;

public class Problem4 {

  //Parameter(s): char ch - the character to be searched for in the String
  //              String phrase - the String to be searched through
  //Return:       int - the number of character triples in the String
  public static int spyingOnTriplets(char ch, String phrase) {

    //YOUR CODE HERE

    return 0;
  }


  /////////////////////DO NOT MODIFY ANYTHING BELOW THIS LINE///////////////////
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    ArrayList<String> input = new ArrayList<String>();
    while (in.hasNext()) {
      input.add(in.nextLine());
    }
    for (int i = 0; i < input.size(); i++) {
      char searchLetter = input.get(i).charAt(0);
      String searchString = input.get(i).substring(2);

      System.out.println(spyingOnTriplets(searchLetter, searchString));
    }

  }

}

d ddidddd
f ffffffluffffffy
f fluffyyyyy
z heyhowyoudoin
o ooooo
o oooo
b blblbl
b bbb
c c-c-c
' '''
- -----
p chicken

 

At the time, we continued writing inputs and templates by hand. However, we put a lot of effort into PCFramework, which was a collection of shell scripts that would allow all testing of test-cases to be handled automatically.

As an example, basic workflow looked like:

cd BPCFa15/Solutions/dev # Move into the solution writer directory
cp ../Templates/Problem1.java Brandon/ # Move the template into my own workdir
vim Brandon/Problem1.java # Fill in the function stub with my solution
./test.sh 1 Brandon # Test my solution against "sample input" and "corner input", which are hand crafted
./compare.sh 1 Brandon Dylan Marisa # Compare outputs of solutions and verify they are the same
cp Brandon/problem1.out tests/problem1.out # Move Brandon's output into the official tests folder

This allowed us to have “Sample inputs” (sanity inputs whose outputs were provided), “Corner inputs” (Difficult corner cases whose outputs were hand-crafted), and “Generated inputs” (inputs that we created by hand but whose outputs were generated by solutions).

Other Benefits of Solution Writers

On the surface, solution writers provided the competition with usable outputs. In addition, the process of crafting solutions by hand provided us with insight into other metrics, such as how difficult the problems really were and how easily they could be understood. More than once, we revoked a question from the question pool after we discovered that no solution writers could agree upon a solution.

On one occasion, we discovered that one of our problems actually boiled down to a difficult scheduling problem and none of our solution writers could optimally solve it. Obviously, this question was pulled.

A “golden solution” for the above problem:

import java.util.*;

public class Problem4 {

  //Parameter(s): char ch - the character to be searched for in the String
  //              String phrase - the String to be searched through
  //Return:       int - the number of character triples in the String
  public static int spyingOnTriplets(char ch, String phrase)
  {
    int count = 0;
    char[] characters = phrase.toCharArray();
    for (int i = 0; i < characters.length - 2; i++)
    {
      if (characters[i] == ch &&
          characters[i+1] == ch &&
          characters[i+2] == ch)
      count++;
    }
    return count;
  }


  /////////////////////DO NOT MODIFY ANYTHING BELOW THIS LINE///////////////////
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    ArrayList<String> input = new ArrayList<String>();
    while (in.hasNext()) {
      input.add(in.nextLine());
    }
    for (int i = 0; i < input.size(); i++) {
      char searchLetter = input.get(i).charAt(0);
      String searchString = input.get(i).substring(2);

      System.out.println(spyingOnTriplets(searchLetter, searchString));
    }

  }

}

 

Supporting More than Java

The usefulness of these verification tools quickly became evident. Since verifying inputs/outputs was now trivial, we could start supporting languages other than Java in our competition (as long as someone wrote a template and we had enough solution writers). Due to contestant demand, the first additional language we supported was C++.

At this point, our competition moved to HackerRank to manage contestant solutions and inputs/outputs.