Makise_Kurisu's blog

By Makise_Kurisu, history, 4 years ago, In English

Hi, can anyone tell if there's a way to stress test solution to an interactive problem by running it over hundreds of test cases ?

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

It’s quite difficult and perhaps someone out there has a catch-all way, but for me I tend to take a copy of my code, and loop over it for a series of predefined tests, with a naive function which replaces the queries and responses. In this naive function I would deterministically calculate the ‘responses’ to my own queries instead of receiving them as inputs.

Limitations:

1) naive functions usually only work on smaller inputs so it probably wouldn’t be able to test larger test cases

2) there may be bugs in the naive function, or other problems introduced by slightly modifying the code

3) this only works for interactive problems where there actually is a deterministic answer. Sometimes (especially in contests like Google Code Jam) you may find that heuristics are appropriate (e.g. if a 90% success rate is the target), or the response has a random element to it. This is much trickier

Google actually develops an ‘interactive runner’ for each of its interactive problems, which runs some cases for you. You could also look to modify that for your specific purposes, but the code is not trivial.

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I don't do this during short contests, but on a long challenge I once used Polygon to run stress tests.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    This is so smart, WOW
    I think if you've had a prewritten task for it the process would be nearly as fast as regular stress-testing.

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

First generate your testcases based on the hack format in the problem. Then write an interactor. Finally replace all your io with functions which you can then replace with function calls to your interactor.