Monday, May 16, 2016

Topcoder problem analysis - RuleEngine (CC 2002 REG Semi 1000 pointer)

Problem statement
https://community.topcoder.com/stat?c=problem_statement&pm=352&rd=62

I have no idea why this was chosen as a 1000 pointer - the problem is really simple looking. So simple in fact that many coders missed a couple of obvious details, and I spent a while successfully challenging several solutions in the practice room...

The cardinal mistakes people made:
  • Forget to use a 64 bit integer for computations - 19 to the 14th power is a huge number.
    Someone actually implemented a simple BigInteger class in C++, without realizing they could use a long long
  • Write a nested for loop that checked all possible numbers for each rule! Probably not going to terminate in the lifetime of the universe! 

Another thing I noticed is the repetitivity of the code in many solutions. If you have two blocks of code that differ in only a few places, it begs to be converted into a function, or often a macro.


Solution

The correct way to solve the problem is:
  • Go through each rule, and count how many numbers fulfill that rule 
  • Multiply all the above counts together



Note the usage of the HANDLE_OP() macro to handle repetitive code - Macros allow you to de-duplicate code in ways that you just cannot by any other means. Here we used the fact that the literal symbol "!=" and so on is the actual C++ operator for that rule. Had we used anything but a macro, we'd have had to write a tedious case statement or similar logic, mapping strings to relational operators.

Note the appending of ",0" to the rules, to make sure the parsing of all rules is uniform. You can ensure that a condition is always met in order to eliminate a conditional statement - this is similar in principle to sentinels, a much underrated tool in your programming toolbox.

No comments:

Post a Comment