crbonilha / problemsetting

Automating problem setting's common tasks.

Problem Setting

This is a tool to help automate problem setting's common tasks, such as generating input/output files, validating input/output files against the problem description's constraints, and validating the solutions.

This tool is opinionated. It forces you to follow step by step actions in order to have all the required data and information in order to guarantee that the IO files will be as robust as possible.

The guidelines that inspired many of the tool's design decisions were inspired by many sources: similar closed source tools, similar guidelines used by various programming competition websites, and learned-the-hard-way lessons.

Setup

To use this tool you must run the "bon.ps1" script on a PowerShell terminal.

Folder structure

In order for this tool to locate all the relevant files, please abide by the following folder structure:

problemsetting/
  bon.ps1
  problems/
    your_problem_a/
      generators/
        descriptor.json
        your_generator.cpp
      io/ (this will be generated by the script)
      solutions/
        your_solution-ac.cpp
        your_solution-wa.cpp
      checkers/
        your_checker.cpp

Commands

Targeting problems

To run any command you must first define which problem you're working on. For that you have to use the "-problems" flag, and provide a comma-separated list of problem names:

$ ./bon.ps1 -problems problem1,problem2 -generateInput

The example above is generating input for the problems "problem1" and "problem2".

Generating input

All the input generation is coordinated by a file inside the "generators" folder called "descriptor.json". This file will describe how many sets of test cases there will be, how many test cases per set there will be, and how each test case will be generated.

Descriptor.json syntax

{
  "1": [                         // this list represents all the test cases for the first set
    {                            // this object represents the first test case
      "generator": "random.cpp", // this will be the generator used for this test case
      "seed": 132,               // this seed will be fed to the generator in order to
                                 // normalize the randomness
      "input": "5"               // whatever lives inside here will be fed into the generator
                                 // in order to parameterize the test case size/scope/complexity
    }, {
      "generator": "random.cpp",
      "seed": 354,
      "input": "20"
    }
  ]
}

Generator file

You can have as many generators as you want. At the moment, the only supported language for generators is C++, however that may change in the future. Your generator will be run every time it's referenced by the descriptor.json file, and it will read from standard input whatever is set on the "seed" and "input" fields.

What your generator prints to standard output will be saved on a input file inside the "io" folder. The exact file depends on which iteration of the descriptor.json list is being run. For example, if the run is for the first test case set (object "1" on the example above) and second object on that list (the object with seed "354" on the example above), then the input file will be saved at "io/1/2.in".

Command

Now that the files are in place, run the following command:

$ ./bon.ps1 -problems liga -generateInput

This command will go through every item on the descriptor.json, run every generator listed there with their requird parameteres (seed and input), and save the output of the run on the specific files inside the "io" folder.

Generating output

The output should be generated by one of your solutions. So the first step is to write your solution inside the "solutions" folder. You can have as many solutions as you want (the more you have the better), but notice that the script should rely on correct solutions in order to generate correct output. In order to specify that a solution is supposed to be the correct one, please append the "-ac" suffix to the solution's file name.

Command

$ ./bon.ps1 -problems liga -generateOutput

This command will compile the first correct solution inside the "solutions" folder (any solution with "-ac" suffix), go through every item on the descriptor.json, run the solution with that input file, and save the output of the solution on a file close to the input file. For example, for the "io/3/2.in" file, it will save the output file at "io/3/2.sol".

Validating the input

Every problem description defines some constraints for the input file. In order to ensure that these constraints are being followed, this tool provides the support for "checkers". Checkers are codes that have the sole purpose of reading the input and checking if it's complete and robust. For example, if the problem description states that the input file will have two positive integers, a checker should be written to guarantee that there will be exactly two integers (no decimals), whose values are greater than zero. Another example of a more complex checker is one that verifies if the given graph is indeed connected.

Location and guidelines

It's encouraged that you write as many checkers as you can. The only supported language at the moment is C++, but that may change in the future. Place your checkers inside the "checkers" folder.

Everything your checker prints will be used for analysis. Some keywords have special meaning. For example, if your checkers prints "wrong", then the script will notice that and mark that input file as having something wrong. On the other hand, if your checker prints "easy", the script will aggregate that keyword and show a resume at the end.

Command

$ ./bon.ps1 -problems liga -checkIo

This command will compile every checker that lives inside the "checkers" folder, go through every input file as defined on the "descriptor.json" file, and run each checker with each input file.

The keywords printed by the checker will be aggregated and used to analyse whether there's an input file that doesn't respect the constraints stablished by the problem's description.