In SRM 556, I made an algorithmic mistake in a problem that completely ruined the day (although the failed challenge was a larger factor, BTW, I found out why my challenge did not work out. It turns out that the solution I tried to challenge had two major bugs, but I only noticed one, but in the specific test case I gave it, the second bug made it work.
I keep saying this. After a match, ask yourself what should you have done to solve one more problem than the amount of problems you solved correctly? In case of failing system tests due to a bug that amounts to modifying a single line of code, then the answer is "find the bug before the end of the coding phase". But how?
Well the answer is in remembering the match. I actually submitted the first two problems quite fast yesterday. So I had like 40 minutes to do basically nothing. I tried to put some interest in div1 1000. But I kept having the feeling I had to find bugs in the other solutions just in case. I kept reviewing the codes and not finding anything. I think that was a mistake. Because we can do better than that to find bugs.
Bruteforce
In the aftermath, I kept reviewing the events. I noticed that it is not difficult to make a bruteforce solution for this problem that works in all right speed for (number of digits) <= 17.
It is not difficult. After placing the first digit card. Then you have two choices for the side at which you place the following cards. So if there are n cards, there are 2n choices of numbers you can make. A single bruteforce using bitmasks can simulate all the cases. Then you can just compare the generated strings and find the one that works better as a result.
// Brute force solution.
string minNumberBrute(string digits, string lowerBound)
{
string best = "z"; //represents a very large number...
// in string lexicographical comparisons
// "z" is larger than any chain of digits.
int n = digits.size();
// try a mask for the 2^(n-1) choices
for (int mask=0; mask < (1<<(n-1) ); mask++) {
string x = string(1, digits[0] );
for (int i=0; i<n-1; i++) {
// depending on the choice, put the digit left or right
if ( mask & (1<<i) ) {
x += digits[i+1];
} else {
x = string(1, digits[i+1]) + x;
}
}
// compare and remember the best.
if (x >= lowerBound) {
best = std::min(best, x);
}
}
return (best == "z") ? string("") : best;
}
Generating test cases
The idea is then to make a program that generates random test cases of 17 digits runs the solution I submitted and the brute force solution and compares the results. If they are the same, repeat. Else output a message saying that the program found a bug.
In c++, use the srand() function to initialize a random number generator. It is very convenient to always use a fixed seed. This way you can repeat the experiment in case something went wrong. (It could happen that your brute force implementation had bugs).
Then use rand() function to generate each of the 17 digits in each of the strings. There are two ways to use rand() to generate integer numbers within a range: A correct one, and an "almost" correct one.
You might use %. Like this page describes: http://www.cplusplus.com/reference/clibrary/cstdlib/rand/, but keep in mind it is not really uniform. If you really want uniformly random then you will need to use something like (int)(X * (rand()/(float)RAND_MAX) ). I just used %. With rand()%10 you get a number from 0 to 9, add it to '0' and you get a random digit.
Some critical thinking please
If you find a mismatch between your solution and bruteforce , it does not always mean you found a bug in your solution. It could be a bug in bruteforce. This is the problem with this idea. You have to develop and debug twice and brute force solutions are not always very easy to implement.
There is also another problem. Random test cases might not be the best way to find bugs in your specific code. Perhaps your code needs something very specific to fail. The alternative is to, instead of using random, try making up your challenges yourself. But this requires you to already suspect that a part of your solution might be wrong. It might also happen that your bug is only found when the size of the input is large, and in that case, you cannot use brute force to test...
Write it down
If you truly found a bug. Then write the case you found down. Once you understand the bug in your solution, resubmit and keep it in mind at the time of the challenge phase. Maybe this information will be of benefit...
Results
Ok, so I tried to measure how well this would help me to find a bug in my failed 500 yesterday. For this specific bug, it took only about 50 random test case attempts before it found a mismatch. I also found out that 2 of the 3 other guys who failed system tests in my room would fail the case I found. I think next time that I have so many time after solving div1 500 I will do this again, because trying the div1 1000 out rarely pays.
0 comments:
Post a Comment