Problem Statement |
| | A Randomized Finite Automaton (RFA) works as follows. The RFA maintains a variable, called its state, which is initially set to 0. When an input character ('a', 'b', or 'c') is fed into the RFA, it must determine which new value is to be assigned to its state. This determining process is governed by a list of rules stored in the RFA. For example, if the RFA is in state 2 and has received an 'a' as input, the RFA would consult element 2 of rulesa. Each element of rulesa is of the form "st:prob st:prob ...", where st denotes a value to be assigned to the state variable, and prob denotes the percentage (out of 100) of such an assignment occurring. If the given probabilities do not add up to 100, the remaining probability is the chance of changing state to 999. If a state (not 999) is missing from a rule, then its prob is assumed to be 0. Once state is 999, regardless of future input, it remains on 999. The machine has analogously defined rulesb, and rulesc defining what to do on 'b' or 'c' accordingly.
When processing an input string, each character is processed in order, left to right, one at a time. Assuming all input strings of length maxLength or fewer (including the string of length 0) are equally likely, return the probability the RFA will be on state finalState once the string is completely processed. The probability returned will be a double, between 0 and 1 inclusive. Results must be accurate to 1e-9. |
| |
Definition |
| | | Class: | RandomFA | | Method: | getProbability | | Parameters: | String[], String[], String[], int, int | | Returns: | double | | Method signature: | double getProbability(String[] rulesa, String[] rulesb, String[] rulesc, int finalState, int maxLength) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | rulesa will contain between 1 and 50 elements inclusive. |
| - | rulesa, rulesb, and rulesc all contain the same number of elements. |
| - | Each element of rulesa, rulesb, and rulesc contain between 0 and 50 characters inclusive. |
| - | Each element of rulesa, rulesb, and rulesc is a single space delimited list of pairs. Each pair is of the form (quotes for clarity) "st:prob" where,
st is an integer, with no extra leading zeros, between 0 and (size of rulesa-1) inclusive, and
prob is a positive integer, with no leading zeros. |
| - | The prob values in a single element of rulesa, rulesb, or rulesc will sum up to a value between 0 and 100 inclusive. |
| - | No 2 pairs in a single element of rulesa, rulesb, or rulesc will have the same st value. |
| - | finalState will be between 0 and (size of rulesa-1) inclusive, or 999. |
| - | maxLength will be between 0 and 10 inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 0.5 | | The 4 strings that need to be considered are (quotes for clarity) "", "a", "b", and "c". Of those 4, the first 2 will end up on state 0, while the latter 2 will end up on state 999. 2 out of 4 produces a probability of .5 . |
|
|
| 1) | |
| | {"1:100","0:100"} | {"1:100","0:100"} | {"1:100","0:100"} | 1 | 3 |
| Returns: 0.75 | | Here all even length strings will result in state 0, and odd length strings will result in state 1. Of the 40 strings considered, 1 has length 0, 3 have length 1, 9 have length 2, and 27 have length 3. Thus 30/40=.75 of them have odd length. |
|
|
| 2) | |
| | {"1:25 2:25 3:25 4:25","0:100","0:100","0:100","0:100"} | {"","","","",""} | {"","","","",""} | 3 | 5 |
| Returns: 0.0020604395604395605 | | All strings that contain a 'b', or 'c' are sent to 999. The strings containing only 'a's begin on state 0, and are evenly distributed between states 1,2,3 and 4 after the first 'a'. After the second 'a' they are all returned to state 0. Examining this pattern, we see that strings that end on state 3 must contain only 'a's and have odd length. Of those, only a quarter of them actually make it to state 3. There are 3 strings consisting of only 'a's that have odd lengths less than or equal 5. This makes 3 out of the total 364 strings. The returned probability is thus 3/364*.25 = .0021 approx. |
|
|
| 3) | |
| | {"1:25 2:25 3:25 4:25","0:100","0:100","0:100","0:100"} | {"","","","",""} | {"","","","",""} | 999 | 5 |
| Returns: 0.9835164835164837 | | The same problem as before, but now we want the strings that will end on 999. This will be any string of positive length that has a 'b' or 'c'. There are 358 of these, resulting in a probability of 358/364 = .984 approx. |
|
|
| 4) | |
| | {"2:9 0:7 3:4 1:2 5:35","2:9 0:7 3:4 1:2 5:35",
"2:9 0:7 3:4 1:2 5:35","2:9 0:7 3:4 1:2 5:35",
"2:9 0:7 3:4 1:2 5:35","2:9 0:7 3:4 1:2 5:35"} | {"0:10 4:7 5:1","0:10 4:7 5:1","0:10 4:7 5:1",
"0:10 4:7 5:1","0:10 4:7 5:1","3:79 2:10"} | {"1:100","2:100","3:100","4:100","5:100","0:100"} | 3 | 10 |
| Returns: 0.002676338903044717 | |
|
| 5) | |
| | {"2:9 0:7 3:4 1:2 5:35","2:9 0:7 3:4 1:2 5:35",
"2:9 0:7 3:4 1:2 5:35","2:9 0:7 3:4 1:2 5:35",
"2:9 0:7 3:4 1:2 5:35","2:9 0:7 3:4 1:2 5:35"} | {"0:10 4:7 5:1","0:10 4:7 5:1","0:10 4:7 5:1",
"0:10 4:7 5:1","0:10 4:7 5:1","3:79 2:10"} | {"1:100","2:100","3:100","4:100","5:100","0:100"} | 3 | 0 |
| Returns: 0.0 | | Same as before, but only the empty string is considered. |
|
|