TopCoder problem "RuleEngine" used in TCCC '02 Reg. Semifinal (Division I Level Three)

Problem Statement


A rule engine is simply a warehouse of tests.  Based on the result of these
tests, actions are taken.  When a set of rules causes an action to be taken,
the rule set is said to "fire".

EXAMPLE Rule Sets:

Example 1:
If the monkey is hungry and the monkey has a banana in it's hand, then the
monkey eats the banana.  The rule set has two rules:
	(RULE) monkey is hungry
	(RULE) monkey has banana
	(ACTION) monkey eats banana.

Example 2:
If X = 2, and Y is between 10 and 15, and Z = 5, then Z = 4.  The rule set has
three rules:
	(RULE) X = 2
	(RULE) Y between 10 and 15
	(RULE) Z = 5
	(ACTION) set Z = 4


It is often very important to know when a given state will cause two different
rule sets to fire.  You will be given two rule sets.  Determine whether there
are any data sets that will cause both rule sets to fire. If so, return the
number of such sets within a set of given bounds.  If not, return "0".
The elements of the rule sets are of the form "<X><comparison>data1,data2" or
"<X><comparison>data1" where <comparison> can be "==", "<", "<=", ">", ">=",
"!=", or "B". <X> is a variable name, a single capital letter 'A'-'Z'. The
element would be TRUE if the comparison of the value in <X> to data1 (or data1
and data2) was true. If all elements of the rule set are TRUE, then the rule
set fires (Double-quotes and angle-brackets are for clarity only).

<comparison> legend:
==	X == data1
<	X < data1
<=	X <= data1
>	X > data1
>=	X >= data1
!=	X != data1
B	X is between data1 and data2, inclusive

X represents an integer variable whose range of possible values are specified
by the below rules.

Method signature: String countSets(String[] ruleSet1, String[] ruleSet2)
Be sure your method is public.

TopCoder will enforce the validity of the inputs.  Inputs are considered valid
if all of the following criteria are met:
  *ruleSet1 and ruleSet2 each have between 1 and 7 elements, inclusive.
*each element of ruleSet1 and ruleSet2 is either of the form
"<X><comparison><data1>" where <comparison> is not the letter "B", or of the
form "<X>B<data1>,<data2>" (quotes and angle-brackets are shown for clarity,
they do not appear in the input).
  *<X> is a letter between 'A' and 'Z', inclusive (upper-case only).
*<data1> and <data2> are integers between -9 and 9, inclusive.  Leading zeros
are possible.
  *<comparison> is one of the following: "==", "<", "<=", ">", ">=", "!=", "B".
*If the <comparison> code is 'B', then <data1> will be less than or equal to

Return the number of distinct data sets made up of values between -10 and 10,
inclusive that will cause both rules to fire.
Format the return value as a String.


ruleSet1 = { "A<1", "B>2" }, ruleSet2 = { "A>1", "BB1,2" }.
Here ruleSet1 will fire if the value in A is less than 1, and the value in B is
greater than 2.  ruleSet2 will fire if the value in A is greater than 1, and
the value in B is between 1 and 2.  The rule sets are mutually exclusive, for A
cannot be both greater than and less than 1 so return "0".

ruleSet1 = { "A<0" }, ruleSet2 = { "A<0" }.
Both rulesets will fire for any value of A between -10 and -1, inclusive.
There are 10 such values, so return "10".

ruleSet1 = { "A==1", "X>=4", "F<1" }, ruleSet2 = { "X>=5", "ZB2,9" }.
ruleSet1 will fire when A is 1, X is greater or equal to 4, and F is less than
1.  ruleSet2 will fire when X is greater than or equal to 5, and Z is between 2
and 9, inclusive.  Both rule sets will fire when:
A is 1.
X is greater than or equal to 5.
F is less than or equal to 0.
Z is between 2 and 9, inclusive.

Hence, the rule sets are not mutually exclusive, so calculate the number of
distinct data sets that can cause the rule set to fire, in which the values are
between -10 and 10, inclusive:

A can only be 1 (1 possible element).
X can be between 5, and 10 inclusive (6 possible elements).
F can be between -10 and 0 inclusive (11 possible elements). 
Z can be between 2 and 9 inclusive (8 possible elements).

The number of distinct data sets that can cause both rule sets to fire within
the given bounds is: 1 * 6 * 11 * 8 = 528.  Return "528".


{ "A<1", "B==2", "C>4", "D>=6", "E<=9", "FB1,2", "J!=6" }, { "E>9" } returns "0".
{ "A<01", "B==2", "C>4", "D>=2", "E<=9", "FB1,2", "J!=6" }, { "A<9", "B>=2" }
returns "475200".
{ "A<=9", "B<=9", "C<=9", "D<=9", "E<=9", "F<=9", "G<=9" }, { "H<=9", "I<=9",
"J<=9", "K<=9", "L<=9", "M<=9", "N<=9" } returns "1638400000000000000".
{ "KB-09,5", "K<3" }, { "Y>4" } returns "72".


Parameters:String[], String[]
Method signature:String countSets(String[] param0, String[] param1)
(be sure your method is public)

Problem url:

Problem stats url:




Problem categories:

Advanced Math, Brute Force, String Parsing