https://github.com/bicsi/autotest

Hello!

For the last two days I have been working on an idea of mine that I had for quite some time but haven't had the time to implement until now. It is a framework for automatic test generation using optimization methods.

The main point

I want to help people that are into problem-setting but might have problems writing generators (or might have little time to do so). I was thinking that, instead of coming up with complicated generators, one might be able to reuse some generic parametric generators for given structures (partitions, graphs, polygons, etc.) and generate tests by focusing on designing a "fitness" function for a given input case.

Not only that, but many times while preparing problems I found that I was writing some generators by giving them some free parameters and trying to optimize something for the test, while keeping some randomness (for example, making the output answer as big as possible s.t. the constraints, generating test cases that have a given number of candidate solutions, generating test cases where line 100 in my code gets called as much as possible, etc.)

Also, I think it's also useful to have some generic framework for easy hyperparameter optimization with as few distractions as possible (in contests like Hash Code, for example).

I've recently learned about automatic hyperparameter optimization using techniques suitable for fitness functions that take time to compute (e.g. programs), and I've experimented with the hyperopt python library for some university projects. And, to be fair, I was pretty impressed. This thing knows what's about when it comes to optimization.

The framework

The framework should be more or less simple to use, if you go to the GitHub repository and read the readme file there. I focused my work in having an API that is as clean as it could be as a front-end and which requires as few extra libraries as possible (just clone/download the repository and install some python libraries).

How to use it

https://github.com/bicsi/autotest

More tehnical stuff (that's not mandatory to the library users)

This is provided that you already went through the human-readable README file, and want to learn more about how this works.

Every generator compiled with the autotest framework will allow some under-the-hood extra interaction with the autotest.py script. Populating the autotest::Params is being done via command-line arguments. For example, if you want to feed $$$n = 5$$$ into a generator, you have to run it via ./gen -Pn 5. When the .get() method is called, the argument is asserted to have been passed to the executable, and its value is validated and converted to the expected type.

However, the autotest.py can't know about what parameters should be fed into the generator. That's why, the generator compiled with the autotest framework can be run in interactive mode (via --interactive command flag). The only difference here is that when a parameter isn't found as a command-line argument, instead of failing, the generator 'asks' the script via stdin/stdout what its value should be. This way, the autotest.py script "gains knowledge" dynamically about the generator at runtime. This is essential, because that means that you can implement generator libraries with "hidden parameters" that are transparent to the user, and which will be optimized automatically by the script.

Then the script optimizes for the sum of absolute differences between the goal metrics given by the model solution and the goal metrics sought in the tests config file. Some weighted sum might be useful in case of multiple goals, but this hasn't been implemented. It also has some L2 regularization implemented, which means that it penalizes parameters with high absolute value.

Future work

For now, the framework does not provide a lot of features (but it works, so at least some credit is due :) ). I think a lot of work will be put into trying to create adapters for different random generator libraries for this autotest::Param format with proper modelling (I have some examples inside the lib/generators.hpp file illustrating that, but they are weak).

Integration with Polygon doesn't sound too bad either.

Probably an "as important" other aspect of improvement is on the stability. In this case, if you think the framework is useful and also prepare contests, try to use it for a contest and see how it works. However, don't expect it to work perfectly, as I've only tested it on happy paths.

This version is just the MVP

Contribution

I feel like this can grow into a rather large project (if you think it deserves to be used), so let me know what your thoughts and ideas are. If you want to contribute, feel free to let me know, and potentially submit a PR (I'm a bit picky about coding style sometimes, so keep that in mind).