PROBLEM STATEMENT
A number pad consists of ten keys, each having exactly one distinct digit 0
through 9. If all keys are pressed exactly once, there are 10 factorial
(10*9*8*7*6*5*4*3*2*1) different ways or permutations to order the key presses.
Create a class Dial that contains the method permute, which has the parameter
order, a String[] of rules governing the order of keys pressed, and an int
firstNum, the first digit to be pressed, and returns the number of permutations
possible when pressing each key on the pad exactly once. There are two types
of rules. The first specifies that digit1 must immediately precede digit2, it
is formatted "<digit1>B<digit2>". The second type specifies that digit1 must
immediately follow digit2 it is formatted "<digit1>A<digit2>". For example,
the rule "9B8" means that after the '9' key is pressed, the next key pressed in
the sequence must be '8'.
DEFINITION
Class: Dial
Method: permute
Parameters: String[], int
Returns: int
Method signature (be sure your method is public): int permute(String[] order,
int firstNum);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- order will have 0 to 10 elements (inclusive)
- each element of order will be formatted "<digit1>A<digit2>" or
"<digit1>B<digit2>" where each digit is between 0 and 9 inclusive, and the two
digits are not the same
- firstNum is an int between 0 and 9 inclusive, representing the first digit in
the sequence of keys pressed
NOTES:
- order may have duplicate rules
- the rules may contradict each other, in which case there is no valid
permutation, and the method returns 0
- an element of order formatted "<digit1>A<digit2>" means the digit1
immediately follows (in the sequence of keys pressed) digit2
- an element of order formatted "<digit1>B<digit2>" means digit1 precedes
(immediately before in the sequence of keys pressed) digit2
EXAMPLES
1)
order = {"0B1","2A1","3A2","4A3","6A5","7A6","9A8","5A4"}
firstNum = 0
Method returns 1
The only sequence of keys that can be pressed is "0123456789" by the rules
given. The number of sequences that begin with '0' is one - the permutation
listed above as the sequence.
2)
order = {"0B1","2A1","3A2","4A3","6A5","7A6","9A8","5A4"}
firstNum = 3
Method returns 0
The only sequence of keys that can be pressed is "0123456789" by the rules
given. The number of sequences that begin with '3' is zero since '3' can never
be the first number pressed because it always follows 2 from the rule "3A2".
3)
order = {"0B1","1B0"}
firstNum = 0
Method returns 0
There is no valid sequence of numbers because '0' can't come before '1' and be
after '1' because each digit is only pressed once.
4)
order = {}
firstNum = 0
Method returns 362880
Since 0 is fixed as the first digit in the sequence, the other 9 digits can be
anything, resulting in 9 factorial permutations.