Problem Statement
You are preparing to traverse through a collection of square rooms, arranged in a regular two-dimensional grid, with a door between each pair of adjacent rooms. It takes you exactly one second to move through an open door from one room to the next. At any second each door will either be open or closed, according to the given probability for that door. You are to compute the expected lengh of time it will take you to get from the upper-left room to the lower-right room, assuming that at every second you optimally choose which open door (if any) to travel through.
The probabilities for each door will be given as a String[] doors. Each element of doors will contain one digit ('0' through '8', inclusive) per door. Each digit corresponds to one door, and gives the probability, for each second, of that door being open. The probability is the value of the digit divided by 8. For example, a '0' means that that door is always closed and an '8' means that that door is always open. The even-indexed elements (zero-based) give the probabilities for doors connecting two horizontally-adjacent rooms, and the odd-indexed elements give the probabilities for doors connecting two vertically-adjacent rooms. The odd-indexed elements will each contain exactly one more digit than the even-indexed elements. doors will contain an odd number of elements.
For example, the following probabilities:
{ "2815",
"67686",
"1324",
"75767",
"6051" }
would represent the grid of rooms with these probabilities for each door:
+-----+-----+-----+-----+-----+
| | | | | |
| 2/8 8/8 1/8 5/8 | "2815"
| | | | | |
+-6/8-+-7/8-+-6/8-+-8/8-+-6/8-+ "67686"
| | | | | |
| 1/8 3/8 2/8 4/8 | "1324"
| | | | | |
+-7/8-+-5/8-+-7/8-+-6/8-+-7/8-+ "75767"
| | | | | |
| 6/8 0/8 5/8 1/8 | "6051"
| | | | | |
+-----+-----+-----+-----+-----+
If it is not possible to reach the lower-right room, your method should return -1.0.
Definition
- Class:
- GreatExpectations
- Method:
- expectedTime
- Parameters:
- String[]
- Returns:
- double
- Method signature:
- double expectedTime(String[] doors)
- (be sure your method is public)
Notes
- There are only doors between adjacent rooms. Rooms on the edges of the grid will have only 3 doors, except for those in the corners, which will have only 2 doors.
- Your return value must have an absolute or relative error less than 1e-9.
Constraints
- doors will contain between 3 and 49 elements, inclusive, and be formatted according to the problem statement.
- Each element of doors will contain between 1 and 50 characters, inclusive.
Examples
{ "4", "44", "4" }Returns: 3.3333333333333335
Each door has a 50% chance of being open at any given second. Starting at the top-left, each second there is a 75% chance of being able to progress to either of the two adjacent rooms, and therefore the expected time to have to wait is 4/3 seconds. From either of the two adjacent rooms, the expected time to reach the bottom-right is 2 seconds. Therefore, the total is 4/3 + 2, or 10/3.{ "48", "440", "42", "862", "06" }Returns: 6.0
This is a 3x3 grid of rooms. Note that the upper-left 4 rooms is the same as the example above, and therefore the expectation to get to the center room in this grid is 10/3. From the center room, you should always wait until the door below opens, even if the door to the right opens first. If you go to the right, you will have to wait an expected 4 additional seconds for the next door to open. But if you wait for the door below, it will take only an expected 4/3 seconds, plus another 4/3 seconds to reach the end. Therefore, the final answer is 10/3 + 4/3 + 4/3 = 6.{ "0808", "88888", "0000", "88888", "8080" }Returns: 14.0
{ "2815", "67686", "1324", "75767", "6051" }Returns: 11.852782338798935
{ "823", "2630", "130" }Returns: -1.0
Back to all problems