Problem Statement |
| | The board game Chutes and Ladders consists of 100 spaces, numbered 0 through 99. Initially, each player
begins on the space 0. Each player takes turns rolling a pair of typical six-sided dice, and moves the
number of spaces indicated on the dice. Each space of the board might be the start of a chute or a ladder,
which immediately warps the player backward or forward to another space on the board. Once a player reaches
or passes the last space on the board, that player wins the game.
Any space on the board, except for the first (0) or last (99) space, may be the start of a chute, a ladder, or neither. No space will have both a chute and a ladder, and no space will have more than one chute or ladder. A space that begins a chute or ladder will not be the end of another chute or ladder. Furthermore, no two adjacent spaces will both have a chute and/or ladder.
A space may, however, be the landing space of more than one chute and/or ladder.
There will be, at most, 20 chutes/ladders on the board
You are given int[]s startLadder and endLadder, whose corresponding elements define
the starting and ending points of each of the chutes and ladders on the game board. For instance,
startLadder[0] is the space that has a chute/ladder which ends at endLadder[0]. You are also given
a int[] players indicating the current position of each player on the board. Player 0
will roll next, followed by player 1, etc.
You are to return a double[] indicating the probability of each player winning the game. |
| |
Definition |
| | | Class: | ChutesAndLadders | | Method: | winningChance | | Parameters: | int[], int[], int[] | | Returns: | double[] | | Method signature: | double[] winningChance(int[] startLadder, int[] endLadder, int[] players) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The return value must be within 1e-9 absolute or relative error of the actual result. |
| |
Constraints |
| - | startLadder will contain between 0 and 20 elements, inclusive. |
| - | endLadder will contain the same number of elements as startLadder. |
| - | Each element of startLadder will be between 1 and 98, inclusive. |
| - | Each element of endLadder will be between 0 and 98, inclusive. |
| - | No two elements of startLadder will be the same. |
| - | No two elements of startLadder will differ by 1. |
| - | No element of endLadder will equal an element of startLadder. |
| - | players will contain between 2 and 4 elements, inclusive. |
| - | Each element of players will be between 0 and 98, inclusive. |
| - | No element of player will equal an element of startLadder. |
| |
Examples |
| 0) | |
| | | Returns: {0.6063557826968836, 0.3936442173031164 } | | With no chutes or ladders to worry about, this is just a straight ahead race to the finish. As expected, the first player has an advantage. |
|
|
| 1) | |
| | { 7, 23, 42, 58, 87} | {35, 91, 11, 31, 22} | {0, 0, 0, 0} |
| Returns:
{0.2850398049975441, 0.2591808222220256, 0.23726366951493458, 0.21851570326549555 } | | Here, we've got a few chutes and ladders, and more players, which evens out the odds a bit. |
|
|
| 2) | |
| | | Returns: {0.013280440302841312, 0.9867195596971587 } | | With the second player starting a good way through the game, he has an advantage in spite of rolling second. |
|
|
| 3) | |
| | {79, 70, 50, 27, 3, 8, 35, 20, 97, 94, 92, 86, 53, 63, 61, 46, 48, 15} | {98, 90, 66, 83, 13, 30, 43, 41, 77, 74, 72, 23, 52, 59, 18, 25, 10, 5} | {21, 32, 56, 41} |
| Returns:
{0.17890364754713348, 0.13868643400691752, 0.5037066355391879, 0.17870328290676118 } | |
|