JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
1.3. Testing Using Alternative Brute-Force Solution | Reply
This is a rewrite of this recipe by it4.kp.

Problem

It's common for a solution to fail due to a small mistake or even misprint that was not found during testing. Problem statements usually don't provide enough examples, and inventing them by hand still can miss a bug. One way to detect them in semi-automatic mode is to test your solution on multiple small random test cases using an alternative brute-force solution.

Solution

Brute-force is the most natural way of solving many problems. Unfortunately, this straightforward method is not appropriate in absolute majority of TopCoder problems due to tight time constraints, so more complicated, more algorithmic and more efficient solutions are required. However, if you want to test your solution on some small test cases, using another brute-force solution is a good way to automate the testing.

This is done much as the name implies - you write a local brute-force solution, run it on a set of small test cases and compare the returns of this solution and the one that is being tested. Since brute-force solution is simpler, it's also less error-prone, so if the results differ on certain test case, it's a reason to start a more detailed investigation on the reasons of the difference.

Discussion

The very first thing to note is that this testing technique is nowhere near a panacea for all problems. Sometimes writing a brute-force solution can be to tricky to waste your time implementing it. Also, your solution can exceed time or memory limit, or suffer from overflow on large test cases, which errors this technique doesn't detect. Nevertheless, it can be useful in general.

Thus, if you submitted a solution and there is no much time left to try another problem, consider testing your solution as described above and shown below. This makes sense for problems which use a rather complicated algorithm you're not so sure about, or for problems with lengthy code which is likely to have a bug. Not much sense to test in this way problems which are a short DP, or are based on a thoroughly tested pre-written code. The brute-force solution mustn't be optimized or anything - it has just to be short and clean enough to be sure that it's correct.

To make this technique really useful, one has to automate applying it as much as possible: write a customizable test case generator and a tool to run two solutions against the same test cases and compare the results, so that during the contest you have only to write the two
solutions and to tune test case generation.

Now, to the examples. Problem statement of ForbiddenStrings contains only three example test cases - clearly too little for a decent testing. The correct solution involved getting recursive formula, but you could easily write a brute-force one that would iterate through all strings of length n and pick non-forbidden ones:

int brute(int n){
    int total = 1, cnt_forbidden = 0;
    
    // Count the total number of strings of letters A, B, C which length is n.
    // Apparently, it's 3^n
    for (int i=1; i<=n; ++i) total *= 3;
    
    // Iterate through all such strings
    for (int i=0; i<total; ++i){
        char s[20];
        int cur = i; // cur is the representation of current string in 3-base numeral system
        for (int j=0; j<n; ++j) {
            s[j] = cur%3 + 'A';
            cur /= 3;
        }
        bool forbidden = false; // Is current string forbidden?
        for (int j=2; j<n; ++j) if (s[j]!=s[j-1] && s[j]!=s[j-2] && s[j-1]!=s[j-2]) {
            forbidden = true;
            break;
        }
        // Increment the number of forbidden strings
        if (forbidden) ++cnt_forbidden;
    }
    
    // Return the number of unforbidden strings
    return total - cnt_forbidden;
}


Another example can be PalindromePhrases: the correct solution involves fairly complex computations, based on dynamical programming; but if we limit ourselves with the sets of 1 to 6 random words, we can just try all possible phrases and count those of them that are palindromes:

int brute(vector<string> words){
    int n = words.size();
    set<string> palindromic_phrases;
    
    // Iterate through all permutations of words
    sort(words.begin(),words.end());
    do {        
        // Iterate through all non-empty subsets of words
        for (int mask = 1; mask < (1<<n); ++mask) {
            string phrase = "";
            string phrase_without_spaces = "";
            for (int j = 0; j < n; ++j) if (mask & (1<<j)) {
                // j-th word is included in the current subset
                if (phrase != "") phrase += " ";
                phrase += words[j];
                phrase_without_spaces += words[j];
            }
            if (is_palindrome(phrase_without_spaces))
                palindromic_phrases.insert(phrase);
        }
    } while (next_permutation(words.begin(),words.end()));
    
    return palindromic_phrases.size();
}
Re: 1.3. Testing Using Alternative Brute-Force Solution (response to post by Nickolas) | Reply
Writing a brute force solution is not the only applicable method to automatically test your solution. For example, consider the ProductsOfDigits problem. If your solution involves lots of special cases (like mine did), submitting it without automated testing is looking for trouble. The problem has the form of "given x and k, find the smallest i such that F(k,i) = x", where the function F can be easily calculated. Thus, the method of automated testing is the following:

for each k
for each i from 0 to a big number
  x = F(k,i)
  j = answer of our program on x
  if j>i then ERROR
  if j<i and F(k,j) != x then ERROR


I think this method is quite generic (it works for problems where you have to reverse some simple operation).
Re: 1.3. Testing Using Alternative Brute-Force Solution (response to post by Eryx) | Reply
That's a nice testing method. It could even make into a separate recipe (since it doesn't really fit the topic of this one), if we could think of other examples (preferably easier ones). Any ideas?
Re: 1.3. Testing Using Alternative Brute-Force Solution (response to post by Eryx) | Reply
As a second thought, we'll make it a sidebar - it's a perfect fit, since it's something rare (no other such problem example) but interesting.
RSS